[m-dev.] For review: additions to array.m

[Ralph Becket]

>From Fergus Henderson on 01/02/2001 06:16:57
> On 31-Jan-2001, Ralph Becket <rbeck at microsoft.com> wrote:
> > Array based quicksorting is substantially less costly in
> > terms of space(O(n) vs O(n log n)) and informal testing 
> > shows it to be about 10 times faster in practice.
> 
> That sounds very good.

It also turns out to be wrong :(

> How do they compare when sorting already-sorted lists?

Tests carried out on larger lists (10000 and 100000 members)
showed quicksort to be 3-4 times more costly than mergesort
for ordered lists (ascending and descending) and 3-5 times
better on randomized lists (as expected).  [See attached
file TestResults-NoRandomization].

So I altered array__sort so that it first randomly permuted
the array before quicksorting it.  This meant that the
median-of-three pivot selection could be done away with.
The results after this change were much more encouraging, 
showing randomized quicksort to be pretty much consistently
2-5 times better on all inputs.  [See attached file
TestResults-WithRandomization].

As a side effect, we also get a potentially useful
array__permutation predicate.

> It would be nice to also provide versions which are
> parameterized on an ordering predicate, like list__sort/3.

Okay, I'll add those.

> > +:- pragma type_spec(array__sort/1, T = int).
> > +:- pragma type_spec(array__sort/1, T = string).
> 
> Those are implementation details, really;
> I don't think they should go in the interface.

Fair enough - done.
> 
> Why did you choose to specialize those types?
> You should document the reason.

Eariler testing showed that type specialization netted about a
30% improvement and it seemed to me that ints and strings are
the sorts of things that one wants to sort more often than any
other.

It also makes benchmark results look better when compared against
other languages :)

> Hmm, it might be nice to also provide
> 
> 	:- mode array__foldl(func(in, di) = uo is det, in, di) = uo is det.

Done.  I'll post a complete diff again once I've added in the
parameterized sort functions.

--
Ralph Becket      |      MSR Cambridge      |      rbeck at microsoft.com 



