On 06/09/2011 09:28 PM, Warp wrote:

>    Hmm, for the compiler to be able to elide the copying and make the changes
> in-place, it would have to know for sure that those nodes that are being
> changed are not being referenced from anywhere else in the program. (Because,
> obviously, if they are referenced by something else, that something else is
> going to see the change although it shouldn't.)
>
>    I'm not sure how a compiler would be able to do that in a complex program
> where nodes and containers are being passed around.

I used to think that the compiler magically performed these kinds of 
optimisation somehow. I've gradually learned that this isn't the case.

Oh, sure, if you write one function that puts some data into a box, and 
another function that immediately takes the data out of that box again, 
the box will probably be optimised away. But for something like updating 
a list / tree / whatever, it's usually not feasible to optimise out the 
copying.

(There /are/ frameworks designed to spot long chains of container 
manipulations and inline them into a giant nested loop. But that's not 
compiler magic, that's clever user-level programming. The example I 
posted contains no such magic.)

>    (Of course the copying is not a big deal if each node contains eg. a
> couple of integers. However, it begins to matter if they contain for example
> large strings, which isn't all that unusual.)

Let us be clear about exactly what is copied:

If you have a heap which contains N internal nodes (since there is only 
"one" leaf node, shared by all heaps in the program) and you insert a 
new item into that heap, then O(log N) new heap nodes get constructed. 
Each [internal] heap node consists of 4 pointers. One points to 
something resembling a vtable [that's how you can tell Node and Leaf 
apart], one points to the datum, and the other two point to the child nodes.

So copying an internal node amounts to copying (and possibly altering) 4 
pointers. This /regardless/ of the type of data the heap holds. Even if 
it holds arbitrary-precision integers, you're still only copying 4 
pointers. The integers haven't changed, and so are not copied.

It does seem a pity that in the [very common] case of starting from an 
empty heap and repeatedly inserting new items into it, you have to keep 
continually generating these new nodes and then throwing them away. In 
mitigation, the GC is heavily optimised for this activity pattern. 
Allocations are cheap. They happen in a per-core allocation area (so no 
cache coherency issues), and each allocation is O(1). When the 
allocation area fills up, a GC sweep happens. Because the allocation 
area is quite small, it can be swept very quickly. The sweep identifies 
garbage, frees it, and defragments the free space (so that allocation is 
still O(1) in all cases).

It would be faster if you didn't have to do all this work, but it's not 
as slow as you'd think.

There are two key scenarios where immutable data becomes a Big Win:

First, there's parallel programming. Immutable data is thread-safe data. 
It /cannot/ change while you're examining it, so race conditions are a 
non-issue. Obviously if you want to /communicate/ between threads, 
that's another matter. But you don't ever have to worry about making one 
thread wait to update something until after the other thread has 
definitely finished using it. You won't ever see bugs where you mutate 
something and then discover that another thread was actually still 
reading it.

Second, backtracking search problems. You might think that copying stuff 
every time you want to change it is inefficient, but if you're doing 
some kind of search problem where you want to search multiple avenues, 
then still having the old copy around drastically simplifies the 
algorithm, and probably /increases/ efficiency. Because the alternative 
is to deduce (or remember) what you did, and then manually undo it if 
you need to backtrack.

Some guy at Google wrote a paper about translating a Python (?) system 
to Haskell, and actually devoted a whole section to the problems of 
trying to enforce immutability in Python, and the difficulties of doing 
without it. Immutable data was sited as one of Haskell's biggest advantages.

The one place where immutability /does/ bit is arrays. Almost all 
Haskell data structures are linked lists or trees of some kind, because 
that way the copying is cheap. But if you update one index of a 
one-million index array, you've got to copy a contiguous block of a 
million elements. Not fast. Immutable arrays are great as super-fast 
lookup tables, but unless the data changes very infrequently, you end up 
needing mutable arrays. Immutable arrays just aren't all that useful.

[Insert rant about how Haskell's array implementation sucks...]

Post a reply to this message