Speeding up string concatenation

Forums for specific tips, techniques and example code
User avatar
BeeJay
Posts: 312
Joined: Tue Jun 30, 2009 2:42 pm
Location: Christchurch, NZ

Speeding up string concatenation

Postby BeeJay » Thu Jan 27, 2011 8:41 am

Something that is not immediately intuitive is that when doing string concatenation with the value returned from a method call, it's actually faster to store the result of the method call into another local variable first, rather than directly concatenating the result of the method call directly onto the local variable. It's also much faster to use local variables for the concatenation rather than concatenating onto on object property.

Consider the following three code snippets:

Code: Select all

// Option 1 foreach object in someCollection do str2 := object.someMethodThatReturnsAString(); str1 := str1 & str2; endforeach;

Code: Select all

// Option 2 foreach object in someCollection do str1 := str1 & object.someMethodThatReturnsAString(); endforeach;

Code: Select all

// Option 3 create c1 transient ; foreach object in someCollection do c1.slob := c1.slob & object.someMethodThatReturnsAString(); endforeach;
Running this code with a relatively small string value being returned shows the following timings for each of the three code examples:

Code: Select all

Iterations Option 1 Option 2 Option 3 5000 9ms 300ms 499ms 10000 16ms 1461ms 3284ms 15000 27ms 5265ms 10463ms 20000 32ms 10174ms 23663ms 25000 40ms 16386ms 39234ms 30000 47ms 24329ms 60821ms 35000 55ms 34375ms 88573ms 40000 66ms 46343ms 120791ms 45000 84ms 65103ms 188288ms 50000 94ms 88301ms 210791ms
Running this code with a method that returns a longer, more real world string, shows that the time difference can grow quite quickly with relatively few iterations.

Code: Select all

Iterations Option 1 Option 2 Option 3 100 3ms 55ms 110ms 200 6ms 288ms 580ms 300 8ms 747ms 1489ms 400 11ms 1384ms 2918ms 500 13ms 2315ms 5030ms
A doff of the hat to Kevin Douglas at Jade for the heads up on the more efficient string concatenation that occurs when using local variables for both parts of the concatenation.

Cheers,
BeeJay.

allistar
Posts: 156
Joined: Fri Aug 14, 2009 11:02 am
Location: Mount Maunganui, Tauranga

Re: Speeding up string concatenation

Postby allistar » Thu Jan 27, 2011 9:15 am

Wow. Those differences in performance are quite significant. It would be interesting to see the relationship between the size of the String being concatenated and the time it takes - one would expect it to be linear, but perhaps it's not (especially when assigning the String to a SLOB property).

For single concatenations the difference would hardly be noticeable in either case (a matter of milliseconds, if not less), but for frameworks that build and return a large amount of String data the difference could be significant enough to change the code.

It would seem to me those that the difference in performance of the 3 methods of String concatenation is an inefficiency in Jade and could be improved "under the hood". Especially Option 1 vs. Option: I would expect there to be no difference given what's going on.

Thanks for the tip.

murray
Posts: 144
Joined: Fri Aug 14, 2009 6:58 pm
Location: New Plymouth, New Zealand

Re: Speeding up string concatenation

Postby murray » Thu Jan 27, 2011 12:06 pm

Wow. Those differences in performance are quite significant. It would be interesting to see the relationship between the size of the String being concatenated and the time it takes - one would expect it to be linear, but perhaps it's not (especially when assigning the String to a SLOB property).

For single concatenations the difference would hardly be noticeable in either case (a matter of milliseconds, if not less), but for frameworks that build and return a large amount of String data the difference could be significant enough to change the code.

It would seem to me those that the difference in performance of the 3 methods of String concatenation is an inefficiency in Jade and could be improved "under the hood". Especially Option 1 vs. Option: I would expect there to be no difference given what's going on.

Thanks for the tip.
I seem to recall that I was once told that appending (as in example 2) actually results in Jade creating a temporary intermediate variable to comple the operation, effectively the same as 'str2' in example 1.
In some cases (e.g. when the length of the new string is known) further performance advantages can be gained by maintaing an index and moving subtrings directly into the destination string, with using '&' to concatenate.
e.g. str[pos, len] := methodResultString; pos := pos + len;
Murray (N.Z.)

Stokes
Posts: 66
Joined: Wed Oct 13, 2010 2:06 pm
Location: QLD, Australia

Re: Speeding up string concatenation

Postby Stokes » Fri Jan 28, 2011 8:53 am

Very helpful, will go through and check some of our functionality now to see if there is anything we can do to speed things up.

Thanks BeeJay

User avatar
ghosttie
Posts: 181
Joined: Sat Aug 15, 2009 1:25 am
Location: Atlanta, GA, USA
Contact:

Re: Speeding up string concatenation

Postby ghosttie » Sat Jan 29, 2011 2:58 am

Is this not an inefficiency that Jade should correct? I can't see going through my whole application making a change that is less readable in order to work around what seems like a bug in the runtime...
I have a catapult. Give me all the money or I will fling an enormous rock at your head.

