Page 1 of 1
Speeding up string concatenation
Posted: Thu Jan 27, 2011 8:41 am
by BeeJay
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.
Re: Speeding up string concatenation
Posted: Thu Jan 27, 2011 9:15 am
by allistar
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.
Re: Speeding up string concatenation
Posted: Thu Jan 27, 2011 12:06 pm
by murray
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;
Re: Speeding up string concatenation
Posted: Fri Jan 28, 2011 8:53 am
by Stokes
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
Re: Speeding up string concatenation
Posted: Sat Jan 29, 2011 2:58 am
by ghosttie
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...
Re: Speeding up string concatenation
Posted: Sat Jan 29, 2011 2:12 pm
by murray
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.
Re: Speeding up string concatenation
Posted: Tue Feb 01, 2011 7:13 pm
by bdavis
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;
Re: Speeding up string concatenation
Posted: Wed Feb 02, 2011 8:13 am
by BeeJay
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.
Re: Speeding up string concatenation
Posted: Fri Feb 18, 2011 8:04 am
by davidmellow
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).
Re: Speeding up string concatenation
Posted: Fri Feb 18, 2011 8:12 am
by allistar
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.