[erlang-questions] [ANN] Priority Queue Implementation

[Michael Truog]

I was looking at Erlang priority queue implementations and the Riak/RabbitMQ one seemed a bit slow. I have a different implementation with the same API here: https://github.com/okeuday/pqueue/blob/master/src/pqueue.erl

The results from my test are here: http://okeuday.livejournal.com/19187.html

The implementation has "in" operations that are roughly 3 times faster (300%), however, the "out" operation became roughly 30% slower. So, as long as the priority queue is storing a decent amount of items, this data structure should provide better speed. The implementation is limited to a specific priority range: -20 (high) to 20 (low).
_______________________________________________
erlang-questions mailing list
erlang-q...@erlang.org
http://erlang.org/mailman/listinfo/erlang-questions

[Ulf Wiger]

I'm partial to skew heaps, mainly because they are so elegant.

http://www.cse.yorku.ca/~andy/courses/4101/lecture-notes/LN5.pdf

Something like this (although I've done only basic testing):

-module(skew).

-export([new/0, in/2, out/1]).

new() ->

    [].

in(X, Heap) ->

    merge({X,[],[]}, Heap).

out([]) ->

    error;

out({X, L, R}) ->

    {X, merge(L, R)}.

merge({P0,Pl,Pr}, {Q0,_,_} = Q) when P0 < Q0 ->

    {P0, Pr, merge(Pl,Q)};

merge({P0,_,_} = P, {Q0,Ql,Qr}) when P0 > Q0 ->

    {Q0, Qr, merge(Ql,P)};

merge({P0,Pl,Pr} = P,{P0,Ql,Qr}) ->   % equal roots

    merge(P, merge(merge(Pl,Pr), merge(Ql,Qr)));

merge([], Q) -> Q;

merge(P, []) -> P.

The cost is amortized O(log N) for in/2 and out/1. For peeking at the min, it's O(1).

BR,

Ulf W

Ulf Wiger, CTO, Erlang Solutions, Ltd.

http://erlang-solutions.com

[Zabrane Mickael]

Hi Ulf,

Michael Truog already has a SkewBinHeap impelmentation here:

https://github.com/okeuday/skewbinheap

Regards,

Zabrane

[Ulf Wiger]

Yeah, obviously, mine was just a sketch, thrown down as an executable comment and optimized for brevity. :)

(Although I'm not convinced, from reading, that Michael's implementation is faster than mine. Anyone who cares deeply enough could of course measure. I am currently not shopping for a faster priority queue, so I will pass on that.)

As an aside, it was a simple skew heap exercise, presented by Chris Okasaki, that made me invite Quviq to Ericsson for the first Erlang QuickCheck pilots. 

The task was to reverse-engineer the insertion order of a particular skew heap. John Hughes solved it with a "brute force approach", using QuickCheck to test his assumptions. Watching him do exploratory hacking with QuickCheck was so much fun that, once he ported QuickCheck to Erlang, I had to try to find out if it could be put to use in a commercial project.

Unfortunately - or fortunately - for Quviq, the only candidate for a useful pilot was stateful, and QuickCheck had no support for that. For lesser minds, that might have been a problem, but John and Thomas quickly invented the statem model. :)

BR,

Ulf W

[Michael Truog]

I think the skew heap I have needs some work, because it seems to come only from Okasaki's code example, so it doesn't take into consideration his suggestions/exercises.  So, only insert is O(1), and the min would need to be stored separately to get O(1) instead of O(log(N)). He had a suggestion for making the merge of two heaps O(1), but I wasn't as concerned about that operation.  It seems hard to get an "out" operation that is O(1) amortized, that is removing the min from the heap (hopefully O(log(N)) worst case).  I will look at testing a heap implementation to see how it might work out.  Thanks for the information.

[Michael Truog]

I modified the example to extend it with queues and it does compare very well, being slightly faster.  I still believe it needs to be tested more, but the implementation becomes simpler and you don't need the static priority limitations, which is nice.  The link is:
https://github.com/okeuday/pqueue/blob/master/src/pqueue2.erl

