RFC TIMERS: BENCH RESULTS

RFC_TIMERS_BENCH_RESULTS.md

HEAP benchmarks

• CPU: Intel i7 14700K
• RAM: 5600 MT/s
• Ubuntu 22.04 / Linux 6.9

Each test creates N items (not measured) and shuffles them (unless said otherwise) then measures how long the operation(s) take to complete. The test repeats itself 10 times. The average time per operation of all runs is eventually printed.

Each test suite is run 3 times. The results below report the usual results. In case of large variations, the test suite is run more times, and the nanoseconds per op becomes a min to max range.

Implementation details

The 4-heap implements a D-ary HEAP where D=4 in a flat array.

The pairing-heap implements a simple twopass pairing algorithm (no auxiliary buffer) and relies on intrusive nodes to avoid extra allocations.

The skip-list implements a forwarding (only links to the next tower, no links to the previous one) using intrusive nodes (actually "towers") to avoid extra allocations.

Operations

Unrealistic benchmarks. They aim to measure the overhead of fully filling and emptying the HEAP.

• insert (ordered) doesn't shuffle the items, and inserts them all in ascending order;

• insert (shuffled) inserts all the items in randomized order.

• delete-min inserts all the items in randomized order (not measured) then measures the time it takes to delete the min item from the HEAP.

• delete inserts all the items in randomized order (not measured) then measures the time it takes to delete them.

		4-HEAP	PAIRING HEAP	SKIP LIST
N=100	insert (ordered)	7 ns/op	7 ns/op	155 ns/op
	insert (shuffled)	32 ns/op	9 ns/op	190 ns/op
	delete-min (all)	64 ns/op	180 ns/op	14 ns/op
	delete (all)	99 ns/op	77 ns/op	303 ns/op
---------------	-------------------	--------------------	--------------	------------------
N=1 000	insert (ordered)	5 ns/op	8 ns/op	154 ns/op
	insert (shuffled)	29 ns/op	7 ns/op	135 to 237 ns/op
	delete-min (all)	54 to 97 ns/op	239 ns/op	3 ns/op
	delete (all)	58 to 362 ns/op	48 ns/op	63 to 477 ns/op
---------------	-------------------	--------------------	--------------	------------------
N=10 000	insert (ordered)	5 ns/op	4 ns/op	111 ns/op
	insert (shuffled)	13 ns/op	3 ns/op	75 ns/op
	delete-min (all)	26 ns/op	75 ns/op	3 ns/op
	delete (all)	447 ns/op	18 ns/op	100 ns/op
---------------	-------------------	--------------------	--------------	------------------
N=100 000	insert (ordered)	1 ns/op	1 ns/op	114 ns/op
	insert (shuffled)	7 ns/op	2 ns/op	165 ns/op
	delete-min (all)	35 ns/op	124 ns/op	4 ns/op
	delete (all)	4352 ns/op	36 ns/op	176 ns/op
---------------	-------------------	--------------------	--------------	------------------
N=1 000 000	insert (ordered)	2 ns/op	2 ns/op	2048 ns/op
	insert (shuffled)	12 ns/op	7 ns/op	1206 ns/op
	delete-min (all)	70 ns/op	295 ns/op	9 ns/op
	delete (all)	48396 ns/op :burn:	102 ns/op	1395 ns/op

In raw operations, the 4-heap is much faster than the pairing heap, but as soon as we need the delete operation, it gets considerably slower, and painfully slow at higher occupancies. Timings, howere have been more stable for the pairing heap.

The skip list has incredible timings for the delete-min operation but overall the performance doesn't stand the comparison. It still fares better than the 4-heap on the delete operation. I pays the price for having to create multiple links, and doesn't have a scenario with mostly lookups over a stable tree where it could shine better.

Scenarios

The scenarios try to be a bit more real, but stil completely fictitious. They aim to measure how operations are affecting each others.

• insert+del-min every 1/3rd of the time, delete the min item from the HEAP, every other 2/3rd of the time insert the next item. Eventually empties the HEAP by deleting the min item. Measures the overall time it took.

• insert+delete every 1/3rd of the time, delete a previously inserted item from the HEAP, every other 2/3rd of the time insert the next item. Eventually empties the HEAP by deleting all the inserted items. Measures the overall time it took.

		4-HEAP	PAIRING HEAP	SKIP LIST
N=100	insert+del-min	117 ns/op	109 ns/op	165 ns/op
	insert+delete	268 ns/op	209 ns/op	653 ns/op
-------------	----------------	--------------------	--------------	------------------
N=1 000	insert+del-min	24 to 127 ns/op	23 ns/op	32 to 75 ns/op
	insert+delete	93 to 479 ns/op	42 ns/op	154 to 477 ns/op
-------------	----------------	--------------------	--------------	------------------
N=10 000	insert+del-min	26 ns/op	23 ns/op	31 ns/op
	insert+delete	486 ns/op	47 ns/op	211 ns/op
-------------	----------------	--------------------	--------------	------------------
N=100 000	insert+del-min	32 ns/op	27 ns/op	39 ns/op
	insert+delete	4425 ns/op	69 ns/op	393 ns/op
-------------	----------------	--------------------	--------------	------------------
N=1 000 000	insert+del-min	79 ns/op	37 ns/op	61 ns/op
	insert+delete	48756 ns/op :burn:	154 ns/op	2662 ns/op

For the scenarios, the pairing heap proves faster with more stable timings than the 4-heap. Surprisingly the skip list performs correctly, but definitely lags behind the pairing heap.