imap
Languages and libraries
data structure library
SHOW HN2024
How HN took it
4 positive, 6 neutral or asking, 0 mixed, 6 critical, out of 16 comments about the project. Thread score -0.13.
Idea: 1 for, 3 againstPerformance: 1 for, 3 againstDesign: 1 for, 0 against
The thread, comment by comment
Each row is a top-level comment and its replies, in HN's order. Select a cell to open that comment on HN.
positive neutral or mixed critical about another commenter or something else the maker
What HN said
What people liked
Novel subnet-mask style prefix construction
From 2 comments
This looks very good. The idea of using a subnet-mask style to compute the prefix of a node is pretty novel. I haven't seen anything like it. The choice of span factor of 16 is a…
ww520 on HNSubnet mask style prefix construction is pretty novel.
ww520 on HN
Good node slot packing and span factor choice
From 1 comment
This looks very good. The idea of using a subnet-mask style to compute the prefix of a node is pretty novel. I haven't seen anything like it. The choice of span factor of 16 is a…
ww520 on HN
Objections
Benchmarks only against std::map and std::unordered_map, missing stronger alternatives
From 2 comments
This really doesn't seem to be comparing to comparable data structures. For int map specializations like this, the optimized alternatives are things like Judy (which is looking…
jemfinch on HNI've written a lot of high performance/scale C++ code using a lot of data structures over the years, and ordered iteration has been very rarely needed; unordered data structures…
jemfinch on HN
Item count limited to about 67 million (2^26)
From 1 comment
Interesting, but the summary does not mention an important fact: the data structure can contain at most 67108864 items, which is a quite low limit.
ursusmaritimus on HN
Mutable and lacks batch set operations
From 1 comment
Appears to be a 16 way branching trie which completely misses both advantages of tree structures over hashes: 1/ This tree is mutable, insert doesn't give you a new tree via path…
JonChesterfield on HN
Looks like a standard 16-way compressed trie
From 1 comment
What novel ideas did you see here? To me this looks like a standard 16-way compressed trie. The node encoding is quite natural if you consider the limitation of 64M entries…
ot on HN
Requests
Benchmark against Judy arrays, roaring bitmaps, absl::btree_map and crit-bit trees
From 3 comments
This really doesn't seem to be comparing to comparable data structures. For int map specializations like this, the optimized alternatives are things like Judy (which is looking…
jemfinch on HNOh come on. Don't be too harsh. This is an ordered map. Most of the mentioned ones are unordered maps. They might be fast but they are unordered. The only comparables are…
ww520 on HNIt'd be nice to include djb's crit-bit tree implementation (linked to from the intro) in the benchmarks ("Performance Test" section).
notfed on HN
Explain why 32-bit ints are used instead of 64-bit
From 1 comment
This limit comes from using int32s. Does anyone have an idea why on modern machines it isn't making use of int64s?
xaellison on HN
Questions
Do insertions invalidate iterators?
From 1 comment
Looks rad, I was going to look into some b-trees for a use-case where I need an ordered map of things similar to integers and this might be better. I couldn't immediately see, is…
repsilat on HN
Alternatives named
Judy arrays
From 2 comments
Interesting! Reminds me a great deal of Judy Arrays: https://en.m.wikipedia.org/wiki/Judy_array Judy Arrays are a radix trie with branching and a few node types designed to be…
AaronFriel on HNThis really doesn't seem to be comparing to comparable data structures. For int map specializations like this, the optimized alternatives are things like Judy (which is looking…
jemfinch on HN
Haskell IntMap
From 1 comment
FWIW there is prior art here. e.g. see IntMap in Haskell: https://hackage.haskell.org/package/containers-0.7/docs/Data-IntMap-Strict.html
bts on HN
absl::btree_map
From 1 comment
Oh come on. Don't be too harsh. This is an ordered map. Most of the mentioned ones are unordered maps. They might be fast but they are unordered. The only comparables are…
ww520 on HN
Roaring bitmaps
From 1 comment
This really doesn't seem to be comparing to comparable data structures. For int map specializations like this, the optimized alternatives are things like Judy (which is looking…
jemfinch on HN
absl flat_hash_map / folly F14
From 1 comment
This really doesn't seem to be comparing to comparable data structures. For int map specializations like this, the optimized alternatives are things like Judy (which is looking…
jemfinch on HN