[m-dev.] for review: use bitsets in quantification

[Fergus Henderson]

On 08-Nov-2000, Zoltan Somogyi <zs at cs.mu.OZ.AU> wrote:
> On 08-Nov-2000, Fergus Henderson <fjh at cs.mu.OZ.AU> wrote:
> > It would probably be more efficient to check if the bit is already set,
> > and if so return Set = Set0, avoiding two memory allocations.
> 
> This will actually be a pessimization if the program never calls this code
> with data that cases the condition to be true. A significant number of
> algorithms never insert a given element into a set twice.

That's true.  But the cost of the test is basically just one conditional
branch, whereas the cost of two memory allocations is likely to be much
higher.  Even with --inline-alloc, we don't optimize MR_incr_hp_atomic(),
so you pay three loads, three stores, and one conditional branch for the
inlined allocation, plus a function call/return, three loads, and two conditional
branches for the non-lined allocation, giving a total of six loads,
six stores, one function call/return, and three conditional branches.
WIthout --inline-alloc you'd get another function call/return and
another conditional branch.  And that's not to mention the cost of
garbage collecting the two cells that are no longer referenced (or the
memory usage increase and locality decrease if they are in fact still
referenced).  So this should be a win even if only a small fraction of
insertions insert the same element into a set.

For a general-purpose library, I think it is usually the right
trade-off to pay a small cost to avoid a potentially large but
potentially rare cost.

> One (ugly) solution is to have two versions of this predicate, one with the
> if-then-else and one without.

That would be OK, but I'm not sure if it's worth an additional version
of the predicate just to save one conditional branch in a predicate that
already does at least three other conditional branches.

-- 
Fergus Henderson <fjh at 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.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------