Arrays have low performance

[biwa]

Version: 3.0.0-beta-2050

Array performance has come up before, see #194 and #832, but it still seems to be an issue.

Accessing arrays seems to be very slow. This is mostly notable if you have to loop over big arrays many times. Take this code for example:

using Jint;

var engine = new Engine();
engine.SetValue("log", new Action<object>(Console.WriteLine));
engine.SetValue("random", new Random(123)); // Set seed to get the same results every time

engine.Execute(@"
class Point
{
	constructor(x, y, z)
	{
		this.x = x;
		this.y = y;
		this.z = z;
	}
}

// Generate lots of points with random-ish x, y, and z values
const allPoints = [];
for(let i=0; i < 20000; i++)
	allPoints.push(new Point(random.next(25), random.next(25), random.next(25)));

const uniquePoints = []

const start = new Date();

// Go through all points and add it to the list of unique points if the x, y, and z
// values have not been seen before
allPoints.forEach(p => {
	if(!uniquePoints.some(e => e.x === p.x && e.y === p.y && e.z === p.z))
		uniquePoints.push(p);
});

const elapsed = (new Date()).getTime() - start.getTime();
log(`There are ${uniquePoints.length} unique points. Finding them took ${elapsed} ms`);

");

It creates an array that has 20000 points with semi-random x, y, and z values (the seed has been set, so it'll always generates the same ones). It then finds points with x, y, and z positions that have not been seen yet, and adds them to an array. The slowness comes from having to loop over uniquePoints over and over again, in this case by using some. The issue isn't with some, though, it happens with all methods, and even when manually looping over the array (and accessing its values).

On my PC it runs for around 33 seconds. I adapted the script for NodeJS, and there it takes around 100 milliseconds. While I of course do not expect V8 performance a factor of 330 seems a bit wild.

[lahma]

Would you like to help out with performance improvements or should we just convert this to discussion trying to find optimal array access patterns?

[lahma]

I think it's more like a happy accident that V8 is so fast for O(n^2) algortihm. You should probably rewrite the logic using lookups against a Set. Also please remember that V8 compiles your code and Jint interpretes on the fly.

[biwa]

Yes, V8 does it ridiculously fast, and I want to emphasize that I do not expect Jint to be close to it. The C# implementation of the code runs for about 900 ms.

I don't think a Set will work here, since the objects are actually unique, just happen to have the same property values.

[lahma]

Here's a version of the sample written with performance in mind.

class Point
{
    constructor(x, y, z)
    {
        this.x = x;
        this.y = y;
        this.z = z;
   }
}

// Generate lots of points with random-ish x, y, and z values
const lookup = new Set();
const allPoints = [];
for(let i=0; i < 20000; i++) {
const point = new Point(random.next(25), random.next(25), random.next(25));
    allPoints.push(point);
}

const uniquePoints = [];

const start = new Date();

// Go through all points and add it to the list of unique points if the x, y, and z
// values have not been seen before
allPoints.forEach(p => {
    const key = p.x + '-' + p.y + '-' + p.z;
    if (!lookup.has(key)) {
        uniquePoints.push(p);
        lookup.add(key);
    }
});

const elapsed = (new Date()).getTime() - start.getTime();
log(`There are ${uniquePoints.length} unique points. Finding them took ${elapsed} ms`);

There are 11274 unique points. Finding them took 88 ms

[biwa]

Thanks, didn't think of doing it like that at all. Now my actual script finishes in finite time.