murray
Posts: 144
Joined: Fri Aug 14, 2009 6:58 pm
Location: New Plymouth, New Zealand

Re: Speeding up string concatenation

Postby murray » Sat Jan 29, 2011 2:12 pm

Is this not an inefficiency that Jade should correct? I can't see going through my whole application making a change that is less readable in order to work around what seems like a bug in the runtime...
Yes. It could bite you in the bum in the following scenario:
  • 1. You rush off and change your code to take advantage of this revealed behaviour.
    2. Jade "improve" the behaviour in a future release (as suggested by ghosttie).
    3. The performance issue is reversed and the changed methods now run slower.
    4. Time to reverse all the changes ... ;)
It is still much better to be using local variables than object properties (for obvious reasons).
You need to be able to justify the optimisation effort. It may not be critical. There may be better ways to spend your valuable time.
Murray (N.Z.)

bdavis
Posts: 1
Joined: Tue Feb 01, 2011 6:35 pm

Re: Speeding up string concatenation

Postby bdavis » Tue Feb 01, 2011 7:13 pm

The string concatenation handling has been improved in JADE 7.0.

In the examples listed, improvements have been made where the receiver is a local variable and the first concatenation element is that same variable and that variable is not referred in other concatenation elements. For example:

str := str + str2;

is now equivalent to:

str := str & object.methodThatReturnsAString(); (etc)

The issue was that a local string implementation was used to handle the concatenation that required multiple memory allocations.

This code will actually be slightly faster than (because less operations are required):

str2 := object.methodThatReturnsAString();
str := str & str2;

The third example is just bad coding. The logic that performs concatenation into an object property means that a getProperty and a setProperty call is required for each access requiring DB access. The logic should be rewritten as:

str := object.prop;

foreach object in coll do
str := str & object.methodThatReturnsAString();
endforeach;

object.prop := str;

This same principle applies to DB and GUI properties. Accessing such properties requires access to the DB cache or to GUI environments. So, when multiple accesses are required to such elements, retrieve the value into a local variable and then reuse that variable and then set the property on completion of the access. For example, the following logic will result in significant overheads both in terms of DB access and GUI access (particularly in relation to the amount of data sent to the Thin Client):
foreach ..
texbox1.text := texbox1.text & str;
endForeach;

compared to:
foreach ..
str := str & ...
endforeach;
textbox1.text := str;

User avatar
BeeJay
Posts: 312
Joined: Tue Jun 30, 2009 2:42 pm
Location: Christchurch, NZ

Re: Speeding up string concatenation

Postby BeeJay » Wed Feb 02, 2011 8:13 am

The string concatenation handling has been improved in JADE 7.0.

In the examples listed, improvements have been made where the receiver is a local variable and the first concatenation element is that same variable and that variable is not referred in other concatenation elements. For example:

str := str + str2;

is now equivalent to:

str := str & object.methodThatReturnsAString(); (etc)
Excellent news!

Murray: Good call on your suggestion of not going through and changing all your code.

Everyone else: I wasn't suggesting you scan your code to find every place that does this in your system, it was just that this was something to be aware of if you were looking at performance problems and the code path in question involves a large number of direct concatenation of the return values from methods or involves a large number of concatenations into an object property. ie: If it ain't broke, don't fix it!!

Cheers,
BeeJay.

davidmellow
Posts: 42
Joined: Thu Aug 27, 2009 1:27 pm
Location: New Plymouth, New Zealand

Re: Speeding up string concatenation

Postby davidmellow » Fri Feb 18, 2011 8:04 am

This is very interesting. Off topic slightly, though perhaps not as Jade/.NET development increases...

This reminds me a bit of the string class in .NET, and why for that platform one should use the StringBuilder class for operations such as appending or replacements.

The string class is immutable, so ...

string s = "Hiya "; // creates a 4 byte string
s += " fellow developers" // creates a new string just long enough to store "Hiya fellow developers", even though it is assigned to same variable

As opposed to

StringBuilder sb = new StringBuilder();
sb.append("Hiya");
sb.append(" fellow developers");

In a loop there is a big difference in overhead, and it becomes extremely significant (in fact, massive) over a lot of iterations (there are a lot of string instances building up for garbage collection using the first, WRONG, methodology).

allistar
Posts: 156
Joined: Fri Aug 14, 2009 11:02 am
Location: Mount Maunganui, Tauranga

Re: Speeding up string concatenation

Postby allistar » Fri Feb 18, 2011 8:12 am

If you consider how one has to deal with this in lower level languages like C or C++, it's becomes apparent why there are overheads. You need to allocate the correct amount of memory before you can poke data into it. If you are building a large string which has unknown length at both design time and runtime you can make a structure like a linked list which you keep allocating blocks to it as text is appended. This leads to a very efficient solution but complicates things like ".pos". As a developer it's handy that Jade and other high level languages take away this complication, but it often has a runtime cost. It is amazing how much faster this sort of thing runs when you do it by hand in a low level language. As an aside, I suspect some of the overhead in Jade is in the interpreter.


Return to “Tips and Techniques”

Who is online

Users browsing this forum: No registered users and 12 guests

cron