Augmenting native DOM array-like objects

[jkd]

I was inspired by this thread (http://www.codingforums.com/showthread.php?t=152936) to explore the possibility of augmenting DOM's array-like objects in non-IE browsers. This is what I have (and it works in Firefox, Safari, and Opera):


(function() {
var methods = ["indexOf", "lastIndexOf", "every", "some", "filter", "map", "forEach", "concat", "slice", "join"];
methods.forEach(function(method) {
if (window.opera) {
NamedNodeMap.prototype[method] =
HTMLOptionsCollection.prototype[method] =
HTMLCollection.prototype[method] =
NodeList.prototype[method] = Array.prototype[method];
}
else {
document.documentElement.attributes.__proto__[method] =
document.createElement("select").options.__proto__[method] =
document.links.__proto__[method] =
document.childNodes.__proto__[method] = Array.prototype[method];
}
});
})();


The question is, do you think something like this is useful in light of the big JS libraries? I personally enjoy the APIs that are available by default in the browser environment, so I don't understand the need to add layer after layer of abstraction away from them. Anyway, I'm just trying to provoke a discussion on the utility of such functions and argue that they put a dent in the utility of some of the JS libraries. With respect to IE, one can send instances of these constructors through the coerce(..., Array) function written in the linked thread to get similar capabilities.

[rnd me]

it reminds me of something i made this summer.

you may be interested in my custom library generator: oobuilder (http://www.danml.com/pub/lib/oobuilder.htm).
the builder only works in firefox (for now), but the resulting code packs can run anywhere.

it's like a hybrid of prototype and jquery.
-it lets you pick and choose the methods you need in your project.
-it has the methods and logic of prototype, but the non-intrusion of jquery.
-it is also custom-built; 4kb of overhead, then only the methods you need.


rather than upgrading all the prototypes, possibly polluting other code, you upgrade on demand.

for example, if you included .sum() from the math methods in your build,
var r = OO([1,2,3]);
alert( r.sum());//shows 6


it's targeted for mainly arrays, but you can do html collections as well.
it does a SIMPLE css query when you pass a string:

//example: make all divs appear bold:
OO("div").bold()

//hide all links:
OO("a").hide();

//hide all links with a title:
OO("a").screen("a.title").hide();



you can browse the API for OO here (http://www.danml.com/pub/lib/ooapi.htm)

feel free to plunder methods off of it if nothing else...

[jkd]

Sure, I like that over the implications of wrapping stuff in a jQuery object, for instance. (Who needs all bajillion methods when you might only be looking for a tiny bit of additional functionality, after all.)

But it is still involves wrapping the object, which means copying each and every property over. In IE, the developer has no choice; but my code demonstrates that you can get all of that for free, without polluting the more global Object.prototype...

Anyway, it's more food for thought than production-code, but I do think it is important to take a step back away from all the abstraction that most libraries are throwing at you. I think a mantra of "fix anything that needs fixing, but let people write code the way they want" needs to be adopted in the "AJAX" community. Mootools, Prototype, jQuery, Y!UI... imagine if those projects released tiny fixes and utilities for cross-browser issues, rather than monolithic libraries that tie you into their way of doing things.

[rnd me]

there seems to be momentum moving away from prototypes.

i don't understand why, i love them, but they are unpopular.
perhaps it's because people don't know how to iterate correctly.
(hasOwnProperty anyone?!?!?!?!?) grrrr...

but, given the sour mood i wrote OO.


i always try to argue for lighter footprints, so cheers to your idea of mini-libs!
$0.02

[Trinithis]

For what it's worth (and for people who don't know), you can achieve the same functionality using the call and apply methods:


Array.prototype.forEach.call(
document.getElementsByTagName("div"),
function(el) {
el.appendChild(document.createTextNode(el.parentNode.tagName));
}
);


Works in all browsers!!!

[jkd]

For what it's worth (and for people who don't know), you can achieve the same functionality using the call and apply methods:


Array.prototype.forEach.call(
document.getElementsByTagName("div"),
function(el) {
el.appendChild(document.createTextNode(el.parentNode.tagName));
}
);


Works in all browsers!!!

No, not in IE. That's why major libraries have some sort of coercion function to an array type. DOM-related objects in IE don't inherit from the JScript Object constructor, which borks native JScript method calls somehow.

Actually, you're right, but not for the right reasons. IE doesn't support Array.prototype.forEach, thus if that snippet does work, that means you have written your own version and hooked it up to the prototype. But that is no longer a native method, thus IE doesn't hiccup on it. If you try it on something like Array.prototype.slice, you'll find that it fails.


It's talked about in this thread (http://www.codingforums.com/showthread.php?t=152936). I think that ideally, array methods can be used on array-like objects directly; barring that, calling from the prototype is the next best. Unfortunately, neither of those is possible in IE (whereas they are both possible in reasonable browsers). Given that, I think I might prefer to call them directly as methods by boot-strapping the DOM prototypes above instead of the more verbose array prototype calls, and just coerce them to arrays for IE.

[Trinithis]

Yeah, sorry about that :D. I forgot to define it.

You made me boot into Windows to test my code...

About Array.prototype.slice, I remember IE not liking that.

[jkd]

Another thought:

1) IE8 still does not support native Array methods working on non-Object objects (e.g. DOM stuff)

