ordered_set: Leaner, faster, richer, safer. #3432
Conversation
Previously, for each element, we used to allocate (and later deallocate)
two separate nodes:
- a node inside a list (two link-pointers plus payload of two pointers);
- a node inside a tree (three link-pointers plus one bool plus actual payload).
Now, we only allocate a single node:
- a node inside a set (three link-pointers plus payload).
The payload of the node inside the set
contains the two link-pointers for list operations
and then the actual payload (an element of type T).
Benefits:
- fewer allocations/deallocations;
- less memory consumed (the payload of two pointers in the list was wasteful);
- better locality of data;
- superiour error-safety guarantees
(the intrusive container operations offer the strongest guarantee: nofail)
(=> merging a fix such as PR p4lang#3294 is no longer needed);
- improved speed.
Side note:
We have preferred boost::container::set to std::set
because the former by default tries to merge the colour flag (a bool flag)
with one of the three links, therefore further reducing memory consumption.
TODO: Consider how this works in a World of Garbage Collection.
The current changeset is a draft -- not yet complete for the purposes of p4c,
but offering the essential features of ordered_set:
iteration in sorted order (now with backwards iteration as well)
and iteration in user-controlled (sequence) order.
It represents a proof of concept and a request for comments. (-:
|
Hi @DoctorNoobingstoneIPresume, this is the ONF bot 🤖 I'm glad you want to contribute to our projects! However, before accepting your contribution, we need to ask you to sign a Contributor License Agreement (CLA). You can do it online, it will take only a few minutes: ✒️ 👉 https://cla.opennetworking.org After signing, make sure to add your Github user ID For more information or help:" |
|
This code does not compile in CI. |
|
Hi @DoctorNoobingstoneIPresume are you planning to continue work on this? It looks very useful. |
| @@ -17,234 17,540 @@ limitations under the License. | |||
| #ifndef _LIB_ORDERED_SET_H_ | |||
| #define _LIB_ORDERED_SET_H_ | |||
|
|
|||
| #include <boost/container/set.hpp> | |||
There was a problem hiding this comment.
Why use boost::set rather than std::set -- the latter is more portable and reliable
There was a problem hiding this comment.
Please accept apologies for my replying late.
As explained in my first comment above, the Boost version of set attempts to merge the colour flag with one of the pointers => each node in the tree demands smaller block on the heap.
There was a problem hiding this comment.
We are in the processing of getting rid of boost in the compiler. On the other hand, we now have support for Abseil.
| @@ -17,234 17,540 @@ limitations under the License. | |||
| #ifndef _LIB_ORDERED_SET_H_ | |||
| #define _LIB_ORDERED_SET_H_ | |||
|
|
|||
| #include <boost/container/set.hpp> | |||
| #include <boost/intrusive/list.hpp> | |||
| #include <boost/tuple/tuple.hpp> | |||
There was a problem hiding this comment.
We should always use std::tuple rather than boost::tuple for better standards compliance.
| MyEnlistedComp; | ||
|
|
||
| typedef | ||
| typename Alloc::template rebind <MyEnlistedNode>::other |
There was a problem hiding this comment.
rebind is deprecated and removed in some newer compilers -- need to use rebind_alloc instead.
Thank you so much... I have now remembered this -- and with joy, I dare say. I hope to, indeed, but need some time to get things back into my head. Thank you for the kind message and the encouragement. It can make a difference in a community. ❤️ |
Previously, for each element, we used to allocate (and later deallocate)
two separate nodes:
Now, we only allocate a single node:
The payload of the node inside the set
contains the two link-pointers for list operations
and then the actual payload (an element of type T).
Benefits:
(the intrusive container operations offer the strongest guarantee: nofail)
(=> merging a fix such as PR ordered_(set|map): Increased exception safety via the new
AutoEraseGuard. #3294 is no longer needed);Side note:
We have preferred boost::container::set to std::set
because the former by default tries to merge the colour flag (a bool flag)
with one of the three links, therefore further reducing memory consumption.
TODO: Consider how this works in a World of Garbage Collection.
The current changeset is a draft -- not yet complete for the purposes of p4c,
but offering the essential features of ordered_set:
iteration in sorted order (now with backwards iteration as well)
and iteration in user-controlled (sequence) order.
It represents a proof of concept and a request for comments. (-: