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

From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2024-05-24 22:09:40

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<int,int>.
> 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/affcfac39bf479a9ac64dcb41e7650d0f8ac64e2/src/Simplex_tree/include/gudhi/Simplex_tree.h#L2314) 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_from_values.html

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.html#iterator_to

> 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