Javascript: indexOf slow on high index despite sparse array?

Question

While running some tests on my site, I ended up with an array that has only 10 String in it, but one with a very high index (600 000 000).

Running indexOf on this array is very slow, making the whole tab freeze for several seconds for each call.

When I tried looking for information about this, most seemed to be saying that modern Javascript implementations use sparse array and that it shouldn't be a problem. I'm using the latest Chrome 62.

The issue is actually reproducible just in the Developer Tools' console. If you try running the following code :

test = [];
test[600000000] = "test";
test.indexOf("test");

You'll see that the console takes several seconds to return the index, indicating that Javascript is looping through every index from 0 to 600000000 rather than skipping directly to the one element. Is this normal behavior?

The function still needs to investigate every single index. There may be some time in the future when JavaScript runtimes deal with this situation, but they don't at present. — Pointy
– Pointy, Commented Dec 6, 2017 at 0:26
@moon No relation whatsoever. The link is about finding the index of an object. — ibrahim mahrir
– ibrahim mahrir, Commented Dec 6, 2017 at 0:27
It seems to me like the ECMAScript spec gives the same algorithm for each, incrementing the loop variable by 1 up to length and accessing each property of the object. Why would includes be faster? When I invoke them on a Proxy they both behave as documented, accessing each property counting by 1. — Josh Lee
– Josh Lee, Commented Dec 6, 2017 at 2:05

dave · Accepted Answer · 2017-12-06 00:30:17Z

6

I'm not sure if this is "normal" behaviour, but an easy replacement would be:

function sparseIndexOf(arr, value) {
    return Object.keys(arr).find(function(k) {
        return arr[k] === value;
    })
}

test = [];
test[600000000] = "test";
sparseIndexOf(test, "test")

answered Dec 6, 2017 at 0:30

dave

65.1k6 gold badges81 silver badges98 bronze badges

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

1 Comment

ibrahim mahrir Over a year ago

Clever workaround. Object.keys will return an array of indexes that actually hold a value (in this case wil return ["600000000"]), so it won't be expensive.

Collectives™ on Stack Overflow

Javascript: indexOf slow on high index despite sparse array?

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related