[erlang-questions] [ANN] Priority Queue Implementation

[Michael Truog]

So, with help from Jesper Louis Andersen there is PropEr testing of pqueue.erl and pqueue2.erl now.  The heap-type implementation of a priority queue (pqueue2) did not preserve the order for a single priority, until later changes fixed this problem.  So, now both data structures have been verified for correctness.  However, this unfortunately impacts the performance such that pqueue.erl is still the quickest as shown below:

TEST run_priority_queue
N == 1000000 (10 runs)
              pqueue get:   484453.9 µs (  1.5), set:   533119.7 µs (  1.0)
             pqueue2 get:   325422.6 µs (  1.0), set:  2477324.7 µs (  4.6)
      priority_queue get:   373607.3 µs (  1.1), set:  1488719.6 µs (  2.8)

So, currently the heap solution is the slowest, slower than the list of priority tuples within priority_queue.  See below if you are interested in the results:
https://github.com/okeuday/pqueue/
https://github.com/okeuday/erlbench/

On 11/11/2011 07:42 AM, Jesper Louis Andersen wrote:
> On Thu, Nov 10, 2011 at 09:12, Michael Truog <mjtruog@REDACTED> wrote:
>> I previously added code that took care of that case, where two nodes needed
>> to be merged that both have queues.  However, I convinced myself at the
>> time, that the case would never happen.  So, the code probably needs to be
>> thought-through a bit more with more testing, but my hope is that merging
>> the queues isn't necessary.
> I have tested (tasted, but my typo was funnier) the forbidden fruit
> that is QuickCheck/PropEr. Your repository now has a pull-request in
> which I add partial testing via proper_statem. It generates an
> internal crash of the data structure code if we makes a bunch of
> inserts and then call len(), see
>
> https://github.com/okeuday/pqueue/issues/4
>
> Only your pqueue2 implementation is affected. pqueue is not shown to
> have any errors (yet). The crash is naturally in the "merge" part of the code :P
>