Performance of selective receive

[David Hopwood]

Pascal Brisset wrote:
> Erlang's selective receive semantics definitely has advantages
> w.r.t. the FIFO communications found in other models.
> But it also comes with a performance penalty which has bitten us
> once in a production system.

The problem is that each selective receive operation has no bound on
how long it may take. This is because selective receive categorizes
messages at the time of the receive operation; also, the categories are
not fixed in advance, they are specified dynamically as a parameter to
the operation.

If messages are instead categorized as they are queued, with one message
queue for each of a fixed set of categories, then the blocking process
can take messages from any required queue in essentially O(1) time.

Of course this doesn't by itself address the issue of messages possibly
being sent faster than the server can keep up -- in many (most?) cases
you still need end-to-end flow control. But the semantics of Erlang's
selective receive are problematic for real-time systems even when
end-to-end flow control is used, because flow control relies on the good
behaviour of all clients in order to avoid backlogs. This clearly cannot
be hard real-time, and it isn't good enough even for many soft real-time
systems.

I think this is quite an important issue in the design of asynchronous
message passing languages. Such languages should IMHO have:

 - first-class message queues, where it is possible to reflect on the
   sequence of messages currently in the queue. This is strictly more
   expressive than Erlang-style selective receive; the extra expressiveness
   is needed to implement policies like discarding messages when a server
   has fallen too far behind.

 - a library of policies that cover the most common cases. For example,
   "normally FIFO, but discard messages that have not been processed in
    time t."

 - some way to apply a policy to any server, without obscuring the server's
   logic and without requiring its clients to change.

 - syntactic sugar for the case where you want all messages matching a
   given pattern to be directed to a particular queue.

It may be that that these features are only used for a small proportion of
servers. Still, I think that there is sufficient justification to include
them in a language, since the workarounds needed if you don't have first-class
message queues are quite ugly (and if you have first-class queues, the other
features are cheap).

-- 
David Hopwood <david.nospam.hopwood@REDACTED>