Re: numerical Lua?

[Luis Carvalho <carvalho@...>]

Hi Diego,

> Two possibilities for the speed difference.  Here are my
> guesses.
> 
> >for q=1,1000 do
> >        x = I + matrix.inv(x)
> >end
> 
> Is the above code generating a new 100x100 matrix at each
> iteration?  I'd be surprized if Matlab didn't optmize this 
> to operate on the matrix 'x' itself, instead of creating a
> new matrix and copying it over 'x'.  This eliminates a lot
> of memory allocation, copying, and a lot of garbage
> collection.

Yes, a new 100x100 matrix is being generated/collected at each iteration.
I also think that Matlab should be very sensitive to l- and r-values and
should feature a very specialized parser, as you suggested. I have thought
about this memory reallocation issue before, and took the shortest lazy path
of assuming the user would be smart enough to find this bottleneck in his
code and transfer it to C using the API, that is, I didn't want to hack the
parser at that time (and still don't) :). 

A not-so-lazy approach would be to provide an "in-place" optional parameter
to most of the functions in the library. I'm postponing this kind of change
until a have a more stable version of NumericLua and more suggestions :). But
you're right: there's a great overhead due to memory allocation, copying, and
collection.

> It woudl be *very* hard to optimize this in Lua. You'd need
> at least two changes.
> 
> One is on the semantics of something like
> 
>     x = matrix(100, 100)
>     y = x
> 
> I don't know if NumericLua does it, but you'd have to create
> a copy of x and place a reference to it on y, instead of
> just pointing y to x.  It would be nice if you did this by
> copy-on-write.  Matlab does something similar to that with
> function arguments.

Matrices are treated as similar to tables as possible, and so y would be a
reference to x in your example. If the user wants a copy, that should be
explicitly stated with y = x:copy() or y = x() (matrix calls are treated as
slicing; more on that below).

What do you mean by copy-on-write? Making a copy of x only when y is written?
Wouldn't it be better to just let the user decide if he wants to copy or just
reference? Isn't worse to copy when not needed?

> The problem is that you'd still need a change to Lua
> metametods. Perhaps Lua 5.2 could have it. We'd need 
> access to an optional l-value. In expressions such as
> 
>     x = a  +  b + c
>     x = (a + b) + c
> 
> the first operation would have changed x. The second would
> receive x both as a target and a source. This means 
> you'd have to implement your operations in such a
> way that the source and target can be the *same*, which is
> not trivial for things like matrix multiplication.

That would be great indeed. Let's wait for Lua 5.2 and see what can be done.
I just want NumericLua to be as clean as possible, running on top of vanilla
Lua and harmonically with other libraries, like Mike Pall's LuaJIT. If more of
the parser/lexer is exposed in future versions of Lua, the better (macros?
"native" token filter?).

> >for i,j in x:entries() do
> >		x[i][j] = math.random()
> >end
> 
> I didn't look at the code, but the syntax above suggests you
> are creating a temporary object for x[i], which then
> receives the [j] indexing. This has got to be slower than
> doing something like x(i, j). I know the syntax looks
> better, but I x(i, j) is also fine and could be *much*
> faster.

Actually there's no temporary object creation. Each row is created along with
the matrix they belong to, and so getting x[i][j] simply involves two __index
lookups. In critical cases -- if we want to beat Matlab :) -- the loop above
can be made faster by, for example, using locals:

for i=1,x:size() do
	local r = x[i]
	for j=1,r:size() do
		r[j] = math.random()
	end
end

I had a previous version where x(i,j) would also index x, but on several
benchmarks this approach came out just a bit faster than x[i][j]. I then decided to
use calls to implement matrix slicing, that is, x(i,j) now returns the submatrix
of x from row i to row j.

Thanks for the food-for-thought,
Luis.


-- 
A mathematician is a device for turning coffee into theorems.
        -- P. Erdos 

-- 
Luis Carvalho
Applied Math PhD Student - Brown University
PGP Key: E820854A <carvalho@dam.brown.edu>