Error in pqueue2 #4

Closed
jlouis opened this Issue Nov 11, 2011 · 4 comments

Comments

Projects
None yet
2 participants
@jlouis
Contributor

jlouis commented Nov 11, 2011

If I use PropEr to generate random sequences, the following one:

[{set,{var,1},{call,queue_srv,in,[-18]}},{set,{var,5},{call,queue_srv,in,[9]}},{set,{var,6},{call,queue_srv,in,[-10,-4]}},{set,{var,18},{call,queue_srv,in,[-29]}},{set,{var,22},{call,queue_srv,in,[11]}},{set,{var,26},{call,queue_srv,len,[]}}]

Fails. We basically "in" a lot of things... -18, 9, (-10 at prio -4), -29 and so on, followed by a call to len. This is the minimal test case, shrunk 12 times. The internal error is:

=ERROR REPORT==== 11-Nov-2011::16:27:08 ===
** Generic server queue_srv terminating 
** Last message in was len
** When Server state == {state,pqueue2,
                               {-4,
                                {0,empty,empty,queue,{"\v",[-29]}},
                                {0,empty,empty,queue,{"\t",[-18]}},
                                element,-10}}
** Reason for termination == 
** {function_clause,[{pqueue2,merge,
                              [{0,empty,empty,queue,{"\v",[-29]}},
                               {0,empty,empty,queue,{"\t",[-18]}}],
                              [{file,"src/pqueue2.erl"},{line,444}]},
                     {pqueue2,out,1,[{file,"src/pqueue2.erl"},{line,173}]},
                     {pqueue2,len,1,[{file,"src/pqueue2.erl"},{line,144}]},
                     {queue_srv,handle_call,3,
                                [{file,"src/queue_srv.erl"},{line,98}]},
                     {gen_server,handle_msg,5,
                                 [{file,"gen_server.erl"},{line,578}]},
                     {proc_lib,init_p_do_apply,3,[]}]}
@okeuday

This comment has been minimized.

Show comment
Hide comment
@okeuday

okeuday Nov 11, 2011

Owner

Thanks, you have found the problematic case. That means a queue:join/2 is required in the merge function, and the proper order appears to be queue:join(Queue2, Queue1), assuming the order merge(H1, H2), however, that is probably not always true. If that is not always true, then this priority queue can not preserve the ordering for a given priority, which is unfortunate, since pqueue can do that.

Owner

okeuday commented Nov 11, 2011

Thanks, you have found the problematic case. That means a queue:join/2 is required in the merge function, and the proper order appears to be queue:join(Queue2, Queue1), assuming the order merge(H1, H2), however, that is probably not always true. If that is not always true, then this priority queue can not preserve the ordering for a given priority, which is unfortunate, since pqueue can do that.

@okeuday

This comment has been minimized.

Show comment
Hide comment
@okeuday

okeuday Nov 12, 2011

Owner

Thank you again for adding the proper integration. I have been meaning to use proper, but have been distracted by other things, but it is a very pleasant experience. I have fixed the problems, even the is_empty issues in both pqueue and pqueue2. So, this means that pqueue2 now provides correctly ordered output. However, this order comes at a cost of efficiency, where the pqueue2 data structure becomes much slower than others (slower than the Riak/RabbitMQ list of tuples). I am not sure if it just becomes a chain of tuples or similar to that to achieve this slowness, only because that was the only way to have pqueue2 output ordered. Either way, it seems like pqueue2 has helped prove a heap solution is a bad path in Erlang.

If you wanted the recent speed test, here is an example from erlbench:

TEST run_priority_queue
N == 1000000 (10 runs)
              pqueue get:   481985.1 µs (  1.5), set:   530995.1 µs (  1.0)
             pqueue2 get:   319051.4 µs (  1.0), set:  2451001.7 µs (  4.6)
      priority_queue get:   368267.0 µs (  1.2), set:  1446207.9 µs (  2.7)
Owner

okeuday commented Nov 12, 2011

Thank you again for adding the proper integration. I have been meaning to use proper, but have been distracted by other things, but it is a very pleasant experience. I have fixed the problems, even the is_empty issues in both pqueue and pqueue2. So, this means that pqueue2 now provides correctly ordered output. However, this order comes at a cost of efficiency, where the pqueue2 data structure becomes much slower than others (slower than the Riak/RabbitMQ list of tuples). I am not sure if it just becomes a chain of tuples or similar to that to achieve this slowness, only because that was the only way to have pqueue2 output ordered. Either way, it seems like pqueue2 has helped prove a heap solution is a bad path in Erlang.

If you wanted the recent speed test, here is an example from erlbench:

TEST run_priority_queue
N == 1000000 (10 runs)
              pqueue get:   481985.1 µs (  1.5), set:   530995.1 µs (  1.0)
             pqueue2 get:   319051.4 µs (  1.0), set:  2451001.7 µs (  4.6)
      priority_queue get:   368267.0 µs (  1.2), set:  1446207.9 µs (  2.7)
@jlouis

This comment has been minimized.

Show comment
Hide comment
@jlouis

jlouis Nov 12, 2011

Contributor

Yeah, that is the price of being more correct :/

On the other hand, we now have a framework by which we can test that new implementations behaves like the old ones.

Contributor

jlouis commented Nov 12, 2011

Yeah, that is the price of being more correct :/

On the other hand, we now have a framework by which we can test that new implementations behaves like the old ones.

@okeuday

This comment has been minimized.

Show comment
Hide comment
@okeuday

okeuday Nov 13, 2011

Owner

Yes, that is valuable and should help find something better than pqueue.erl. I would rather have a solution that didn't depend on a fixed set of priorities, but I enjoy pursuing the fastest solution. Will have to see.

Owner

okeuday commented Nov 13, 2011

Yes, that is valuable and should help find something better than pqueue.erl. I would rather have a solution that didn't depend on a fixed set of priorities, but I enjoy pursuing the fastest solution. Will have to see.

@okeuday okeuday closed this Nov 13, 2011

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment