[erlang-questions] Priority queue

[Paul Mineiro]

With just a binary model of priority (high, normal), you can already
achieve this with a selective receive and your own protocol.

loop () ->
  receive
    { high, Mesg } -> process_message (high, Mesg)
  after 0 ->
    receive
      { Prio, Mesg } -> process_message (Prio, Mesg)
    end
  end,
  loop ().

I agree it does get more interesting when there is a more granular
notion of priority.  For multiple levels of priority one could do nested
receives but it would get unwieldy, and for a continuous notion of
priority this definitely won't work.

-- p

On Fri, 6 Jul 2007, Eranga Udesh wrote:

> Instead you can use an ets table with ordered_set and use ets:first/1 or
> ets:last/1 to get the prioritized messages. But still this is an expensive
> task in terms of insertion and retrieval (2nd and 3rd reasons below).
>
> A simple solution would be to extend Erlang process/message passing model to
> enable to originate priority and normal type messages. When it's a priority
> message, the message is placed at the beginning (head) of the queue. When
> it's a normal message, it's placed at the end of the queue.
>
> Taking gen_server as an exmaple there're 2 functions,
> 	gen_server:pri_call/2/3
> 	gen_server:pri_cast/2
> when run, it places the new message at the beginning of the message queue to
> the gen_server process?
>
> This doesn't preserve the FIFO for priority messages (but LIFO), but at
> least it could give the facility to deliver a high priority message to a
> process without waiting for its turn in the message queue.
>
> BRgds,
> - Eranga
>
>
>
> -----Original Message-----
> From: erlang-questions-bounces@REDACTED
> [mailto:erlang-questions-bounces@REDACTED] On Behalf Of Eranga Udesh
> Sent: Friday, July 06, 2007 8:47 PM
> To: yerl@REDACTED; ulf.wiger@REDACTED;
> erlang-questions@REDACTED
> Subject: Re: [erlang-questions] Priority queue
>
> Well, gb_trees are created in process heap. Therefore between 2 processes
> you cannot have a shared gb_tree. So, one process cannot add messages while
> the other retrieves.
>
> Also gb_trees is O(log n) complex. Hence it's not like queue where messages
> are entered from one side (tail) and read from the other side (head). It's a
> complex task than a plain message queue, which is O(1). Also a process has
> to constantly query a gb_tree to see if a message is available.
>
> Ideally, a process waits until a message is put in to its input stream.
>
> Pls correct me if I am wrong.
>
> BRgds,
> - Eranga
>
>
>
> -----Original Message-----
> From: yerl@REDACTED [mailto:yerl@REDACTED]
> Sent: Friday, July 06, 2007 6:42 PM
> To: casper2000a@REDACTED; ulf.wiger@REDACTED;
> erlang-questions@REDACTED
> Subject: Re: RE: [erlang-questions] Priority queue
>
> As pointed by Ulf for priority queues, just use "gb_trees".
>
> What do you mean by "efficient message retrieval" ?
> Explain further your problem.
>
> cheers
> Y.
>
> Explain further your problem? What do you want to
>
> ----Message d'origine----
> >De: "Eranga Udesh" <casper2000a@REDACTED>
> >A: "'Ulf Wiger \(TN/EAB\)'" <ulf.wiger@REDACTED>,
> >	"'Yerl'" <yerl@REDACTED>,
> >	<erlang-questions@REDACTED>
> >Sujet: RE: [erlang-questions] Priority queue
> >Date: Fri, 6 Jul 2007 17:43:09 +0530
> >
> >How to handle Priority Queues between processes, while keeping efficient
> >message retrieval?
> >
> >BRgds,
> >- Eranga
> >
> >
> >-----Original Message-----
> >From: erlang-questions-bounces@REDACTED
> >[mailto:erlang-questions-bounces@REDACTED] On Behalf Of Ulf Wiger
> (TN/EAB)
> >Sent: Thursday, June 28, 2007 2:17 AM
> >To: Yerl; erlang-questions@REDACTED
> >Subject: Re: [erlang-questions] Priority queue
> >
> >
> >You can use a gb_trees structure:
> >
> >in(Item, Prio, Q) ->
> >   gb_trees:insert({Prio,now()}, Item, Q).
> >
> >out(Q) ->
> >   gb_trees:take_smallest(Q).
> >
> >peek(Q) ->
> >   gb_trees:smallest(Q).
> >
> >The order will be FIFO. If you want LIFO, you
> >could negate the Prio value and take_largest
> >instead.
> >
> >BR,
> >Ulf W
> >
> >> -----Original Message-----
> >> From: erlang-questions-bounces@REDACTED
> >> [mailto:erlang-questions-bounces@REDACTED] On Behalf Of Yerl
> >> Sent: den 27 juni 2007 20:56
> >> To: erlang-questions@REDACTED
> >> Subject: [erlang-questions] Priority queue
> >>
> >> Hi Folks!
> >>
> >> I'm looking for a robust implementation of "Priority queue"
> >> (http://en.wikipedia.org/wiki/Priority_queue) in Erlang.
> >>
> >> Any pointer?
> >>
> >> cheers
> >> Y.
> >> _______________________________________________
> >> erlang-questions mailing list
> >> erlang-questions@REDACTED
> >> http://www.erlang.org/mailman/listinfo/erlang-questions
> >>
> >_______________________________________________
> >erlang-questions mailing list
> >erlang-questions@REDACTED
> >http://www.erlang.org/mailman/listinfo/erlang-questions
> >
> >
>
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions
>

Ignorance of what is going on is no barrier to confidence.