Re: [boost] [container] Draft development plan for Boost.Container

El 24/05/2024 a las 19:54, Marc Glisse via Boost escribió:

On Tue, 21 May 2024, Ion Gaztañaga via Boost wrote: since you are asking, here are some comments as a user.

Performance:

You already have #248 about a performance regression in flat_map. It can currently be twice as fast to use a struct { int key; mutable int value; } in a flat_set than a flat_map. I would prioritize fixing known performance issues before looking for others, but I guess it is a worthy goal.

Yes, I previously was using type-punning to be able to use memcpy in flat_map when key and mapped_type were trivial, but compiler warnings and some suspicious aliasing issues were reported, so I had to roll-back. I'll need to revisit this, I'm not sure if other flatmap implementations (chromium, folly...) perform some type of type punning to achieve the speedup.

- Among what you propose, I may be interested in the B/T-trees and the skip lists, if their performance turns out to be worth it. For hive, if the existing implementation can be included in boost with only minor tweaks, why not. Otherwise, if hive gets standardized and standard library vendors don't mess up their implementation too much, having a version in boost doesn't seem worth the trouble, or at least it is less interesting than having structures not present in the standard. segtor: for the longest time I thought deque used blocks of varying size... It looks interesting, but I am not sure I would actually use it.

I appreciate the feedback.

- https://en.wikipedia.org/wiki/Order_statistic_tree (it could be a new option in an existing container or at least share a lot of code with other trees)

To achieve this we should add augmented trees in Boost.Intrusive (it' been proposed, but not implemented).

- vector optimized for the empty case: I was going to suggest it, but I now see you have added it to the document since the initial post :-)

Thanks. Do you know any public reference implementation of this idea or some talk/paper that explains the advantages, some benchmark etc.? I tried to find some information when writing the plan, but I couldn't find something relevant.

Improvements:

For performance, it is often useful to provide an allocator to node-based structures like list and set. A well-tuned allocator may want to know the size of the nodes in advance (preferably at compile-time, not wait for the first call to allocate()). However, this information can be very inconvenient to access. If you could provide a simple, reliable way to extract this information (one that still works if a user defines recursive maps or other complicated cases with incomplete types), that would be great.

Thanks, this seems a good idea.

Document a way to go from a pointer to an iterator in set and other datastructures. Maybe we only needed that because we didn't know about the advanced options of intrusive lists at the time, but for a map whose values are connected through intrusive linked lists, we had to write fragile code (https://github.com/GUDHI/gudhi-devel/blob/affcfac39bf479a9ac64dcb41e7650d0f8...) to get from a linked list hook to a map iterator.

This sounds similar to Boost.Intrusive iterator_to: https://www.boost.org/doc/libs/1_85_0/doc/html/intrusive/obtaining_iterators... but for Intrusive this is easy because "value_type" is the whole node, whereas in boost::container::set/list/map value_type is embedded in a node. Maybe some pointer arithmetic magic could be used to offer a "iterator_to". Boost Multiindex already offers a similar utility: https://www.boost.org/doc/libs/1_69_0/libs/multi_index/doc/tutorial/indices....

Maintenance:

It seems important to follow what is going on in the standard. I see you already have is_transparent, the node stuff, that's good. You are missing at least erase_if though.

Yes, Boost.Container should at least implement at least the most useful operations.

Thank you for maintaining this Boost library,

I appreciate your feedback and thanks for using it. Best, Ion