[erlang-questions] Priority queue

[Ulf Wiger (TN/EAB)]

I think Jay Nelson's slides on message passing 
fundamentals, prepared for EUC 2006, have a pretty
thorough discussion on prioritizing messages:

http://www.duomark.com/erlang/briefings/euc2006/pJ.html

The whole presentation starts at:

http://www.duomark.com/erlang/briefings/euc2006/

Adding priority receive on top of the erlang model
is not easy, and it gets messy, which Jay's examples
show. The one form of priority receive that works 
really well in Erlang is normal selective receive,
which temporarily gives priority to messages 
matching a given set of patterns.

BR,
Ulf W 

> -----Original Message-----
> From: erlang-questions-bounces@REDACTED 
> [mailto:erlang-questions-bounces@REDACTED] On Behalf Of Eranga Udesh
> Sent: den 6 juli 2007 18:52
> To: 'Paul Mineiro'; erlang-questions@REDACTED
> Subject: Re: [erlang-questions] Priority queue
> 
> This is a better code. 
> 
> 1st "receive after 0" block also takes some CPU cycles. I 
> wonder if this can be significant when handling a high 
> throughput of low priority messages.
> 
> Thanks,
> - Eranga
> 
> 
> 
> -----Original Message-----
> From: erlang-questions-bounces@REDACTED
> [mailto:erlang-questions-bounces@REDACTED] On Behalf Of Paul Mineiro
> Sent: Friday, July 06, 2007 9:47 PM
> To: erlang-questions@REDACTED
> Subject: Re: [erlang-questions] Priority queue
> 
> 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.
> _______________________________________________
> 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
>