[m-dev.] Re: sparse bitsets

[Simon Taylor]

On 11-Dec-2006, Zoltan Somogyi <zs at csse.unimelb.edu.au> wrote:
> I found another quadratic algorithm in the compiler that shows up when
> compiling Doug Auclair's training cars example, which has a predicate
> contaning more than a hundred thousand variables.

Eek.  I definitely wasn't thinking of sets that size when I wrote
the sparse_bitset module.

> I think the solution is to change the representation used in sparse_bitset.m
> to be hierarchical. Besides leaf nodes just like the current bitset_elem,
> that contain information about up to bits_per_int adjacent potential elements,
> we should also have nonleaf nodes that represent information about larger and
> larger groups of potential elements. For example, we could have a level N
> nonleaf nodes representing information about bits_per_int * 2^N potential
> elements (naturally aligned, as bitset_elems are). These nodes wouldn't contain
> that information directly; they would point to an ordered list of lower level
> nodes, with bitset_elems at the bottom of the pile.

It may be almost as efficient, and probably simpler, to use a map(int, int)
rather than an assoc_list(int, int) as we do now.  The current implementation
is careful to hide potential pointer-like integers from the GC, so it depends
on how good Boehm GC is at dealing with these.  Last time I tested, allocating
bitset_elems using GC_malloc_atomic was slightly slower.  It may not matter
in practice.

Simon.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at csse.unimelb.edu.au
Administrative Queries: owner-mercury-developers at csse.unimelb.edu.au
Subscriptions:          mercury-developers-request at csse.unimelb.edu.au
--------------------------------------------------------------------------