libsoundio VS Klib

Audio DSP is definitely the deep end of the pool. I believe the Zig programming language owes its creation to Andrew Kelley (the creator) trying to write stuff for an audio workbench going "damn, this is really hard to do with C, why does C suck so much" and just creating a language that's like C but without the bad parts to do it himself. I'm not joking, this is literally the origin of Zig as I've heard it from a podcast, and here is Andrew's old audio lib for proof: https://github.com/andrewrk/libsoundio

http://libsound.io is a great cross platform library for reading and writing to sound cards. i have used it successfully on macos and i’m sure it supports linux and possibly windows too. you will probably also need lib audio for reading and writing to files.

Hmm... after some research it seems that I've misunderstood Zig's situation a bit. Zig has introduced null-terminated string types a couple of years ago, but still encourages you to do most string operations with slices instead. Let me explain:

Zig's string literals (which you create with parenthesis like "Hello world!") are null-terminated byte arrays, expressed as the type const [N:0]u8 (where the :0 tells you that it's null-terminated), whereas the more typical array might be written as const [N]u8. The reason for this feature is not because the language wants you to use null-terminated strings, but because these static strings need to be stored in the global data section of the ELF executable, and these require you to use null-termination. But if you want to do any mutable operation with this string, you need to convert this into a proper slice (ptr + size). And it seems like Zig developers don't really use null-terminated types that much at the API level, but use it for things like C interop or cases where you really need it for special optimizations.

Noting that from the PR that introduced this feature, Andrew Kelley writes:

> I think you will find that the Zig community in general (and especially myself) agrees with you on this [null-terminated strings being fragile], and APIs in general should prefer slices to null terminated pointers. Even if you are using Zig to create a C library, and even in actual C libraries, I would recommend pointer and length arguments rather than null terminated pointers, like this: https://github.com/andrewrk/libsoundio/blob/1.1.0/soundio/so...

> That being said, I want to repeat what I said earlier about null terminated pointers: A null terminated array is not inherently an evil C concept that is intruding in the Zig language. It's a general data storage technique that is valid for some memory constrained use cases. I also stumbled on a Real Actual Use Case inside LLVM. The bottom line for me is that null terminated pointers exist in the real world, and especially in systems programming. You can see this in interfaces with the operating system in the standard library...

So he acknowledges null-terminated strings can certainly be useful in certain situations outside of legacy reasons, which is good to know. And Zig creating a special type for this shows that a good systems language needs to be designed to accommodate the needs of the outside world.

Perhaps you could use either http://libsound.io/ or SDL2 game library + SDLAudioIn (http://burningsmell.org/sdl_audioin/) which provides low-level APIs to access operating-system sound systems like Alsa, PulseAudio, PipeWire, and CoreAudio (not sure how well it is supported by SDL2).

Comparison: https://github.com/andrewrk/libsoundio/wiki/libsoundio-vs-SD...

Fun fact: Andrew Kelley, the creator of the Zig programming language, kind of created it so he could work on audio processing.

Based on: https://github.com/andrewrk/libsoundio/blob/master/example/sio_sine.c

Does this fit your needs? https://github.com/andrewrk/libsoundio

I listened to the Co-recursive podcast the other day that featured Andrew Kelley, the creator of the Zig programming language. Before Zig he developed Libsoundio - https://github.com/andrewrk/Libsoundio, to solve problems around realtime audio.

Audio will probably come later, but libsoundio will be the first thing in terms of groundwork. Integrating that in the same way we've integrated GLFW, so you can just cross compile and get cross-platform audio to boot.

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