Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
209443005:
Add optimized _OneByteString.toLowerCase. (Closed)
|
Created:
6 years, 9 months ago by Anders Johnsen Modified:
6 years, 9 months ago CC:
reviews_dartlang.org Visibility:
Public. |
DescriptionAdd optimized _OneByteString.toLowerCase.
BUG=
R=sgjesse@google.com, sra@google.com, srdjan@google.com
Committed: https://code.google.com/p/dart/source/detail?r=34393
Patch Set 1 #
Total comments: 7
Patch Set 2 : Create unified _ASCII.toLowerCase(Byte). #Patch Set 3 : Tiny fix. #Patch Set 4 : Tiny fix. #Patch Set 5 : Optimize toLowerCase. #
Total comments: 2
Patch Set 6 : Move impl to _OneByteString. #
Total comments: 10
Patch Set 7 : Use table, code from lrn@. #Patch Set 8 : length == 1 case #
Total comments: 17
Patch Set 9 : Rename. #Patch Set 10 : Remove lenght == 1 check. #Patch Set 11 : #
Total comments: 4
Patch Set 12 : Fix test. #
Messages
Total messages: 29 (0 generated)
On 2014/03/24 15:39:41, Anders Johnsen wrote: Is is possible to get the performance you need by implementing a specialized _OneByteString.toLowerCase?
DBC https://codereview.chromium.org/209443005/diff/1/sdk/lib/io/http_headers.dart File sdk/lib/io/http_headers.dart (right): https://codereview.chromium.org/209443005/diff/1/sdk/lib/io/http_headers.dart... sdk/lib/io/http_headers.dart:524: final int aCode = "A".codeUnitAt(0); Is this only run the first time the method is called? Would it be better to be class-level or top-level final?
https://codereview.chromium.org/209443005/diff/1/sdk/lib/io/http_headers.dart File sdk/lib/io/http_headers.dart (right): https://codereview.chromium.org/209443005/diff/1/sdk/lib/io/http_headers.dart... sdk/lib/io/http_headers.dart:524: final int aCode = "A".codeUnitAt(0); On 2014/03/24 17:50:16, kevmoo wrote: > Is this only run the first time the method is called? > > Would it be better to be class-level or top-level final? When looking at the SSA of the VM, it's heavily inlined. But I'll consider creating an all-static class with these constants.
https://codereview.chromium.org/209443005/diff/1/sdk/lib/io/http_headers.dart File sdk/lib/io/http_headers.dart (right): https://codereview.chromium.org/209443005/diff/1/sdk/lib/io/http_headers.dart... sdk/lib/io/http_headers.dart:524: final int aCode = "A".codeUnitAt(0); On 2014/03/24 19:02:59, Anders Johnsen wrote: > On 2014/03/24 17:50:16, kevmoo wrote: > > Is this only run the first time the method is called? > > > > Would it be better to be class-level or top-level final? > > When looking at the SSA of the VM, it's heavily inlined. But I'll consider > creating an all-static class with these constants. If they are only used in http_headers, just leave 'em in this class.
https://codereview.chromium.org/209443005/diff/1/sdk/lib/io/http_headers.dart File sdk/lib/io/http_headers.dart (right): https://codereview.chromium.org/209443005/diff/1/sdk/lib/io/http_headers.dart... sdk/lib/io/http_headers.dart:524: final int aCode = "A".codeUnitAt(0); On 2014/03/24 19:04:05, kevmoo wrote: > On 2014/03/24 19:02:59, Anders Johnsen wrote: > > On 2014/03/24 17:50:16, kevmoo wrote: > > > Is this only run the first time the method is called? > > > > > > Would it be better to be class-level or top-level final? > > > > When looking at the SSA of the VM, it's heavily inlined. But I'll consider > > creating an all-static class with these constants. > > If they are only used in http_headers, just leave 'em in this class. Yeah, but so far there is two places it's used (parser as well), and I just tried to scan through, and found several other places. I should fix.
lgtm, with comments https://codereview.chromium.org/209443005/diff/1/sdk/lib/io/http_headers.dart File sdk/lib/io/http_headers.dart (right): https://codereview.chromium.org/209443005/diff/1/sdk/lib/io/http_headers.dart... sdk/lib/io/http_headers.dart:524: final int aCode = "A".codeUnitAt(0); Yes, as you have noticed we have the _CharCodes constants in http_parser.dart. We should consolidate all of these. https://codereview.chromium.org/209443005/diff/1/sdk/lib/io/http_headers.dart... sdk/lib/io/http_headers.dart:537: result[i] = toLowerCase(codeUnit); I don't see the need to a function call here (even though it most likely is inlined).
PTAL, unified all of IO for this. https://codereview.chromium.org/209443005/diff/1/sdk/lib/io/http_headers.dart File sdk/lib/io/http_headers.dart (right): https://codereview.chromium.org/209443005/diff/1/sdk/lib/io/http_headers.dart... sdk/lib/io/http_headers.dart:537: result[i] = toLowerCase(codeUnit); On 2014/03/25 07:54:25, Søren Gjesse wrote: > I don't see the need to a function call here (even though it most likely is > inlined). Pulled out and shared across all of IO.
https://codereview.chromium.org/209443005/diff/100001/sdk/lib/io/common.dart File sdk/lib/io/common.dart (right): https://codereview.chromium.org/209443005/diff/100001/sdk/lib/io/common.dart#... sdk/lib/io/common.dart:129: // - 0x41 is 'A' LOVE the explicit comments. No guessing. Thanks!
srdjan: This was originally an attempt to add a ASCII-only toLowerCase, but sra suggested that a toLowerCase on _OneByteString would be much more beneficial. everyone else: PTAL, I've changed the CL topic and intention.
https://codereview.chromium.org/209443005/diff/100001/sdk/lib/io/common.dart File sdk/lib/io/common.dart (right): https://codereview.chromium.org/209443005/diff/100001/sdk/lib/io/common.dart#... sdk/lib/io/common.dart:129: // - 0x41 is 'A' On 2014/03/25 14:38:25, kevmoo wrote: > LOVE the explicit comments. > > No guessing. Thanks! Yeah, it helps understanding. Moved stuff around, PTAL :)
lgtm, but what about toUpperCase? https://codereview.chromium.org/209443005/diff/140001/runtime/lib/string_patc... File runtime/lib/string_patch.dart (right): https://codereview.chromium.org/209443005/diff/140001/runtime/lib/string_patc... runtime/lib/string_patch.dart:781: int _nextLowerCase(int offset) { Shouldn't this be called _nextUpperCase/_nextUpperCaseiNDEX?
https://codereview.chromium.org/209443005/diff/140001/runtime/lib/string_patc... File runtime/lib/string_patch.dart (right): https://codereview.chromium.org/209443005/diff/140001/runtime/lib/string_patc... runtime/lib/string_patch.dart:784: int codeUnit = this.codeUnitAt(offset); final codeUnit https://codereview.chromium.org/209443005/diff/140001/runtime/lib/string_patc... runtime/lib/string_patch.dart:786: // Optimzed ASCII check: s/Optimzed/Optimized/ https://codereview.chromium.org/209443005/diff/140001/runtime/lib/string_patc... runtime/lib/string_patch.dart:792: // Optimzed remaining LATIN1 check: ditto https://codereview.chromium.org/209443005/diff/140001/runtime/lib/string_patc... runtime/lib/string_patch.dart:818: result._setAt(offset, this.codeUnitAt(offset) | 0x20); What is the advantage of using OR instead of ADD? https://codereview.chromium.org/209443005/diff/140001/sdk/lib/io/http_parser.... File sdk/lib/io/http_parser.dart (right): https://codereview.chromium.org/209443005/diff/140001/sdk/lib/io/http_parser.... sdk/lib/io/http_parser.dart:937: // Optimzed version: ditto https://codereview.chromium.org/209443005/diff/140001/sdk/lib/io/http_parser.... sdk/lib/io/http_parser.dart:942: return ((x - 0x41) & 0x7f) < 26 ? x | 0x20 : x; Use more parentheses, again: advantage of OR vs ADD?
On 2014/03/25 15:28:05, Søren Gjesse wrote: > lgtm, but what about toUpperCase? I agree, but toUpperCase is harder. You occasionally need two a byte result, since codes 181 µ and 255 ÿ map to 924 and 376 (i.e. +743 and +121). It would be fine to call super.toUpperCase() to access the general runtime version if these are seen. > > https://codereview.chromium.org/209443005/diff/140001/runtime/lib/string_patc... > File runtime/lib/string_patch.dart (right): > > https://codereview.chromium.org/209443005/diff/140001/runtime/lib/string_patc... > runtime/lib/string_patch.dart:781: int _nextLowerCase(int offset) { > Shouldn't this be called _nextUpperCase/_nextUpperCaseiNDEX?
https://codereview.chromium.org/209443005/diff/140001/runtime/lib/string_patc... File runtime/lib/string_patch.dart (right): https://codereview.chromium.org/209443005/diff/140001/runtime/lib/string_patc... runtime/lib/string_patch.dart:827: return result; In the case of a one character string, the VM might have an invariant that the 'character' strings are canonicalized. (V8 does this for ascii) What makes me think this is line 233. You might need to return result[0] when length==1
I did some tests with various _OneByteString.toLowerCase implementations. The fastest one seems to be table based (https://codereview.chromium.org/211283003/) but I haven't tested it fully yet.
PTAL, I've pulled in the table-solution lrn@ presented. Performance numbers shows a notable speedup for HTTP-based benchmarks. https://codereview.chromium.org/209443005/diff/140001/runtime/lib/string_patc... File runtime/lib/string_patch.dart (right): https://codereview.chromium.org/209443005/diff/140001/runtime/lib/string_patc... runtime/lib/string_patch.dart:818: result._setAt(offset, this.codeUnitAt(offset) | 0x20); On 2014/03/25 15:46:31, srdjan wrote: > What is the advantage of using OR instead of ADD? No need for SMI overflow checks? https://codereview.chromium.org/209443005/diff/140001/runtime/lib/string_patc... runtime/lib/string_patch.dart:827: return result; On 2014/03/25 16:00:33, sra1 wrote: > In the case of a one character string, the VM might have an invariant that the > 'character' strings are canonicalized. (V8 does this for ascii) > > What makes me think this is line 233. > You might need to return result[0] when length==1 Done.
lgtm https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... File runtime/lib/string_patch.dart (right): https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... runtime/lib/string_patch.dart:783: 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, Why not Uin8List instead? Any performance difference? https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... runtime/lib/string_patch.dart:817: String _toLowerCaseUpperCaseDetected(int firstUpperCaseIndex) { _toLowerCaseUpperCaseDetectedAt
https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... File runtime/lib/string_patch.dart (right): https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... runtime/lib/string_patch.dart:817: String _toLowerCaseUpperCaseDetected(int firstUpperCaseIndex) { The "At" doesn't add anything when the parameter is named as it is. https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... runtime/lib/string_patch.dart:825: } I tried this split into "known non-uppercase" and "rest", and for me it was slower than just having just one loop that translates everything. Probably depends on the string, my strings weren't that long, so the first upper-case string was early in the string. I recommend trying without it. It gives just one loop with a completely standard for-loop from 0 to length. That optimizes very well. https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... runtime/lib/string_patch.dart:830: return result[0]; I don't think this is necessary. I haven't done it in other functions that creates strings, like trim.
https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... File runtime/lib/string_patch.dart (right): https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... runtime/lib/string_patch.dart:783: 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, On 2014/03/25 20:05:37, srdjan wrote: > Why not Uin8List instead? Any performance difference? I tried, and saw a minor slowdown with a HTTP benchmark. https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... runtime/lib/string_patch.dart:817: String _toLowerCaseUpperCaseDetected(int firstUpperCaseIndex) { On 2014/03/25 20:05:37, srdjan wrote: > _toLowerCaseUpperCaseDetectedAt Done.
https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... File runtime/lib/string_patch.dart (right): https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... runtime/lib/string_patch.dart:817: String _toLowerCaseUpperCaseDetected(int firstUpperCaseIndex) { On 2014/03/25 20:10:12, Lasse Reichstein Nielsen wrote: > The "At" doesn't add anything when the parameter is named as it is. No, but it makes the call-site more clear. https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... runtime/lib/string_patch.dart:825: } On 2014/03/25 20:10:12, Lasse Reichstein Nielsen wrote: > I tried this split into "known non-uppercase" and "rest", and for me it was > slower than just having just one loop that translates everything. Probably > depends on the string, my strings weren't that long, so the first upper-case > string was early in the string. > > I recommend trying without it. > It gives just one loop with a completely standard for-loop from 0 to length. > That optimizes very well. Will try! https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... runtime/lib/string_patch.dart:830: return result[0]; On 2014/03/25 20:10:12, Lasse Reichstein Nielsen wrote: > I don't think this is necessary. I haven't done it in other functions that > creates strings, like trim. But it it fetches the right 'symbol' object? Srdjan, wdyk?
https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... File runtime/lib/string_patch.dart (right): https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... runtime/lib/string_patch.dart:817: String _toLowerCaseUpperCaseDetected(int firstUpperCaseIndex) { On 2014/03/25 20:10:12, Lasse Reichstein Nielsen wrote: > The "At" doesn't add anything when the parameter is named as it is. It is all about reading the code at call site, where the argument names are not visible. https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... runtime/lib/string_patch.dart:825: } On 2014/03/25 20:10:12, Lasse Reichstein Nielsen wrote: > I tried this split into "known non-uppercase" and "rest", and for me it was > slower than just having just one loop that translates everything. Probably > depends on the string, my strings weren't that long, so the first upper-case > string was early in the string. > > I recommend trying without it. > It gives just one loop with a completely standard for-loop from 0 to length. > That optimizes very well. We need to run the benchmarks on a typical set of inputs to gain meaningful numbers. Are we doing that? https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... runtime/lib/string_patch.dart:830: return result[0]; On 2014/03/25 20:12:26, Anders Johnsen wrote: > On 2014/03/25 20:10:12, Lasse Reichstein Nielsen wrote: > > I don't think this is necessary. I haven't done it in other functions that > > creates strings, like trim. > > But it it fetches the right 'symbol' object? > > Srdjan, wdyk? I'd remove it.
https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... File runtime/lib/string_patch.dart (right): https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... runtime/lib/string_patch.dart:830: return result[0]; On 2014/03/25 20:14:49, srdjan wrote: > On 2014/03/25 20:12:26, Anders Johnsen wrote: > > On 2014/03/25 20:10:12, Lasse Reichstein Nielsen wrote: > > > I don't think this is necessary. I haven't done it in other functions that > > > creates strings, like trim. > > > > But it it fetches the right 'symbol' object? > > > > Srdjan, wdyk? > > I'd remove it. > Done.
https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... File runtime/lib/string_patch.dart (right): https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... runtime/lib/string_patch.dart:783: 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, It can't be const then, so it will be lazily initialized (and cost a little extra to access, but reading it into a local once per method might be enough).
https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... File runtime/lib/string_patch.dart (right): https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... runtime/lib/string_patch.dart:783: 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, On 2014/03/25 20:33:57, Lasse Reichstein Nielsen wrote: > It can't be const then, so it will be lazily initialized (and cost a little > extra to access, but reading it into a local once per method might be enough). A static final is quite efficient. Once the optimization kicks in, the variable has been already initialized and the content is known and invariant .
https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... File runtime/lib/string_patch.dart (right): https://codereview.chromium.org/209443005/diff/280001/runtime/lib/string_patc... runtime/lib/string_patch.dart:783: 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, On 2014/03/25 20:33:57, Lasse Reichstein Nielsen wrote: > It can't be const then, so it will be lazily initialized (and cost a little > extra to access, but reading it into a local once per method might be enough). Putting it into a local final var made it even slower.
lgtm with test fixes if original reviewers are happy https://codereview.chromium.org/209443005/diff/390001/tests/corelib/string_to... File tests/corelib/string_to_lower_case_test.dart (right): https://codereview.chromium.org/209443005/diff/390001/tests/corelib/string_to... tests/corelib/string_to_lower_case_test.dart:11: var twoByteString = new String.fromCharCodes( This is probably a _OneByteString. You have to do the toLowerCase before the substring to guarantee the operation happens on a one byte string. Maybe you should add an assert that there are two byte characters in the string Expect.isTrue(twoByteString.codeUnits.any((u) => u >= 256); Before you check in, temporarily add a mistake to the table to see that the test finds the problem. https://codereview.chromium.org/209443005/diff/390001/tests/corelib/string_to... tests/corelib/string_to_lower_case_test.dart:13: Expect.listEquals(oneByteString.toLowerCase(), twoByteString.toLowerCase()); Expect.equals. (This will fail in checked mode since a String is not a List.)
Thanks all. I'll land now, and we can iterate this in the future as needed. https://codereview.chromium.org/209443005/diff/390001/tests/corelib/string_to... File tests/corelib/string_to_lower_case_test.dart (right): https://codereview.chromium.org/209443005/diff/390001/tests/corelib/string_to... tests/corelib/string_to_lower_case_test.dart:11: var twoByteString = new String.fromCharCodes( On 2014/03/25 21:29:13, sra1 wrote: > This is probably a _OneByteString. > You have to do the toLowerCase before the substring to guarantee the operation > happens on a one byte string. > > Maybe you should add an assert that there are two byte characters in the string > > Expect.isTrue(twoByteString.codeUnits.any((u) => u >= 256); > > Before you check in, temporarily add a mistake to the table to see that the test > finds the problem. Done. https://codereview.chromium.org/209443005/diff/390001/tests/corelib/string_to... tests/corelib/string_to_lower_case_test.dart:13: Expect.listEquals(oneByteString.toLowerCase(), twoByteString.toLowerCase()); On 2014/03/25 21:29:13, sra1 wrote: > Expect.equals. > > (This will fail in checked mode since a String is not a List.) Done.
Message was sent while issue was closed.
Committed patchset #12 manually as r34393 (presubmit successful). |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