begin 600 TestResults-NoRandomization
M"G-T87)T:6YG('-O<G1I;F<@8F5N8VAM87)K(&]N(#$P(&ET96US"F%V97)A
M9VEN9R!O=F5R(#$P(&ET97)A=&EO;G,*"FQI<W1?7W-O<G0O,2!O;B!A<V-E
M;F1I;F<@<V5Q=65N8V4Z(#!M<PIL:7-T7U]S;W)T+S$@;VX at 9&5S8V5N9&EN
M9R!S97%U96YC93H@,&US"FQI<W1?7W-O<G0O,2!O;B!R86YD;VUI>F5D('-E
M<75E;F-E.B`P;7,*87)R87E?7W-O<G0O,2!O;B!A<V-E;F1I;F<@<V5Q=65N
M8V4Z(#!M<PIL:7-T+V%R<F%Y('1I;64@/2`@(&YA;B4*87)R87E?7W-O<G0O
M,2!O;B!D97-C96YD:6YG('-E<75E;F-E.B`P;7,*;&ES="]A<G)A>2!T:6UE
M(#T@("!N86XE"F%R<F%Y7U]S;W)T+S$@;VX@<F%N9&]M:7IE9"!S97%U96YC
M93H@,&US"FQI<W0O87)R87D@=&EM92`]("`@;F%N)0H*<W1A<G1I;F<@<V]R
M=&EN9R!B96YC:&UA<FL@;VX@,3`P(&ET96US"F%V97)A9VEN9R!O=F5R(#$P
M(&ET97)A=&EO;G,*"FQI<W1?7W-O<G0O,2!O;B!A<V-E;F1I;F<@<V5Q=65N
M8V4Z(#!M<PIL:7-T7U]S;W)T+S$@;VX at 9&5S8V5N9&EN9R!S97%U96YC93H@
M,6US"FQI<W1?7W-O<G0O,2!O;B!R86YD;VUI>F5D('-E<75E;F-E.B`P;7,*
M87)R87E?7W-O<G0O,2!O;B!A<V-E;F1I;F<@<V5Q=65N8V4Z(#!M<PIL:7-T
M+V%R<F%Y('1I;64@/2`@(&YA;B4*87)R87E?7W-O<G0O,2!O;B!D97-C96YD
M:6YG('-E<75E;F-E.B`Q;7,*;&ES="]A<G)A>2!T:6UE(#T@,3`P+C`P)0IA
M<G)A>5]?<V]R="\Q(&]N(')A;F1O;6EZ960@<V5Q=65N8V4Z(#!M<PIL:7-T
M+V%R<F%Y('1I;64@/2`@(&YA;B4*"G-T87)T:6YG('-O<G1I;F<@8F5N8VAM
M87)K(&]N(#$P,#`@:71E;7,*879E<F%G:6YG(&]V97(@,3`@:71E<F%T:6]N
M<PH*;&ES=%]?<V]R="\Q(&]N(&%S8V5N9&EN9R!S97%U96YC93H@,VUS"FQI
M<W1?7W-O<G0O,2!O;B!D97-C96YD:6YG('-E<75E;F-E.B`S;7,*;&ES=%]?
M<V]R="\Q(&]N(')A;F1O;6EZ960@<V5Q=65N8V4Z(#EM<PIA<G)A>5]?<V]R
M="\Q(&]N(&%S8V5N9&EN9R!S97%U96YC93H at -6US"FQI<W0O87)R87D@=&EM
M92`](#8P+C`P)0IA<G)A>5]?<V]R="\Q(&]N(&1E<V-E;F1I;F<@<V5Q=65N
M8V4Z(#5M<PIL:7-T+V%R<F%Y('1I;64@/2`V,"XP,"4*87)R87E?7W-O<G0O
M,2!O;B!R86YD;VUI>F5D('-E<75E;F-E.B`R;7,*;&ES="]A<G)A>2!T:6UE
M(#T at -#4P+C`P)0H*<W1A<G1I;F<@<V]R=&EN9R!B96YC:&UA<FL@;VX@,3`P
M,#`@:71E;7,*879E<F%G:6YG(&]V97(@,3`@:71E<F%T:6]N<PH*;&ES=%]?
M<V]R="\Q(&]N(&%S8V5N9&EN9R!S97%U96YC93H at -C%M<PIL:7-T7U]S;W)T
M+S$@;VX at 9&5S8V5N9&EN9R!S97%U96YC93H at -C=M<PIL:7-T7U]S;W)T+S$@
M;VX@<F%N9&]M:7IE9"!S97%U96YC93H at .31M<PIA<G)A>5]?<V]R="\Q(&]N
M(&%S8V5N9&EN9R!S97%U96YC93H@,30X;7,*;&ES="]A<G)A>2!T:6UE(#T@
M-#$N,C(E"F%R<F%Y7U]S;W)T+S$@;VX at 9&5S8V5N9&EN9R!S97%U96YC93H@
M,3$P;7,*;&ES="]A<G)A>2!T:6UE(#T at -C`N.3$E"F%R<F%Y7U]S;W)T+S$@
M;VX@<F%N9&]M:7IE9"!S97%U96YC93H@,S=M<PIL:7-T+V%R<F%Y('1I;64@
M/2`R-30N,#4E"@IS=&%R=&EN9R!S;W)T:6YG(&)E;F-H;6%R:R!O;B`Q,#`P
M,#`@:71E;7,*879E<F%G:6YG(&]V97(@,3`@:71E<F%T:6]N<PH*;&ES=%]?
M<V]R="\Q(&]N(&%S8V5N9&EN9R!S97%U96YC93H@,3`W.6US"FQI<W1?7W-O
M<G0O,2!O;B!D97-C96YD:6YG('-E<75E;F-E.B`Q,3`T;7,*;&ES=%]?<V]R
M="\Q(&]N(')A;F1O;6EZ960@<V5Q=65N8V4Z(#$V.3=M<PIA<G)A>5]?<V]R
M="\Q(&]N(&%S8V5N9&EN9R!S97%U96YC93H at -#0U,6US"FQI<W0O87)R87D@
M=&EM92`](#(T+C(T)0IA<G)A>5]?<V]R="\Q(&]N(&1E<V-E;F1I;F<@<V5Q
M=65N8V4Z(#,R,#AM<PIL:7-T+V%R<F%Y('1I;64@/2`S-"XT,24*87)R87E?
M7W-O<G0O,2!O;B!R86YD;VUI>F5D('-E<75E;F-E.B`U,31M<PIL:7-T+V%R
3<F%Y('1I;64@/2`S,S`N,38E"@==
`
end

begin 600 TestResults-WithRandomization
M"G-T87)T:6YG('-O<G1I;F<@8F5N8VAM87)K(&]N(#$P(&ET96US"F%V97)A
M9VEN9R!O=F5R(#$P(&ET97)A=&EO;G,*"FQI<W1?7W-O<G0O,2!O;B!A<V-E
M;F1I;F<@<V5Q=65N8V4Z(#!M<PIL:7-T7U]S;W)T+S$@;VX at 9&5S8V5N9&EN
M9R!S97%U96YC93H@,&US"FQI<W1?7W-O<G0O,2!O;B!R86YD;VUI>F5D('-E
M<75E;F-E.B`P;7,*87)R87E?7W-O<G0O,2!O;B!A<V-E;F1I;F<@<V5Q=65N
M8V4Z(#!M<PIL:7-T+V%R<F%Y('1I;64@/2`@(&YA;B4*87)R87E?7W-O<G0O
M,2!O;B!D97-C96YD:6YG('-E<75E;F-E.B`P;7,*;&ES="]A<G)A>2!T:6UE
M(#T@("!N86XE"F%R<F%Y7U]S;W)T+S$@;VX@<F%N9&]M:7IE9"!S97%U96YC
M93H@,&US"FQI<W0O87)R87D@=&EM92`]("`@;F%N)0H*<W1A<G1I;F<@<V]R
M=&EN9R!B96YC:&UA<FL@;VX@,3`P(&ET96US"F%V97)A9VEN9R!O=F5R(#$P
M(&ET97)A=&EO;G,*"FQI<W1?7W-O<G0O,2!O;B!A<V-E;F1I;F<@<V5Q=65N
M8V4Z(#!M<PIL:7-T7U]S;W)T+S$@;VX at 9&5S8V5N9&EN9R!S97%U96YC93H@
M,&US"FQI<W1?7W-O<G0O,2!O;B!R86YD;VUI>F5D('-E<75E;F-E.B`Q;7,*
M87)R87E?7W-O<G0O,2!O;B!A<V-E;F1I;F<@<V5Q=65N8V4Z(#!M<PIL:7-T
M+V%R<F%Y('1I;64@/2`@(&YA;B4*87)R87E?7W-O<G0O,2!O;B!D97-C96YD
M:6YG('-E<75E;F-E.B`P;7,*;&ES="]A<G)A>2!T:6UE(#T@("!N86XE"F%R
M<F%Y7U]S;W)T+S$@;VX@<F%N9&]M:7IE9"!S97%U96YC93H@,&US"FQI<W0O
M87)R87D@=&EM92`]("`@:6YF)0H*<W1A<G1I;F<@<V]R=&EN9R!B96YC:&UA
M<FL@;VX@,3`P,"!I=&5M<PIA=F5R86=I;F<@;W9E<B`Q,"!I=&5R871I;VYS
M"@IL:7-T7U]S;W)T+S$@;VX at 87-C96YD:6YG('-E<75E;F-E.B`T;7,*;&ES
M=%]?<V]R="\Q(&]N(&1E<V-E;F1I;F<@<V5Q=65N8V4Z(#-M<PIL:7-T7U]S
M;W)T+S$@;VX@<F%N9&]M:7IE9"!S97%U96YC93H at .6US"F%R<F%Y7U]S;W)T
M+S$@;VX at 87-C96YD:6YG('-E<75E;F-E.B`R;7,*;&ES="]A<G)A>2!T:6UE
M(#T@,C`P+C`P)0IA<G)A>5]?<V]R="\Q(&]N(&1E<V-E;F1I;F<@<V5Q=65N
M8V4Z(#)M<PIL:7-T+V%R<F%Y('1I;64@/2`Q-3`N,#`E"F%R<F%Y7U]S;W)T
M+S$@;VX@<F%N9&]M:7IE9"!S97%U96YC93H@,VUS"FQI<W0O87)R87D@=&EM
M92`](#,P,"XP,"4*"G-T87)T:6YG('-O<G1I;F<@8F5N8VAM87)K(&]N(#$P
M,#`P(&ET96US"F%V97)A9VEN9R!O=F5R(#$P(&ET97)A=&EO;G,*"FQI<W1?
M7W-O<G0O,2!O;B!A<V-E;F1I;F<@<V5Q=65N8V4Z(#8R;7,*;&ES=%]?<V]R
M="\Q(&]N(&1E<V-E;F1I;F<@<V5Q=65N8V4Z(#8X;7,*;&ES=%]?<V]R="\Q
M(&]N(')A;F1O;6EZ960@<V5Q=65N8V4Z(#DV;7,*87)R87E?7W-O<G0O,2!O
M;B!A<V-E;F1I;F<@<V5Q=65N8V4Z(#,P;7,*;&ES="]A<G)A>2!T:6UE(#T@
M,C`V+C8W)0IA<G)A>5]?<V]R="\Q(&]N(&1E<V-E;F1I;F<@<V5Q=65N8V4Z
M(#(Y;7,*;&ES="]A<G)A>2!T:6UE(#T@,C,T+C0X)0IA<G)A>5]?<V]R="\Q
M(&]N(')A;F1O;6EZ960@<V5Q=65N8V4Z(#,P;7,*;&ES="]A<G)A>2!T:6UE
M(#T@,S(P+C`P)0H*<W1A<G1I;F<@<V]R=&EN9R!B96YC:&UA<FL@;VX@,3`P
M,#`P(&ET96US"F%V97)A9VEN9R!O=F5R(#$P(&ET97)A=&EO;G,*"FQI<W1?
M7W-O<G0O,2!O;B!A<V-E;F1I;F<@<V5Q=65N8V4Z(#$Q,#)M<PIL:7-T7U]S
M;W)T+S$@;VX at 9&5S8V5N9&EN9R!S97%U96YC93H@,3$S-VUS"FQI<W1?7W-O
M<G0O,2!O;B!R86YD;VUI>F5D('-E<75E;F-E.B`Q-S4T;7,*87)R87E?7W-O
M<G0O,2!O;B!A<V-E;F1I;F<@<V5Q=65N8V4Z(#0Q,VUS"FQI<W0O87)R87D@
M=&EM92`](#(V-BXX,R4*87)R87E?7W-O<G0O,2!O;B!D97-C96YD:6YG('-E
M<75E;F-E.B`S.39M<PIL:7-T+V%R<F%Y('1I;64@/2`R.#<N,3(E"F%R<F%Y
M7U]S;W)T+S$@;VX@<F%N9&]M:7IE9"!S97%U96YC93H@,S0X;7,*;&ES="]A
4<G)A>2!T:6UE(#T at -3`T+C`R)0H=
`
end
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------