FStringCat - Even Faster String Concatenation!

StringCat was fast, but just not fast enough!

The problem with StringCat was that it did not take advantage of the very high speed of the built in string concatenation method for short string in JScript. With a small change, this can be corrected with a huge speed up.

The trick is to put an accumulator in the concatenator. Built in concatenation is used to add to the accumulator until it hits a 'magic' size, then the accumulator's contents are added to the linked list and the accumulator reset:

    var accum='';
    this.push=function(what)
    {
        accum+=what;
        if(accum.length>2800)
        {
            if(typeof(sp)=='undefined')
            {
                ep=new Array();
                sp=ep;
            }
            else
            {
                var oep=ep;
                ep=new Array();
                oep[1]=ep;
            }
            ep[0]=accum;
            accum='';
            ++l;
        }
    }

The first question with this set-up is what size to set the accumulator maximum (the point beyond which it is reset). To find a good approximation for this, I set up a little test. The test is specific to the hardward, JScript version etc, but it is better than nothing. I timed the concatenation of one hundred thousand short strings with different accumulator sizes. The results are in the following graph:

From this graph we can see that the optimum is between 10^3.3 and 10^3.6; I therefore chose a value of 2800. This gives a very large performance increase indeed compared to the original StringCat:

As always, here is the source (you can also get it from www.nerds-central.com

function FStringCat()
{
    var sp;
    var ep;
    var l=0;
    var accum='';
    
    this.push=function(what)
    {
        accum+=what;
        if(accum.length>2800)
        {
            if(typeof(sp)=='undefined')
            {
                ep=new Array();
                sp=ep;
            }
            else
            {
                var oep=ep;
                ep=new Array();
                oep[1]=ep;
            }
            ep[0]=accum;
            accum='';
            ++l;
        }
    }
    
    this.toString=function()
    {
        if(l==0)return accum;
        ep[0]+=accum;

        while(l>1)
        {
            var ptr=sp;
            var nsp=new Array();
            var nep=nsp;
            var nl=0;
            
            while(typeof(ptr)!='undefined')
            {
                if(typeof(nep[0])=='undefined')
                {
                    nep[0]=ptr[0];
                    ++nl;
                }
                else
                {
                    if(typeof(ptr[0])!='undefined')nep[0]+=ptr[0];
                    nep[1]=new Array();
                    nep=nep[1];
                }
                ptr=ptr[1];
            }
            sp=nsp;
            ep=nep;
            l=nl;
        }
        return sp[0];
    }
}