Speed up identifying keywords in scanner, by using extra table.

runtime/vm/scanner.cc

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/scanner.h"
 
 #include "platform/assert.h"
 #include "vm/dart.h"
 #include "vm/flags.h"
 #include "vm/object.h"
 #include "vm/object_store.h"
 #include "vm/symbols.h"
 #include "vm/thread.h"
 #include "vm/token.h"
 #include "vm/unicode.h"
 
 namespace dart {
 
 DEFINE_FLAG(bool, print_tokens, false, "Print scanned tokens.");
 
 
-Scanner::KeywordTable Scanner::keywords_[Token::numKeywords];
+Scanner::KeywordTable Scanner::keywords_[Token::kNumKeywords];
+int Scanner::keywords_char_offset_[Scanner::kNumLowercaseChars];
 
 
 void Scanner::Reset() {
   // Non-changing newline properties.
   newline_token_.kind = Token::kNEWLINE;
   newline_token_.literal = NULL;
   // We don't preserve the column information.
   newline_token_.position.column = 0;
 
   // Non-changing empty string token properties.
@@ skipping 249 matching lines @@
   int ident_length = 0;
   int ident_pos = lookahead_pos_;
   int32_t ident_char0 = source_.CharAt(ident_pos);
   while (IsIdentChar(c0_) && (allow_dollar || (c0_ != '$'))) {
     ReadChar();
     ident_length++;
   }
 
   // Check whether the characters we read are a known keyword.
   // Note, can't use strcmp since token_chars is not null-terminated.
-  int i = 0;
-  while (i < Token::numKeywords &&
-         keywords_[i].keyword_chars[0] <= ident_char0) {
-    if (keywords_[i].keyword_len == ident_length) {
-      const char* keyword = keywords_[i].keyword_chars;
-      int char_pos = 0;
-      while ((char_pos < ident_length) &&
-             (keyword[char_pos] == source_.CharAt(ident_pos + char_pos))) {
-        char_pos++;
+  int ch = ident_char0 - 'a';
+  if (ch >= 0 && ch < kNumLowercaseChars) {

[hausner, 2014/06/03 17:59:26]

why not if (('a' <= ident_char0) && (ident_char0 <= 'z')) {....

Less cryptic IMO and saves you computing ch for anything not starting with a
lowercase letter.

[Anders Johnsen, 2014/06/03 18:52:59]

Good idea. I'll work on a updated version with this guard in, instead.

+    int i = keywords_char_offset_[ch];
+    while (i < Token::kNumKeywords &&
+           keywords_[i].keyword_chars[0] <= ident_char0) {
+      if (keywords_[i].keyword_len == ident_length) {
+        const char* keyword = keywords_[i].keyword_chars;
+        int char_pos = 1;
+        while ((char_pos < ident_length) &&
+               (keyword[char_pos] == source_.CharAt(ident_pos + char_pos))) {
+          char_pos++;
+        }
+        if (char_pos == ident_length) {
+          current_token_.literal = keywords_[i].keyword_symbol;
+          current_token_.kind = keywords_[i].kind;
+          return;
+        }
       }
-      if (char_pos == ident_length) {
-        current_token_.literal = keywords_[i].keyword_symbol;
-        current_token_.kind = keywords_[i].kind;
-        return;
-      }
+      i++;
     }
-    i++;
   }
 
   // We did not read a keyword.
   current_token_.kind = Token::kIDENT;
   String& literal =
       String::ZoneHandle(Symbols::New(source_, ident_pos, ident_length));
   if (ident_char0 == Library::kPrivateIdentifierStart) {
     // Private identifiers are mangled on a per library basis.
     literal = String::Concat(literal, private_key_);
     literal = Symbols::New(literal);
@@ skipping 611 matching lines @@
       OS::Print("\n%d (%d): ", currentLine, i);
     }
     OS::Print("%s ", Token::Name(td.kind));
   }
   OS::Print("\n");
 }
 
 
 void Scanner::InitOnce() {
   ASSERT(Isolate::Current() == Dart::vm_isolate());
-  for (int i = 0; i < Token::numKeywords; i++) {
+  for (int i = 0; i < kNumLowercaseChars; i++) {
+    keywords_char_offset_[i] = Token::kNumKeywords;
+  }
+  for (int i = 0; i < Token::kNumKeywords; i++) {
     Token::Kind token = static_cast<Token::Kind>(Token::kFirstKeyword + i);
     keywords_[i].kind = token;
     keywords_[i].keyword_chars = Token::Str(token);
     keywords_[i].keyword_len = strlen(Token::Str(token));
     keywords_[i].keyword_symbol = &Symbols::Keyword(token);
+
+    int ch = keywords_[i].keyword_chars[0] - 'a';
+    if (keywords_char_offset_[ch] == Token::kNumKeywords) {
+      keywords_char_offset_[ch] = i;
+    }
   }
 }
 
 }  // namespace dart