Show HN: Integer Map Data Structure

#1

Post by billziss » Thu, Jan 25, 2024, 12:28 AM UTC

This project presents a new data structure for storing ordered integer maps. The proposed data structure is a compressive, cache-friendly, radix tree that has performance comparable to an unordered map (`std::unordered_map`) and is an order of magnitude faster than an ordered map (`std::map`).

Show HN: Integer Map Data Structure
github.com

Re: Show HN: Integer Map Data Structure

#2

Post by bts » Thu, Jan 25, 2024, 12:55 AM UTC

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

Re: Show HN: Integer Map Data Structure

#3

Post by winrid » Thu, Jan 25, 2024, 2:22 AM UTC

Neat, thank you! I'd love to see how it compares to the libgdx IntMap[0].

[0] https://github.com/libgdx/libgdx/blob/master/gdx/src/com/bad...

Re: Show HN: Integer Map Data Structure

#4

Post by NWoodsman » Thu, Jan 25, 2024, 2:26 AM UTC

Also will throw in to the mix, in C#:

https://julesjacobs.com/2014/11/11/immutable-vectors-csharp....

His implementation uses buffers of capacity 32, generics, and bit shifting to do lookups.

Re: Show HN: Integer Map Data Structure

#5

Post by repsilat » Thu, Jan 25, 2024, 2:27 AM UTC

winrid wrote: post #3

Neat, thank you! I'd love to see how it compares to the libgdx IntMap[0]. [0] https://github.com/libgdx/libgdx/blob/master/gdx/src/com/bad...

This is a radix tree (ordered, does more allocations), that is a hash table. Also TFA is C/C++, libgdx looks like Java.

Re: Show HN: Integer Map Data Structure

#6

Post by repsilat » Thu, Jan 25, 2024, 2:32 AM UTC

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 there mention of whether insertions invalidate iterators? Maybe not strictly needed for my use-case but good to know.

Re: Show HN: Integer Map Data Structure

#7

Post by winrid » Thu, Jan 25, 2024, 4:19 AM UTC

repsilat wrote: post #5

winrid wrote: post #3

Neat, thank you! I'd love to see how it compares to the libgdx IntMap[0]. [0] https://github.com/libgdx/libgdx/blob/master/gdx/src/com/bad...

This is a radix tree (ordered, does more allocations), that is a hash table. Also TFA is C/C++, libgdx looks like Java.

yeah, just thought it'd be fun to compare :) ordered is a big difference.

Re: Show HN: Integer Map Data Structure

#8

Post by kccqzy » Thu, Jan 25, 2024, 4:21 AM UTC

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.

Re: Show HN: Integer Map Data Structure

#9

Post by notfed » Thu, Jan 25, 2024, 6:00 AM UTC

It'd be nice to include djb's crit-bit tree implementation (linked to from the intro) in the benchmarks ("Performance Test" section).

Re: Show HN: Integer Map Data Structure

#10

Post by jemfinch » Thu, Jan 25, 2024, 6:08 AM UTC

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 quite aged these days) or roaring bitmaps, not to mention that any C++ developer using "ordinary" maps will be using absl's SwissTable (flat_hash_map) or folly's F14 (F14FastMap) or perhaps absl::btree_map if order is important. Comparisons to std::map and std::unordered_map are simply too naive to make the case for this data structure.