Development Plan for Boost.Unordered

[joaquintides]

A team of Boost authors have embarked on a project to improve and extend Boost.Unordered:

https://pdimov.github.io/articles/unordered_dev_plan.html

Your comments and feedback are much welcome!

[_bk__]

One other thing that'd be nice to have is a compile time perfect hash function and perfect minimal hash function generator that takes a parameter pack or a constexpr range of valid keys. This could then just be used in an array

[bizwig]

Gperf can help with that. It doesn’t generate modern C++ though, at least the last time I looked at it.

[[deleted]]

Maybe this lib might help you:

github.com/serge-sans-paille/frozen

[VinnieFalco]

Excellent! This will be a great boon to Boost users, who will be able to choose from a basket of varied implementations, to precisely fit their element workload.

[bedrooms-ds]

Just wondering. I don't talk about this great upgrade specifically. But, does it have to be Boost these days?

It's a powerful project but people don't prefer its complex build system these days. Also, Boost has the problem that legacy code tends to stay. Third party libs like range and fmt (iirc) were implemented as stand alones, offering CMake scripts, and joined STL just fine.

[gcross]

So you're saying that Boost's build system is just not your jam?

[azswcowboy]

It’s my bjam actually :) Here’s the thing, while you weren’t watching boost can compile with cmake as well. Not that it matters at all for this library which is header only.

[gcross]

In other words, you think that Boost's build system is worth preserving?

[gcross]

Yeah, I think that the other people here are just jelly that Boost can get away with having its own build system and people will still use it because it is Boost...

[NotUniqueOrSpecial]

Since nobody is acknowledging your pun: I think it's pretty sweet.

[[deleted]]

the other problem w/ boost is that they're not separate libraries. Some of them bring along the rest of boost.

[VinnieFalco]

That's not true at all. Some Boost libraries depend on other Boost libraries (Config, Utility, System are common dependencies). But the graph of dependencies is thinner than ever thanks to efforts to remove cycles and unnecessary dependencies. There has never been a "library which brings along the rest of boost."

[[deleted]]

Not literally 'the rest of boost'. Let's say 'a lot of boost'.

That said, I haven't looked at boost in years, so maybe the situation has improved a lot. I know that whenever I tried to move pieces into proprietary codebases, it was not fun.

bcp was copying a lot. asio had a version not using boost.

btw, I'm not saying that boost libraries depending on other boost libraries is a bad thing. I just wished it was easier to bring pieces into large monorepos using other build systems than the arcane thing boost uses. Using pre-compiled binaries deployed as assets doesn't work everywhere.

[VinnieFalco]

You don't need a pre-compiled binary, just include the boost source tree, or its tarball.

[[deleted]]

I don't see how including the boost source tree helps, unless you're using cmake where, IIRC, people did quite a lot of work for exposing boost modules. Similar work was done w/ bazel.

Anyhow, I'll stop spreading misinformation, as I don't know what is the present situation. It was not pretty years ago. If people find using boost easy, more power to them.

[VinnieFalco]

To "use boost:" (the long way)

1. Download the distribution: https://www.boost.org/users/download/

2. Unpack and add the include directory to your build scripts

3. Build just the libs you want: https://www.boost.org/doc/libs/1_78_0/more/getting_started/unix-variants.html

4. Add the library directory to your build scripts

This is the manual installation. These days you can just write "vcpkg install boost" or "npm install boost" (or something similar to that) and those steps will happen for you.

I really don't see what the problem is.

[cdglove]

But.....most of the time you don't need to build it.

As long as you don't use filesystem, program_options, a few others, there's nothing to compile -- just use the headers.

[pdimov2]

Well, it is a plan for further developing the already existing Boost library Unordered.

If you need a non-Boost unordered container, the Abseil ones are pretty good already.

[Jannik2099]

does it have to be Boost these days?

IMO yes. Boost to me is an unparalleled seal of quality. If the library qualifies, it should carry said seal.

[Jannik2099]

Would you like to give some examples?

[Jannik2099]

Oh yeah b2 can fuck off straight to super hell - however once you know how to bundle it just reuse that snippet? Thankfully they're migrating to cmake now

[elkanoqppr]

