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 > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
