7 ms·
Hashmaps in Factor are faster than in Zig
- kencausey 3y agoTitle is a bit clickbait. This is regarding Hashmaps specifically. Read or at least scan through it where the author will submit a fix for the Zig implementation resulting in Zig's Hashmap being 50% faster than the Factor implementation.
- lll-o-lll 3y agoHash 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 agoNot 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 agoActually 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 agoWhen 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 agoOne 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 agoBun 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 agoThat’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
- tialaramex 3y agoMy 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 agoLinked lists are necessary when you have structures that can't be moved. Very important in a highly concurrent or lockfree environment.
- AndyKelley 3y agoI 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 agoIt'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 agoZig is rather new, so it doesn't surprise me.
- senderista 3y agoI don't see a compelling reason to use tombstones in linear probing except in a concurrent context (where you can't move entries around). The tombstone-free deletion algorithm is quite simple: https://github.com/senderista/hashtable-benchmarks/blob/master/src/main/java/set/int64/LPLongHashSet.java#L184 https://github.com/senderista/hashtable-benchmarks/blob/mast.... No rehashing is necessary.
- celeritascelery 3y agoThis is a really cool approach! But if it so obvious, why doesn't every hashmap use it? It seems like there are some trade-offs here that I must be missing.
- Leszek 3y agoIf you do any kind of probing other than linear probing (e.g. quadratic probing) this approach doesn't work anymore, because your collisions are no longer densely grouped together.
- senderista 3y agoThe main tradeoff is concurrency: it's difficult to safely read a hash table while its entries are being concurrently relocated. Another tradeoff is (probably) higher average latency (but worst-case latency is much better since there's no global rehashing required).
- adgjlsfhk1 3y agoimo a pretty good approach is tombstones where you delete trailing tombstones. that way the tombstones can't overly clog the dictionary but never have to move live objects
- senderista 3y agoHere is a simple heuristic for avoiding most tombstones when the load factor isn't too high: https://arxiv.org/pdf/1808.04602.pdf https://arxiv.org/pdf/1808.04602.pdf
- benatkin 3y agoWhy hashmaps? Python has named tuples. Oh - this puts a lot of keys into one hashmap, not a ton of objects with the same keys. :)
- murkt 3y agoPython also has dicts.
- benatkin 3y agoOf course. I was just saying that a lot of the time hashmaps don't get very many entries. There is serialization and deserialization where Cap'n Proto, Flatbuffers, and Protocol Buffers have a savings over JSON by not repeating key names of a list of maps.
- murkt 3y agoI fail to see how is this relevant to the article. HashMap/dict can as well store a mapping from an integer to an integer. Or from a token to an integer, or whatever, and it has nothing to do with serialization, JSON inefficiency or lists of maps.
- asplake 3y agoUse the structure that best fits the problem. The saving to which you refer applies only to serialisation, not to the use of the structure by an algorithm.
- Dwedit 3y agoSo in other words, bug in Zig library causes linear execution time on something that isn't supposed to be linear.
- chmod600 3y agoFactor looks cool, but what's it really about? Can someone who loves the language explain why?
- m031 3y agoFound this page on that subject: https://concatenative.org/wiki/view/Factor/FAQ/Why%3F https://concatenative.org/wiki/view/Factor/FAQ/Why%3F
- Avshalom 3y agoIt's as flexible as commonlisp or smalltalk.
- mrjbq7 3y agoI'm a bit biased as I've been working on and with Factor for 15 years and I am also the author of the linked article and "Re: Factor" blog. I find Factor to have a compelling sweet spot of concise syntax, dynamic features, and (relatively) high performance. But in particular, I think we've done a good job with a few things: 1) Making the language very "clickable", so you can introspect and dig down into all function and type definitions. 2) Provide a lot of batteries-included in the standard library. 3) Make it super easy to accept contributions, there's a part of the distribution that is "extra" and has low barrier to entry and then we commit to keeping code working and promoting things to the main standard library when they are useful/documented/tested enough.
- broken-kebab 3y agoI always suspected that Factor appeared as an attempt to re-live Forth magic, but at higher level, more applicable outside of embedded domain
- deleted 3y ago[deleted]
- zelphirkalt 3y agoNot a good showcase of Factor code. All variable names 1 letter, seemingly simply chosen subsequent letters in the alphabet, instead of any names, that would indicate what the code does.
- mrjbq7 3y agoI agree, I've written much better Factor code. This was mainly to get a matching test case working simply...