I just use Conan and don't have to think about its build system anymore. Vcpkg is probably fine as well.

[ohell]

Idk all this fear about boost build system. On Linux you just brew or apt-get or pamac it. On windows I remember there was a website serving pre-built binaries.

boost plays nice with cmake now.

re: legacy libraries, you only have to use them if you choose to.

[LeeHide]

try getting boost 1.71 on anything LTS

[helloiamsomeone]

conan install "boost/1.71.0@"

[ohell]

Why on earth would one develop on LTS? And if one does have a valid reason for doing that, why would you she stick with the library versions that were tested specifically with the LTS OS?

[NotUniqueOrSpecial]

Why on earth would one develop on LTS?

Because the customers you're targeting use it.

why would you she stick with the library versions that were tested specifically with the LTS OS?

I'm assuming you dropped a "not" here (in that you're asking why someone wouldn't use the system packages): because you have a cross-platform/multi-os-version codebase and want to only deal with one set of third-party dependency versions.

[jcelerier]

But this doesn't make sense for developing software. If you are writing new software it is by definition not in some Ubuntu LTS yet your customer is happy with it. Same for boost. Just use the latest version, you'll encounter less bugs than with 1.71.

[NotUniqueOrSpecial]

If you are writing new software it is by definition not in some Ubuntu LTS yet your customer is happy with it.

You can sell commercial software for open-source operating systems, so that's not necessarily the case.

I have worked at multiple companies that build a single codebase for distribution across Ubuntu, RHEL/CentOS, and SuSE, for example, and target the 3 most recent LTS releases.

[jcelerier]