with erlbench results here ((with R14B02, without HiPE) on an AMD Phenom 9950 Quad-Core (64 bit) running Linux 2.6.32-23-generic (Ubuntu)):
TEST run_priority_queue
N == 1000000 (10 runs)
              pqueue get:   481774.3 µs (  1.4), set:   525589.1 µs (  1.0)
             pqueue2 get:   332711.2 µs (  1.0), set:   680209.0 µs (  1.3)
      priority_queue get:   362588.9 µs (  1.1), set:  1443674.2 µs (  2.7)

[Ulf Wiger]

Always nice when the simplest approaches prove to be among the fastest. :)

You don't have a case for merging two trees where the roots are the same and both are queues. I guess there isn't any perfect way to merge the queues, unless you put timestamps on each entry…

BR,

Ulf W

[Michael Truog]

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 haven't been able to crash the data structure without that case while using many priorities, but it still requires investigation.

On 11/10/2011 12:01 AM, Ulf Wiger wrote:

Always nice when the simplest approaches prove to be among the fastest. :)

You don't have a case for merging two trees where the roots are the same and both are queues. I guess there isn't any perfect way to merge the queues, unless you put timestamps on each entry�

BR,

Ulf W

On 10 Nov 2011, at 08:45, Michael Truog wrote:

I modified the example to extend it with queues and it does compare very well, being slightly faster.� I still believe it needs to be tested more, but the implementation becomes simpler and you don't need the static priority limitations, which is nice.� The link is:

https://github.com/okeuday/pqueue/blob/master/src/pqueue2.erl

with erlbench results here ((with R14B02, without HiPE) on an AMD Phenom 9950 Quad-Core (64 bit) running Linux 2.6.32-23-generic (Ubuntu)):
TEST run_priority_queue
N == 1000000 (10 runs)

������������� pqueue get:�� 481774.3 �s (� 1.4), set:�� 525589.1 �s (� 1.0)
������������ pqueue2 get:�� 332711.2 �s (� 1.0), set:�� 680209.0 �s (� 1.3)
����� priority_queue get:�� 362588.9 �s (� 1.1), set:� 1443674.2 �s (� 2.7)

On 11/09/2011 08:58 AM, Michael Truog wrote:

I think the skew heap I have needs some work, because it seems to come only from Okasaki's code example, so it doesn't take into consideration his suggestions/exercises.� So, only insert is O(1), and the min would need to be stored separately to get O(1) instead of O(log(N)). He had a suggestion for making the merge of two heaps O(1), but I wasn't as concerned about that operation.� It seems hard to get an "out" operation that is O(1) amortized, that is removing the min from the heap (hopefully O(log(N)) worst case).� I will look at testing a heap implementation to see how it might work out.� Thanks for the information.

On 11/09/2011 01:00 AM, Ulf Wiger wrote:

Yeah, obviously, mine was just a sketch, thrown down as an executable comment and optimized for brevity. :)

(Although I'm not convinced, from reading, that Michael's implementation is faster than mine. Anyone who cares deeply enough could of course measure. I am currently not shopping for a faster priority queue, so I will pass on that.)

As an aside, it was a simple skew heap exercise, presented by Chris Okasaki, that made me invite Quviq to Ericsson for the first Erlang QuickCheck pilots.�

The task was to reverse-engineer the insertion order of a particular skew heap. John Hughes solved it with a "brute force approach", using QuickCheck to test his assumptions. Watching him do exploratory hacking with QuickCheck was so much fun that, once he ported QuickCheck to Erlang, I had to try to find out if it could be put to use in a commercial project.

Unfortunately - or fortunately - for Quviq, the only candidate for a useful pilot was stateful, and QuickCheck had no support for that. For lesser minds, that might have been a problem, but John and Thomas quickly invented the statem model. :)

BR,

Ulf W

On 9 Nov 2011, at 09:45, Zabrane Mickael wrote:

Hi Ulf,

Michael Truog already has a SkewBinHeap impelmentation here:

https://github.com/okeuday/skewbinheap

Regards,