2) IE8 *does* support NodeList, HTMLCollection, etc.

So, it would be possible to add these methods to the DOM's array-like structures in IE8, as long as we write them ourselves. Not hard, especially since the only useful native methods in IE, (slice, join, and concat) are easily duplicated in JS (and the others need to be written anyway).

The idea of writing:

element.childNodes.filter(function(node) { return node.nodeType != 3 }).forEach(function(element) {
blabla
})


instead of:

Array.prototype.filter.call(element.childNodes, function(node) { return node.nodeType != 3 }).forEach(function(element) {
blabla
})


appeals to me, since it is more in line with what I am thinking when I am trying to write the code to do what I want. (I feel like the JS mindset is OBJECT->VERB rather than VERB->OBJECT, by design.) The fact that this can work in IE8, Firefox 2+, Safari 3+, Opera 9+ is just wonderful too.

[Trinithis]

In the past, I would have preferred the terse way, but I've gotten used to calling on the prototype.

I just tested the JS 1.5 Array methods in both IE and FF on HTMLCollections. The following yield errors in IE. If a * is by it, the code fails in FF as well.

slice
pop *
push *
reverse
shift *
unshift *
join
toSource * (Non-standard)
toString *

[jkd]

I'm surprised concat() didn't raise an error. (Remember that [].concat(something) will return [[something]] instead of [something] if something is not an array... we would desire the latter case, however.)

An improvement on my code to take into account IE8 (this is assuming the array extras are defined somewhere else):

(function() {
var methods = ["indexOf", "lastIndexOf", "every", "some", "filter", "map", "forEach", "reduce", "reduceRight", "concat", "slice", "join"];
methods.forEach(function(method) {
if ({}.__proto__) { // Everything except IE, Opera
document.documentElement.attributes.__proto__[method] =
document.createElement("select").options.__proto__[method] =
document.links.__proto__[method] =
document.childNodes.__proto__[method] = Array.prototype[method];
}
else { // IE, Opera (will do nothing in IE<8 however)
var fun = Array.prototype[method];
if (window.NamedNodeMap)
NamedNodeMap.prototype[method] = fun;
if (window.HTMLOptionsCollection)
HTMLOptionsCollection.prototype[method] = fun;
if (window.HTMLCollection)
HTMLCollection.prototype[method] = fun;
if (window.NodeList)
NodeList.prototype[method] = fun;
}
});

if (IE8) { // need some real IE8 detection here
function array(obj) {
var arr = new Array(obj.length);
for (var i = 0; i < arr.length; i++)
arr[i] = obj[i];
return arr;
}

var patch = ["join", "concat", "slice"];
patch.forEach(function(method) {
NamedNodeMap.prototype[method] = HTMLCollection.prototype[method] = NodeList.prototype[method] = function() {
return Array.prototype[method].apply(array(this), arguments);
};
});
}
})();

[rnd me]

i think this is or should be the age old debate of javascript.

we would like to have it both ways: we don't want lookup pollution, and we don't want looping. i think it's going to have to be one or the other. the more recent trend is looping, specifically binding methods to objects upon their creation (decoration).

for example, using i don't think element.childNodes.filter is more compact than coding
$$("#element *").filter for example. coercion during the gathering phase makes some sense as well, giving us a kind of custom result to work with. throw in some fancy gathering control, and you see why jquery has taken off...

