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

Niklas Hambüchen mail at nh2.me
Sat Apr 13 05:09:13 CEST 2013

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

See here:


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:


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

Where could the stack overflows come from?


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

More information about the Haskell-Cafe mailing list