Zabrane

On Nov 9, 2011, at 9:42 AM, Ulf Wiger wrote:

I'm partial to skew heaps, mainly because they are so elegant.

http://www.cse.yorku.ca/~andy/courses/4101/lecture-notes/LN5.pdf

Something like this (although I've done only basic testing):

-module(skew).

-export([new/0, in/2, out/1]).

new() ->

� � [].

in(X, Heap) ->

� � merge({X,[],[]}, Heap).

out([]) ->

� � error;

out({X, L, R}) ->

� � {X, merge(L, R)}.

merge({P0,Pl,Pr}, {Q0,_,_} = Q) when P0 < Q0 ->

� � {P0, Pr, merge(Pl,Q)};

merge({P0,_,_} = P, {Q0,Ql,Qr}) when P0 > Q0 ->

� � {Q0, Qr, merge(Ql,P)};

merge({P0,Pl,Pr} = P,{P0,Ql,Qr}) -> � % equal roots

� � merge(P, merge(merge(Pl,Pr), merge(Ql,Qr)));

merge([], Q) -> Q;

merge(P, []) -> P.

The cost is amortized O(log N) for in/2 and out/1. For peeking at the min, it's O(1).

BR,

Ulf W

On 9 Nov 2011, at 04:33, Michael Truog wrote:

I was looking at Erlang priority queue implementations and the Riak/RabbitMQ one seemed a bit slow. �I have a different implementation with the same API here: https://github.com/okeuday/pqueue/blob/master/src/pqueue.erl

The results from my test are here: http://okeuday.livejournal.com/19187.html

The implementation has "in" operations that are roughly 3 times faster (300%), however, the "out" operation became roughly 30% slower. �So, as long as the priority queue is storing a decent amount of items, this data structure should provide better speed. �The implementation is limited to a specific priority range: -20 (high) to 20 (low).

_______________________________________________
erlang-questions mailing list
erlang-q...@erlang.org
http://erlang.org/mailman/listinfo/erlang-questions

Ulf Wiger,�CTO, Erlang Solutions, Ltd.

http://erlang-solutions.com

_______________________________________________
erlang-questions mailing list
erlang-q...@erlang.org
http://erlang.org/mailman/listinfo/erlang-questions

Ulf Wiger,�CTO, Erlang Solutions, Ltd.

http://erlang-solutions.com

  
_______________________________________________
erlang-questions mailing list
erlang-q...@erlang.org
http://erlang.org/mailman/listinfo/erlang-questions

Ulf Wiger,�CTO, Erlang Solutions, Ltd.

http://erlang-solutions.com

[Ulf Wiger]

On 10 Nov 2011, at 09:12, Michael Truog 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 haven't been able to crash the data structure without that case while using many priorities, but it still requires investigation.

I guess it depends in part on whether merge/2 is used as an internal helper function, or exported as part of the API. If it's an API function, one should probably assume that it *could* happen. Otherwise, I'm inclined to agree that it shouldn't be needed.

BR,
Ulf W

Ulf Wiger, CTO, Erlang Solutions, Ltd.

[David Mercer]

On Wednesday, November 09, 2011, Ulf Wiger wrote:

 

Yeah, obviously, mine was just a sketch, thrown down as an executable comment and optimized for brevity. :)

 

I bet you’re a hoot once you get a few beers in you.  Next time you’re in Mobile, Alabama, give me a holler and I’ll shout you one.

 

Cheers,

 

DBM

[Jesper Louis Andersen]

On Thu, Nov 10, 2011 at 09:12, Michael Truog <mjt...@gmail.com> 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

--
J.

[Hynek Vychodil]

I have used this pretty raw but simple priority queue implementation
for mine primes generation with true sieve:

-module(pair_heap).

-compile(inline).

-export([new/0, insert/2, find_min/1, delete_min/1, merge/2, to_list/1,
from_list/1, insert_list/2]).

new() -> [].

find_min([H|_]) -> H;
find_min([]) -> empty.

