Feedback request: priority queues in containers

[Jim Apple]

> I encourage you to test it
> out for yourself, but I think you'll find similar results.  =D

I don't spend a lot of time thinking about non-asymptotic
optimizations, so I may have made an error or ten, but I found vastly
different results for heap sort.

I tested heap sorting mostly following the description of your example:
1. Generate 25,000 random Ints
2. System.Mem.performGC
3. Start timer
4. Insert Ints into PQ
5. Remove one at a time until there are none left
6. Print the last one removed
7. Stop timer

I compiled with GHC 6.10.1 and -O2.

I tested four implementations of binomial PQs:

A: Brodal-Okasaki binomial PQs, modified for O(1) findMin (the first
implementation in the paper I linked, transcribed by me by hand). This
file contains no strictness or unpacking annotations or optimizations.
B: Wasserman PQs, using your unpacking but writing the functions
myself (just so I could make a small file that I could be sure I
mostly understood). This is clearly different from D, your proposal,
but I think it uses the same algorithms (not functions) and the same
data structures (down to unpacking and strictness).
C: Simple binomial queues without the O(1) findMin modification, as
written by you in the last attachment on 3909. This implementation
uses some unpacking and strictness annotations, and uses a different
deleteMin algorithm than Brodal & Okasaki use. You called this
implementation "sparse" to distinguish it from your nested types
proposal.
D: Wasserman PQs, using your latest proposed patch from ticket 3909.

Binomial priority queue timings (in milliseconds, averaged over 20 runs)
A: Simple Brodal-Okasaki list implementation:
199.3697
B: Wasserman nested type implementation, simple functions:
235.0143
C: Wasserman's 'Quick' list implementation:
179.7227
D: Wasserman's proposed nested type implementation:
163.47515

D is still the fastest. However, A is a good bit faster than B. Is it
possible that C would show a similar advantage over D if it were
optimized as carefully as D?

Also, why do my benchmarks show only slight differences between the
implementations when yours show massive ones?

It is possible I am making a noob benchmarking error. Attached is a
zip file that should contain everything necessary to replicate my
tests.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: HeapSortTest.zip
Type: application/zip
Size: 12253 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/libraries/attachments/20100317/3b3e328b/HeapSortTest.zip