[Haskell-cafe] ANN: psqueue-benchmarks - benchmarks of priority queue implementations

[Niklas Hambüchen]

I actually found a (potential) problem with the GHC implementation.

See here:

https://github.com/nh2/psqueue-benchmarks/blob/db89731c5b4bdd2ff2ef81022a65f894036d8453/QueueBenchmark.hs#L44

If I fromList 1000000 entries into the queue, it stack space overflows.

I got the same problem with the fingertree implementation, so maybe I
just construct the test case wrong and cause the stack space overflow
myself, but it works with the other two implementations.

Also, looking at the updated graph:

http://htmlpreview.github.com/?https://raw.github.com/nh2/psqueue-benchmarks/master/report.html

we can see that GHC's queue is 3 times slower than queuelike for
"findmin sequential".

Where could the stack overflows come from?

Niklas

On 30/03/13 09:07, Kazu Yamamoto (山本和彦) wrote:
> Hi Niklas,
> 
>> No, it does not stack overflow, and it seems to perform slightly better
>> than the other implementations; it also doesn't suffer from the toList
>> slowness problem as does listlike.
> 
> Thanks. It's nice.
> 
>> However, it is probably not as generally usable as it hardcodes the
>> priorities to be Doubles.
> 
> I think that you can import the tips of GHC PSQ to original PSQ.
> 
> P.S.
> 
> If you need test cases, you can find some properties for Heap
> (priority queue) here:
> 
> 	https://github.com/kazu-yamamoto/llrbtree/blob/master/test/Heap.hs
> 
> You can add some properties relating dilatation to them.
> 
> --Kazu
>