[erlang-questions] Ideas for a new Erlang
Richard A. O'Keefe
ok@REDACTED
Fri Jun 27 06:51:27 CEST 2008
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.
More information about the erlang-questions
mailing list