Saturday, June 21, 2008

Lazy developers, Stack concept, and the fastest, unobtrusive, JavaScript StringBuilder

Fast Web, and lazy developers


About 1 month ago, I have posted a little piece of code that, in some way, could be a little revolution for JavaScript 3rd edition, and every kind of library.
I explained how to use native Array methods with an object, to extend Array itself, or simply create a Stack behaviour, compatible with every used browser.
Few comments a part, in both Ajaxian and this site, it seems that nobody had enough fantasy to use that tricky piece of code to create every kind of Stack based constructor, library, or Iterator, without destroying the native Array.prototype. So, here I am, with another little piece of code that uses the same Stack concept to create a StringBuilder constructor.

The Fastest Unobtrusive JavaScript StringBuilder


A common problem with JavaScript and, specially, Internet Explorer, is string concatenation.
You can find every kind of benchmark, even in IEBlog, about string concatenation problems.
IE Team seems to suggest the usage of an Array, because it is much faster than plus operator, i.e.

"a" + "b" + "c"
// slower than
["a", "b", "c"].join("")

Different libraries, and different developers, use daily a StringBuilder like constructor, to perform string concatenation and finally create resulted string.

You can find different implementation, and someone is better for some feature than another one, but every implementation is not using the Stack constructor trick:

function StringBuilder(){
// (C) Andrea Giammarchi - Mit Style License
if(arguments.length)
this.append.apply(this, arguments);
};
StringBuilder.prototype = function(){
var join = Array.prototype.join,
slice = Array.prototype.slice,
RegExp = /\{(\d+)\}/g,
toString = function(){return join.call(this, "")};
return {
constructor:StringBuilder,
length:0,
append:Array.prototype.push,
appendFormat:function(String){
var i = 0, args = slice.call(arguments, 1);
this.append(RegExp.test(String) ?
String.replace(RegExp, function(String, i){return args[i]}):
String.replace(/\?/g, function(){return args[i++]})
);
return this;
},
size:function(){return this.toString().length},
toString:toString,
valueOf:toString
}
}();

Above constructor is fast as is Array one, when you use them to push values inside the stack. In few words, there's nothing faster to do this simple task, than a native method as push is.

var str = new StringBuilder("a", "b", "c");
str.append("de", "f");
alert(str.length); // 5
alert(str.size()); // 6, the length of the string
alert(str); // abcdef

You can use a StringBuilder instance inside append method without problems, as you can use plus operator to simply create a String, even if it does not make sense

alert(new StringBuilder("abc") + new StringBuilder("def"));
(str = new StringBuilder("abc")).append(new StringBuilder("def"));
alert(str);

Finally, you can use a simplified version of the appendFormat method too:

alert(
new StringBuilder("a", "b", "c").
appendFormat("{0}{1}{0}", 0, 1).
appendFormat("???", 1, 2, 3)
);
// abc010123


What's next?


We can use Stack and/or ArrayObject constructors, or concepts, to literally create every kind of FILO/LIFO/LILO/FIFO based constructor, and without modifying the native Array.prototype.
It is simply up to you, but what I am already working over is:

  • a generic Collection constructor, with predefined Type (new Collection(Person), to have a Collection of Persons, for example)

  • a Matrix manager, which aim is to become the fastest one, with JavaScript

  • something else ... so please, stay tuned ;)

8 comments:

Michael (iSkitz) said...

Hey Andrea,
At it again I see ;-) Great!

So I just read your post and although I haven't fully absorbed your accomplishment looks like you've created a very useful piece of code. Thanks!

I followed your link back to your Ajaxian post then looked at your test bench page. I suspect that you haven't received the kind of attention or seen the kind of adoption you might expect for such a clever solution because:

1. It's very low-level as in assembly vs. java in today's widget and GUI manipulation library environment. Only hardcore JavaScript developers would probably be interested and they'd definitely be the only ones capable of appreciating what you achieved.

2. Even hardcore developers need easy to read data showing why your creation is so important. The test bench for example isn't as informative as you may like. I for one wasn't sure what the numbers I saw meant, and looking at the page's JavaScript to try to better understand didn't help since the code was minified. I suspect "pretty" graphs or tables is not in your area of interest ;-) but I think 1 or two might go a long way to help people appreciate your work.

3. I think a demonstration of the problem and how your code solves it would really drive the significance home.

I read your blog often and know you're a gifted programmer, perhaps with a bit more gloss your work can attract the kind of attention it deserves! I'm definitely looking forward to your generic Collection constructor. I've created one in the past myself, but never focused on it's performance, so seeing yours will be insightful!

Anonymous said...

It seems smart. Congratulations!

Andrea Giammarchi said...

Cheers Michael (and anonymous too)
As you know, I write more code for develpers than for surfer, and that is why I do not use to make my presentations rich, elegant, styled, or something else may be cool, but for my target probably superfluous.

At the same time it is the second comment I receive about "ugly demos", so I suppose you are definitively right :D

The Collection is more simple than you think, but it will be fast enough, and strict (types / classed check)
Maybe it will not be fast with the append method, but it will be fast enough with sort, reverse, and every other useful Array prototype ;)

Mega69 said...

Good work, however by doing some benchmark tests I noticed that string concatenation is faster than join concatenation in Firefox and Opera; besides join concatenation is faster in IE only when the string to build is quite big; the IEBlog says:
"Not only is the code simpler, but it is also much faster for this case. When the number of values being concatenated is small enough the concatenation operator still wins. You’ll have to do performance testing when you choose this approach and make sure it fits your algorithm."

In other words I think that the performances of a StringBuilder are relative.

Andrea Giammarchi said...

Hi Mega :)
Obviously I did not write an example with 100 concatenations, and the point of this post is that a lot of developers use a StringBuilder like constructor, but nobody uses the Stack trick to make them faster and unobtrusive.

As I wrote in that blog long time ago, the fastest way ever is the method concat, but it creates a new string, so its purpose cannot be the same of a StringBuilder.

Finally, we need a StringBuilder exactly in those case where we concatenate a lot of informations, otherwise it does not make sense to have a dedicated constructor to do something like:

(str = new StringBuilder("a")).append("b");
alert(str)

do you agree? :)

Mega69 said...

I agree with you about the fact that we should use StringBuilder only when there's a huge number of concatenations.

However your class is useful mainly in Internt Explorer, other browsers optimize the concatenations in order to achieve similar results.

Andrea Giammarchi said...

Other browsers will be fast enough, and the aim is to use one reasonable fast way for every browser.

If we choose to use a StringBuilder, it does not make sense to write code twice, one for other browsers, one completely different for IE.

But this is only a possibility, and the problem is that if you look for a StringBuilder constructor, the faster one extends native Array without a reason. (so again, the point of this post is another one :D)

Anonymous said...

Lots of good reading here, many thanks! I had been researching on yahoo when I observed your article, I’m going to add your feed to Google Reader, I look forward to more from you.