Performance of selective receive

[Richard A. O'Keefe]

It seems to me that the mailbox rescannign problem can be at least
greatly ameliorated at fairly low cost, without change to syntax or
semantics.

First off, let's consider how many different receives a process is
likely to execute.  We really need some good runtime statistics on
this.  But we can get some kind of clue by counting the number of
receives per module
  #M #R		#R is the number of receives in a module.
1088 0		#M is the number of modules with that many receives.
  98 1		So 1088 modules have no receive, 98 have one,
  60 2		60 have two, ..., and 1 module has twenty-one receives.
  40 3
  22 4
  15 5
  11 6
   3 7
   5 8
   8 9
   3 10
   2 11
   1 12
   1 13
   1 19
   1 21

Most processes "belong" to some one module, so this gives us some idea
of how many receives a process might have.  It's an underestimate, because
of behaviours and the like.

Consider a typical receive:

            receive
                {Port, {data, [Command, $o, $k]}} -> ...
	    ;   {Port, {data, [Command |T]}} -> ...
	    ;   {Port, Else} -> ...
	    ;   {'EXIT', Port, normal} -> ...
	    ;   {'EXIT', Port, Error} -> ...
	    end

the bodies of the choices don't actually matter here.
In fact we could imagine this done as

    case receive(fun ({P,{data,[C,$o,$k]}}) when P = Port -> {1,C}
                   ; ({P,{data,[C|T]}})     when P = Port -> {2,C,T}
                   ; ({P,E})                when P = Port -> {3,E}
                   ; ({'EXIT',P,normal})    when P = Port -> {4}
                   ; ({'EXIT',P,E})         when P = Port -> {5,E}
                   ; (_)                                  -> []
                  end)
    of  {1,Command} -> ...
     ;  {2,Command,T} -> ...
     ;  {3,E} -> ...
     ;  {4} -> ...
     ;  {5,E} -> ...    
    end

The point I want to make here is that there is a clear separation between
the matching code and the action code, and that receive can be done by
passing *something* to a built-in operation which just determines which
is the first match, if any, and returns selected data.

In the matching code, we find
 - constants and constructors
 - bound variables
 - don't-care variables (variables which, whatever their spelling,
   are dead after the match)
 - response variables (variables which are unbound before the match,
   and are live after it).

We can *completely* characterise the matching part of a receive request
by
    - the sequence of patterns and responses
      (which is nothing more or less than a program point)
    - a tuple of all the bound variables.

So any particular instance of the receive shown above can be
characterised by {<<the code address>>, Port}.

In fact, we can go a step further, as I'll explain later.

Now here's the idea.  In addition to its mailbox/message queue,
a process should maintain a cache of
    {{Which_Match,V1,...,Vn}, Last_Scan}
pairs, where
    {Which_Match,V1,...,Vn}
groups a sequence of patterns and responses and
    Last_Scan
identifies the last message to have been examined (unsuccessfully, of
course) by the receive in question.

Now when a new receive is done, you scan the cache looking for a
{Which_Match,V1,...,Vn} key that is equal to the new one.  If you
find a match, you resume scanning from just after that message.
If you do not find a match, you start scanning from the beginning.

How big should the cache be?  That's really a matter for measurement,
not guessing, but I would *guess* that 4 entries with an LRU policy
might be enough.

There are a number of fairly obvious refinements of this.