- Boost - lists.boost.org

[Bloom] Some questions
by Ivan Matek 21 May '25

21 May '25

Hi everybody, I was reading the documentation/code, and I have some questions/comments. 1. Why is unit of measurement bit? I understand that conceptually bloom filters(maybe others, did not check) are bit arrays, but for me this seems like very error prone. Would verbose alternative of using boost::bloom::bits(1000) or boost::bloom::bytes(125) be preferred? I did not suggest UDL, as I feel for such rarely used class it may be overkill. 2. boost::hash<short> (and other integral ones) afaik are identity, I presume this is not an issue because you do extra steps if hash_is_avalanching is false, but maybe users should prefer avalanching hash? If so maybe suggest fast avalanching hash available in boost... btw I tried to read the docs but I got(not a big issue, since I read them from original. version): 404 Not Found - Code: NoSuchKey - Message: The specified key does not exist. - Key: develop.bloom.cpp.al/unordered/doc/html/unordered/reference/hash_traits.html - RequestId: JHRNESDX8BYY6T2G - HostId: nz9kkYamNQ4ocu023JneA7PyMHTEyQK9jgMSSBuwReE0OQAslcN0xOZxgopXpvn/63AFQzreXgM= 3. libs/unordered/include/boost/unordered/detail/mulx.hpp contains mulx implementation that seems very similar to one used in bloom, and authors are same. Although this is tiny duplication, would it be best to extract it somewhere to avoid duplication? 4. Is there no benefit in having a power of 2 sized bloom filters? AFAIK it is trick used by hash maps (requires hash is good) to get faster indexing. I see you use clever 128bit multiplication that generates fast mul instruction to avoid division, but I still presume shift and masking would be faster. 5. Why is BOOST_ASSERT(fpr>=0.0&&fpr<=1.0); not BOOST_ASSERT(fpr>0.0&&fpr<=1.0); , i.e. is there benefit of allowing calls with impossible fpr argument? This may sound like nitpicking, but I think it is wrong to allow calls with arguments that give people wrong idea of what bloom filters are capable. I understand that this functionality is under capacity *esimation**,*but I still think it may be confusing. 6. Related to 6. : It is relatively easy to OOM with this if you are "reckless" with fpr value, I would add a suggestion to docs to mention this(if it is not already there, maybe I missed it). 7. It may be just me, but I believe Filter Definition chapter would benefit from visual example, in particular how is BucketSize related to subarray size. 8. Regarding choosing optimal value: In the example we use 10M elements. From what I see they are unused in our computations till the end so I would rewrite: "*Suppose we plan to insert 10M elements and want to keep the FPR at 10−4. The chart gives us five possibilities:*" to something like " Suppose we plan to insert 10M elements and want to keep the FPR at 10−4. Looking up FPR in the chart(this step is not dependent on number of elements) gives us five possibilities:" 9. My IDE complains about redundant inline on member functions. Is this intentionally done since (afaik msvc) some compilers use inline as optimization(inlining) hint or? 10. Should #if 1 in may_contain be there?

5 21

[Bloom] Submit Your Review – Only Two Days Left!
by Arnaud Becheler 20 May '25

20 May '25

Dear Boost community, As a reminder, the review period for the candidate Boost.Bloom library by Joaquín M López Muñoz is set to close in two days, on May 22nd, 2025. If you haven’t had a chance to submit your review yet, there’s still time! All feedback is welcome—whether it’s a quick first impression or a detailed analysis, every comment helps us maintain the quality and standards of Boost libraries. You can find the library here: - Repo: https://github.com/joaquintides/bloom - Documentation: https://master.bloom.cpp.al/ Courtesy from Christian Mazakas, you may want to try out their Boost Nightly demo repository during the Boost.Bloom review period: https://github.com/cmazakas/vcpkg-registry-test If you’re interested in participating but need a bit more time, please let me know—it may be possible to extend the review window slightly to accommodate additional feedback. Thank you to everyone who has already contributed! Best regards, Arnaud Becheler Review Manager, Boost.Bloom

1 0

[openmethod] [policies]
by Jean-Louis Leroy 20 May '25

20 May '25

