Re: [hub] Andrzej's review

El 23/04/2026 a las 17:44, Andrzej Krzemienski escribió:
> Hi Everyone,
> This is a short review of Boost.Hub.
> First, I wanted to yet again thank Joaquín for this contribution. 
> Also, thanks to Ion for managing the review.

Hi Andrzej, thank you for your review!

> I personally never had a need for a container with colony/hive/hub 
> properties, so I do not speak as an expert in the problem domain. I 
> have read the docs for the library, investigated the API, compared 
> against std::hive, and played with the library on Compiler Explorer 
> (GCC 15.2) trying to break it.
>
> I recommend accepting Hub into Boost. For me, it is equally fine 
> whether this would be a separate library or part of Boost.Container. 
> The library is clearly useful. It belongs in Boost more than in the 
> Standard Library.
I totally agree with you on that last statement.
> Regarding the design, there is not much flexibility here: it has 
> already been designed while standardizing std::hive. Although the STD 
> has this impractical type requirements Container and SequenceContainer 
> that (i) are not useful and (ii) do not play well with std::hive, so 
> Boost.Hub has a chance to set things straight. For instance, neither 
> hub nor hive are SequenceContainers, as pointed out in another thread.
Noted previously, will fix.
> As indicated in another thread, I recommend making the `visit` 
> functions free functions and renaming them to `for_each` and 
> `for_each_while` (as per Joaquí's suggestion). While the latter name 
> is funny, it is the most adequate one also. This could also be a 
> customization point for all containers: it would default to regular 
> `std::for_each` but offer container authors to provide a faster 
> implementation.
Noted too, will replace visit_XX with for_each_XX. As for the 
customization point, I undertand this is out of scope for this 
particular proposal, but maybe Ion is thinking in something along that 
line for his support of segmented iterators. It's an interesting design 
problem.
> We are encouraged to prefer Boost's Hub over Hive based on numbers, 
> but it is not clear to me if the better numbers are due to the 
> necessary API changes, or because Joaquín is a better implementer. 
> What was the primary motivation to scrap the block size control?

I'm glad you ask. When I first saw the implementation of plf::hive, it 
struck me how complicated (and clever) it is, but then I had the hunch 
something simpler could actually be faster. I wrote a quick PoC and 
figures were encouraging so I kept on working on it.

I am not the author of plf::{hive|colony}, but in 
https://plflib.org/colony.htm we have some rationale leading to the 
current implementation for that container:

* "Using a boolean flag (or similar) to indicate the inactivity of an 
object" was considered but then discarded due to slow iteration when 
checking the boolean flags.
* The fact that plf::{hive|colony}'s blocks grow in size as more 
elements are added (sort of like std::vector) seems to be informed by a 
quest for maximum cache locality, but we also read: "Because colony (by 
default) has a growth pattern for new memory blocks, the number of 
insertions before a new memory block is required increases as more 
insertions take place. Hence the insertion time complexity is O(1) 
amortised". This last statement looks inaccurate to me: insertion time 
for plf::{hive|colony} is unconditionally O(1) and does not depend on 
any growth factor to be so --growing block sizes is important for 
std::vector's amortization of insertions cause it reallocates elements, 
but plf::{hive|colony} doesn't reallocate. Curiously enough, the std 
spec for std::hive indicates that insertions and erasures are constant 
time, without any reference to amortization.

If we discard growing blocks, fix their size to 64 elements and use 
std::countr_zero and related ops (which are extremely fast) for 
occupancy bitmask manipulation, we esentially have the design for 
boost::container::hub.

So, the fact that boost::container::hub is faster is mainly explained by

1. Insertion/erasure code is extremely simple, no skipfields or free 
lists of elements, code boils down to handling a linked list of blocks 
and playing with their occupancy bitmasks.
2. boost::container::hub allocates many more times than 
plf::{hive|colony} (its blocks are typically smaller), but seemingly 
modern allocators are fast enough that this does not detract too much 
from the speedup in 1.
3. I've dispensed with some sources of complexity like the fact 
plf::{hive|colony} iterators are three-way comparable: I honestly can't 
think of a scenario where this is relevant, and three-way-comparability 
doesn't come for free either in memory usage or execution time.

There's a definite drawback with the design of boost::container::hub wrt 
plf::{hive|colony}, namely that cache locality is poorer (smaller block 
sizes), which may affect iteration speed, hence the visitation functions.

> Regarding the documentation, I find the one currently present in the 
> README satisfactory (modulo the SequenceContainer requirements), and 
> friendlier than these in Boost.Container. So I wonder what the effect 
> of merging would be.
>
> Regarding the implementation, I didn't have time to follow all of it but:
> 1. It is impressive that it is only 1800 lines.
> 2. It is easy to read and understand; also well documented, where needed.
> 3. I am concerned about the usage of BOOST_LIKELY. Are these the 
> source of performance? It is my understanding that they are very 
> fragile and may give opposite effects once something changes in the 
> compiler implementation. Plus it is easy to fabricate the data that 
> will make the program go slow when the "negative" branches are 
> deliberately triggered.
This is not the source of performance. I guess I've written too many 
high performance containers and these annotations come naturally to me. 
Anyway, compilers don't do anything fancy with [[likely]] beyond 
rearranging branches so that the most likely branch has the highest 
intruction cache locality.
> 4. There is this line:
> `size_type memory() const noexcept // TODO: remove`
> Is this something to be fixed?
Yes, I need to remove it, I used it privately for some local benchmarks.
> 5. Compiling with -Wall gives me a warning in GCC when sorting an 
> empty hub: a zero-sized heap array is allocated:
> https://godbolt.org/z/dWvxv9n8s
> This is technically fine to allocate such arrays, but maybe it is 
> worth to make -Wall clean.
This has spawn its own subthread, so allow me to answer there.
> I know that Joaquín is responsive and am confident that the Hub 
> implementation will be maintained.

Thanks again for your time and feedback,

Joaquín M López Muñoz

_______________________________________________
Boost mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://lists.boost.org/mailman3/lists/boost.lists.boost.org/
Archived at: https://lists.boost.org/archives/list/[email protected]/message/6CWSVFKPTPYY6MSUSU7DSYDJTLBQ64TU/