Bug 63330 – Concatenating string literals and WTF::Strings using operator+ is suboptimal

• Status: RESOLVED
• Resolution: FIXED
• Component: Web Template Framework

[Adam Roben (:aroben)]

The following code:

String color("brown");
String workEthic("lazy");
String result = L"The quick " + color + L" fox jumped over the " + workEthic + L" dogs";

...doesn't behave in an optimal way. The optimal behavior would be for the + expressions to build up a StringAppend object, and only to convert to a String at the very end. What actually happens is:

1. L"The quick " is converted to a String
2. (String(L"The quick ") + color) is evaluated, resulting in a StringAppend object
3. StringAppend::operator String() is called
4. (String(L"The quick brown") + L" fox jumped over the ") is evaluated, resulting in a StringAppend object
5. StringAppend::operator String() is called

...and so on.

You can see that each concatenation is being converted to a String before the next concatenation occurs. It also shouldn't be necessary for the first wide string to be converted to a String.

[Adam Roben (:aroben)]

Created attachment 98503 [details]
patch for discussion

This patch fixes the above issues. I'm unsure whether this is the right way to fix it, however. Any thoughts?

[Nikolas Zimmermann]

(In reply to comment #0)
> The following code:
> 
> String color("brown");
> String workEthic("lazy");
> String result = L"The quick " + color + L" fox jumped over the " + workEthic + L" dogs";
> 
> ...doesn't behave in an optimal way. The optimal behavior would be for the + expressions to build up a StringAppend object, and only to convert to a String at the very end. What actually happens is:
> 
> 1. L"The quick " is converted to a String
Sounds like the right StringTypeAdapter is missing.
Try adding one for your string type in JavaScriptCore/wtf/text/StringConcatenate.h, that will make the String conversion unncessary when invoking operator+.

> 2. (String(L"The quick ") + color) is evaluated, resulting in a StringAppend object
> 3. StringAppend::operator String() is called
> 4. (String(L"The quick brown") + L" fox jumped over the ") is evaluated, resulting in a StringAppend object
> 5. StringAppend::operator String() is called
> 
> ...and so on.
> 
> You can see that each concatenation is being converted to a String before the next concatenation occurs. It also shouldn't be necessary for the first wide string to be converted to a String.
That's stupid... Is this fixed when introducing the right StringTypeAdapter for wchar?

[Adam Roben (:aroben)]

(In reply to comment #2)
> (In reply to comment #0)
> > The following code:
> > 
> > String color("brown");
> > String workEthic("lazy");
> > String result = L"The quick " + color + L" fox jumped over the " + workEthic + L" dogs";
> > 
> > ...doesn't behave in an optimal way. The optimal behavior would be for the + expressions to build up a StringAppend object, and only to convert to a String at the very end. What actually happens is:
> > 
> > 1. L"The quick " is converted to a String
> Sounds like the right StringTypeAdapter is missing.
> Try adding one for your string type in JavaScriptCore/wtf/text/StringConcatenate.h, that will make the String conversion unncessary when invoking operator+.

There is already a StringTypeAdapter<const UChar*>. On Windows, UChar == wchar_t. So there's already the correct StringTypeAdapter for wide strings.

[Nikolas Zimmermann]

(In reply to comment #3)
> (In reply to comment #2)
> > (In reply to comment #0)
> > > The following code:
> > > 
> > > String color("brown");
> > > String workEthic("lazy");
> > > String result = L"The quick " + color + L" fox jumped over the " + workEthic + L" dogs";
> > > 
> > > ...doesn't behave in an optimal way. The optimal behavior would be for the + expressions to build up a StringAppend object, and only to convert to a String at the very end. What actually happens is:
> > > 
> > > 1. L"The quick " is converted to a String
> > Sounds like the right StringTypeAdapter is missing.
> > Try adding one for your string type in JavaScriptCore/wtf/text/StringConcatenate.h, that will make the String conversion unncessary when invoking operator+.
> 
> There is already a StringTypeAdapter<const UChar*>. On Windows, UChar == wchar_t. So there's already the correct StringTypeAdapter for wide strings.

Oh okay, I overlooked that! but why is it converted to a string
The whole String result should be evaluated to:
String result = StringAppend<const UChar*, StringAppend<String, StringAppend<const UChar*, .... > > >.operator String();

It's intessting that your patch fixes it, I'd like Darin or Maciej to have a look here!

[Darin Adler]

What about non-wide strings on other platforms?

[Adam Roben (:aroben)]

(In reply to comment #5)
> What about non-wide strings on other platforms?

I tried compiling this in a Debug build on Mac OS X 10.6:

String color("brown");
String workEthic("lazy");
String result = "The quick " + color + " fox jumped over the " + workEthic + " dogs";

What happens is:

1. ("The quick " + color) is evaluated, resulting in a StringAppend object
2. StringAppend::operator String() is called
3. (String(L"The quick brown") + " fox jumped over the ") is evaluated, resulting in a StringAppend object
4. StringAppend::operator String() is called

...and so on.

This is also suboptimal. I believe this would also be fixed by my attached patch.

[Adam Roben (:aroben)]

The problem in both of these examples is that the concatenation is happening left-to-right, so the left-hand side of the expression is always a StringAppend object. But our operator+ that takes a StringAppend only takes a StringAppend on the right-hand side.

[Darin Adler]

Comment on attachment 98503 [details]
patch for discussion

This looks good to me. I could have sworn I brought up this issue during the development of the StringAppend template.

[Adam Roben (:aroben)]

(In reply to comment #8)
> (From update of attachment 98503 [details])
> This looks good to me. I could have sworn I brought up this issue during the development of the StringAppend template.

OK, I'll write up a ChangeLog and submit a real patch!

[Nikolas Zimmermann]

(In reply to comment #7)
> The problem in both of these examples is that the concatenation is happening left-to-right, so the left-hand side of the expression is always a StringAppend object. But our operator+ that takes a StringAppend only takes a StringAppend on the right-hand side.

*grml* I have the feeling we discussed that at some point. _Maybe_ it got lost during the 20+ patches marathon needed to get it building :(
I am very sorry, for the trouble it caused. Thanks for your analysis, it's clear that your patch is better!

[Adam Roben (:aroben)]

Created attachment 98746 [details]
Make concatenating string literals and WTF::Strings more efficient

[Darin Adler]

Comment on attachment 98746 [details]
Make concatenating string literals and WTF::Strings more efficient

View in context: https://bugs.webkit.org/attachment.cgi?id=98746&action=review

> Source/JavaScriptCore/wtf/text/StringOperators.h:109
>  template<typename U, typename V, typename W>
> -StringAppend<U, StringAppend<V, W> > operator+(U string1, const StringAppend<V, W>& string2)
> +StringAppend<StringAppend<U, V>, W> operator+(const StringAppend<U, V>& string1, W string2)
>  {
> -    return StringAppend<U, StringAppend<V, W> >(string1, string2);
> +    return StringAppend<StringAppend<U, V>, W>(string1, string2);
>  }

I think the reason this is correct is that the + operator is left-associative. Ideally we should make unit test cases for this that somehow check how many string objects are allocated. I would want to use tests to prove that this does not adversely affect expressions like these:

    a + (b + c)
    (a + b) + (c + d)

with various types of arguments.

[Adam Roben (:aroben)]

Created attachment 99742 [details]
Ensure no intermediate WTF::Strings are created when concatenating with string literals

[Adam Roben (:aroben)]

Created attachment 99743 [details]
Ensure no intermediate WTF::Strings are created when concatenating with string literals

[WebKit Review Bot]

Attachment 99743 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/ChangeLog', u'Source..." exit_code: 1

Tools/TestWebKitAPI/Tests/WTF/StringOperators.cpp:43:  Missing space before ( in while(  [whitespace/parens] [5]
Total errors found: 1 in 7 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Adam Roben (:aroben)]

Created attachment 99745 [details]
Ensure no intermediate WTF::Strings are created when concatenating with string literals

[Darin Adler]

Comment on attachment 99745 [details]
Ensure no intermediate WTF::Strings are created when concatenating with string literals

Would you like to fix the Windows build failure before I review this?

[Adam Roben (:aroben)]

(In reply to comment #17)
> (From update of attachment 99745 [details])
> Would you like to fix the Windows build failure before I review this?

Strange, I didn't notice it didn't build on Windows (filed bug 64276). I must have uploaded the wrong version of the patch. (It can get confusing when moving patches between computers!) The only changes required should be some new entries in the WebKit2.def file, so you can review this as-is if you want. But I'll try to upload a new version later today.

[Nikolas Zimmermann]

Great job Adam, especially on the tests!

[Adam Roben (:aroben)]

Committed r90813: <http://trac.webkit.org/changeset/90813>