[SVN] r3879 (TextMate)

[Allan Odgaard]

On 28/6/2006, at 14:46, James Edward Gray II wrote:

> On Jun 28, 2006, at 5:01 AM, Allan Odgaard wrote:
>> • use ‘<<’ instead of ‘+=’ when appending to strings, as the  
>> former is magnitudes faster
> Until GC is triggered...  ;)

I think the problem is that << is a native String method and will  
append to the string using an exponential growing buffer, so if we do:

    1024.times { str << 'a' }

It does log2(1024) re-allocations and full copies of the string.  
Resulting in 10 reallocations and 2048 bytes copied in total.

Though += is not a native string method, so doing:

    1024.times { str += 'a' }

Is equivalent to:

    1024.times { str = str + 'a' }

Here we do 1024 reallocations (one in each iteration), and thus copy  
the entire string as well, resulting in (1024*1023)/2 or 523,776  
bytes copied in total.

So the first is O(n) in the size of the resulting string, where the  
latter os O(n^2).