[e-lang] Making 'with' efficient

[Kevin Reid]

With a naive implementation of e.g. ConstList#with/1, if a list is  
constructed by accumulation, the list will be repeatedly copied, with  
the complete operation taking O(n^2) time in the number of elements.

I have now implemented a mechanism to avoid this in E-on-CL  
(revisions 823 and 824):


Each call to with/1 returns a vector-with-cell, which is a kind of  
lazy-ref (a newly introduced class). A lazy-ref does not compute its  
referent until it is examined (call, shorten, Ref.state, ...).

vector-with-cell recognizes the with/1 message specially and  
constructs another vector-with-cell; thus the accumulation is  
initially stored as a reverse linked list.

When turning a vector-with-cell into an actual vector (ConstList),  
the recipient is examined for being another vector-with-cell  
(recursively), and thus the resulting ConstList can be allocated and  
populated without having constructed the intermediate shorter  
ConstLists.

A similar optimization is performed for ConstMaps, and ConstSet  
inherits this by way of being a wrapper for ConstMap. (Note that this  
changes the GC behavior; if you retain [a => b].with(a, c) without  
examining it, b will be retained.)


With this optimization, 'with' accumulation takes O(n) time in my  
benchmarks, and is actually faster than using a FlexList (though this  
is probably due to the current FlexList implementation).


I chose to use the lazy-ref technique rather than something more  
'just objects' primarily because it would have been harder to ensure  
that the implementation differences were transparent (for consistent  
selflessness). In this implementation, with/1 is the only method  
implemented specially, and the transparency is handled the existing  
code for forwarding-refs.


The relevant ref implementation classes are:

   forwarding-ref
     resolved-ref
     lazy-ref
       with-cell
         vector-with-cell
         const-map-with-cell

A lazy-ref becomes a resolved-ref when its referent is computed.

Resolved-refs are also what resolved promises become, and were  
previously known as forwarding-refs.

-- 
Kevin Reid                            <http://homepage.mac.com/kpreid/>