[erlang-questions] Ideas for a new Erlang

[Richard A. O'Keefe]

On 26 Jun 2008, at 11:33 am, Matthew Reilly wrote:
> In terms of Erlang's selective receive, it's possible to get around  
> the
> O(N) look up issue w/o a language change (albeit with a slight  
> change to
> the VM) if you restrict which patterns you use.
>
> (Review of the selective receive problem)
> The problem is that given code like:
>  receive
>     some_term -> some_value
>  end.
> each time this receive is hit, the whole message queue is scanned. If
> there are N unmatched messages pending, then this take O(N) each time
> this bit of code is hit.

The idea of noting which receive was done last and restarting from
where that left off has been around for a while.

In fact we can do even better, again with a VM change.
Here's the idea.  Instead of the mailbox being a simple list,
make it a doubly linked list with an extra thread, plus an
array of pointers to messages.  Hash each message using
	if message is a tuple of size > 0 then
	   if first element is an atom then
	      hash(atom) combined with size
	   else
	      size
	else
	   if message is an atom then
	      hash(atom)
	   else
	      0
Given
	receive
	   {key,......} ->
	end

the compiler generates code to probe just the message thread that
contains tuples the right size with the right key.  With multiple
cases, you have to merge several message threads.

This is only a sketch.  You wouldn't want to bother with elaborate
machinery while the mailbox was small.

Note that the scheme Matthew Reilly describes is quite general if
you treat the matching process in two stages.  Take a prescan
where all the already bound variables in the patterns have been
replaced by wild-cards, and any guard tests that now contain
wild-cards have been discarded (but don't throw away type tests
for variables to be bound by the match).  If you remember where
the prescan got up to, it doesn't matter what the bound variables
are, they can't possibly cause things that failed to match the
prescan to match instead.  So the code becomes something like

	if the last receive was this one,
	   P := the stored prescan position
         else
	   P := the start of the queue
	while P is not empty and the message
	  at P does not match the prescan
	do advance P to the next message
	Record that the last receive was this
	one and that prescanning reached P.
	Contiune as now.

No restriction on patterns is actually needed.