it's a scalpel, and prototypes are a hatchet.

i've always liked prototypes more.
i consider it "upgrading" the language itself.
If done well, it can signifigantly reduce the amount of code written later on.
the code built on top of prototypes looks more like javascript and less like a specific library.


are protos faster?
i don't know.
they are 2nd in line as far as resolution goes...
will tracing and JIT affect any performance differences going forward? probably.


here's a question for discussion:
what's the main advantage of moving these methods to the element prototype?

[jkd]

for example, using i don't think element.childNodes.filter is more compact than coding
$$("#element *").filter for example.

Not any more compact, sure. But that jquery-like statement is certainly going to be a lot slower, not to mention the future penalty of losing direct access to the DOM and directing everything through another abstraction layer.

As for namespace pollution, I would agree that adding to Object.prototype is second only to adding to the global namespace with respect to polluting the JS environment. However, adding directly to the array-like DOM objects I feel like is not pollution, since by and large we really want those objects to have these methods.

Moving them to the prototype has 3 big advantages, in my opinion:
1. No coercion (faster)
2. More concise code
3. Does not force a particular way of coding

In the very least, #1 should be something to think about.

[rnd me]

i am not sure what abstraction layer you mention. you get an array of dom objects with my examples, so that should be pretty fast. arrays might even be faster than collections. hmmm.

prototypes still pollute the lookup chain. you have to compare each one to the sought key. one-offing the methods (ala element.childNodes.ob.forEach) could avoid this problem at a slight penalty of code length.



Moving them to the prototype has 3 big advantages, in my opinion:
1. No coercion (faster)

In the very least, #1 should be something to think about.

counter point: css querys are native methods in all new browsers, so it should be much faster than a jquery search is now to get to the starting point. after that, i think performance should be comparable. decorating one result object with methods does not take very long in my testing. Arrays already have this stuff, so coercing a collection to an array gives us all this without the extra wrapper functions.


thank god that we have a language that permits this debate, and allow un-rivaled coding style flexibility.

i would like to see a final version of your code, or perhaps help with profiling.
It sounds really neat if it can work in all ecmaScript environs.
I started decorating my searches after giving up on IE protos...

i don't know if it's mentioned anywhere in the links i posted, but you can export the methods in my OO code to any prototype programatically. it handles all the applies and argument mapping automatically...

[jkd]

I'm only going on jQuery, but your example returns an array of jQuery objects, not an array of DOM nodes. See http://docs.jquery.com/Traversing/filter.

As for the penalty of proceeding up the prototype chain, it's going to be just as fast as calling the methods on an Array. So if calling filter() on an Array of DOM nodes if slow, then so would calling it on an HTMLCollection of DOM nodes. Somehow though, I don't think that is the case.

As for native CSS queries, there is a difference between traversing a linked list of nodes and compiling a string to a selector, executing it against the DOM, then returning an array of results, which still needs to be traversed! Native code behind it doesn't magically change the computational complexity, it only reduces the overhead by a constant factor at best.

Lastly, I iterate again that coercion will always be slower than a prototype lookup. If you need to copy n properties, then it is an O(n) process, whereas the prototype lookup is guaranteed to only traverse up the chain once before finding the property.

[Trinithis]

Isn't worrying about prototype chain lookup speed like worrying about function call overhead. In other words, isn't it negligible?

[jkd]

Isn't worrying about prototype chain lookup speed like worrying about function call overhead. In other words, isn't it negligible?

Yes. Even more, Array.prototype.filter.call(mycollection, function(el) {blabla}) requires 3 property lookups, whereas mycollection.filter(function(el) { blabla}) requires 1 property miss, followed by a property lookup (the prototype) and then another lookup (filter), so I'd wager they are about as fast as one another (though Google's V8 might prefer the former).

But you're right, I think the overhead of a prototype chain is insignificant compared to coercing an object by copying its properties; yet, even that is considerably fast, so the real question is what feels like better JS.

[rnd me]

Lastly, I iterate again that coercion will always be slower than a prototype lookup.


Nope, not true in my testing.

I usually use the following function coercing collections into arrays:

