lua vs. tiscript on nbody test

[Krzysztof Kowalczyk]

Just a random data point that you might find interesting.

I ported nbody test from javascript to tiscript and compared the speed
of execution with lua 5.1. This is floating-point intensive benchmark
and lua supposedly is good at that.

In my benchmark lua is about 6 times faster than tiscript.

On a separate note: JavaScript seems to accept var n = Array(...)
syntax while tiscript requires var n = new Array(...).

-- kjk

[Andrew]

Hi, Krzysztof.

Can I take a look on your test somewhere?

In any case keep in mind following.
Let's say you need to compute Math.sqrt(x) in a loop:

function Foo()
{
var results = []; results.length = 100; // array of length 100
for( var i = 1; i <= 100; ++i)
results[i-1] = Math.sqrt(i);
}

Direct call of Math.sqrt(i) is not so effective inside the loop as
statement Math.sqrt(v) means following:

1) Find global object with symbol 'Math' and put it on top of the
stack.
2) In the object on top of the stack find member with symbol 'sqrt'
and put it on top of the stack.
3) If top of the stack is a function then call it with value of
argument 'i'

As you may see there are two hash table lookups in sumple Math.sqrt(v)
call. Not so effective inside loops.

To improve function above I would rewrite it as:

function Foo()
{
var results = []; results.length = 100; // array of length 100
var sqrt = Math.sqrt;
for( var i = 1; i <= 100; ++i)
results[i-1] = sqrt(i);
}

Here statement
var sqrt = Math.sqrt;
does lookup in these hash tables only once. Then sqrt(i) is a simple
call of function from local variable.
List of local variables is known upfront to the compiler. This list
(of locals) is just a vector so call sqrt(i); is just:

1) Copy locals[n] to the top of the stack. n here is some integer
known at compile time.
2) If top of the stack is a function then call it with value of
argument 'i'.

Which is better.

----------------------------------
In principle you may define following in your code:

Math.sqrt = function() { something completely different };

and allowance to do this requeres compiler to do deep lookup each time
when it sees Math.sqrt(i).

Thus if you need to do call global functions in cycles make local
'shortcuts' for them.

All above is valid not for TIScript only but for JavaScript too.

On Jul 14, 2:51 am, "Krzysztof Kowalczyk" <kkowalc...@gmail.com>
wrote:

[Andrew]

I suspect that you use test:
http://shootout.alioth.debian.org/gp4/benchmark.php?test=nbody&lang=all

These two tests:
Lua:
http://shootout.alioth.debian.org/gp4/benchmark.php?test=nbody&lang=lua&id=2
and JS:
http://shootout.alioth.debian.org/gp4/benchmark.php?test=nbody&lang=javascript&id=0
are not equivalent.

Lua test is not using hash lookups inside loops at all.

