libc VS Klib

> I absolutely don't see how this is a problem with semver,

Strange to not see it. Semver promises to solve dependency hell. In the example everyone correctly followed the sevmver and the app is broken by a dependency hell issue.

> it is not the responsibility of semver to tell a language how packages should be isolated and loaded. That is a problem of a) the language and b) dependency resolution in the package manager.

So semver only works for "good" languages?

> Bundler, by design, does not allow the above, instead having a flat, consistent vision of dependencies.

Ok, so what happens with the app when packages managed by Bundler get fragmented by depending on an incompatible version of sub-dependency (commons-logging 1.1.1 vs 2.0.1 as in the example)?

Also note, even for languages and tooling supporting multiple library versions loaded side by side, there are scenarios where things break.

For example, the "libc apocalypse" situation in Rust https://github.com/rust-lang/libc/issues/547

Here after the "libc" module released a major version, the definition for the `void` C type in two versions of the lib are considered by the compiler as two different types, resulting in breakages everywhere around the library ecosystem.

There are also scenarios for dynamic languages / runtime errors.

> None of this is the responsibility of semver. In fact, semver would help the language provide tooling to detect that kind of "hey this instance is from foo-1.0 but you're trying to consume it in foo-2.0".

And what's next after it detected the dependency hell? It's too late and the person suffering is not in the position to fix it. You have to upgrade to "authentication 1.1.2" for security compliance, because the version 1.1.1 has known vulnerabilities. But that breaks the application, because the maintainer of the lower level dependency "commons-logging" follows semantic versioning.

The promise was to prevent dependency hell, not to detect it.

Quoting the ticket and reiterating the point of my first comment above:

Once again, the point of this ticket is to:

    Remove the false promise that SemVer solves dependency hell by simply increasing major version.

Even if coexistence of multiple library versions is supported, there are scenarios where things break.

For example, the "libc apocalypse" situation in Rust https://github.com/rust-lang/libc/issues/547

Here after the "libc" module released a major version, the definition for the `void` C type in two versions of the lib are considered by the compiler as two different types, resulting in breakages everywhere around the library ecosystem.

There are also scenarios for dynamic languages / runtime errors in statically typed languages.

My main problem with the current SemVer spec, is that it does not mention multiple lib versions problem, and promises the dependency hell issues can be solved simply by updating major version number. Thus encouraging to break backward compatibility freely.

Also note, it's not the case that SemVer is intended only for languages supporting multiple library versions. The SemVer is a product of Ruby community, and Ruby has a global namespace for classes and unable to have several versions of a lib simultaneously.

In 2000s they were breaking compatibility left and right, neglecting elementary compatibility practices. If you were working on an application, practically every time when you update dependencies, something would break.

So (in 2011 ?) they came out with this "manifesto" (Why such a big name? This scheme of versioning was well established in linkers and sonames of all Unix-like systems for decades - it goes back to at least 1987 paper "Shared Libraries in SunOS").

It's a good thing SemVer acknowledges finally that compatibility is a serious matter. Only that it's better to discourage compatibility breakages. An in cases when it's really needed (I agree such cases exists), there are things to take care of in addition to simply increase major version num.

The libc crate exposes system C APIs in Rust code, and is used by the compiler and standard library. It also does not contain any C code. See for yourself.

Ok, what if we are sure that our C code would use a given version of malloc/free only to allocate memory (are we ever sure about anything like that is out of the scope of the article)? Well, in this case we are brave enough to use libc crate in our rust code:

Port libc. I recommend using bindgen for this.

While looking at the libc crate and its build script, I don’t quite understand when or how the crate’s libc definitions link to the build target’s actual libc.

For what it's worth, there's been discussion of this not only for glibc on Linux but also for BSDs which take many more liberties with API and ABI compatibility to keep their technical debt low. I can't summarise the years of discussion here but I encourage anyone interested to read through https://github.com/rust-lang/libc/issues/570

In answer to what appears to be a misunderstanding about Rust:

> Its foreign function interface seems particularly poorly implemented. The official Rust documentation suggests the use of the external third-party libc library (called a 'crate' in Rust parlance) to provide the type definitions necessary to interface with C programs. As of the time of writing, this crate has had 95 releases. Contrast this with Ada’s Interfaces.C package, which was added the language in Ada 95 and hasn’t needed to change in any fundamental way since.

Rust's libc crate isn't third-party, it's first-party, developed by the Rust project itself: https://github.com/rust-lang/libc/ . It's also not just for "type definitions necessary to interface with C programs"; here's the first heading and first paragraph of its README:

"libc - Raw FFI bindings to platforms' system libraries"

libc provides all of the definitions necessary to easily interoperate with C code (or "C-like" code) on each of the platforms that Rust supports. This includes type definitions (e.g. c_int), constants (e.g. EINVAL) as well as function headers (e.g. malloc).

The fact that this library contains low-level type definitions for every platform that Rust supports explains why it's had more than one release: new platforms get added, platforms add new interfaces, and platforms change the definitions of existing interfaces.

> It lacks basic features necessary for the task, like bitfields, and data structure packing.

The latter is achieved via the built-in `repr(packed)` attribute (https://doc.rust-lang.org/nomicon/other-reprs.html#reprpacke...) and the former is provided by the bitflags crate: https://crates.io/crates/bitflags (while unlike libc this does not live under the rust-lang org on Github, it does live under its own org which appears to be populated exclusively by Rust project team members).

It came up in this issue in the libc crate. The initializer for a static has to be const, which is why the issue submitter wanted it. He couldn't use lazy_static or once_cell, common patterns in Rust, since he was later using the static in a unix signal handler (which must be async signal safe).

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