function obValsl(ob){var r=[],mx=ob.length;for(var z=0;z<mx;z++){r[z]=ob[z];}return r;}
function tags(elm,tid){var t="getElementsByTagName";if(tid){if(elm.charcodeAt){elm=el(elm);}return obValsl(elm[t](tid));}return obValsl(document[t](elm));};


all of your copied array methods are available to the result of the above function, even in IE.


after having enough of the unsupported arguing, I actually just ran tests in the big4 browsers.

here are the results:
//code:
//protos: var C = document.getElementsByTagName("div").map(function(a){return a.id;});
// tags: var C = tags("div").map(function(a){return a.id;});

//FF3:
// protos: [954,952,948,949,952,955,949,953,945,974].avg()//953.1
// tags: [913,908,912,909,911,942,926,931,918,918].avg()//918.8

//OP9.5:
// protos:[1404,1342,1357,1357,1357,1358,1341,1357,1342,1342].avg()//1355
// tags: [1607,1591,1514,1528,1529,1513,1514,1513,1529,1513].avg()//1535

//safari: 3.6
// protos: [1570,1546,1582,1568,1552,1557,1564,1537,1535].avg()//1556
// tags: [1536,1578,1480,1483,1485,1484,1492,1491,1486].avg()//1501

//IE7:
//protos: //NA
//tags //[4929,4867,4898,4882,4852,4867].avg()//4882

