Rich Hickey's slides from jvm lang summit - worth a read?

[Justin Johansson]

Chris Nicholson-Sauls Wrote:

> bearophile wrote:
> > Walter Bright:
> > 
> >> I've been thinking of transitioning dmd's semantic analysis to using immutable data structures because it will reduce allocations, not increase them.<
> > 
> > As usual I am ignorant about such matters, so I can't give you a good answer.
> > But from what I've seen in immutable-based languages, they produce a sustained flux of small/little immutable objects that the GC has to free and allocate all the time. This stresses the GC. Surely people here that know Clojure or Scala, Haskell or F# may give you a better answer. Maybe even numbers of the amount of object flux they face in normal programs. So the situation with strings may be not generalizable to the other immutable data structures a program may need to use.
> > 
> > Bye,
> > bearophile
> 
> My personal experience with Scala, at least, has been that it doesn't hurt anything.  Even 
> just considering the most common kinds of operations: ( 1 :: 2 :: 3 :: 4 :: 5 :: Nil ) 
> creates a Scala list of five values... but in the process creates five different lists! 
> Consider it "unrolled" to something like this:
> tmp = 5 :: Nil
> tmp = 4 :: tmp
> tmp = 3 :: tmp
> tmp = 2 :: tmp
> tmp = 1 :: tmp
> tmp
> 
> Yipes.  BUT... think of it as a single-linked-list structure, and its not really that bad, 
>   because each of those objects is quite small, and all five of them are preserved in the 
> original list. Compare:
> A = 3 :: 4 :: Nil
> B = 2 :: a
> C = 1 :: a
> 
> Here we have two lists (B & C) being made, each with four items... but only four items 
> total, not eight, because the '4' and '3' cells in A are being reused between them.  I 
> think that kind of capability is what has Walter interested.
> 
> -- Chris Nicholson-Sauls
> 
> P.S. -- Just to make your head hurt... "::" isn't even an operator, its the name of a 
> class (& a singleton too...) defined in the stdlib as a derivative of List.  Scala is just 
> weird like that.

<<<<
"But from what I've seen in immutable-based languages, they produce a sustained flux of small/little immutable objects that the GC"
>>>>

It's not just small/little fragments .. often the entire list that the system/library/language just made a copy of in order to preserve immutability.

Take a classical Lisp cons list for example.  Its a singly linked list referenced by just a single pointer to the head of the list, and with each cell comprising of a datum and a link to the next cell in the list.

Now appending a single item to the head of the list happens in O(n) time and preserves immutability (by default) of the original list by virtue of the intrinsic recursive structure of a cons list.

OTOH, and assuming you want list immutability, appending items to the end of the list happens in quadratic time since a copy must be made of the list that you are appending to.  By this rational, it's not just GC of individual (as in small/little) cons cells, it's garbage collection of entire lists of the tiny tots to worry about.

btw. It wasn't that long ago that I wrote an immutable list library in JavaScript using JS dynamic arrays and taking advantage of common structure.  My goal was to make prepending items to front of the list and appending items to end of the list happen in more-or-less the same linear time.

Glad to say that I succeeded and did a benchmark comparison against Python.  My JS implementation (yes, non-native list processing written in JS) beat Python hands down in an overall performance benchmark for both prepend and append operations.

>From what I've read of Clojure, found out by playing with it, and perusing its source,
it's no slouch either when it comes to making as much use of common data as possible in order to make for immutability without performance-cripple.

Ah, there's a glimmer of hope with D dynamic arrays to achieve similarly.

-- Justin Johansson