NumericLua optimization trick: lazy copying

["Paul Chiusano" <paul.chiusano@...>]

Hi all,

> for q=1,1000 do
>         x = I + matrix.inv(x)
> end

A few days ago there was some discussion about how the above loop will
end up making lots of copies of x. I think there's a way you can avoid
this without requiring hacks to the lua parser, or any sort of
sophisticated code analysis, or Yet Another Metamethod Request, while
still allowing one to keep the same natural syntax (no need for
x:div(...), etc) The basic idea is to perform all operations in place,
and only make copies if the original value is requested. The key is
that most operations have inverses which can be used to 'backtrack' to
the original state, if it ends up being needed. I'll explain:

Each matrix/vector has two parts: a 'core', and a 'pending' list - the
core is the actual data structure itself; the 'pending' list is just a
list of operations (lua functions) which must be applied to a copy of
the core before it can perform any operation. So, given

-- a = [...]
b = a + 1

initially, a's core is [...] and its pending list is empty. The
expression a + 1 modifies a's core [...] in place, but appends a
'subtract 1' operation to a's pending list. b gets the modified core
and an empty pending list. If later, we call one of a's methods, (like
doing a[4], say), then we copy the core which it currently shares with
b, then apply the pending subtraction operation to this new core, (
thus recovering the original value of a), and then finally go ahead
with returning a[4]. On the other hand, if a was just a temporary
variable, it'll get garbage collected and we'll have saved ourselves
from making an unneeded copy.

Being lazy about making copies like this can 'naturally' result in
some nice optimizations. a = a + b will do the operation in place, and
the old value will simply become garbage. Or in the expression 'a + 1
* 2 + b', we won't make copies for the temporary results of
subexpressions. Best of all, the programmer can still just write
things in the most natural style, and these sorts of optimizations
will just happen automagically behind the scenes.

Anyway, it's kind of a zany idea but it could work. A lot of the
common operations have inverses, and those that don't can still be
copied as before or, of course, manually mutated in place. With Lua's
first class functions / closures, it'd be possible to pull something
like this off!

Thoughts?

-Paul