[m-rev.] for review: tree_bitset.m

Zoltan Somogyi zs at csse.unimelb.edu.au
Tue Dec 19 16:25:58 AEDT 2006


On 19-Dec-2006, Ralph Becket <rafe at csse.unimelb.edu.au> wrote:
> > +:- func list_to_set(list(T)) = tree_bitset(T) <= enum(T).
> > +:- pred list_to_set(list(T)::in, tree_bitset(T)::out) is det <= enum(T).
> 
> I assume you're only providing `(in, ..., in, out) is det' pred versions
> for backwards compatibility?

Yes. I'll see if anything breaks when I delete it and similar redundant
predicates.

> I'd like to see MR_GC_NEW_ATOMIC added to runtime/mercury_memory.h for
> this.  But that's another change.

Actually, you can now get the same effect with --use-atomic-alloc, but my
benchmarking showed that this lead to a slowdown. When I investigated,
I found problems with LLDS optimizations not being run due to the presence
of C other code, specifically, the access to ML_BITS_PER_INT. Hence the
other diff for optimization expressions involving that constant. More
experimentation required installing a compiler with that optimization,
which just got done.

I will get rid of the use of MR_GC_NEW_ATOMIC here as soon as I can figure
out how to do so without causing a slowdown.

> > +to_sorted_list(Set) = foldr(func(Elem, Acc0) = [Elem | Acc0], Set, []).
> 
> to_sorted_list(Set) = foldr(list.cons, Set, []).

Done.

> > +filter(P, S) = S ^ to_sorted_list ^ list.filter(P) ^ sorted_list_to_set.
> 
> The last time I tried using ^ as "postfix" function application there
> were squawks from the gallery.  Personally I prefer to see ^ as
> syntactic sugar and I'm happy with this style, but strong opinions were
> voiced that ^ should be reserved specifically for field access.

I agree; that code is not mine but Simon's, copied from sparse_bitset.
I will change it.

> > +make_singleton_set(A) = insert(init, A).
> 
> It's a good idea to module qualify that init or we might hit
> ambiguity problems with intermodule optimization.

No, we won't; .opt files contain the module qualified versions of clauses.

> You can find the least set bit of a 2s complement number Bits0 with
> (Bits0 /\ -Bits0).  You can convert that to a BitNum with a simpler
> loop.  I appreciate that your algorithm is O(log n), but I suspect
> the constant factors are larger.

I copied that code, and much else, from sparse_bitset without change.
I'll leave it as it is, for now.

> > +list_to_set(List) = Set :-
> > +    list.sort(List, SortedList),
> > +    Set = sorted_list_to_set(SortedList).
> 
> list_to_set(List) = sorted_list_to_set(list.sort(List)).

Done.

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



More information about the reviews mailing list