[m-dev.] Re: sparse bitsets

[Zoltan Somogyi]

On 12-Dec-2006, Simon Taylor <staylr at gmail.com> wrote:
> 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 know.

Part of the problem is our basic approach of allocating a variable for each
function symbol, but that is too deeply emdedded to change.

> 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.

That wouldn't achieve my objective, which is: if you union two sets that don't
overlap, the complexity of the union operation shouldn't depend on the size
of the sets. We get the problem we do because constructing the union may
(and in the training cars example, does) involve copying the list of
bitset_elems in one set, just to append the other set at the end. With an
explicitly hierarchical data structure design, you can avoid that traversal.
With a data structure in which the hierarchical structure is hidden behind
an abstraction barrier and in which the hierarchies of two sets aren't
guaranteed to be aligned anyway, I don't think the traversal can be avoided.

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.

I certainly wasn't thinking of that; that is a second order issue compared
to the quadratic complexity I mentioned in my previous email.

Zoltan.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------