ordered_set: Leaner, faster, richer, safer.

[DoctorNoobingstoneIPresume]

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 #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. (-:

[onf-cla-manager[bot]]

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 DoctorNoobingstoneIPresume to the agreement.

For more information or help:" https://wiki.opennetworking.org/x/BgCUI

[mihaibudiu]

This code does not compile in CI.

[fruffy]

Hi @DoctorNoobingstoneIPresume are you planning to continue work on this? It looks very useful.

[DoctorNoobingstoneIPresume]

Hi @DoctorNoobingstoneIPresume are you planning to continue work on this? It looks very useful.

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. ❤️