you can view the testpad here (http://danml.com/pub/perftest.htm)

you have to hand-edit to switch between test type, to be fair as possible.

the work load is simple, but it should reveal the difference between copying into an array vs using a mapped proto.

if you dispute the methodology, please help me to improve it.

I am surprised, i though protos would win hands down.
But they didn't, and in more browsers, the Array was faster.
Opera does seem to love your code though.

All in all, i think the diffs are more alike than different.

the main point should be that they are roughly comparable, usually under 10%.

everything else equal, i think my usual Array code is more compact, and it runs in IE to boot.


still a little surprised though...

EDIT: chrome results
note: these were run a different computer, so the numbers don't compare to above numbers, but they should be ok to compare against each other.

again we see the array coercion beating (slightly) the proto code in chrome.

//tags: [2398,2383,2380,2389,2386,2394,2392,2383,2393,2389]//2388
//protos: [2560,2511,2509,2516,2580,2497,2494,2498,2498,2505]//2516


one last thought:
i bet tracemonkey will eat up my loopy obValsl function, so perhaps mine has a lot more room to grow...

[jkd]

I'm getting Opera running my prototype-based lookup roughly 9-10% slower, where Firefox 3 (not 3.1) gives it a 15-20% faster, Safari 3.2 is 45-50% faster, and Google Chrome anywhere in between 1-50% (!!!) I'm a little puzzled by Opera, but everything else is expected.

[rnd me]

I'm getting Opera running my prototype-based lookup roughly 9-10% slower, where Firefox 3 (not 3.1) gives it a 15-20% faster, Safari 3.2 is 45-50% faster, and Google Chrome anywhere in between 1-50% (!!!) I'm a little puzzled by Opera, but everything else is expected.

are you using the same test? what are you comparing it to? jQuery or my Array coercion? Are you using linux or mac os?

how can you get across-the-board opposite results? even opera is inverse for both of us! my results were a lot more tightly nested as well...

i would like to examine your test setup.
like Reagan said: trust but verify.

i just cannot for the life of me understand how everything could be the opposite on your setup!

heh, I can see why you like the proto code!!! (jk)

[jkd]

i would like to examine your test setup.
like Reagan said: trust but verify.

i just cannot for the life of me understand how everything could be the opposite on your setup!


www.jasonkarldavis.com/bench.html

Short of doing a null hypothesis test on the difference of means, I did print out values representing a 95% confidence interval around the time it takes to execute a single map operation (in ms). Positive percent differences favor prototype, negative favors array.

[rnd me]

okay, had a chance to test things.

nice testing rig by the way...

i ran your page though my browser cycle on permanent press and got slightly tighter though approx results as what you reported.

This was confusing to me; hadn't i just run a test doing basically the same thing? with opposite results?

after digging into the benchmark code a little, i downloaded it onto my own server to make some adjustments.

i wanted to move to a real-world content model (W3 HTML4 form spec),and a few minor changes as detailed below for completeness, though it's nothing that should affect the outcome:


//no need for uncertainty, also might reduce cpu caching/prediction advantages to toggle...
switch (Math.round(Math.random())) { //TO:
switch ( i++ % 2) {

//a little more room between calls, perhaps a little garbage collection...
setTimeout(arguments.callee, 25); //TO:
setTimeout(arguments.callee, 295);

//i am impatient...
if (pTimes.length > 40 && aTimes.length > 40) //TO:
if (pTimes.length > 30 && aTimes.length > 30)
aTimes.length) / 40 * ... //TO:
aTimes.length) / 30 * ...

//a shortcut so i can run my own numbers later...
window.times=({p: pTimes, a: aTimes});




ok. so i got a version i was totally happy with.
I was wondering if the real world content would make a diff.
it seemed to slightly tighten the results, but nothing super-significant.


still puzzled and most intrigued, i delved into the code.
I found what i believe to be a most important consideration.
your prototype version got to run on a pre-existing collection,
but the array version had to be created from scratch each time.
it started off of the shoulders of the version fed to the prototype one, thus it did a lot more work per call.

I am most interested in real world, so i thought the most realistic approach would be to gather each collection inside each bench function before the loop. after all, we aren't going to be doing hundreds of thousands of the same things over and over on the exact same set...
gathering the set each time seems more realistic.

this seemed to cause an error in firefox somehow. what was most strange was that the error popped-up during the test, somehow it broke mid-test!
I can't understand that one at all, perhaps a stack/buffer thing, i don't know...

details:
//when trying to gather each time:
function benchPrototype() {
var start = new Date();
for (var i = 0; i < 5000; i++){
var divs = document.getElementsByTagName("div");
divs.map(function(el) { return el.nodename });
}
return ((new Date()) - start) / 5000;

}

ERROR (@ 86.67% done... )
divs.map is not a function bench.html (line 94)
divs.map(function(el) { return el.nodename });


\n\

That not working, i figured that the next best thing would be to give each bench function it's own object. i would use the function i posted (and usually use) to gather an array, and the prototype version would use a pre-built collection, as it did before:

// update global reference
divs = document.getElementsByTagName("div"); //standard js
divs2 = tags("div"); //my function


the results, are quite different that what you report and i initially found:

version used (http://danml.com/pub/bench.html)for results below:

//resuts on pre-gathered objects:
FF 3.0:

Time for prototype lookup: (0.281,0.331)
Time for array lookup: (0.161,0.299)
Percent difference: -33.12%


Opera 9.62:

Time for prototype lookup: (0.390,0.406)
Time for array lookup: (0.145,0.153)
Percent difference: -166.56%


Safari 3.2:

Time for prototype lookup: (0.337,0.345)
Time for array lookup: (0.106,0.112)
Percent difference: -211.76%


Chrome:

Time for prototype lookup: (0.648,0.656)
Time for array lookup: (0.098,0.104)
Percent difference: -542.73%


Chrome was a different computer so don't cross-compare.
if Chrome JIT is an indicator of tracemonkey, things are looking good for my array version.

i still think gathering each time would be more realistic. i expect roughly comparable performance between the two under those conditions...


one final caveat: http://danml.com/pub/benchaccident.htm
during my testing, i accidentally created a version with two identical bench functions: both array and prototype versions contain the exact same code; the prototype version specifically. For unexplainable reasons the "prototype" version of the identical function was 15-25% faster. i tried flipping the switch statements, same thing; prototype won consistently. i don't understand that one at all.


______________
scripting aside, i just want to say that this has been an enjoyable thread, much more engaging (for me anyway) than "validation help (URGENT!)" type threads. thanks for giving me something to really think about...

[jkd]

The reason for gathering only once was to specifically test how long it takes to iterate through the collection, as that is where the performance of either method was called into question. If getElementsByTagName() dominates either of our methods in time, then you're not going to get an accurate measure of how quickly we can iterate.

Also, I admittedly I don't know much about the optimizations of a JS interpreter, which is why I randomly selected a method to bench in order to avoid branch prediction. (I doubt that is somehow any problem though.)

And if we're actually concerned with real-world performance, then note that either method takes fractions of a single millisecond to compute one way or another. :) I'm definitely convinced that type coercion isn't (practically) slow.