Mutation

[Harvey J. Stein]

Henry G. Baker writes:
 > > Regarding the use of mutation, isn't it pretty common once you start
 > > using arrays?  When doing large data analyses in Lisp, I've had to
 > > replace lists of numbers with typed arrays, and changed computations
 > > to all work in place so as to reduce garbage creation.  This is to
 > > increase efficiency, and often helps alot (can give a factor of 2 or 3
 > > speedup, or even make an intractible problem tractible).  What sort of
 > > effects are the anti-mutation proposals going to have on this?
 > > 
 > > -- 
 > > Harvey J. Stein
 > 
 > The problem with functional objects is indeed functional arrays.  You
 > have to have some way to initialize them.  One way to do this is to
 > have them start life as mutable arrays, and then at some point you
 > 'freeze' them into immutable arrays.  The problem with this approach
 > is that it 'surprises' the person still holding onto a pointer to the
 > old 'mutable' array.  These semantics are very unpleasant because they
 > violate the constancy of type.
 > 
 > Another approach is to create a brand new functional array by copying
 > an existing mutable array.  This solves the problem of bad semantics,
 > but forces you to throw away and GC a perfectly good mutable array for
 > every immutable array.  So we have good semantics, but bad performance.
 > 
 > The third approach walks the tight-rope between the previous two
 > approaches.  The array starts life as a _linear_ array, which is
 > mutated in-place in order to initialize it.  Since linear objects
 > aren't recovered by the GC, the linear object's storage can be
 > immediately 'recycled' (by 'freezing') as the functional array itself,
 > which is already conveniently initialized.  Furthermore, since it is a
 > linear object, there cannot possibly be any other pointers to the
 > object, so good semantics are preserved.

I'm not sure I understand the utility of functional arrays.  Aside
from the difficulty with initialization semantics, it doesn't seem
like a large functional array is of much use.  Here's one example:

I have, say, 6 vectors x1, ... , x5, and y of say 20,000 elements
each.  I have a family of functions f_a:R^5-->R.  a is a vector from
R^10.  I want to find a best fit of f_a to the observed data, i.e. -
find the a which minimizes

   sum  (f_a(x1_i, ..., x5_i) - y_i)^2
    i

f_a(x) is a complicated function.  It takes much time to evaluate it
at the 20,000 data points.  The minimization algorithm basically
amounts to selecting an a, computing the above sum, and maybe some
related sums (such as the gradient of the above at a), and then
selecting a new a based on the previously selected tries, and
repeating.

Originally, I had the above with the x1...x5 and y as lists, and had
something like:

   (defun fcn (a)
       (big hairy computation on a, and the globals x1...x5 which
        returns a vector of 20,000 elements, with lots of mapcars to
        work with everything as a vector))

   (defun sum (a)
	(apply #'+ (mapcar #'square (mapcar #'- (fcn a) y))))

Now the above, aside from being inefficient for all sorts of reasons,
would also generate huge amounts of data for each computation of (sum
a).

So, instead, I made x1,..., x5, and y arrays, and defined an array
fcn-result.  Now, fcn and sum looks something like:

   (let ((fcn-result (make-array 20000 :element-type 'double)))
      (defun fcn (a)
         (dotimes (i 20000)
            (setf (aref fcn-result i)
                  (hairy computation on (aref x1 i) through (aref x5 i)
                         and (aref a 1) ... (aref a 10), which generates
                         no garbage)))
         fcn-result))

    (defun sum (a)
       (let ((sum 0)
             (f (fcn a)))
          (dotimes (i 20000)
             (incf sum (square (- (aref f i) (aref y i)))))
          sum))

Now they don't generate any garbage, not even a new 20,000 element
vector for each computation, because the code is now basically Fortran
like - fcn-result is a workspace for fcn.  Anyone who holds the return
value of fcn past another call to fcn will have an out of date result
vector.  Thus, from a coding ease and maintenance point of view, the
functional version is better - it's easier to code and has much
simpler semantics.  With the second version, the programmer has to be
careful not to hold onto the return value of fcn for too long.

However, the Fortran like version runs much much faster than the
functional version because it's basically doing the same computations
but not producing any garbage.  There is an especially large
difference in the case where the Fortran version can stay in memory,
but the functional version causes swapping.  It can also be the
difference between being able to solve a problem of a given size and
not being able to solve the problem.

My question is, where do functional arrays fit into the above problem?
Could they be used to make the first version as efficient as the
second version?  If not, why would I want them?

-- 
Harvey J. Stein
Berger Financial Research
abel@netvision.net.il