Faster data access in javascript; for loop and if statement vs deep multidimensional arrays

Question

I'm building a data structure for storing tile data from isometric maps. I'm currently using a multidimensional array with 3 axis.

var tile = tilesArray[X][Y][Z];

I'm wondering if it would be faster to use a for loop to find data

tilesArray[i] = tileObject

function getTile(x, y, z) {

    //loop through the tiles till we find the right one
    for (var i = 0; i < tilesArray.length; i += 1) {

        //grab the tile
        var tile = tilesArray[i];

        //check the tile position to see if it is the one requested
        if (tile.position[0] = x && tile.position[1] = y && tile.position[2] = z) {
            return tile;
        }   
    }

    //if the tile is not found and we fall out of the for loop return false
    return false;
}

So to recap

var tile = tilesArray[X][Y][Z];

vs

var tile = getTile(x, y, z);

[ jsperf.com ] - but in general, the array access will always be faster here, since there is no function call overhead. — jAndy
– jAndy, Commented Jun 10, 2011 at 10:02

Miquel · Accepted Answer · 2011-06-10 10:58:51Z

1

If there will be mostly random access and a lot of gaps then you could encapsulate an associative array looking like this

var store = {};

function setTile(x, y, z, tile) {
    k = x*1000000 + y*1000 + z;
    store["K" + k] = tile;
}

function getTile(x, y, z) {
    k = x*1000000 + y*1000 + z;
    return store["K" + k];
}

setTile(1, 7, 5, "1-7-5");
alert (getTile(1,7,5));

It is not as fast as the multidimensional array, but it is definitely faster than iteration and an space saver in comparison to the array.

The example would support indexes up to 999 though

answered Jun 10, 2011 at 10:58

Miquel

4,8493 gold badges22 silver badges19 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Robert Hurst Over a year ago

I think I will use this in another system. I can't use it for the tiles as indexes could end up in the 100k. Its a good idea though.

Raynos · Accepted Answer · 2011-06-10 10:57:02Z

0

Benchmark

The object is 2/3 times as slow in chrome 12.

The object is 1000 times slower in firefox 4. (Basically arrays are really fast in FF4, about a 1000 times faster then chrome)

Becuase the Object is nice and OO and doesn't involve having a 3 dimensional array with a LOT of gaps I would recommend using it as its just generally a better way to store data.

edited Jun 10, 2011 at 10:57

answered Jun 10, 2011 at 10:10

Raynos

170k57 gold badges359 silver badges399 bronze badges

4 Comments

Robert Hurst Over a year ago

but would it be a serious problem if I'm accessing the data a lot? I need to be able to do this ~1000 times a second for path finding.

Raynos Over a year ago

@RobertHurst Depends are the tiles moving around? You could cache or memoize the get function if the position is static.

Raynos Over a year ago

@RobertHurst if you run the test in FF4 you'll see FF4 is optimised to hell for array access so that completely changes things.

Robert Hurst Over a year ago

Interesting. I realize Its not an easy question to answer but I appreciate the insight. Thank you.

Seldaek · Accepted Answer · 2011-06-10 10:02:02Z

0

Direct array access is the fastest you can get in most languages I think, especially when compared to a loop + function call. No offense, but this sounds like a bad idea :) Keep it as is.

answered Jun 10, 2011 at 10:02

Seldaek

42.3k10 gold badges100 silver badges78 bronze badges

2 Comments

jAndy Over a year ago

unfortunatly, Javascript has no real Arrays and it's not as fast as array access in other c-like languages. However, it'll still be faster in this situation.

Seldaek Over a year ago

Yeah I'm not implying it's the fastest way across all languages, but for the use case at hand, and especially the proposed alternative, it sounds much better.

Miquel · Accepted Answer · 2011-06-10 10:08:06Z

0

It depends on the type of access you will do really. Will it be mostly insertions and then sequential access? Then the linear storage such as linked list with a access function might be better.

Will be mostly individual random access? then array access is definitely fastest.

answered Jun 10, 2011 at 10:08

Miquel

4,8493 gold badges22 silver badges19 bronze badges

Comments

Martin Strandbygaard · Accepted Answer · 2011-06-10 10:51:09Z

Array indexing is approx. 3 times faster, using the test below and executed in node.js (Google V8 engine). It indexes the same element. You definitely want to try indexing random elements to get a better feel for how they compare.

var tilesArray = createTileArray();

function createTileArray()
{
    var rank = 1000;
    var start = new Date();

    // Define
    var ar = new Array(3);

    // Create
    for (var i=0; i < 3; i++)
    {
        ar[i] = new Array(rank);

        for (var j=0; j < rank; j++)
        {
            ar[i][j] = new Array(rank);
        }
    }

    // Fill
    for ( var i = 0; i < 3; i++) {
        for ( var j = 0; j < rank; j++) {
            for ( var k = 0; k < rank; k++) {
                ar[i.valueOf()][j.valueOf()][k.valueOf()] = 3;
            }
        }
    }

    var end = new Date();

    console.log("Created array in: " + (end-start) + "ms");

    return ar;
}

function getTile(array, x, y, z) {

    // loop through the tiles till we find the right one
    for (var i = 0; i < array.length; i++) {

        // grab the tile
        var tile = array[i];

        // check the tile position to see if it is the one requested
        if (tile[0] === x && tile[1] === y && tile[2] === z) {
            return tile;
        }   
    }

    // if the tile is not found and we fall out of the for loop return false
    return false;
}

function arrayIndexing(array, loopCount)
{
    var start = new Date();

    for (var i = 0; i < loopCount; i++) {
        var elem = array[1][2][3];
    }

    var end = new Date();
    console.log("Array indexing in: " + (end-start) + "ms");
}

function loopIndexing(array, loopCount)
{
    var start = new Date();

    for (var i = 0; i < loopCount; i++) {
        getTile(array, 1, 2, 3);
    }

    var end = new Date();

    console.log("Loop indexing in: " + (end-start) + "ms");
}

var loopCount = 1000000;

arrayIndexing(tilesArray, loopCount);
loopIndexing(tilesArray, loopCount);

That only really tests Chrome though. Firefox 4 is a 1000 times slower whereas Chrome is 2 times slower.

Collectives™ on Stack Overflow

Faster data access in javascript; for loop and if statement vs deep multidimensional arrays

5 Answers 5

1 Comment

4 Comments

2 Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

1 Comment

4 Comments

2 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related