[Haskell-cafe] ANN: psqueue-benchmarks - benchmarks of priority queue implementations
mail at nh2.me
Sat Apr 13 05:09:13 CEST 2013
I actually found a (potential) problem with the GHC implementation.
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
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.
> If you need test cases, you can find some properties for Heap
> (priority queue) here:
> You can add some properties relating dilatation to them.
More information about the Haskell-Cafe