Klib VS meson

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

[1]: https://github.com/mesonbuild/meson/issues/8153

The Meson build system Version: 1.2.3 Source dir: /home/patrik/workspace/Waybar Build dir: /home/patrik/workspace/Waybar/build Build type: native build Project name: waybar Project version: 0.9.24 C compiler for the host machine: cc (gcc 13.2.0 "cc (Debian 13.2.0-5) 13.2.0") C linker for the host machine: cc ld.bfd 2.41 C++ compiler for the host machine: c++ (gcc 13.2.0 "c++ (Debian 13.2.0-5) 13.2.0") C++ linker for the host machine: c++ ld.bfd 2.41 Host machine cpu family: x86_64 Host machine cpu: x86_64 Compiler for C++ supports link arguments -lc++fs: NO Compiler for C++ supports link arguments -lc++experimental: NO Compiler for C++ supports link arguments -lstdc++fs: YES Program git found: YES (/usr/bin/git) WARNING: You should add the boolean check kwarg to the run_command call. It currently defaults to false, but it will default to true in future releases of meson. See also: https://github.com/mesonbuild/meson/issues/9300 Has header "filesystem" : YES Checking if "nl_langinfo with _NL_TIME_WEEK_1STDAY, _NL_TIME_FIRST_WEEKDAY" : links: YES Run-time dependency threads found: YES Found pkg-config: /usr/bin/pkg-config (1.8.1) Run-time dependency fmt found: YES 9.1.0 Run-time dependency spdlog found: YES 1.12.0 Run-time dependency wayland-client found: YES 1.22.0 Run-time dependency wayland-cursor found: YES 1.22.0 Run-time dependency wayland-protocols found: YES 1.32 Run-time dependency gtkmm-3.0 found: YES 3.24.8 Run-time dependency dbusmenu-gtk3-0.4 found: YES 16.04.0 Run-time dependency gio-unix-2.0 found: YES 2.78.1 Run-time dependency jsoncpp found: YES 1.9.4 Run-time dependency sigc++-2.0 found: YES 2.12.1 Found CMake: /usr/bin/cmake (3.27.7) Run-time dependency libinotify found: NO (tried pkgconfig and cmake) Run-time dependency epoll-shim found: NO (tried pkgconfig and cmake) Run-time dependency libinput found: YES 1.23.0 Run-time dependency libnl-3.0 found: YES 3.7.0 Run-time dependency libnl-genl-3.0 found: YES 3.7.0 Run-time dependency upower-glib found: YES 1.90.2 Run-time dependency libpipewire-0.3 found: YES 0.3.85 Run-time dependency playerctl found: YES 2.4.1 Run-time dependency libpulse found: YES 16.1 Run-time dependency libudev found: YES 252 Run-time dependency libevdev found: YES 1.13.1 Run-time dependency libmpdclient found: YES 2.20 Run-time dependency xkbregistry found: YES 1.6.0 Run-time dependency jack found: YES 0.126.0 Run-time dependency wireplumber-0.4 found: YES 0.4.15 Library sndio found: YES Checking for function "sioctl_open" with dependency -lsndio: YES Run-time dependency gtk-layer-shell-0 found: YES 0.8.1 Run-time dependency systemd found: YES 252 Computing int of "__cpp_lib_chrono" : 201611 Configuring waybar.service using configuration Run-time dependency cava found: NO (tried pkgconfig and cmake) Looking for a fallback subproject for the dependency cava Executing subproject cava cava| Project name: cava cava| Project version: 0.9.1 cava| C compiler for the host machine: cc (gcc 13.2.0 "cc (Debian 13.2.0-5) 13.2.0") cava| C linker for the host machine: cc ld.bfd 2.41 cava| Has header "iniparser.h" : NO cava| Has header "iniparser4/iniparser.h" : NO Message: cava is not found. Building waybar without cava subprojects/cava-0.9.1/meson.build:65:3: ERROR: Problem encountered: iniparser library is required A full log can be found at /home/patrik/workspace/Waybar/build/meson-logs/meson-log.txt WARNING: Running the setup command as `meson [options]` instead of `meson setup [options]` is ambiguous and deprecated.

As it happens, I recently landed a PR in meson to add a clang-like Weverything mode that includes all of that, so you can get a minimal list of more or less all GCC warnings, organized by version, from the meson source here: https://github.com/mesonbuild/meson/blob/710a753c78077220b13a9f7e999dcdb61339efb1/mesonbuild/compilers/mixins/gnu.py

Came here to post the same. The answer for How to build software? is Meson[1] for C and C++ and also other languages. Works well on Windows and Mac, too.

I’ve written a small Makefile to learn the basic and backgrounds. Make is fine. But the next high-level would have been Autotools, which is an intimidating and weird set of tools. Most new stuff written in C/C++ use now Meson and it feels sane.

[1] https://mesonbuild.com

If you are very fortunate, you'll be able to choose something else. I like meson myself: it looks a bit like python, it's popular, small, simple, well-documented, easy to install and update, and it works well everywhere.

I suggest changing the build tool. Meson improved C and C++ a lot:

https://mesonbuild.com/

The dependency declaration and auto-detection is nice. But the hidden extra is WrapDB, built-in package management (if wanted):

    https://mesonbuild.com/Wrap-dependency-system-manual.html

> C's only REAL problem (in my opinion) which is the lack of dependency management. Most everything else can be done with a makefile and a half decent editor.

Care to hear about our lord and saviour Meson?

Both of your quoted problems are mutually incompatible: dependency management isn't the job of the compiler, it's a job for the build or host system. If you want to keep writing makefiles, be prepared to write your own `wget` and `git` invocations to download subprojects.

Meanwhile, Meson solves the dependency management problem in a way that makes both developers and system integrators/distributions happy. It forces you to make a project that doesn't have broken inter-file or header dependency chains and cleans up all the clutter and cruft of a makefile written for any non-trivial project, while making it trivial to integrate other meson projects into your build, let other people integrate your project into theirs, and provides all of the toggles and environment variables distribution developers need to package your library properly. You can really have your cake and eat it too.

https://mesonbuild.com/

Other people going down this route seem to end up writing cmake replacements instead. I'm thinking of something like meson here except that meson never intended to transpile to cmake.

I thought I would share my custom installer script for the latest GitHub versions of CMake, Ninja, and Meson.