Bug 63330

Summary: Concatenating string literals and WTF::Strings using operator+ is suboptimal
Product: WebKit Reporter: Adam Roben (:aroben) <aroben>
Component: Web Template FrameworkAssignee: Nobody <webkit-unassigned>
Status: RESOLVED FIXED    
Severity: Normal CC: darin, mjs, webkit.review.bot, zimmermann
Priority: P2    
Version: 528+ (Nightly build)   
Hardware: PC   
OS: Windows XP   
See Also: https://bugs.webkit.org/show_bug.cgi?id=247121
Attachments:
Description Flags
patch for discussion
none
Make concatenating string literals and WTF::Strings more efficient
none
Ensure no intermediate WTF::Strings are created when concatenating with string literals
none
Ensure no intermediate WTF::Strings are created when concatenating with string literals
none
Ensure no intermediate WTF::Strings are created when concatenating with string literals darin: review+

Description Adam Roben (:aroben) 2011-06-24 09:52:54 PDT
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.
Comment 1 Adam Roben (:aroben) 2011-06-24 09:55:30 PDT
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?
Comment 2 Nikolas Zimmermann 2011-06-24 11:20:51 PDT
(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?
Comment 3 Adam Roben (:aroben) 2011-06-24 12:42:47 PDT
(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.
Comment 4 Nikolas Zimmermann 2011-06-24 13:10:47 PDT
(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!
Comment 5 Darin Adler 2011-06-24 14:11:38 PDT
What about non-wide strings on other platforms?
Comment 6 Adam Roben (:aroben) 2011-06-27 07:25:50 PDT
(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.
Comment 7 Adam Roben (:aroben) 2011-06-27 07:26:49 PDT
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.
Comment 8 Darin Adler 2011-06-27 08:13:39 PDT
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.
Comment 9 Adam Roben (:aroben) 2011-06-27 08:28:52 PDT
(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!
Comment 10 Nikolas Zimmermann 2011-06-27 08:40:22 PDT
(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!
Comment 11 Adam Roben (:aroben) 2011-06-27 10:27:32 PDT
Created attachment 98746 [details]
Make concatenating string literals and WTF::Strings more efficient
Comment 12 Darin Adler 2011-06-27 11:55:38 PDT
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.
Comment 13 Adam Roben (:aroben) 2011-07-05 14:06:13 PDT
Created attachment 99742 [details]
Ensure no intermediate WTF::Strings are created when concatenating with string literals
Comment 14 Adam Roben (:aroben) 2011-07-05 14:07:16 PDT
Created attachment 99743 [details]
Ensure no intermediate WTF::Strings are created when concatenating with string literals
Comment 15 WebKit Review Bot 2011-07-05 14:09:38 PDT
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.
Comment 16 Adam Roben (:aroben) 2011-07-05 14:10:50 PDT
Created attachment 99745 [details]
Ensure no intermediate WTF::Strings are created when concatenating with string literals
Comment 17 Darin Adler 2011-07-10 21:34:24 PDT
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?
Comment 18 Adam Roben (:aroben) 2011-07-11 06:41:15 PDT
(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.
Comment 19 Nikolas Zimmermann 2011-07-12 00:15:23 PDT
Great job Adam, especially on the tests!
Comment 20 Adam Roben (:aroben) 2011-07-12 06:36:19 PDT
Committed r90813: <http://trac.webkit.org/changeset/90813>