Thoughts on laziness (long)

[Ulf Wiger]

On Thu, 19 Oct 2000, Jeffrey Straszhiem wrote:

>Efficient dictionaries are a very important feature, and hash tables
>seem to be the only way to get them.  And for that reason Erlang has
>made the right choice in throwing purity to the wind and providing ets
>tables and their like.

Actually, you could view ets tables as an analogy to a server process
holding the tables (or one process per table), updating a functional
structure, and servicing insert/lookup requests via message passing.
I wrote an Erlang-based ets implementation for the Erlang processor,
and this is how it was done.

My point is that you could well claim that the one impure feature of
Erlang's is message passing. Ets tables bring nothing more to the
table than what could be done using "classic" Erlang - it just does it
faster.

>One thing your comparison did not point out is this data is only
>relevant in cases where you use the data in a single-threaded manner.
>By "single-threaded" here I don't mean to imply concurrency, but
>instead threads of data flow.  Here is an example:

Ehmm, I'm not too sure about this. If you have the case of a single
process updating a private data structure, then you can do well with a
functional data structure on the process's own heap, but as soon as
you want to support concurrency, you need to place the data structure
in a server process; then it's entirely up to that process to decide
which granularity of concurrency you want. In order to support safe
updates on ets tables, you'd funnel all updates through a server
process, while atomic reads might go directly agains the ets table
(for the functional structure, all operations must go through the same
process).

The performance comparison then stacks up the same way as for the
single-threaded case, with an equivalent copying and scheduling
overhead for both models; the one exception is that simple reads 
on an ets table can be optimized and go directly to the table,
thus avoiding this overhead. As far as I can tell, this increases the
advantage of ets tables over functional structures in the concurrent
case.

I'm not knocking Okasaki, but I don't think he factored in Erlang's
concurrency model in his analysis.

/Uffe
-- 
Ulf Wiger                                    tfn: +46  8 719 81 95
Strategic Product & System Management        mob: +46 70 519 81 95
Ericsson Telecom AB,              Datacom Networks and IP Services
Varuvägen 9, Älvsjö,                    S-126 25 Stockholm, Sweden