[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