Does javascript support numerically indexed arrays with a more optimized algorithm than an associative array?

Question

I know that Python, Perl, Java, Lua and obviously C (as it's the only array that's in ANSI standard afaik) support faster looking of numerically indexed arrays than doing a hash lookup or anything like that. Does Javascript also?

As an example in code of what I mean, in the case of Perl:

for(i=0;i<10;i++)
{
 # Do something
}

is slower than:

for (1..9)
{
 # do something else
}

or:

@var = (1,2,3)
foreach(@var)
{
 print $_; # look I'm fancy
}

and faster than:

foreach my $key (keys %hash) 
{
 print $_; # Look I'm fancy
}

and in python, given the following:

class thisClass:
 def methodOne(i):
 return i+1
thisDict = { 
 'number': 1
}

These two operations are similar in speed because both involve a hash lookup into a same-widthed hash:

thisObject = new thisClass
i = thisObject.methodOne(1)

and:

i = 1+thisDict['1'];

Both of these kinds of lookups are slower than this:

thisTuple = (1,)
i = thisTuple[0]+1

While this:

thisArray = [1,2]
for i in thisArray:
 print i

is iterated faster than:

thisTuple = (1,2)
for i in thisTuple:
 print i

by which I mean lists iterate faster than tuples.

Does Javascript support numerically indexed arrays differently than associatinve arrays? I don't believe Javascript supports more than arrays and associative arrays, but if it does how do they compare to the two speed wise?

• user7043: Your Python examples contain numerous errors (I can't judge the Perl examples as I know next to no Perl). (1) is not a tuple (1, or (1,) is). There is no difference in iteration speed between tuples and lists. thisObject is a class, so (in Python 2) thisObject.methodOne(1) will raise a TypeError. The key in thisDict is 'number', not '1'. Tuple indices start at 0, so the first element of thisTuple is thisTuple[0], not thisTuple[1].
• Nathan C. Tresch: @delnan, stackoverflow.com/questions/68630/… you're mistken. Sorry about the syntax errors. You're right, I didn't instantiate the object, because I assumed that everyone here would understand that obviously you'd have to instantiate that. Oh no, an index off by one mistake. I typoed and didn't catch it in my proofreading. So, you're wrong about one thing and you've pointed out a bunch of really small errors which do not detract from the intention of the question on a site that isn't supposed to be for overly technical posts. Thanks!
• Nathan C. Tresch: @delnan Okay, all better now. Thanks! Since you understood the meaning of all of the tiny errors, you realize you could have edited it also, and likely you would have taken less time to change the 4 characters than to type your comment, right? It's not that I don't appreciate it or anything.
• Nathan C. Tresch: @delnan You're right, the link just says that accessing is faster. The benchmarks I've run show that iterating is faster also, I woulnd't have posted it if I didn't have proof that it was at least true sometimes. Like I said, you could have fixed the rest of the errors in less time than it took to write that, so I'm not sure what you expect me to say other than "Thanks a lot for the book when you could have saved yourself time by correcting it and leaving a comment to see the edits." ;)
• user16764: Delnan, "and yes, I'm nitpicking, because I prefer nitpicking over misleading, broken examples (no examples would be fine too)." is a false dichotomy. As has been pointed out to you before, it would have been more constructive for you to take the third option of just editing the question.

Answer 1

JavaScript does not have any explicit way to specify that you want a normal array rather than an object--everything is an object by default. However, modern JavaScript engines have aggressive optimizations for objects that act like arrays. (Here is a good overview of what V8 does, for example.)

Modern JavaScript engines use "just-in-time compilation" (JIT). This means they optimize code based on how it's used at runtime. If the engine sees that an object is being accessed with consecutive numeric indices, it can optimize these into an array-like structure. However, this may take some time to take effect, which you should keep in mind if you want to write your own benchmarks.

Unfortunately, these are all optimizations that are not part of the language's semantics. This means that you cannot rely on any of them across engines. So if you're writing code that would benefit from array-like semantics, treat your objects just like normal arrays and be sure to profile on your target interpreter(s).

Additionally, for very specific use-cases, JavaScript has typed arrays. If you have raw binary data--like an array of ints or floats--you can take advantage of these typed arrays for storing, reading and writing them much more efficiently.

Unfortunately, you may have some issues with browser support of typed arrays. They have only been recently added to the proprietary browsers, so if you need to support IE <10 or Safari <5.1, you can't use them.

• supercat: From what I can tell, an array in JavaScript seems to be a combination of an object and a linear array. Whole-number keys get stored in the array, and everything else gets stored in the object. If one adds various things to an array in random order and then uses for, it will list out all the whole-number subscripts first, in numerical order, followed by everything else in the order added (including fractional numbers).
• Tikhon Jelvis: @supercat: That depends on which JavaScript implementation you use. It's not part of the standard, so you can't necessarily rely on it. It's probably true for most browsers at the moment, but they might change it in the future—after all, they changed to this implementation from just returning every key in the order it was added recently, I believe.
• supercat: Is it specified that slice() will copy all items with whole-number indices, and nothing else? I've noticed that calling slice on a very sparse array containing only a few elements can be very slow. If a non-array object is constructed which uses an array as a prototype, calling slice seems to include any whole-number-indexed items from the non-array object. I don't think there's any way to make an array which has anything else as a prototype, but I don't really know.
• Tikhon Jelvis: @supercat: I'm not entirely sure exactly how slice is defined in the standard, but I suspect you're right in that it has to work with all the whole-number keys. Perhaps it also depends on the length property of the array.
• supercat: Slice would also have to take the length of the array into consideration, since it encapsulates an aspect of state separate from the array contents; not sure how it should behave if a derived object defines length differently. I would guess that a typical implementation, writing foo[100000] would allocate an array of slightly over 100,000 elements (if one hadn't already been allocated), and that the length property of any array would be no greater than the length of the backing store, but I'm not sure what would happen if one called slice on a derived element...

Answer 2

Those tests seem to support the idea that there is some optimization in favor of arrays on most browsers :

Javascript Array Performance Oddities