Faster IntSet by using BitMaps in the lower branches

[Milan Straka]

Hi Joachim,

> for one of my applications, I am generating huge IntSets (and IntMaps),
> and I am regularly hitting the memory constraints of my machine. Hence I
> am looking for a better implementation of IntSets with smaller memory
> foot print, at least in the case of dense sets, e.g. those where it is
> likely that a few values are equal in all but the lower 5 or 6 bits.
> 
> So instead of a simple tree, I re-implemented IntSet as a tree where the
> nodes contain bit maps of one machine word (32 or 64 entries):
> 
> Instead of
> Data.IntSet> putStr $ showTree $ fromList [-3, -1,1,2,42,100]
> *
> +--*
> |  +--*
> |  |  +--*
> |  |  |  +-- 1
> |  |  |  +-- 2
> |  |  +-- 42
> |  +-- 100
> +--*
>    +-- -3
>    +-- -1
> 
> we have
> 
> Data.DenesIntSet> putStr $ showTree $ fromList [-3, -1,1,2,42,100]
> *
> +--*
> |  +-- 0 0000000000000000000001000000000000000000000000000000000000000110
> |  +-- 64 0000000000000000000000000001000000000000000000000000000000000000
> +-- -64 1010000000000000000000000000000000000000000000000000000000000000
> 
> 
> The results are promising. I have attached a "progress" graph, comparing
> the performance of IntMap with DenseIntMap. As you can see, performance
> is better for most common operations, greatly better for intersection
> and union, and comparable for fold/filter/findMax/findMin.
> 
> And here is the memory usage of an IntSet with one million members and
> varying distance between the entries:
> 
> $ cat membench.hs
> import qualified Data.IntSet as S
> import qualified Data.DenseIntSet as DS
> import System.Environment
> 
> main = do
>     [what, sizeS, stepS] <- getArgs
>     let list = [0,read stepS .. read stepS * read sizeS]
>     if what `elem` ["r","R"] then  S.size ( S.fromList list) `seq` return ()
>                              else DS.size (DS.fromList list) `seq` return ()
> 
> For IntSet, the memory consumption does not change notably with the step
> size:
> 
> $ ./membench +RTS -t -RTS r 1000000 1 2>&1 | perl -n -e '/, (\d+M) in use/ && print "$1\n"'
> 80M
> $ ./membench +RTS -t -RTS r 1000000 2 2>&1 | perl -n -e '/, (\d+M) in use/ && print "$1\n"'
> 80M
> $ ./membench +RTS -t -RTS r 1000000 10 2>&1 | perl -n -e '/, (\d+M) in use/ && print "$1\n"'
> 79M
> $ ./membench +RTS -t -RTS r 1000000 100 2>&1 | perl -n -e '/, (\d+M) in use/ && print "$1\n"'
> 79M
> 
> But for DenseIntMap, we see that dense maps are, as desired, much more compact:
> 
> $ ./membench +RTS -t -RTS d 1000000 1 2>&1 | perl -n -e '/, (\d+M) in use/ && print "$1\n"'
> 2M
> $ ./membench +RTS -t -RTS d 1000000 2 2>&1 | perl -n -e '/, (\d+M) in use/ && print "$1\n"'
> 3M
> $ ./membench +RTS -t -RTS d 1000000 10 2>&1 | perl -n -e '/, (\d+M) in use/ && print "$1\n"'
> 18M
> $ ./membench +RTS -t -RTS d 1000000 100 2>&1 | perl -n -e '/, (\d+M) in use/ && print "$1\n"'
> 77M
> 
> 
> I have put the code here:
> https://github.com/nomeata/containers/blob/denseintmap/Data/DenseIntSet.hs
> 
> It certainly needs a bit more cleanup, e.g. documenting, commenting and
> maybe improving the test coverage (as, after all, I added quite a bit of
> logic that can now go wrong). And I did not test the code on a 32 bit
> system yet.
> 
> But I’d like to hear from you whether this could in principle go into
> the containers library (as IntSet, not as DenseIntSet) or if there is a
> reason not to use this implementation.

Great job! Yes, this can definitely go into containers as IntSet. It is
a neat idea, which vastly decreases memory consumption for dense sets.
In case the set is dense many operations are also faster as the tree is
of lower depth. The operations which are searching for nonexact value
(find minimum, find neighbor of an element, also list elements in
ascending order) can go slower, as visible on your findMax.

Could you please also generate comparison of and IntSet and DenseIntSet,
when the set is sparse (eg [1, 65 .. N])? I would like to see the time
complexities then. Also please include toList. If the results are fine,
I currently see no reason why not to push the code in.

When you are happy with the code, could you please send a pull request
on the github containers repo? I (and/or Johan, if he wants) will look
at the code. Of course, having good comments and test coverage would be
a great help. I am quite busy till Sun 25, but have some time after that.

Cheers,
Milan