%insert(E, H) -> merge([E], H).
insert(E, []) -> [E];
insert(E, [EH|SH]) when EH < E -> [EH|[[E]|SH]];
insert(E, [_|_]=H) -> [E|[H]].

merge([EA|_]=A, [EB|SB]) when EB < EA -> [EB|[A|SB]];
merge([EA|SA], [_|_]=B) -> [EA|[B|SA]];
merge([], B) -> B;
merge(A, []) -> A.

delete_min([]) -> [];
delete_min([_|SH]) ->
merge_pairs(SH).

merge_pairs([]) -> [];
merge_pairs([X]) -> X;
merge_pairs([A,B|T]) -> merge(merge(A,B), merge_pairs(T)).

to_list([]) -> [];
to_list(H) -> [find_min(H) | to_list(delete_min(H))].

from_list([]) -> [];
from_list(L) -> insert_list(L, new()).

insert_list([E|T], H) -> insert_list(T, insert(E, H));
insert_list([], H) -> H.

It worked pretty well and fast for mine purposes.

--
Hynek Vychodil
BI consultant

GoodData
náměstí 28. října 1104/17, 602 00, Brno - Černá Pole
Office:   +420 530 50 7704
E-mail:  hy...@gooddata.com
Web:     www.gooddata.com

[Michael Truog]

I was looking for a priority queue implementation where the priority is separate from the value being queued, where the order is preserved for the same priority. That might not be a typical application of a heap to a priority queue, because it might be expected to lose order within the heap structure. Since I want the priority to be separate from the value, the data structure I am trying to pursue is a bit different.

[Hynek Vychodil]

You can achieve this simply using {Priority, Order, Value} or
{Priority, now(), Value} i.e. you can do it by wrapping mine pair_heap
implementation to very simple wrapper.

new() -> {0, pair_heap:new()}.

in(Priority, Value, {Count, Q}) ->
{Count+1, pair_heap:insert({Priority, Count, Value}, Q)}.

out({Count, Q}) ->
case pair_heap:find_min(Q) of
{_,_,Value} -> {Value, {Count, pair_heap:delete(Q)}};
empty -> empty
end.

If you need biggest priority first you can change

in(Priority, Value, {Count, Q}) ->
{Count+1, pair_heap:insert({-Priority, Count, Value}, Q)}.

There is not need make special priority implementation in Erlang.

--
Hynek Vychodil
BI consultant

GoodData
náměstí 28. října 1104/17, 602 00, Brno - Černá Pole
Office:   +420 530 50 7704
E-mail:  hy...@gooddata.com
Web:     www.gooddata.com

[Michael Truog]

On 11/12/2011 05:19 AM, Hynek Vychodil wrote:
> There is not need make special priority implementation in Erlang.

Oh, but there is! I think it is nice to have efficient data structures, just to keep software efficient. So, there is a need, especially in a language like Erlang that happens to be slower than more native code execution. Pursuing quality can help us avoid software that just becomes slower as it grows (see http://en.wikipedia.org/wiki/Wirth%27s_law).

So, yes, there is no need to care, unless you care about quality.

[Hynek Vychodil]

Keeping separate implementations for each edge cases even they do same
thing will never help improve quality of code. DRY

--
Hynek Vychodil
BI consultant

GoodData
náměstí 28. října 1104/17, 602 00, Brno - Černá Pole
Office:   +420 530 50 7704
E-mail:  hy...@gooddata.com
Web:     www.gooddata.com

[Michael Truog]

Perhaps you perceive quality as an academic type of quality, where all descriptions are short so they can be consumed quickly and easily. I agree the code for pqueue.erl is long, however, that is a price for efficiency in that case. So, it really depends on how you judge quality. When you consider data structures as stable building blocks for higher-level logic, you might realize that data structures source code never really changes that much once it is acceptable. So, even if the source code is dense, it isn't something that needs to be modified... quite the contrary, it shouldn't need modifications since it is meant to be a stable building block. You are welcome to try and create something more efficient with a smaller amount of code. That might achieve the quality you think is missing.

[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 <mjt...@gmail.com> 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
>

_______________________________________________