Re: [boost] [interval container (itl)] A pretty large bitset

Subject: Re: [boost] [interval container (itl)] A pretty large bitset
From: Joachim Faulhaber (afojgo_at_[hidden])
Date: 2009-11-03 05:08:06

2009/11/3 Scott McMurray <me22.ca+boost_at_[hidden]>:
> 2009/11/2 Joachim Faulhaber <afojgo_at_[hidden]>:
>>
>> As a new use case of interval containers I have developed
>> a *large_bitset* class template on top of itl::interval_map
>> that is able to combine interval compression *and* bitset
>> compression. It is, for instance, capable of representing
>> the bitset mentioned above
>>
>> '01010101...010'
>>  a            b
>>
>>  a: bit 0
>>  b: bit 2^64-1
>>
>> containing 2^63 bits (or elements) with just *one* internal
>> interval associated to only *one* value of 64bit length ;)
>>
>> Curious??
>>
>
> Quite.

The compact storage of repeated bit patterns is only the lead story
to baffle the reader a bit ;)

In the end I do not think that this is the most important property of
large_bitset. In fact it is just a byproduct of the basic idea to
combine interval and bitset compression via an itl::interval_map of
bitsets.

> How does it handle a repeat of 128 1s then 128 0s then 128 1s etc?
> (Or any repeating signal with a period longer than one storage unit?)

So a large_bitset<uint64_t, mini::bits<uint64_t> > would handle
them this way:

[0,2)->"111...1"  (all 64 bits set)
[2,4)->"111...1"
...
[k,k+2)->"111...1"

which is obviously much less compact than the initial example
but still a good compression.

But, to be honest, the "periodic bit compression magic" has
more limitations than that. For instance it does not manage
to represent a bit pattern
"100100100...100"
with a single node like this can be done for patterns with
an even period length <= 64 (or word_length).

As I said, it's just a nice byproduct of the design. More
important IMO is the combination of interval and bit
compression as such and also the fact that large_bitset
can be implemented with *very little* code

http://www.herold-faulhaber.de/boost_itl/doc/libs/itl/doc/html/boost_itl/projects.html

on top of itl::interval_map, which demonstrates the potential
of interval containers.

Cheers
Joachim