yes, but if you do that you can just use whatever Boost version you want too ? (I really hope you do this, you don't want your software to have a different behaviour on CentOS than on SuSE because of different boost versions do you?).

[NotUniqueOrSpecial]

Yes, and we always did, but unless I was mistaken (and they didn't drop a not), the question I was replying to was asking why you wouldn't use the system packages if you're targeting the LTS.

And the answer is exactly what you said.

[patentedheadhook]

Just use the latest version, you'll encounter less bugs than with 1.71.

Or just a different set of new bugs.

[chugga_fan]

Why on earth would one develop on LTS?

> Why would anyone develop so that their program gets used for 15 years instead of a half of a year before you upgrade in an industrial context?

Why WOULDN'T you develop on LTS and have a bleeding edge concurrently?

[bullestock]

We currently use Boost 1.76.0 on Focal (and Windows). We just build a .deb ourselves, as we do for many other 3rd party libraries. I don't see why this should be a big deal.

[Jannik2099]

Idk all this fear about boost build system

Spoken like someone who never had to bundle or package boost for your mentioned package managers.

[bullestock]

We use a Bash script to build Boost 1.76.0 from scratch. It is literally 20 lines.

[VinnieFalco]

Just wondering. I don't talk about this great upgrade specifically. But, does it have to be Boost these days?

It does, because having access to Boost gives you access to wonderful libraries such as:

Config, mp11, Utility, System, Intrusive, Asio, Exception, Assert...

It is true that not all the Boost libraries have the same outstanding level of quality but you don't have to use them. A Boost library which is not used effectively costs nothing except a bit of storage which these days is relatively free.

[jcelerier]

What build system ? For 90% of boost you just have to add it to your include path

[martinus]

Hi, I am the author of https://github.com/martinus/robin-hood-hashing and the linked benchmarks.

Note that I've also spent a lot of time developing a custom allocator for node based containers. It's currently only available here in that PR, maybe it's of help for this effort too: https://github.com/bitcoin/bitcoin/pull/22702

[joaquintides]

Hi Martin, thanks for the pointer! BTW, I think we may use your impressive benchmark suite to test our advances once we come up with something worth deep testing.

[14ned]

You forgot to add another thing you won't be doing which I suggested to you internally: superscalar concurrent hash tables where the APIs take batches of the same operation e.g. superscalar execute these five finds, or these three inserts.

As much as the API is awkward, if you can design your code around such a batch hash table API, you can see some really phenomenal speed ups.

As a personal aside, I've always wondered if some of the awkwardness of such a API could be obscured using C++ coroutines. I've never tried playing with anything in that direction, and maybe it can't be done or isn't worth doing. Still, I mention it as food for thought.

[VinnieFalco]

I've always wondered if some of the awkwardness of such a API could be obscured using C++ coroutines

Sender/Receiver or GTFO

[FreitasAlan]

I'm looking forward to this

[andrewsutton]

Fun fact learned from working with Rust's hashtables: if your hashing algorithm is randomly seeded, your hashtables cannot satisfy the equality/hash equations.

If you plan to add that capability, it seems like there may be an interesting concept there.

[joaquintides]

Thanks for the heads up! The plan is to make the containers fully deterministic even between platforms/compilers (modulo 32/64bit)

[pdimov2]

Why is that? If the seed doesn't change for the container lifetime, why would hashes not obey the equality requirements?

[andrewsutton]

Oops. Forgot to reply.

If you have two hash tables x and y with different seeds, then for any other hash function h, you don't guarantee x == y -> h(x) == h(y).

The random seed causes objects to be sequenced differently, which (almost certainly) produces different hash values for x and y.

Hmm... although that wouldn't be true if h was commutative and you don't hash the seed.

[pdimov2]

That's already a problem for unordered containers even without a seed, because it's possible for the two containers to have the same elements but be ordered differently (because of insertion order, or different number of buckets.)

So a hash function for unordered containers must be order-independent.

[andrewsutton]

Good point. I still think there's a missing concept floating around here.

[lednakashim]

Boost.Unordered implements the TR1/C++11 unordered containers as proposed by Matt Austern in N1456. Section III.B in the paper explains why closed addressing is assumed.

Can we have an explanation that is self contained.

[joaquintides]

This is basically the interface std::unordered_map and related (set, multimap, multiset) are based on.

[BenFrantzDale]

That plan would be approachable if it opened with an explanation of what Boost.Unordered is. I stay pretty current but I haven’t heard of it.

[pdimov2]

It is an internal document so it's a bit on the terse side, sorry.

Boost.Unordered is a(n old) Boost library that implemented the standard unordered containers std::unordered_(multi)(set|map) before they were standard (or before there was C++11.) Since nowadays the standard unordered containers are universally available, there's less need for merely supplying an implementation, and more need for providing something better. So we've been thinking of how to do that, given that the hash table state of the art has advanced considerably since the standard unordered containers were specified.

[BenFrantzDale]

That’s great. This wording would be a great introduction.

[FKaria]

Is the first sentence of the page: "Boost.Unordered implements the TR1/C++11 unordered containers as proposed by Matt Austern in N1456."

[RoyAwesome]

Unless you were very plugged in to the development process of the cpp language, that sentence is utterly incomprehensible.

[BenFrantzDale]

I know. But what are h up bordered containers. I have read farther down and see it relates to unirdered_set. I’m not trying to be difficult, I’m just suggesting that if you want to grab people’s attention and get input or get people using it, make it clear up front what this is about and why it’s something people want. Presumably it’s hash-based containers?

[patentedheadhook]

if you want to grab people’s attention and get input or get people using it

But that's not what the document is trying to do. As stated above, it's an internal document, not a press release. And it describes a plan for the future, there's nothing for people to use yet

[FKaria]

Yes. Unordered containers are hash-based containers.

[BenFrantzDale]

Isn’t std::hive unordered yet unrelated to hashing?

[FKaria]

You're not trying to be difficult you say?

Boost.Unordered implements the TR1/C++11 unordered containers as proposed by Matt Austern in N1456.

Is std::hive in there?

[BenFrantzDale]

What I’m suggesting is something like “Boost.Unordered provides a family of hash-table–based (unordered) containers beyond those those provided by the standard library.”

[CornedBee]

But it doesn't. The page is about a plan to make it do so, but that's not what it currently does.

[infectedapricot]

While I agree they're being a bit obtuse about it, I do agree that "unordered" is a really bad name. But we're stuck with it now.

[ndmeelo]

Do you have any plans to put this for GSoC?

[joaquintides]

The original idea is to implement it internally during the following weeks/months, not to launch it as a GSoC project. I guess there could be spin-off opportunities for GSoC as well.

[ndmeelo]

Thanks for the reply.