4 ms·

Hash maps are such a fundamentally important data structure that it comes as a surprise that the Zig implementation is so broken. Good to see it’s getting fixed

Hash maps are such a fundamentally important data structure that it comes as a surprise that the Zig implementation is so broken. Good to see it’s getting fixed, but surprising that this wasn’t detected before.

murkt 3y ago
Not that many hashmaps see hundreds of millions of entries in their lifetime. Given that Zig isn’t widely used, it’s probable that noone has really stumbled upon this behaviour in a non-benchmark setting.
- shemii 3y ago
  Actually it seems according to the issue that TigerBeetle (one of the bigger zig projects out there) noticed this issue [1]. It's also on their issue tracker [2]. [1] https://github.com/ziglang/zig/issues/17851 https://github.com/ziglang/zig/issues/17851 [2] https://github.com/tigerbeetle/tigerbeetle/issues/1191 https://github.com/tigerbeetle/tigerbeetle/issues/1191
  - brabel 3y ago
    When you use a language that's in alpha- (maybe beta- now?) stage, this kind of thing should be expected. Even with the latest version of Zig, perfectly correct programs can segfault due to miscompilation, so performance issues are not even the biggest worry you should have.
    - shemii 3y ago
      One thing I really don't unserstand is how bun already reached stability with it's 1.0 release (https://bun.sh/blog/bun-v1.0 https://bun.sh/blog/bun-v1.0) while being written in Zig, which still hasn't reached it's 1.0 release.
      - fastball 3y ago
        Bun is compiled to a binary, so not sure it matters how stable the underlying language is if Bun itself has a stable API?
        KolmogorovComp 3y ago
        That’s the point OP is making, even if the program is bug-free, given the compiler’s current state there’s a chance the compiled binary has bugs (due to miscompilation). Now that can happen with every compiler but using one in still in alpha significantly increases the risk.
        fastball 3y ago
        Does it help at all that Zig is LLVM-based?
        wredue 3y ago
        Not particularly. And zig is moving away from llvm anyway.
      - kreetx 3y ago
        Versioning isn’t an exact science, and people use whatever they see fit, both for technical but also marketing purposes.
      - brabel 3y ago
        If you test your software built on Zig close to 100% then you can be pretty confident you didn't run into any of the Zig compiler bugs. Bun has certainly run into them but they can almost always be worked around... if you work around all problems and manage to catch everything then yeah, you can have an application that's production worthy while being built on a compiler that's not quite there yet. The problem is, of course, you almost certainly didn't test anything near 100% and probably not even everything users may do with your software, so it's a risky bet.
      - losvedir 3y ago
    - kprotty 3y ago
      Are there any links / examples for the miscompilations?
      - KolmogorovComp 3y ago
        Zig’s issue tracker list them [0]. [0]: https://github.com/ziglang/zig/issues?q=is%3Aopen+is%3Aissue+label%3Amiscompilation https://github.com/ziglang/zig/issues?q=is%3Aopen+is%3Aissue...
        kprotty 3y ago
        Thanks, seems like most are from LLVM or packed structs.
tialaramex 3y ago
My impression from the article is that Zig provides several different hashtables and not all of them are broken in this way. This reminds me of Aria's comment in her Rust tutorial https://rust-unofficial.github.io/too-many-lists/ https://rust-unofficial.github.io/too-many-lists/ about failing to kill LinkedList. One philosophy (and the one Rust chose) for a stdlib is that this is only where things should live when they're so commonly needed that essentially everybody needs them either directly or to talk about. So, HashTable is needed by so much otherwise unrelated software that qualifies, BloomFilter, while it's real useful for some people, not so much. Aria cleaned out Rust's set of standard library containers before Rust 1.0, trying to keep only those most people would need. LinkedList isn't a good general purpose data structure, but, it was too popular and Aria was not able to remove it. Having multiple hash tables feels like a win (they're optimized for different purposes) but may cost too much in terms of the necessary testing to ensure they all hit the quality you want.
- otabdeveloper4 3y ago
  Linked lists are necessary when you have structures that can't be moved. Very important in a highly concurrent or lockfree environment.
  - boxed 3y ago
    Can't you have a list of pointers instead?
    - xgstation 3y ago
      Resizing/deleting items in list in most implementations are either not lock free or not threadsafe
      - boxed 3y ago
        Linked lists aren't either so....?
      - chmod775 3y ago
AndyKelley 3y ago
I personally have two habits that made me not notice: 1. I generally prefer ArrayHashMap 2. I tend to not delete things from hash maps
liftm 3y ago
It's surprisingly common for fledgling programming languages… cough https://accidentallyquadratic.tumblr.com/post/153545455987/rust-hash-iteration-reinsertion https://accidentallyquadratic.tumblr.com/post/153545455987/r... (I know https://news.ycombinator.com/item?id=38138223 https://news.ycombinator.com/item?id=38138223, but at least I'm not the first one this time.)
29athrowaway 3y ago
Zig is rather new, so it doesn't surprise me.