Hi all, and in particular Joaquín, Christian, Ruben and Steven who contributed remarks on the policy system. I followed some of Ruben's suggestions. There is now a registry that contains collections of classes and methods, and, after initialize(), dispatch data. It also contains a collection of policies. In part this is "just" renaming: what used to be a Policy is now a Registry, and what used to be a Facet is now a Policy. But this is not just cosmetic. The registry mechanism is clearly separated from the policies. Many old facets were CRTP templates, but not always. Now a policy (ex-facet) is - always - a Mp11 quoted meta-function that takes a registry as a single argument. This complicates creating policies a bit, but makes using them much easier, I think. CRTP is gone from the interface (in fact it is hidden). `fork` is gone. The debug and release stock policies looked like this: struct release : basic_policy< release, std_rtti, fast_perfect_hash<release>, vptr_vector<release>, vectored_error_handler<release>> {}; struct debug : release::fork<debug>::with< runtime_checks, basic_error_output<debug>, basic_trace_output<debug>> {}; Now they are: struct release : registry< std_rtti, fast_perfect_hash, vptr_vector, vectored_error_handler, stderr_output> {}; struct debug : registry< std_rtti, fast_perfect_hash, vptr_vector, vectored_error_handler, stderr_output, runtime_checks, trace> {}; An application that wants to use a standard map instead of a fast hash table, and keep all the rest the same, could say: struct my_registry : default_registry::with<vptr_map<>> {}; Or, using an unordered_flat_map: struct my_registry : default_registry::with< vptr_map<boost::mp11::mp_quote<boost::unordered_flat_map>>> {}; I also took Ruben's suggestion of having only one output policy, instead of one for error reporting, and one for tracing. Now, even in release builds, the default handler writes a diagnostic to stderr, before calling abort(). Policies are not aggregated via multiple inheritance anymore. At the moment, I am not convinced with Ruben's approach of making the registry (formerly policy) an object. There would still need to be a static instance of that object, which would contain instances of policy objects. Six of one or half of a dozen of the other. From there Ruben suggested making the dependencies between policies (ex-facets) explicit, as far as I can see this leads to a mess of conditionally enabled constructors. You can see the changes here: https://github.com/jll63/Boost.OpenMethod/pull/22 It's still a draft. The documentation is not yet updated, I'll do a big doc pass when things stabilize again. If you want to post comments directly to the PRs, drop me a line and I will invite you as a collaborator. J-L

2 2

Fwd: [Boost-docs] SGI STL Documentation gone from Boost website ?
by René Ferdinand Rivera Morell 19 May '25

19 May '25

---------- Forwarded message --------- From: Adder via Boost-docs <boost-docs(a)lists.boost.org> Date: Mon, May 19, 2025 at 5:31 PM Subject: [Boost-docs] SGI STL Documentation gone from Boost website ? To: <Boost-docs(a)lists.boost.org> Cc: Adder <adder.thief(a)gmail.com> Dear Authors of Boost and Maintainers of the Boost website, I used to find it useful to find the original STL Documentation on the Boost website, but now https://www.boost.org/sgi/stl/ now gives "404 - Page Not Found". May I ask whether this is intentional or just an accident, please ? Anyway, many thanks for everything you have been doing !! >:D< Adder _______________________________________________ Boost-docs mailing list Boost-docs(a)lists.boost.org https://lists.boost.org/mailman/listinfo.cgi/boost-docs -- -- René Ferdinand Rivera Morell -- Don't Assume Anything -- No Supongas Nada -- Robot Dreams - http://robot-dreams.net

2 1

[review] boost.bloom
by Claudio DeSouza 18 May '25

18 May '25

Hello there, I have spent some time playing around with boost.bloom and my review is ACCEPT. The library is very well written, provides intuitive interfaces that are already common in C++ and familiar to users, and the SIMD optimisations are very impressive. Documentation is exemplary, although I would suggest adding a short summary of how this is not a container despite the similarities in interface but how in practice it differs from a set, so the short of attention can better catch the gist of it. I feel the source code could have been better documented for future maintainers, but that’s of no importance overall. I looked into other implementations for bloom filters, and this boost implementation could be described as “very fancy”, however the user experience has no unnecessary clutter and is friendly enough to the non-expert. I particularly must admit I felt out of depth opining in the implementation in general beyond recognising this candidate stands out in its quality by comparison with other implementations. Bloom looks exactly like the sort of thing boost is known to provide model implementation for, and it seems to be a perfect candidate to boost. A sort of “going back to its roots” IMO. Claudio

2 1

[fsc] New website is up at boost.org
by Joaquin M López Muñoz 13 May '25

13 May '25

As all of you have probably already found out by now, boost.org <http://boost.org> is now hosting the long anticipated new website! This has been a lot of work by a lot of people, and we at the FSC are so happy that the project has finally seen the light and would like to say big thanks to everybody involved. The new website is probably the most visible result of the new Fiscal Sponsorship Model approved by the community in September 2024. Please take a moment to review the site and provide your feedback, either here or by filling an issue at https://github.com/boostorg/website-v2/issues <https://github.com/boostorg/website-v2/issues> Looking forward to upcoming developments in the Boost Project. Joaquin M Lopez Munoz Boost Fiscal Sponsorship Committee

7 9

Re: [boost] [graph] which algorithm/visitor to use?
by Andrzej Krzemienski 13 May '25

13 May '25

