JS array implementation?

**Trinithis** · 12-17-2007, 05:33 AM

Does anyone know how js arrays are implemented? Are they like maps, linked lists, java arrays, or what? Or perhaps different browsers implement them in different styles?

My guess is that they are map-like because of the ability to dynamically add properties to objects. But still, I would like to know how it works.

Also, let's say you are making an array of length 10. Based on its implementation, would

Code:

var a = new Array(10);
for(var i = 0; i < 10; ++i)
  a[i] = i;

make any performance difference over the following?

Code:

var a = [];
for(var i = 0; i < 10; ++i)
  a[i] = i;

[].shift() vs [].pop() speeds also come to mind.

**Twey** · 12-17-2007, 06:11 AM

Arrays are just objects with some setters and getters for numerical properties. The number you use in the square brackets is converted to a string; if 1 were a legal identifier, you'd be able to do [1, 2, 3].1.

Based on its implementation, would [pre-declaring the array's length] make any performance difference ...?

Depends on the implementation. If I remember correctly, in Spidermonkey no: it just sets the length. It wouldn't be unthinkable that the implementation could create the appropriate properties as well, though.

**jscheuer1** · 12-17-2007, 06:11 AM

The two declaration methods are equivalent. There might be minor speed issues. Only with huge arrays could these amount to any appreciable matter.

I think pop() has been around longer and isn't as versatile.

Something you alluded to, but didn't come right out and say is that arrays may have properties assigned to them, ex:

Code:

var a = new Array(10);
for(var i = 0; i < 10; ++i)
  a[i] = i;
a.someProp=document.images[0];
a.anotherProp='orange';

Which I've often made extensive use of, as it can come in quite handy at times.

**Twey** · 12-17-2007, 06:14 AM

Something you alluded to, but didn't come right out and say is that arrays may have properties assigned to them

Any object can have properties assigned to it. Generally you'd be better off using an Object or a user-defined Hash object, since ECMAScript arrays are really designed for numerical keys, and adding properties might break some things (for..in for instance).

**Trinithis** · 12-17-2007, 06:17 AM

Thanks for the replies. I mainly just wanted to make sure that shifting an array wouldn't cause all the overhead that non-associative arrays have to deal with. Same for other methods that could be time-consuming unless handled properly.

Edit:
Whoops! Nevermind. Shifting and unshifting do come at a performance cost. Still fast if the array length is less than 1000.

As for hashes, I've seen stuff like an array/ordinary object that keeps track of the keys along with indices so it can be iterated w/o a for-in loop. It's always fun to see how people do things in different ways though for learning experiences.

**Twey** · 12-17-2007, 07:11 AM

Yes, see this thread: http://www.dynamicdrive.com/forums/s...ad.php?t=21845.

**Trinithis** · 12-17-2007, 07:18 AM

I do like the way you code

. . . Hopefully I'm getting there . . .

You got any other library-type code I could study?

**Twey** · 12-17-2007, 07:32 AM

Whoops! Nevermind. Shifting and unshifting do come at a performance cost.

Yes they do, since all the elements of the array must be rearranged. This would be more efficient were the array implemented as a linked list, but at the cost of performance elsewhere.

I do like the way you code

Haha, I'm glad

You got any other library-type code I could study?

Probably. On what topic?