Re: [new-regalloc] What is the status on current sources

[Fergus Henderson <fjh at cs dot mu dot oz dot au>]

On 10-Feb-2001, Michael Matz <matzmich@cs.tu-berlin.de> wrote:
> On Fri, 9 Feb 2001, Daniel Berlin wrote:
> > 
> > This reminds me, I have a compressed bitvectors class i implemened to
> > fix the huge memory usage problem for the interference graph.
> > [.. description of it ...]
> 
> I once (looong ago, as I wrote still DOS demos ;) ) had something similar
> (although in Pascal).

The latest version of the Mercury standard library also has something
similar, although in Mercury ;-)

The source code is available from the Mercury web site
<http://www.cs.mu.oz.au/mercury/> if you're interested.
But I enclose below some of the documentation.
This representation for sparse bit vectors is different from the one
that Daniel described, and I wonder how the two compare.

% File: sparse_bitset.m.
...
% This module provides an ADT for storing sets of integers.
% If the integers stored are closely grouped, a sparse_bitset
% is much more compact than the representation provided by set.m,
% and the operations will be much faster.
%
%
% Efficiency notes:
%
% A sparse bitset is represented as a sorted list of pairs of integers.
% For a pair `Offset - Bits', `Offset' is a multiple of `int__bits_per_int'.
% The bits of `Bits' describe which of the elements of the range
% `Offset' .. `Offset + bits_per_int - 1' are in the set.
% Pairs with the same value of `Offset' are merged.
% Pairs for which `Bits' is zero are removed.
%
% The values of `Offset' in the list need not be contiguous multiples
% of `bits_per_int', hence the name _sparse_ bitset.
%
% A sparse_bitset is suitable for storing sets of integers which
% can be represented using only a few `Offset - Bits' pairs.
% In the worst case, where the integers stored are not closely
% grouped, a sparse_bitset will take more memory than an
% ordinary set, but the operations should not be too much slower.

The "ordinary sets" refered to here are represented as sorted lists
with no duplicates.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.