murkt 3y ago

Not that many hashmaps see hundreds of millions of entries in their lifetime. Given that Zig isn’t widely used, it’s probable that noone has really stumbled upon this behaviour in a non-benchmark setting.

shemii 3y ago
Actually it seems according to the issue that TigerBeetle (one of the bigger zig projects out there) noticed this issue [1]. It's also on their issue tracker [2]. [1] https://github.com/ziglang/zig/issues/17851 https://github.com/ziglang/zig/issues/17851 [2] https://github.com/tigerbeetle/tigerbeetle/issues/1191 https://github.com/tigerbeetle/tigerbeetle/issues/1191
- brabel 3y ago
  When you use a language that's in alpha- (maybe beta- now?) stage, this kind of thing should be expected. Even with the latest version of Zig, perfectly correct programs can segfault due to miscompilation, so performance issues are not even the biggest worry you should have.
  - shemii 3y ago
    One thing I really don't unserstand is how bun already reached stability with it's 1.0 release (https://bun.sh/blog/bun-v1.0 https://bun.sh/blog/bun-v1.0) while being written in Zig, which still hasn't reached it's 1.0 release.
    - fastball 3y ago
      Bun is compiled to a binary, so not sure it matters how stable the underlying language is if Bun itself has a stable API?
      - KolmogorovComp 3y ago
        That’s the point OP is making, even if the program is bug-free, given the compiler’s current state there’s a chance the compiled binary has bugs (due to miscompilation). Now that can happen with every compiler but using one in still in alpha significantly increases the risk.
        fastball 3y ago
        Does it help at all that Zig is LLVM-based?
        wredue 3y ago
        Not particularly. And zig is moving away from llvm anyway.
    - kreetx 3y ago
      Versioning isn’t an exact science, and people use whatever they see fit, both for technical but also marketing purposes.
    - brabel 3y ago
      If you test your software built on Zig close to 100% then you can be pretty confident you didn't run into any of the Zig compiler bugs. Bun has certainly run into them but they can almost always be worked around... if you work around all problems and manage to catch everything then yeah, you can have an application that's production worthy while being built on a compiler that's not quite there yet. The problem is, of course, you almost certainly didn't test anything near 100% and probably not even everything users may do with your software, so it's a risky bet.
    - losvedir 3y ago
  - kprotty 3y ago
    Are there any links / examples for the miscompilations?
    - KolmogorovComp 3y ago
      Zig’s issue tracker list them [0]. [0]: https://github.com/ziglang/zig/issues?q=is%3Aopen+is%3Aissue+label%3Amiscompilation https://github.com/ziglang/zig/issues?q=is%3Aopen+is%3Aissue...
      - kprotty 3y ago
        Thanks, seems like most are from LLVM or packed structs.

tialaramex 3y ago

My impression from the article is that Zig provides several different hashtables and not all of them are broken in this way. This reminds me of Aria's comment in her Rust tutorial https://rust-unofficial.github.io/too-many-lists/ https://rust-unofficial.github.io/too-many-lists/ about failing to kill LinkedList. One philosophy (and the one Rust chose) for a stdlib is that this is only where things should live when they're so commonly needed that essentially everybody needs them either directly or to talk about. So, HashTable is needed by so much otherwise unrelated software that qualifies, BloomFilter, while it's real useful for some people, not so much. Aria cleaned out Rust's set of standard library containers before Rust 1.0, trying to keep only those most people would need. LinkedList isn't a good general purpose data structure, but, it was too popular and Aria was not able to remove it. Having multiple hash tables feels like a win (they're optimized for different purposes) but may cost too much in terms of the necessary testing to ensure they all hit the quality you want.

otabdeveloper4 3y ago
Linked lists are necessary when you have structures that can't be moved. Very important in a highly concurrent or lockfree environment.
- boxed 3y ago
  Can't you have a list of pointers instead?
  - xgstation 3y ago
    Resizing/deleting items in list in most implementations are either not lock free or not threadsafe
    - boxed 3y ago
      Linked lists aren't either so....?
    - chmod775 3y ago

AndyKelley 3y ago

I personally have two habits that made me not notice: 1. I generally prefer ArrayHashMap 2. I tend to not delete things from hash maps

liftm 3y ago

It's surprisingly common for fledgling programming languages… cough https://accidentallyquadratic.tumblr.com/post/153545455987/rust-hash-iteration-reinsertion https://accidentallyquadratic.tumblr.com/post/153545455987/r... (I know https://news.ycombinator.com/item?id=38138223 https://news.ycombinator.com/item?id=38138223, but at least I'm not the first one this time.)

29athrowaway 3y ago

Zig is rather new, so it doesn't surprise me.