boost VS Klib

coost is a cross-platform C++ basic library with both performance and ease of use. It is like boost, but much smaller, the static library built on linux and mac is only about 1MB in size. Although small, it provides enough powerful features:

Not so much ease, as flexibility.

In the end, the thing that matters the most for software is being able to get logic into code as efficiently as possible. This includes being able to write concise code, being able to execute it and see results, debug it efficiently, use libraries easily, and deploy it to production. Python has all of this.

The rest of the stuff, like strong typing, memory safety, e.t.c are at best academic. The supposed advantages of those just don't hold up once you start to look into the real world. Linux, which runs on most devices that support an os hardware wise, is written purely in C. Python is used as a backend for very big projects like Youtube, Instagram, Spotify, e.t.c. Its also used to run Openpilot (https://github.com/commaai/openpilot), which has performance on par with Teslas autopilot.

Meanwhile in Java world, with strict typing, you have egregious vulnerabilities like log4shell, amongst others (https://java-0day.com/).

Language evolution is also a thing to look at with this stuff. The more "strict" you try to make a language, the worse its going to become as people are necessarily going to find hacks around it. With java, type safety strict features like having getters and setters get abstracted away behind an annotation processor that hacks the AST (Lombok), and thats not only considered ok, but is encouraged to be used. With C++, template metaprogramming got extremely out of hand with https://www.boost.org/, where the error messages for one thing used to be pages long. Rust manage to sneak this under the radar with the unsafe clause, which is going to see standard use in many codebases, thus negating any of its advantages.

In the end, good code comes from good developers, full stop. Every codebase will necessarily have tests for production deployment, and anything that language features don't catch during compilation or static checking can be checked with testing if you have developers that understand what they are doing and can write appropriate testing frameworks.

And based on that, its pretty attractive to use Python especially when you consider developer time. And the flexibility means you can write your code in different forms to suit your use case, where it be OOP with MyPy type checking, functional, imperative, or super complex if you want.

For those who didn't know what is Boost, it's a C++ library that helps to prevent re-inventing the wheel while trying to program something quite complex as example looping only with macro, Boost Preprocessor. Fortunately, Boost Preprocessor Repeat also works with plain C, not only C++. So, my OrangePi board can calculate hash at compile-time. Unfortunately, my SIX Hash algorithm requires sizeof(input) and Boost... won't... work... with it. Hours of workarounds, no luck.

If you have the ability to use third-party libraries (though if you can't this project is going to be a nightmare, lol...) I would recommend using the Beast library from the Boost collection of libraries. It's a little bit more verbose than some options, but not that much more, and it's better maintained. REST webservices are built on top of the HTTP framework, so it's just a matter of sending a HTTP GET request to a server (or POST/UPDATE/DELETE, depending on how exactly the api on the other end is implemented) and reading the response you get back. This is a very basic sample of a client sending a GET request to a server. If you need to change this to do a POST (or some other kind of request), there's only two real changes that need to be made:

The person you replied to used slightly confusing terminology. Conda deals with non-python packages. As in if you wanted to install boost for C++.

I'm not sure if its just me but I'm finding I can't access any of the download links on the Boost Website.

rich standard library and Boost;

Boost is also another ubiquitous library. Lots of code that doesn't make it into the standard kind of ends up here. Lots of code that gets into the standard starts here. Boost.Asio might end up being our network API in 23.

In my example the table stores the hash codes themselves instead of the keys (because the hash function is invertible)

Oh, I see, right. If determining the home bucket is trivial, then the back-shifting method is great. The issue is just that it’s not as much of a general-purpose solution as it may initially seem.

“With a different algorithm (Robin Hood or bidirectional linear probing), the load factor can be kept well over 90% with good performance, as the benchmarks in the same repo demonstrate.”

I’ve seen the 90% claim made several times in literature on Robin Hood hash tables. In my experience, the claim is a bit exaggerated, although I suppose it depends on what our idea of “good performance” is. See these benchmarks, which again go up to a maximum load factor of 0.95 (Although boost and Absl forcibly grow/rehash at 0.85-0.9):

https://strong-starlight-4ea0ed.netlify.app/

Tsl, Martinus, and CC are all Robin Hood tables (https://github.com/Tessil/robin-map, https://github.com/martinus/robin-hood-hashing, and https://github.com/JacksonAllan/CC, respectively). Absl and Boost are the well-known SIMD-based hash tables. Khash (https://github.com/attractivechaos/klib/blob/master/khash.h) is, I think, an ordinary open-addressing table using quadratic probing. Fastmap is a new, yet-to-be-published design that is fundamentally similar to bytell (https://www.youtube.com/watch?v=M2fKMP47slQ) but also incorporates some aspects of the aforementioned SIMD maps (it caches a 4-bit fragment of the hash code to avoid most key comparisons).

As you can see, all the Robin Hood maps spike upwards dramatically as the load factor gets high, becoming as much as 5-6 times slower at 0.95 vs 0.5 in one of the benchmarks (uint64_t key, 256-bit struct value: Total time to erase 1000 existing elements with N elements in map). Only the SIMD maps (with Boost being the better performer) and Fastmap appear mostly immune to load factor in all benchmarks, although the SIMD maps do - I believe - use tombstones for deletion.

I’ve only read briefly about bi-directional linear probing – never experimented with it.

It could be that the cost of the function calls, either directly or via a pointer, is drowned out by the cost of the one or more cache misses inevitably invoked with every hash table lookup. But I don't want to say too much before I've finished my benchmarking project and published the results. So let me just caution against laser-focusing on whether the comparator and hash function are/can be inlined. For example stb_ds uses a hardcoded hash function that presumably gets inlined, but in my benchmarking (again, I'll publish it here in coming weeks) shows it to be generally a poor performer (in comparison to not just CC, the current version of which doesn't necessarily inline those functions, but also STC, khash, and the C++ Robin Hood hash tables I tested).

Not an entirely uncommon idea. I've written one.

There's also a well-known one here, in klib: https://github.com/attractivechaos/klib/blob/master/kvec.h

Code reuse is achievable by (mis)using the preprocessor system. It is possible to build a somewhat usable API, even for intrusive data structures. (eg. the linux kernel and klib[1])

I do agree that generics are required for modern programming, but for some, the cost of complexity of modern languages (compared to C) and the importance of compatibility seem to outweigh the benefits.

[1]: http://attractivechaos.github.io/klib

Unordered hash map shootout CMAP = https://github.com/tylov/STC KMAP = https://github.com/attractivechaos/klib PMAP = https://github.com/greg7mdp/parallel-hashmap FMAP = https://github.com/skarupke/flat_hash_map RMAP = https://github.com/martinus/robin-hood-hashing HMAP = https://github.com/Tessil/hopscotch-map TMAP = https://github.com/Tessil/robin-map UMAP = std::unordered_map Usage: shootout [n-million=40 key-bits=25] Random keys are in range [0, 2^25). Seed = 1656617916: T1: Insert/update random keys: KMAP: time: 1.949, size: 15064129, buckets: 33554432, sum: 165525449561381 CMAP: time: 1.649, size: 15064129, buckets: 22145833, sum: 165525449561381 PMAP: time: 2.434, size: 15064129, buckets: 33554431, sum: 165525449561381 FMAP: time: 2.112, size: 15064129, buckets: 33554432, sum: 165525449561381 RMAP: time: 1.708, size: 15064129, buckets: 33554431, sum: 165525449561381 HMAP: time: 2.054, size: 15064129, buckets: 33554432, sum: 165525449561381 TMAP: time: 1.645, size: 15064129, buckets: 33554432, sum: 165525449561381 UMAP: time: 6.313, size: 15064129, buckets: 31160981, sum: 165525449561381 T2: Insert sequential keys, then remove them in same order: KMAP: time: 1.173, size: 0, buckets: 33554432, erased 20000000 CMAP: time: 1.651, size: 0, buckets: 33218751, erased 20000000 PMAP: time: 3.840, size: 0, buckets: 33554431, erased 20000000 FMAP: time: 1.722, size: 0, buckets: 33554432, erased 20000000 RMAP: time: 2.359, size: 0, buckets: 33554431, erased 20000000 HMAP: time: 0.849, size: 0, buckets: 33554432, erased 20000000 TMAP: time: 0.660, size: 0, buckets: 33554432, erased 20000000 UMAP: time: 2.138, size: 0, buckets: 31160981, erased 20000000 T3: Remove random keys: KMAP: time: 1.973, size: 0, buckets: 33554432, erased 23367671 CMAP: time: 2.020, size: 0, buckets: 33218751, erased 23367671 PMAP: time: 2.940, size: 0, buckets: 33554431, erased 23367671 FMAP: time: 1.147, size: 0, buckets: 33554432, erased 23367671 RMAP: time: 1.941, size: 0, buckets: 33554431, erased 23367671 HMAP: time: 1.135, size: 0, buckets: 33554432, erased 23367671 TMAP: time: 1.064, size: 0, buckets: 33554432, erased 23367671 UMAP: time: 5.632, size: 0, buckets: 31160981, erased 23367671 T4: Iterate random keys: KMAP: time: 0.748, size: 23367671, buckets: 33554432, repeats: 8, sum: 4465059465719680 CMAP: time: 0.627, size: 23367671, buckets: 33218751, repeats: 8, sum: 4465059465719680 PMAP: time: 0.680, size: 23367671, buckets: 33554431, repeats: 8, sum: 4465059465719680 FMAP: time: 0.735, size: 23367671, buckets: 33554432, repeats: 8, sum: 4465059465719680 RMAP: time: 0.464, size: 23367671, buckets: 33554431, repeats: 8, sum: 4465059465719680 HMAP: time: 0.719, size: 23367671, buckets: 33554432, repeats: 8, sum: 4465059465719680 TMAP: time: 0.662, size: 23367671, buckets: 33554432, repeats: 8, sum: 4465059465719680 UMAP: time: 6.168, size: 23367671, buckets: 31160981, repeats: 8, sum: 4465059465719680 T5: Lookup random keys: KMAP: time: 0.943, size: 23367671, buckets: 33554432, lookups: 34235332, found: 29040438 CMAP: time: 0.863, size: 23367671, buckets: 33218751, lookups: 34235332, found: 29040438 PMAP: time: 1.635, size: 23367671, buckets: 33554431, lookups: 34235332, found: 29040438 FMAP: time: 0.969, size: 23367671, buckets: 33554432, lookups: 34235332, found: 29040438 RMAP: time: 1.705, size: 23367671, buckets: 33554431, lookups: 34235332, found: 29040438 HMAP: time: 0.712, size: 23367671, buckets: 33554432, lookups: 34235332, found: 29040438 TMAP: time: 0.584, size: 23367671, buckets: 33554432, lookups: 34235332, found: 29040438 UMAP: time: 1.974, size: 23367671, buckets: 31160981, lookups: 34235332, found: 29040438