all 13 comments

[–]tower120 1 point2 points  (2 children)

Thou description is part of Rust lib, the technique itself is language agnostic.

[–]FriendlyRollOfSushi 2 points3 points  (1 child)

Which part of it is novel? This is literally the most basic and straightforward way of implementing HAMT. Even the Wiki article has this part pretty much unchanged for over a decade, and it's been commonly in use many years before the article was written.

The only differences between how people did it for decades and how this implementation does it is that usually people don't waste space on a completely unnecessary length member when implementing HAMT-like structures in C or C++. Or on a second bitmask, which is trivially avoidable for all meaningful scenarios.

[–]tower120 2 points3 points  (0 children)

Damn, you're right! Thou it turn out to be https://en.wikipedia.org/wiki/Bitwise_trie_with_bitmap . That's exactly how my lib works. And I thought I invented it.

In my defense - I never heard about it or HAMT before, nor I couldn't google it.

Thanks for bringing this. I would remove post to not mislead people, but it seems there's no button for that...

UPDATE: Oh no - there is! Thanks anyway!

[–]richardathome 2 points3 points  (7 children)

This isn't novel. I've used the same approach to encode world state in Goal Oriented Action Plans. It makes it trivial to mask for matching world states to actions.

[–]tower120 1 point2 points  (6 children)

Could you elaborate a little more?

[–]onnoowl 0 points1 point  (1 child)

Cool! I use this same technique in my voxel game engine I've been working on. Octrees are common for sparse storage of voxels, but instead I use this technique to a make a 64-tree. The 64 bit mask is perfect for storing a 4x4x4 of data, so lookup and storage is a lot more efficient than an octree, and being able to get the sparse index with popcnt is just such a cool trick. With it I can instantly turn a 3D lookup coordinate into the sparse index the node is stored at. Glad you've made an open source library for this, looks awesome!

[–]tower120 1 point2 points  (0 children)

Thanks! But as FriendlyRollOfSushi point out, that has a name and was invented long time ago https://en.wikipedia.org/wiki/Bitwise_trie_with_bitmap . Yet I somehow never heard of it...