Qp tries: smaller and faster than crit-bit tries(fanf.livejournal.com)

fanf.livejournal.com

Qp tries: smaller and faster than crit-bit tries

http://fanf.livejournal.com/137283.html

3 comments

"You can use popcount() to implement a sparse array of length N containing M < N members using bitmap of length N and a packed vector of M elements. A member i is present in the array if bit i is set, so M == popcount(bitmap). The index of member i in the packed vector is the popcount of the bits preceding i.

"

FWIW: These kind of sparse array tricks have been around forever:

https://gcc.gnu.org/ml/gcc-patches/2007-03/msg01308.html

The original idea for that patch didn't come from philip bagwell's paper, but from some code from the late 80's i saw at IBM.

Thus, i suspect this kind of thing has been around forever

fanf211 anni fa

Yes, but surprisingly hard to find a good citation! Best I can do is note where I found out about it, or at least what inspired this project...

DannyBee11 anni fa

I 100% agree with this part :) I'm glad you noted it explicitly somewhere, as this trick should be better known.

Note that while sparse, it is not as memory efficient as, for example, linked list bitmaps.

This is because the mask is going to contain O(universe/wordsize) bits, and depending on the size of the universe, the mask may be larger than the actual data stored!

yjh050211 anni fa

more general, adaptive version: https://github.com/armon/libart

fanf211 anni fa

Yes, that's pretty elaborate :-)

There's space in qp tries for jumbo nodes - they currently use flag values of 0, 1, 2, so 3 is available for byte-at-a-time branches.

nullc11 anni fa

Careful, you're going to reinvent libjudy. :P

drudru1111 anni fa

just skimmed the beginning, saw a mention of the use of popcount. That looks interesting. It is an article like this that I really enjoy on HN. Thanks for writing it.