Welcome! Please see the About page for a little more info on how this works.

0 votes
in data.int-map by
retagged by

In clojure.data.int-map contrib library, the INode impelementation Branch stores its children always in an INode[] of length 16, even though often/usually, not all 16 of the children's spots are taken up. For instance, the representation of

(int-map 0 0 1 0) 

Will be represented with a Branch node with an INode[] where the 0-position contains 0->0, the 1-position contains 1->0, and the other 14 spaces in the array are null, see below:

This is a difference to the core hashmap/hashset implementation which uses a (in their case, 32-bit, but the branching factor in int-map is only 16) bitmap to keep track of which positions in the array are present and then at read time you can see how many bits are present (set to 1) in the bitmap, to the right of the index you want to read, and that tells you what the true index in the compressed array is.

It would probably be worth taking a look at if use of bitmaps could positively effect performance and memory use of int-map's here.

Could also try compressing further by combining the bitmap and/or mask and/or prefix and/or offset because these fields are large enough that they are not using all of their bits. mask (long), for instance, is only ever one of 15, 15 << 4, 15 << 8, 15 << 12, etc. offset (int) is only ever 0 ... 60 I think. And prefix (long) similarly is only storing a binary representation of a bitmask between 0...64 in length so in principle could be compressed quite a bit too. Among these I bet there would be a field to store some 16 bits of a bitmask without having to add an other field.

1 Answer

+1 vote
selected by