PDA

View Full Version : 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


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

make any performance difference over the following?


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:


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 themAny 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.


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/showthread.php?t=21845.

Trinithis
12-17-2007, 07:18 AM
I do like the way you code :D . . . 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 :DHaha, I'm glad :)
You got any other library-type code I could study?Probably. On what topic?

Trinithis
12-17-2007, 07:36 AM
Anything you've got. One could always learn more. If you want you can PM it to me. Or you could post it. Anyway, until later. Sleep beckons.

Twey
12-17-2007, 07:37 AM
It's likely all buried deep in the DD archives, my hard drive, and/or my brain. I'd need keywords to search it out from any of those sources.

Trinithis
12-17-2007, 05:53 PM
In that case, it's not that big of a deal. Perhaps I'll finish my 'elite' js game. I call it: Pacman: The Evil Alter Ego

Screenshot (http://img.photobucket.com/albums/v251/Trinithis/dynamicDrive/pacman.gif)

Twey
12-17-2007, 05:56 PM
404 :)

Trinithis
12-17-2007, 05:57 PM
Try again. I uploaded the wrong img the first time around.