pon., 12 maj 2025 o 00:49 Seth <bugs(a)sehe.nl> napisał(a): > On Sun, May 11, 2025, at 9:53 PM, Andrzej Krzemienski wrote: > > Thanks Seth. This is indeed a solution. But I think it is too heavy for > the task at hand. If I understand this correctly, it will first compute > *every* path between every two airports, only to later discard the too long > ones. The constraint that my problem has -- allow only four or less edges > in the path -- should be able to make the task computationally smaller. > > > It feels like this as a "concern" really has nothing to do with graphs, > and everything with geometry? How about you stuff all the airports in a > boost::geometry::index::rtree and query the nearest until you cross the > threshold distance for both airports (the query results will be in > ascending order of distance - see > https://stackoverflow.com/a/22910024/85371 (include the comments from the > BG devs). > > That moves all the distance calculations out of your hand and puts the > onus of spatial indexing on the BG library. > > I think the rest could be simplified even without the filtered_graph with > just some custom heuristics on astar_search. IIRC the heuristics allow you > to control which edges to examine or skip [Aas opposed to the DFS/BFS > visitors, as you correctly noted.]. I have't used A* as much myself, to be > completely frank. > > Good luck > Thanks. This is an important observation that although I am using something that can be modeled as a graph, using Boost.Graph may be a bad choice. On the other hand, this geographical constraint seems to have drawn most of the attention. But I also expressed another problem: being able to constrain the search to paths limited by the number of edges. Is this also something beyond the scope of Boost.Graph? Is my use case too simplistic for a grah library to be useful? Regards, &rzej;

2 1

[OpenMethod] review starts on 28th of April
by Дмитрий Архипов 12 May '25

12 May '25

Dear Boost community. The peer review of the proposed Boost.OpenMethod will start on 28th of April and continue until May 7th. OpenMethods implements open methods in C++. Those are "virtual functions" defined outside of classes. They allow avoiding god classes, and visitors and provide a solution to the Expression Problem, and the banana-gorilla-jungle problem. They also support multiple dispatch. This library implements most of Stroustrup's multimethods proposal, with some new features, like customization points and inter-operability with smart pointers. And despite all that open-method calls are fast - on par with native virtual functions. You can find the source code of the library at https://github.com/jll63/Boost.OpenMethod/tree/master and read the documentation at https://jll63.github.io/Boost.OpenMethod/. The library is header-only and thus it is fairly easy to try it out. In addition, Christian Mazakas (of the C++ Alliance) has added the candidate library to his vcpkg repository (https://github.com/cmazakas/vcpkg-registry-test) The library is also available in Compiler Explorer under the name YOMM2. As the library is not domain-specific, everyone is very welcome to contribute a review either by sending it to the Boost mailing list, or me personally. In your review please state whether you recommend to reject or accept the library into Boost, and whether you suggest any conditions for acceptance. Other questions you might want to answer in your review are: * What is your evaluation of the design? * What is your evaluation of the implementation? * What is your evaluation of the documentation? * What is your evaluation of the potential usefulness of the library? * Did you try to use the library? With what compiler? Did you have any problems? * How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? * Are you knowledgeable about the problems tackled by the library? Thanks in advance for your time and effort! Dmitry Arkhipov, Staff Engineer at The C++ Alliance.

12 60

Re: [boost] [openmethod] On the unreasonable efficiency of fast_perfect_hash
by Joaquin M López Muñoz 12 May '25

12 May '25

El 12/05/2025 a las 12:06, Ivan Matek escribió: > > > On Sun, May 11, 2025 at 9:01 PM Joaquin M López Muñoz via Boost > <boost(a)lists.boost.org> wrote: > > > https://github.com/joaquintides/perfect_range_hash > > > Thank you for this. Unfortunately even this basic math is a bit too > complex for me > so few small comments: > > 1. stylistically I would link to particular hash of source code, > although documentation > link is nicer. Reason is that documentation link can die I can relink to a more stable doc if the lib is accepted. > 2. afaik C is not randomly chosen between 0<= C <= 2^64, i.e. it is > always an odd number. You're right. We'd have to ask the author, but I guess the "| 1" in "hash_mult = uniform_dist(rnd) | 1" is there to avoid the (very unlikely) case hash_mult = 0. In any case, this small adjustment doesn't change the big picture statistically --the output distribution is largely dominated by C/B, where C is the multiplier and B is 2^(64-m), so the least significant bit of C is mostly swallowed along the way. > 3. in my brief experiments I tried to add large gap, and randomly pick > subset of types, > and performance was still amazing. > > Example for 3.: [...] This case of 231 type_ids scattered in a range of 3000 positions is lower-bounded by (has better chances than) the baseline case with 3000 adjacent positions, which has a probability 0.14 of finding a perfect hash multiplier for 4096 buckets. Note that a "hard" case would involve having your type_ids distributed across the entire 64-bit space of possible numerical values, and in the example you wrote the values are confined to a range that is around 10^14 times smaller than 2^64 --this is the fact that the algorithm takes an implicit advantage of. Joaquin M Lopez Munoz

5 5

[openmethod] On the unreasonable efficiency of fast_perfect_hash
by Joaquin M López Muñoz 12 May '25

12 May '25

Some days ago we discussed the fact that the perfect hashing machinery of candidate Boost.OpenMethod is apparently at odds with the theoretical probability of finding a viable function by chance (i.e. using brute force). I've taken a closer look at this issue and wrote a small article explaining why Boost.OpenMethod's fast_perfect_hash is so exceptionally successful: https://github.com/joaquintides/perfect_range_hash I hope the analysis is of interest to those puzzling over this. Joaquin M Lopez Munoz

2 1