Ideas for faster math in lua

[Niklas Frykholm <niklas@...>]

I would like to be able to process lots of small mathematical objects 
(vector3 and quaternions) in a resource constrained environment 
(computer game), without having to pay the cost of new-ing and garbage 
collecting them. I.e. I would just like to reuse a pool of existing objects.

I have some ideas on how to do this, but none that I'm really satisfied 
with.

I should mention first that we are talking about lots of small 
computations, rather than a few big ones, so a numarray solution or 
something similar won't work. And it doesn't have to be implemented in 
standard Lua, patching the source is fine.

So here are some ideas:

(1) Extending the Value union to have vector3 and quaternion as basic 
lua types

This would give them the same performance characteristics as floats 
(which don't have to be new:ed). However it would more than double
the memory used by Lua, which I think is unacceptable in my constrained 
environment.

(2) "Manually" reusing vector3s and quaternions

This means pushing vector3s that we are done with to some _cache = {}, 
and fetching new vector3s from the _cache instead of creating them. 
Essentially it means doing manual memory management in Lua.

There are some ways of sugar coating it, saying that some function 
returns temporary values, that you need to save if you don't want them 
to be reused... etc. But it is hard to get away from the fact that we're 
doing manual memory management in a garbage collected language. A simple 
line such as:

	self.y = self.y - self.x * dot_product(self.x, self.y)
	self.y = self.y:normalized()

Becomes a lot more complicated when you have to start to think of which 
objects you need to "save" and "free" and when to do it. It is error 
prone and ugly.

(3) Adding limited reference counting to lua

This would mean modifying a reference counter whenever a TValue is 
created/copied or destroyed in Lua, such as when the stack size is 
changed, etc.

The reference counter does not have to be perfect... it's ok for it to 
overestimate the number of references, it just has to make sure that it 
never underestimates them. Overestimating references just means that the 
object will be cleaned up by garbage collection instead of being 
recycled while underestimating will give bugs.

Still... a lot of lua functions will have to be patched to do reference 
counting. It is a lot of work, easy to miss something and create bugs.


Three different ideas... none is really satisfying. Has anyone tried to 
do something similar? What approach did you use? How well did it work?

// Niklas