On benchmarks, heaps, priority queues

[aaronwmail-usenet]

I've been wondering about benchmarks recently.

What is a fair benchmark?

How should benchmarks be vetted or judged?

I decided to see what you folks thought, so for discussion I
compared two priority queue implementations I
published for Python in 1995 against the "heap" priority
queue implementation added to the python distribution
recently (python 2.3+).

My implementations and the benchmark code are in

http://xsdb.sourceforge.net/bench/pq3.py

(benchmark code near the bottom of the file). The python
standard implementation should be in your Lib/ directory.

Below please find the numerical results of the benchmarks.
They compare the implementations

PQPython23 - the Lib implementation
PQ0 - my insertion sort based variant
PQueue - my "heap" based variant
(like PQPython23, but different).

There are 2 benchmarks used.

insertBench
-- which does insertions followed by deletes.
mixBench
-- which does insertions and deletes mixed together.

Here is my summary of the results:

1) For sizes less than 10000 the insertion
sort PQ0 is always better.

2) For insertBench sized >10000 PQ0 is very
bad and the other two are comparable with
PQPython23 always a little faster.

3) For mixBench both of my implementations are
better than the Python23 implementation for
all sizes tested, but PQ0 is far superior.

Here is my analysis of the results:

1) The python23 implementation is best when you
expect to be doing mainly inserts with few deletions
and the expected size is >10000 (otherwise use pq0).

2) PQ0 is best if you expect to be doing many deletions
interspersed with many inserts.

3) PQueue is generally worse than the other two
unless you want to use a non-standard comparison
function (which the others don't support).

My questions to you:

Are my conclusions valid?

What is a better way to perform and publish benchmarks?

-- thanks, Aaron Watters

===
JUVENILE COURT TO TRY SHOOTING SUSPECT
-- a "real life headline" (that should work)

ENCLOSURE: run of
http://xsdb.sourceforge.net/bench/pq3.py on my machine.
=======================

BENCHMARKS FOR 1000

insertBench
__main__.PQPython23 on 1000 elapsed 0.039999961853 got 1000
__main__.PQ0 on 1000 elapsed 0.00999999046326 got 1000
__main__.PQueue on 1000 elapsed 0.0299999713898 got 1000

mixBench
__main__.PQPython23 on 1000 elapsed 0.00999999046326 got 502
__main__.PQ0 on 1000 elapsed 0.0 got 502
__main__.PQueue on 1000 elapsed 0.00999999046326 got 502

BENCHMARKS FOR 10000

insertBench
__main__.PQPython23 on 10000 elapsed 0.261000156403 got 10000
__main__.PQ0 on 10000 elapsed 0.209999799728 got 10000
__main__.PQueue on 10000 elapsed 0.361000061035 got 10000

mixBench
__main__.PQPython23 on 10000 elapsed 0.0599999427795 got 5003
__main__.PQ0 on 10000 elapsed 0.0500001907349 got 5003
__main__.PQueue on 10000 elapsed 0.0699999332428 got 5003

BENCHMARKS FOR 100000

insertBench
__main__.PQPython23 on 100000 elapsed 3.24500012398 got 100000
__main__.PQ0 on 100000 elapsed 7.93099999428 got 100000
__main__.PQueue on 100000 elapsed 4.82699990273 got 100000

mixBench
__main__.PQPython23 on 100000 elapsed 0.641000032425 got 50000
__main__.PQ0 on 100000 elapsed 0.470999956131 got 50000
__main__.PQueue on 100000 elapsed 0.651000022888 got 50000

BENCHMARKS FOR 200000

insertBench
__main__.PQPython23 on 200000 elapsed 6.98000001907 got 200000
__main__.PQ0 on 200000 elapsed 28.3209998608 got 200000
__main__.PQueue on 200000 elapsed 10.4350001812 got 200000

mixBench
__main__.PQPython23 on 200000 elapsed 1.29099988937 got 100001
__main__.PQ0 on 200000 elapsed 0.911999940872 got 100001
__main__.PQueue on 200000 elapsed 1.33200001717 got 100001

BENCHMARKS FOR 300000

insertBench
__main__.PQPython23 on 300000 elapsed 10.9159998894 got 300000
__main__.PQ0 on 300000 elapsed 69.6300001144 got 300000
__main__.PQueue on 300000 elapsed 19.3279998302 got 300000

mixBench
__main__.PQPython23 on 300000 elapsed 2.4430000782 got 150000
__main__.PQ0 on 300000 elapsed 1.58299994469 got 150000
__main__.PQueue on 300000 elapsed 2.14300012589 got 150000

BENCHMARKS FOR 400000

insertBench
__main__.PQPython23 on 400000 elapsed 16.2630000114 got 400000
__main__.PQ0 on 400000 elapsed 153.661000013 got 400000
__main__.PQueue on 400000 elapsed 24.7860000134 got 400000

mixBench
__main__.PQPython23 on 400000 elapsed 2.91400003433 got 200000
__main__.PQ0 on 400000 elapsed 1.8630001545 got 200000
__main__.PQueue on 400000 elapsed 2.73399996758 got 200000

BENCHMARKS FOR 500000

insertBench
__main__.PQPython23 on 500000 elapsed 20.1890001297 got 500000
__main__.PQ0 on 500000 elapsed 246.383999825 got 500000
__main__.PQueue on 500000 elapsed 30.1040000916 got 500000

mixBench
__main__.PQPython23 on 500000 elapsed 3.2650001049 got 250000
__main__.PQ0 on 500000 elapsed 2.35299992561 got 250000
__main__.PQueue on 500000 elapsed 3.32500004768 got 250000

BENCHMARKS FOR 1000000

insertBench
__main__.PQPython23 on 1000000 elapsed 43.0320000648 got 1000000
__main__.PQ0 on 1000000 elapsed 1376.39899993 got 1000000
__main__.PQueue on 1000000 elapsed 67.2970001698 got 1000000

mixBench
__main__.PQPython23 on 1000000 elapsed 6.93000006676 got 500001
__main__.PQ0 on 1000000 elapsed 4.8069999218 got 500001
__main__.PQueue on 1000000 elapsed 6.82999992371 got 500001