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

From: Marc Glisse (marc.glisse_at_[hidden])
Date: 2024-05-24 17:54:14

On Tue, 21 May 2024, Ion Gaztañaga via Boost wrote:

> Lately I've been collecting some ideas about how to improve the library and 
> keep it interesting/useful both for other Boost libraries and Boost users.
>
> I've somewhat formalized a bit some of those ideas and I'd like to share them 
> here in order to obtain feedback from the developers. Here's the document:
>
> https://docs.google.com/document/d/1VdMTheFUczC946dP3VKPseOoUq3sVKjU73oMvK8FE3o/edit?usp=sharing
>
> Note that this document does not outline a schedule for all those ideas, it's 
> an initial description of possible developments that should be 
> evaluated/prioritized, as developing a substantial subset of the proposals 
> would be a huge task.
>
> Thanks in advance for your attention and comments.

Hello,

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.

Debug:

Not that important to me.

New structures:

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

- 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)

- 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 :-)

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.

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.

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.

Thank you for maintaining this Boost library,

-- 
Marc Glisse