See, JS:
NBodySystem.prototype.advance = function(dt){
for (var i=0; i<size; i++) {
var bodyi = this.bodies[i]; // <<<<< this.bodies - hash lookup
in 'this' object.

And the same in LUA:

local function advance(bodies, nbody, dt)
for i=1,nbody do
local bi = bodies[i] // <<<<<< bodies is a local variable here

And take a look on declaration 'local function advance()', on this
'local'.
This means that advance function is used locally - without any hash
lookups at all.

----------------------
What are the goals of this shootout? To reach maximum effectiveness of
the code or to show typical solution and measure its results?

[Krzysztof Kowalczyk]

Yes, this is the test I've been using. You can see the exact code at
http://kjk.googlecode.com/svn/trunk/bench/ (nbody.lua, nbody.tis,
timeit.py for how I measure the time). I use windows and latest
official binary of lua 5.1.2. tiscript is built by me on windows as
release build using my makefile.vc script in tiscript source (nmake -f
makefile.vc TARGET=rel) using visual studio 2005.

My goal was to get a ballpark figure of how fast tiscript is compared
to other existing solution that I could use (I'm looking for a small,
embeddable in C code language).

I tried to speed up nbody.tis using your suggestions.

Doing var sqrt = Math.sqrt() actually slowed down the script a little
bit (but the loop was short so the lookup savings might be offset by
additional assignement).

I tried to move advance() method out of the object, make it a function
and pass bodies as an argument, but I'm getting an error I don't
understand:
tiscript2:
Error: nbody2.tis(162) : syntax error : Expecting 'const', 'var',
'function' or 'property'

line:stdout.println(bodies.energy());
here:______^

(this is http://kjk.googlecode.com/svn/trunk/bench/ nbody2.tis). I'm
probably doing something obviously wrong.

I would be curious to see how much a tiscript expert could speedup
nbody.tis - I just did a straight translation of JavaScript code
without looking at ways to improve it.

-- kjk

[Andrew]

Here is my version of the test.
I did almost the same optimizations as used in LUA test
http://kjk.googlecode.com/svn/trunk/bench/nbody.lua
Looking on optimizations they made I can say that tiscript and lua
have the same kind of VM/architecture.

In my tests tiscript is 5 times slower on this number-crunching test.
I suspect that problem is in following: tiscript value is a 64-bit
thing so float value (double + C++) is packaged there, thus each
operation with it is additional rshift/lshift (effectively tiscript
uses 63-bit floats).

nbody.tis ===========

var PI = 3.141592653589793;
var SOLAR_MASS = 4 * PI * PI;
var DAYS_PER_YEAR = 365.24;

type Body
{
function offsetMomentum(px,py,pz)
{
this.vx = -px / SOLAR_MASS;
this.vy = -py / SOLAR_MASS;
this.vz = -pz / SOLAR_MASS;
return this;
}
}

var Jupiter = {
prototype:Body,
x: 4.84143144246472090e+00,
y: -1.16032004402742839e+00,
z: -1.03622044471123109e-01,
vx: 1.66007664274403694e-03 * DAYS_PER_YEAR,
vy: 7.69901118419740425e-03 * DAYS_PER_YEAR,
vz: -6.90460016972063023e-05 * DAYS_PER_YEAR,
mass: 9.54791938424326609e-04 * SOLAR_MASS
};

var Saturn = {
prototype:Body,
x: 8.34336671824457987e+00,
y: 4.12479856412430479e+00,
z: -4.03523417114321381e-01,
vx: -2.76742510726862411e-03 * DAYS_PER_YEAR,
vy: 4.99852801234917238e-03 * DAYS_PER_YEAR,
vz: 2.30417297573763929e-05 * DAYS_PER_YEAR,
mass: 2.85885980666130812e-04 * SOLAR_MASS
};

var Uranus = {
prototype:Body,
x: 1.28943695621391310e+01,
y: -1.51111514016986312e+01,
z: -2.23307578892655734e-01,
vx: 2.96460137564761618e-03 * DAYS_PER_YEAR,
vy: 2.37847173959480950e-03 * DAYS_PER_YEAR,
vz: -2.96589568540237556e-05 * DAYS_PER_YEAR,
mass: 4.36624404335156298e-05 * SOLAR_MASS
};

var Neptune = {
prototype:Body,
x: 1.53796971148509165e+01,
y: -2.59193146099879641e+01,
z: 1.79258772950371181e-01,
vx: 2.68067772490389322e-03 * DAYS_PER_YEAR,
vy: 1.62824170038242295e-03 * DAYS_PER_YEAR,
vz: -9.51592254519715870e-05 * DAYS_PER_YEAR,
mass: 5.15138902046611451e-05 * SOLAR_MASS
};

var Sun = {
prototype:Body,
x: 0.0,
y: 0.0,
z: 0.0,
vx: 0.0,
vy: 0.0,
vz: 0.0,
mass: SOLAR_MASS
};

type NBodySystem
{
function this(bodies)
{
var px = 0.0;
var py = 0.0;
var pz = 0.0;
var size = bodies.length;

for (var i=0; i<size; i++){

var b = bodies[i];
var m = b.mass;
px += b.vx * m;
py += b.vy * m;
pz += b.vz * m;
}
bodies[0].offsetMomentum(px,py,pz);
this.bodies = bodies;
}

function energy()
{
var dx, dy, dz, distance;
var e = 0.0;
var bodies = this.bodies;
var size = bodies.length;

var sqrt = Math.sqrt;
for (var i=0; i<size; ++i)
{
var bodyi = bodies[i];

e += 0.5 * bodyi.mass *
( bodyi.vx * bodyi.vx
+ bodyi.vy * bodyi.vy
+ bodyi.vz * bodyi.vz );

for (var j=i+1; j<size; j++)
{
var bodyj = bodies[j];
dx = bodyi.x - bodyj.x;
dy = bodyi.y - bodyj.y;
dz = bodyi.z - bodyj.z;

distance = sqrt(dx*dx + dy*dy + dz*dz);
e -= (bodyi.mass * bodyj.mass) / distance;
}
}
return e;
}

function advance(dt)
{
var dx, dy, dz, distance, mag;
var bodies = this.bodies;
var size = bodies.length;
var sqrt = Math.sqrt;

for (var i=0; i<size; ++i) {
var bodyi = bodies[i];
var bodyi_x = bodyi.x, bodyi_y = bodyi.y, bodyi_z = bodyi.z;
var bodyi_mass = bodyi.mass;
for (var j=i+1; j<size; ++j)
{
var bodyj = bodies[j];
var bodyj_mass = bodyj.mass;

dx = bodyi_x - bodyj.x;
dy = bodyi_y - bodyj.y;
dz = bodyi_z - bodyj.z;

distance = sqrt(dx*dx + dy*dy + dz*dz);
mag = dt / (distance * distance * distance);

var dx_mag = dx * mag;
var dy_mag = dy * mag;
var dz_mag = dz * mag;

bodyi.vx -= dx_mag * bodyj_mass;
bodyi.vy -= dy_mag * bodyj_mass;
bodyi.vz -= dz_mag * bodyj_mass;

bodyj.vx += dx_mag * bodyi_mass;
bodyj.vy += dy_mag * bodyi_mass;
bodyj.vz += dz_mag * bodyi_mass;
}
}

for (var i=0; i<size; i++) {

var body = bodies[i];
body.x += dt * body.vx;
body.y += dt * body.vy;
body.z += dt * body.vz;
}
}
}

function main()
{
var n = 200000;
var bodies = new NBodySystem
(
[ Sun,Jupiter,Saturn,Uranus,Neptune ]
);

stdout.println(bodies.energy());

for (var i=0; i<n; i++)
{
bodies.advance(0.01);
}

stdout.println(bodies.energy());
}

main();

[Andrew]

Comparing lua time with other languages using data from:
http://shootout.alioth.debian.org/gp4/benchmark.php?test=nbody&lang=all
will give us following picture:

lua/PHP = 3.74
lua/Python = 3.74
lua/TIScript = 4.43 (on my PC)
lua/JavaScript (SpiderMonkey/Mozilla) = 5.16
lua/Ruby = 7.62

less number is better.

I would say that among languages with similar feature set (php/python/
js/Ruby) TIScript looks not so bad.
And keep in mind that numeric computations somehow is not that
scripting languages were designed for.
Scripting language is supposed to be a glue between native functions/
components. This is how I see it.

[Krzysztof Kowalczyk]

Yes, I'm seeing the same thing. The improved script speeds up from ~6x
lua time to ~5x lua time.

-- kjk

On 7/14/07, Andrew <andrew.f...@gmail.com> wrote:
>