Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
10230004:
Optimize the JSON parser by tokenizing while parsing and using jump-table. (Closed)
|
Created:
8 years, 8 months ago by Anders Johnsen Modified:
8 years, 7 months ago CC:
reviews_dartlang.org Visibility:
Public. |
DescriptionOptimize the JSON parser by tokenizing while parsing and using jump-table.
I've also updated the test to include a few corner cases.
My tests shows a 50-80% speedup. The optimization will also give a lower
memory usage since we don't keep a list of all tokens alive.
BUG=
TEST=
Committed: https://code.google.com/p/dart/source/detail?r=7056
Patch Set 1 #
Total comments: 27
Patch Set 2 : Inline and small fixes. #
Total comments: 18
Patch Set 3 : Optimized expectKeyword and privitized JsonParser. #Patch Set 4 : Pull out a few more constants. #
Total comments: 2
Messages
Total messages: 11 (0 generated)
Sorry for popping up, but I wrote the original version. https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart File lib/json/json.dart (right): https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:31: JSONParseException(int this.position, String message) { I think you can omit int before this.position. https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:32: this.message = "JSONParseException: $message, at offset $position"; nit: please, use single quote lines (here and below) https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:37: String message; message should be final as well, and probably you should use initializer list syntax. https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:131: int tokenKind = _token(); please, final tokenKind https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:149: Object _parseWord(String word, Object value) { shouldn't it be _expectWord rather than parse? https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:169: void parseObjectEntry() { as you're fighting for performance, is local function invocation slower than inlining? https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:170: String key = _parseString(); final key = ..., please https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:171: if (!_isa(COLON)) _error("Expected ':' when parsing object"); will it work properly for "foo"[space]:? https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:198: while (_isa(COMMA)) { ditto https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:320: bool _isChar(int char) { => syntax?
Thank you for jumping in! :) Your feedback is always welcome! https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart File lib/json/json.dart (right): https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:31: JSONParseException(int this.position, String message) { On 2012/04/26 16:13:20, antonmuhin wrote: > I think you can omit int before this.position. I'm unsure to why we would omit int here. Could you explain? https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:32: this.message = "JSONParseException: $message, at offset $position"; On 2012/04/26 16:13:20, antonmuhin wrote: > nit: please, use single quote lines (here and below) Sure, changed, but why favor single over double? https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:37: String message; On 2012/04/26 16:13:20, antonmuhin wrote: > message should be final as well, and probably you should use initializer list > syntax. Done. https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:131: int tokenKind = _token(); On 2012/04/26 16:13:20, antonmuhin wrote: > please, final tokenKind Done. https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:149: Object _parseWord(String word, Object value) { On 2012/04/26 16:13:20, antonmuhin wrote: > shouldn't it be _expectWord rather than parse? Yeah, also, renamed to expectKeyword. https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:169: void parseObjectEntry() { On 2012/04/26 16:13:20, antonmuhin wrote: > as you're fighting for performance, is local function invocation slower than > inlining? Well spotted, rewritten! https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:170: String key = _parseString(); On 2012/04/26 16:13:20, antonmuhin wrote: > final key = ..., please Done. https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:171: if (!_isa(COLON)) _error("Expected ':' when parsing object"); On 2012/04/26 16:13:20, antonmuhin wrote: > will it work properly for "foo"[space]:? Yes, every token-based method uses _token, that will eat any whitespaces. I've added a test for it. https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:198: while (_isa(COMMA)) { On 2012/04/26 16:13:20, antonmuhin wrote: > ditto Same. Added test case. https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:320: bool _isChar(int char) { On 2012/04/26 16:13:20, antonmuhin wrote: > => syntax? Done.
lgtm https://chromiumcodereview.appspot.com/10230004/diff/5001/lib/json/json.dart File lib/json/json.dart (right): https://chromiumcodereview.appspot.com/10230004/diff/5001/lib/json/json.dart#... lib/json/json.dart:41: class JsonParser { Do you want this to be visible from the outside? If not, you could make this library private by using the _JsonParser name with the underscore at the beginning. https://chromiumcodereview.appspot.com/10230004/diff/5001/lib/json/json.dart#... lib/json/json.dart:151: json.substring(position, position + word.length) != word) { substring is expensive so you could consider iterating through the char codes explicitly without copying it out. https://chromiumcodereview.appspot.com/10230004/diff/5001/lib/json/json.dart#... lib/json/json.dart:288: position--; // No digit, recover. recover -> backtrack? https://chromiumcodereview.appspot.com/10230004/diff/5001/lib/json/json.dart#... lib/json/json.dart:320: bool _isa(int tokenKind) => _token() == tokenKind; _isa -> _isToken?
LGTM, can't wait to see the impact https://chromiumcodereview.appspot.com/10230004/diff/5001/lib/json/json.dart File lib/json/json.dart (right): https://chromiumcodereview.appspot.com/10230004/diff/5001/lib/json/json.dart#... lib/json/json.dart:86: Add a static final int LAST_NON_LITERAL or LAST_ASCII or similar, and use that in e.g., the jump-table ininitalization https://chromiumcodereview.appspot.com/10230004/diff/5001/lib/json/json.dart#... lib/json/json.dart:94: tokens = new List<int>(RBRACE + 1); maybe we should encapsulate this in a singleton class, i.e., initialize this list once, right now we will allocate memory for this and spend time on it for every json parse call. Alternatively just have a static list in this class and initialize it on request https://chromiumcodereview.appspot.com/10230004/diff/5001/lib/json/json.dart#... lib/json/json.dart:138: case NULL_LITERAL: return _expectKeyword("null", null); Make constants for "null", "false", "true", they are probably in a symbol table (or will be eventually :-) ), but that is a lookup anyway https://chromiumcodereview.appspot.com/10230004/diff/5001/lib/json/json.dart#... lib/json/json.dart:151: json.substring(position, position + word.length) != word) { I think we can avoid allocation here by just looking at the characters the json string and the word string. https://chromiumcodereview.appspot.com/10230004/diff/5001/lib/json/json.dart#... lib/json/json.dart:163: // Return early if empty object. I don't see an early return
Thank you all for the reviews. Committing! https://chromiumcodereview.appspot.com/10230004/diff/5001/lib/json/json.dart File lib/json/json.dart (right): https://chromiumcodereview.appspot.com/10230004/diff/5001/lib/json/json.dart#... lib/json/json.dart:41: class JsonParser { On 2012/04/27 06:49:29, Mads Ager wrote: > Do you want this to be visible from the outside? If not, you could make this > library private by using the _JsonParser name with the underscore at the > beginning. Ah yes, done! https://chromiumcodereview.appspot.com/10230004/diff/5001/lib/json/json.dart#... lib/json/json.dart:86: On 2012/04/27 06:57:31, ricow1 wrote: > Add a static final int LAST_NON_LITERAL or LAST_ASCII or similar, and use that > in e.g., the jump-table ininitalization Done. https://chromiumcodereview.appspot.com/10230004/diff/5001/lib/json/json.dart#... lib/json/json.dart:94: tokens = new List<int>(RBRACE + 1); On 2012/04/27 06:57:31, ricow1 wrote: > maybe we should encapsulate this in a singleton class, i.e., initialize this > list once, right now we will allocate memory for this and spend time on it for > every json parse call. Alternatively just have a static list in this class and > initialize it on request Done, this should help a lot on many small json parsings. https://chromiumcodereview.appspot.com/10230004/diff/5001/lib/json/json.dart#... lib/json/json.dart:138: case NULL_LITERAL: return _expectKeyword("null", null); On 2012/04/27 06:57:31, ricow1 wrote: > Make constants for "null", "false", "true", they are probably in a symbol table > (or will be eventually :-) ), but that is a lookup anyway Done. https://chromiumcodereview.appspot.com/10230004/diff/5001/lib/json/json.dart#... lib/json/json.dart:151: json.substring(position, position + word.length) != word) { On 2012/04/27 06:49:29, Mads Ager wrote: > substring is expensive so you could consider iterating through the char codes > explicitly without copying it out. Nice catch, updated. https://chromiumcodereview.appspot.com/10230004/diff/5001/lib/json/json.dart#... lib/json/json.dart:151: json.substring(position, position + word.length) != word) { On 2012/04/27 06:57:31, ricow1 wrote: > I think we can avoid allocation here by just looking at the characters the json > string and the word string. Done. https://chromiumcodereview.appspot.com/10230004/diff/5001/lib/json/json.dart#... lib/json/json.dart:163: // Return early if empty object. On 2012/04/27 06:57:31, ricow1 wrote: > I don't see an early return Yeah, was refactored. Removing comment :) https://chromiumcodereview.appspot.com/10230004/diff/5001/lib/json/json.dart#... lib/json/json.dart:288: position--; // No digit, recover. On 2012/04/27 06:49:29, Mads Ager wrote: > recover -> backtrack? Aye! https://chromiumcodereview.appspot.com/10230004/diff/5001/lib/json/json.dart#... lib/json/json.dart:320: bool _isa(int tokenKind) => _token() == tokenKind; On 2012/04/27 06:49:29, Mads Ager wrote: > _isa -> _isToken? Done.
Drive-by-comment. https://chromiumcodereview.appspot.com/10230004/diff/14001/lib/json/json.dart File lib/json/json.dart (right): https://chromiumcodereview.appspot.com/10230004/diff/14001/lib/json/json.dart... lib/json/json.dart:285: } You need to bail out here if the first character after the sign is not a digit, e.g., "-.2" is not valid. (I assume you only get here if the first character is a sign or digit, so it's only "-." or "-e2" that's a problem).
https://chromiumcodereview.appspot.com/10230004/diff/14001/lib/json/json.dart File lib/json/json.dart (right): https://chromiumcodereview.appspot.com/10230004/diff/14001/lib/json/json.dart... lib/json/json.dart:285: } On 2012/04/27 07:26:36, Lasse Reichstein Nielsen wrote: > You need to bail out here if the first character after the sign is not a digit, > e.g., "-.2" is not valid. > (I assume you only get here if the first character is a sign or digit, so it's > only "-." or "-e2" that's a problem). Ah yes, I forgot to finish this if...else statement. Very nice spotted! Will upload another CL.
https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart File lib/json/json.dart (right): https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:31: JSONParseException(int this.position, String message) { Why duplicate type info? Field position is known to be int from decl below. On 2012/04/27 05:22:22, ajohnsen wrote: > On 2012/04/26 16:13:20, antonmuhin wrote: > > I think you can omit int before this.position. > > I'm unsure to why we would omit int here. Could you explain? https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:32: this.message = "JSONParseException: $message, at offset $position"; Sorry, I don't know---for some reason I use single quotes as defaults and believe json lib follows this style. On 2012/04/27 05:22:22, ajohnsen wrote: > On 2012/04/26 16:13:20, antonmuhin wrote: > > nit: please, use single quote lines (here and below) > > Sure, changed, but why favor single over double?
DBC https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart File lib/json/json.dart (right): https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:32: this.message = "JSONParseException: $message, at offset $position"; It seems it's the most prevalent quoting in Dart, probably taken from the JS style guide which prefers ' over ". http://google-styleguide.googlecode.com/svn/trunk/javascriptguide.xml?showone... Personally I write double quotes all the time, and only notice and change them if someone else notices. It's just in my fingers from years of C/C++/Java (and JavaScript with double-quotes) programming. Single quotes are for characters! I also read them more easily, and don't get hit when writing "isn't" in my strings. https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:37: String message; I'd also move the fields above the constructor. https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:131: int tokenKind = _token(); final int tokenKind; Don't drop the type. (I don't particularly care for making local variables final - seems like overdoing it, any competent compiler should be able to see that it doesn't change anyway).
https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart File lib/json/json.dart (right): https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:32: this.message = "JSONParseException: $message, at offset $position"; Lasse, this file used single quotes, not double quotes, hence I asked to follow this style. If consensus is double quotes are preferred, that's okay, but I'd ask for a separate change and for changing all the quotes. On 2012/04/30 08:12:02, Lasse Reichstein Nielsen wrote: > It seems it's the most prevalent quoting in Dart, probably taken from the JS > style guide which prefers ' over ". > http://google-styleguide.googlecode.com/svn/trunk/javascriptguide.xml?showone... > > Personally I write double quotes all the time, and only notice and change them > if someone else notices. It's just in my fingers from years of C/C++/Java (and > JavaScript with double-quotes) programming. Single quotes are for characters! I > also read them more easily, and don't get hit when writing "isn't" in my > strings. https://chromiumcodereview.appspot.com/10230004/diff/1/lib/json/json.dart#new... lib/json/json.dart:131: int tokenKind = _token(); Again, that's the style in this file. And I used final's not for performance sake, but for semantics sake: now it's obvious for the one who reads the code, that this value shouldn't change. But I was ridiculed for my love to finals in Java as well. On 2012/04/30 08:12:02, Lasse Reichstein Nielsen wrote: > final int tokenKind; > Don't drop the type. (I don't particularly care for making local variables final > - seems like overdoing it, any competent compiler should be able to see that it > doesn't change anyway). |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
