Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Integer Map Data Structure

github.com

Post reply on HN
Print view View original

21–28 of 28 posts

Re: Show HN: Integer Map Data Structure

#21

Post by zogrodea »

kccqzy wrote: post #8
bts wrote: post #2

FWIW there is prior art here. e.g. see IntMap in Haskell: https://hackage.haskell.org/package/containers-0.7/docs/Data...

It hardly seems comparable given that this Haskell data structure must necessarily be persistent.

I'm not sure what you mean by "necessarily must be persistent" here, but (under my interpretation which means only persistent implementations of this data structure are possible) that's not true.

The IntMap paper by Chris Okasaki acknowledges that the data structure is not a new one (it's a PATRICIA tree), but one that was around 30 years old at the date his paper was published and deserved to be better known. The functional/persistent implementation is what's novel about Okasaki's paper.

Edit: The data structure this submission is about looks like great work! Excited to see it and will probably attempt my own ports of it to other languages.

Re: Show HN: Integer Map Data Structure

#22

Post by ww520 »

mrazomor wrote: post #18
ww520 wrote: post #16

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 good compromise between node size and tree depth. The node slot packing is amazing. Actually if you relax the restriction on 64-byte node to 128-byte node, you can get 64 bits per slot and will get a much higher limit for the item count. New…

If I understood it correctly, it's not much different from what `absl::flat_hash_map` does. Look for "Metadata information"/control bits at https://abseil.io/about/design/swisstables

I believe it's quite different. If I'm not mistaken, flat_hash_map is a typical hash table, with a hash function to map the key to a bucket. Its novel part is using the 7 lower bits of the hashed value as a bit mask against the control bits to check the presence of the item. It's like a mini-Bloom-Filter where a false query means the item definitely not in the bucket while a positive query means the item might be in the bucket. A subsequent search through the bucket can confirm the existence of the item.

This int map is a trie with an integer based key.

Re: Show HN: Integer Map Data Structure

#23

Post by ot »

ww520 wrote: post #19
jemfinch wrote: post #17

Earlier quoted context omitted.

I'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 still rule the day in performance the vast majority of the time, and their lower constant factors very frequently outperform more specialized data structures. They're absolutely worth benchmarking against if the goal is actual uptake in the a…

That just means you never have the need for implementing a querying or search functionality. Range query and search are used everywhere and need ordered maps. I'm not saying we should rush to adopt it right the way, but at least don't dismiss it hastily. It has some novel ideas to advance the art.

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 (which is really not a lot). Did I miss something?

Re: Show HN: Integer Map Data Structure

#24

Post by JonChesterfield »

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 copying

2/ union/intersection style operations can be sublinear. None of the batch operations are implemented

Re: Show HN: Integer Map Data Structure

#25

Post by xaellison »

ursusmaritimus wrote: post #11

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.

This limit comes from using int32s. Does anyone have an idea why on modern machines it isn't making use of int64s?

Re: Show HN: Integer Map Data Structure

#26

Post by ww520 »

ot wrote: post #23
ww520 wrote: post #19

Earlier quoted context omitted.

That just means you never have the need for implementing a querying or search functionality. Range query and search are used everywhere and need ordered maps. I'm not saying we should rush to adopt it right the way, but at least don't dismiss it hastily. It has some novel ideas to advance the art.

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 (which is really not a lot). Did I miss something?

Subnet mask style prefix construction is pretty novel.

Re: Show HN: Integer Map Data Structure

#27

Post by kccqzy »

zogrodea wrote: post #21
kccqzy wrote: post #8

Earlier quoted context omitted.

It hardly seems comparable given that this Haskell data structure must necessarily be persistent.

I'm not sure what you mean by "necessarily must be persistent" here, but (under my interpretation which means only persistent implementations of this data structure are possible) that's not true. The IntMap paper by Chris Okasaki acknowledges that the data structure is not a new one (it's a PATRICIA tree), but one that was around 30 years old at the date his paper was published and deserved to be better known. The fu…

Sorry I wasn't clear. What I meant is that an idiomatic Haskell data structure needs to be persistent: an insertion needs to produce a new version of the data structure with the inserted element while keeping the original. So almost all Haskell data structures need to satisfy this requirement otherwise using it is a lot of PITA, even though the ST monad makes mutations fairly easy. However the original submission is not persistent, and so they aren't comparable.

Re: Show HN: Integer Map Data Structure

#28

Post by zogrodea »

kccqzy wrote: post #27
zogrodea wrote: post #21

Earlier quoted context omitted.

I'm not sure what you mean by "necessarily must be persistent" here, but (under my interpretation which means only persistent implementations of this data structure are possible) that's not true. The IntMap paper by Chris Okasaki acknowledges that the data structure is not a new one (it's a PATRICIA tree), but one that was around 30 years old at the date his paper was published and deserved to be better known. The fu…

Sorry I wasn't clear. What I meant is that an idiomatic Haskell data structure needs to be persistent: an insertion needs to produce a new version of the data structure with the inserted element while keeping the original. So almost all Haskell data structures need to satisfy this requirement otherwise using it is a lot of PITA, even though the ST monad makes mutations fairly easy. However the original submission is…

Oh, that makes sense and I agree. Appreciate the clarification!
Post reply on HN