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. 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. 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. 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. 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? 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. 4. There is this line: `size_type memory() const noexcept // TODO: remove` Is this something to be fixed? 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. I know that Joaquín is responsive and am confident that the Hub implementation will be maintained. Regards, &rzej;
Andrzej Krzemienski wrote:
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.
The warning isn't caused by the zero sized allocation (which is legal.) It's because the compiler can see that the array has zero elements, but can't see that the loop inside this call to visit https://github.com/joaquintides/hub/blob/063cf1d3589d4893b53964084ee56f4476e... is never executed. So it says "if this loop is executed, it would be UB because there aren't any elements there" but this is a false positive because the loop isn't executed. (The subsequent loops suffer from the same issue and also cause warnings for the same reason.) A common problem with GCC, and unfortunately nothing can be done about it short of disabling the warning.
Andrzej Krzemienski wrote:
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.
The warning isn't caused by the zero sized allocation (which is legal.)
It's because the compiler can see that the array has zero elements, but can't see that the loop inside this call to visit
https://github.com/joaquintides/hub/blob/063cf1d3589d4893b53964084ee 56f4476eed471/include/boost/container/hub.hpp#L1628
is never executed. So it says "if this loop is executed, it would be UB because there aren't any elements there" but this is a false positive because the loop isn't executed.
(The subsequent loops suffer from the same issue and also cause warnings for the same reason.)
A common problem with GCC, and unfortunately nothing can be done about it short of disabling the warning.
On second thought, given that the warning only fires on empty containers, it might be possible to avoid if `sort` checks for `empty()` (or `size() <= 1`) and returns. Adding a branch to avoid a warning is a bit dubious in general, but in this case it avoids a completely unnecessary allocation as well, so it's sound even in principle. :-)
El 23/04/2026 a las 18:52, Peter Dimov via Boost escribió:
Andrzej Krzemienski wrote:
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. The warning isn't caused by the zero sized allocation (which is legal.)
It's because the compiler can see that the array has zero elements, but can't see that the loop inside this call to visit
https://github.com/joaquintides/hub/blob/063cf1d3589d4893b53964084ee 56f4476eed471/include/boost/container/hub.hpp#L1628
is never executed. So it says "if this loop is executed, it would be UB because there aren't any elements there" but this is a false positive because the loop isn't executed.
(The subsequent loops suffer from the same issue and also cause warnings for the same reason.)
A common problem with GCC, and unfortunately nothing can be done about it short of disabling the warning. On second thought, given that the warning only fires on empty containers, it might be possible to avoid if `sort` checks for `empty()` (or `size() <= 1`) and returns.
Adding a branch to avoid a warning is a bit dubious in general, but in this case it avoids a completely unnecessary allocation as well, so it's sound even in principle. :-)
Yes, I'll do that, the cost is negligible and the other two internal sorting functions (proxy_sort and compact_sort) have an analogous check (though in this case it's necessary). Joaquín M López Muñoz
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
participants (4)
-
Andrzej Krzemienski -
Ion Gaztañaga -
Joaquin M López Muñoz -
Peter Dimov