Prototype Roaring Bitmap Usage as SDR impls and later Matrix ops

[cogmission]

This is just an issue to track the progress of prototyping the use of Roaring Bitmaps in place of int arrays as the major payload container within htm.java.

The hope after talking with Daniel Lemire, is that there will be efficiency gained by not creating large data data structures and moving them around as opposed to the smaller footprint of a compressed bitmap. The expectation is that we can take for granted that there will be an improvement in memory consumption, however we are also anticipating performance gains by manipulating smaller containers as opposed to int arrays.

This issue will be to track the progress of the prototype...

[cogmission]

@lemire Hi Daniel,

I've set up a basic project which will include jmh tests for one of the ml algorithms in our project. This will obligate the conversion of 24 classes (sounds more numerous than the actual work). What I am doing is creating a wrapper called SDR (SparseDistributedRepresentation) which will replace all the places in code where an "int[]" is used. The wrapper will internally contain a Roaring Bitmap.

This work once done will then be run against the use of int[], and maybe I'll do an implementation using boolean[]'s also (as you suggested). What do you think?

...also what I need to know is what the fastest way is to:

1. Create a RrBM (RrBM == RoaringBitmap)
2. Test two RrBMs for equality
3. Convert to from sparse/dense representation
   a.) how to create a RrBM using dense representation? (0,1,1,0,0,0,0,1 --> [1,2,7]) and back again
4. Iterate over the bits

...keeping in mind they will always only be binary. I've consulted the API docs, I just want to make sure if there are any methods for the above that you recommend as the highest performing?

[cogmission]

Here is the SDR wrapper so far: https://gist.github.com/cogmission/e7b06f5ab545a80b19be

Here is how I'm doing dense to sparse, size handling etc... Any recommendations?

[lemire]

Saw the code. Will get back to you.

[cogmission]

Just updated it again... Thanks btw! :-)

[lemire]

Good. Please note that RoaringBitmap.bitmapOf is quite happy with unsorted data. Here is what the spec. says right now:

The provided integers values don't have to be in sorted order, but it may be preferable to sort them from a performance point of view.

[lemire]

+1

[cogmission]

@lemire Good to know. (re: sorting). I think the sorting is necessary within our application (though I'm not sure why it would be since the bits are randomly accessed anyway (i.e. retrieving bit "2000" is just as fast as retrieving bit "0") when converting to an integer array. At least I think it is... Anyway, I will definitely keep that in mind, thanks for reviewing the code!

So I should assume the way I'm going about this is ok?

[lemire]

Yes. Looks ok.