Faster JavaScript StringBuilder

Ferreri Gabriele (Megasoft78)

3.74/5 (9 votes)

May 1, 2008

CPOL

3 min read

63982

265

A faster JavaScript StringBuilder

Introduction

I'm currently working with a complex AJAX control (Grid), and I have to concatenate a lot of strings (HTML) to render them on the client side with JavaScript.

In JavaScript, each string is immutable (like .NET), and this means that every time the engine concatenates a string using + or +=, it creates a new instance of string and disposes the old one. This, in some browsers (mainly Internet Explorer), makes the concatenation very slow. In other browsers like Mozilla Firefox or Safari, these concatenations are optimized before getting executed (JavaScript engine in Firefox 3 is absolutely amazing!!!).

Unfortunately, I have to support Internet Explorer 6 and Internet Explorer 7, and as everybody knows, this is a very big problem.

Background

Normally, to optimize string concatenation, Array and Array.join methods are used. In ASP.NET Ajax Framework 1.0, this approach is used in StringBuilder and performance is very good in Internet Explorer. The following code explains this approach:

    // The constructor initializes an Array
    StringBuilderEx = function()
    {
        this._buffer = new Array();
    }

    StringBuilderEx.prototype =
    {
    // This method appends the string into an array 
        append : function(text)
        {
            this._buffer[this._buffer.length] = text;
        },
        
    // This method does concatenation using JavaScript built-in function
        toString : function()
        {
            return this._buffer.join("");
        }
    };

We can optimize this class using a trick in JavaScript: every function call has a cost and we can use a function pointer to redirect append to push and toString to join:

    // Assigns our class to Array class
    var StringBuilderEx = Array;
    
    // Using prototype I link function append to push and toString to join
    Array.prototype.append=Array.prototype.push;
    Array.prototype.toString=Array.prototype.join;

It seems like very strange code, but it is very quick because we jump 1 function call for every append and 1 for every toString.

Using append alone to generate HTML makes the code very difficult to maintain. ASP.NET AJAX framework has an additional method that formats text similar to the C# format, which extends String (String.format). The following example shows the same string concatenation using append alone and with append and String.format together:

// It's very difficult to maintain
var sb = Sys.StringBuilder();
sb.append("<div style='width:");
sb.append(width);
sb.append("px;height:");
sb.append(height);
sb.append("px'></div>");

// It's more readable and easy to maintain
var sb = Sys.StringBuilder();
sb.append(String.format("<div style='width:{0}px;height:{1}px'></div>", width, height));

Unfortunately, the performance with String.format is very bad in Internet Explorer. I searched on the Internet for a way to do append and format with good performance, and I found some good examples. I combined them with some of my original ideas.

I implemented two solutions to have append and format together (appendFormat):

Using regular expression (syntax "Hello {0}! {1}"): Using this /\{(\d+)\}/g I search for all decimal numbers within { and }, and I use a function to replace the argument.
Using split and join (syntax "Hello ?! ?"): Using ? (Question mark) symbol to replace arguments, I just split once and join twice in the toString function.

    // Assign our class to Array class
    var StringBuilderEx = Array;
    
    // Using prototype I link function append to push
    Array.prototype.append=Array.prototype.push;

    // Used to convert arguments in array
    Array.prototype._convertToArray=function(arguments)
    {
        if (!arguments) 
            return new Array();

        if (arguments.toArray)
            return arguments.toArray();

        var len = arguments.length 
        var results = new Array(len);

        while (len--)
        {
            results[len] = arguments[len];
        }

        return results;
    };

    // First solution using regular expression
    Array.prototype.appendFormat=function(pattern)
    {
        var args = this._convertToArray(arguments).slice(1);
    
        this[this.length]=pattern.replace(/\{(\d+)\}/g, 
            function(pattern, index)
            {
                return args[index].toString();
            });
    };
     
    // Second solution using split and join
    Array.prototype.appendFormatEx=function(pattern)
    {
        if (this._parameters==null)
            this._parameters = new Array();
        
        var args = this._convertToArray(arguments).slice(1);
    
        for (var t=0,len=args.length;t<len;t++)
        {
            this._parameters[this._parameters.length]=args[t];
        }

        this[this.length]=pattern;
    };

    // Concatenate the strings using join 
    // (some lines of code are relay with second solution)
    Array.prototype.toString=function()
    {
        var hasParameters = this._parameters!=null;
        hasParameters = hasParameters && this._parameters.length>0;
    
        if (hasParameters)
        {
            var values = this.join("").split('?');
            var tempBuffer = new Array();
        
            for (var t=0,len=values.length;t<len;t++)
            {
                tempBuffer[tempBuffer.length]=values[t];
                tempBuffer[tempBuffer.length]=this._parameters[t];
            }
     
            return tempBuffer.join("");
        }
        else
        {
            return this.join("");
        }
    };

Using the Code

I wrote a custom class in JavaScript called StringBuilderEx that contains the following methods:

append: Append string
appendFormat: Append and format string using the same C# syntax ("Hello {0}")
appendFormatEx: Append and format string using a custom syntax ("Hello ?")
toString: Retrieve the concatenation of strings

// Sample
var sb = new StringBuilderEx();
sb.append("Hello");
sb.appendFormat("Hello {0}!!! {1}", "World", "Bye");
sb.append("Hello ?!!! ?", "World", "Bye");

Performance

I tested it on Vista with Internet Explorer 7:

Run Tests Append Strings (20000)...

Test concatenate strings with + : 17552 ms.
Test concatenate strings with Sys.StringBuilder (append): 667 ms.
Test concatenate strings with StringBuilderEx (append): 461 ms.

Run Tests Append Strings with Format (20000)...

Test concatenate strings with Sys.StringBuilder (appendFormat): 4204 ms.
Test concatenate strings with StringBuilderEx (appendFormat): 1658 ms.
Test concatenate strings with StringBuilderEx (appendFormat Split+Join): 1225 ms.

I also tested it on Vista with Firefox 3.0b5:

Run Tests Append Strings (20000)...

Test concatenate strings with + : 109 ms.
Test concatenate strings with Sys.StringBuilder (append): 211 ms.
Test concatenate strings with StringBuilderEx (append): 152 ms.

Run Tests Append Strings with Format (20000)...

Test concatenate strings with Sys.StringBuilder (appendFormat) : 1962 ms.
Test concatenate strings with StringBuilderEx (appendFormat): 770 ms.
Test concatenate strings with StringBuilderEx (appendFormat Split+Join): 497 ms.

Points of Interest

I don't know if this is the fastest StringBuilder (probably no), but actually it is quite fast with Internet Explorer 7 and FF3 (even more for Sys.StringBuilder), and this gives a big performance improvement in my grid. I hope this helps someone.

If someone knows of a way to have better performance, do not hesitate to contact me!

History

1^st May 2008 - First release
3^rd May 2008 - Fixed bugs and changed article