Quiz series: Micro JavaScript / How _not_ to copy arrays

[Prototype | http://prototype.conio.net/] library has a wonderful function named $A. Btw, funny enough phenomena with naming convention used for global functions in Ajax libraries – if it is soooo global and useful then it deserves a

😉 Ok, $A is really useful, personally, I’d added several more

to it.

Prototype library intensively used so-call parameter binding (or “curling”). I’ll discuss this in later post, but for now just imaging the following: if function receives less arguments then expecting, it returns function with same behavior but with shorter arguments list while part of parameters are “bound” to original argument values:

function mult() {
 switch (arguments.length) {
 case 0: return mult;
 case 1:
 var a = arguments[0];
 var mult_by = function() {
 return arguments.length ? a * arguments[0] : mult_by;
 };
 return mult_by;
 default: return arguments[0] * arguments[1];
 }
}

var a = mult( 19, 77 ); // 1463
var b = mult( 8, 9); // 72
var twice = mult(2); // mult with first parameter bound to 2
var c = twice(14.5) // 29

Hope you got the idea. So Prototype uses this technique intensively, but actual implementation is slightly different. Sure, it’s done in more generic manner. And to support this “generic manner” it’s necessary to clone original arguments of function to Array, modify it and further pass to “curled” nested function via Function.apply.

However, when I read the code for $A function I was shocked. It’s hard to imaging more inefficient implementation:

var $A = Array.from = function(iterable) {
 if (!iterable) return [];
 if (iterable.toArray) {
 return iterable.toArray();
 } else {
 var results = [];
 for (var i = 0; i < iterable.length; i++)
 results.push(iterable[i]);
 return results;
 }
}

First line is obvious – if we pass something that do not evaluates to true (null, undefined, empty string (?), zero(?), NaN(?) ) we just return empty array. Next is obvious too: if object supports own method to get array we use it. The broken code is actually “manual” copying of array-like objects.

“Array-like” is term used to describe JavaScript object that walks and quacks like Array: they have integer-indexed properties and a length property that describes number of indexed properties.

If you’ve ever been on other side of JavaScript, i.e. you’ve created own host objects for Rhino or SpiderMonkey interpreter, you may share my frustration. See, any “array-like” has length property, so we (or they, Prototypers) know size of result in advance. We can use Array(size) constructor to allocate necessary memory for result only once and then just set every element by index, instead of pushing elements one by one and resizing array with every operation. Do I need to clarify what is more efficient? I bet no…

But the inefficiency doesn’t end here. The way original iterable is iterated is an example of bad coding as well.  Think, how many times iterable.length is calculated in loop? One? You are kidding, this is not binary code compiled by C compiler! iterable.length is calculated iterable.length times. Plain dumb. And final performance hint: iteration works faster for Aray if it is done in reverse order. Don’t ask me why – it simply works this way. You can find plenty of related tests with Google. And for logic of this code block, iteration order doesn’t matter. So, final result is:

var $A = Array.from = function(iterable) {
 if (!iterable) return [];
 if (iterable.toArray) {
 return iterable.toArray();
 } else {
 var cnt = iterable.length;
 var results = new Array(cnt);
 for (var i = cnt - 1; i >= 0; i--)
 results[i] = iterable[i];
 return results;
 }
}

Readable/Explicit/Simple? Yes. Yes. Have the same size? Yes. And far more efficient.

Oh, the quiz question. Just for academic interest, how many chars are necessary to copy “array-like” object to JavaScript Array? Efficiency aside 😉 Given:

var a = ;

var b = <expression>;

alert(“Size: ” + b.length + “\n” + b.join(“\n”));

Your turn!