Optimizing keyword matching in the scanner

[Yoni Feigelson]

I came across Blazingly fast parsing, part 1: optimizing the scanner · V8

Looking at the code, 2 things came to mind:

1. Doubling the size of the hash table produced by gperf would increase the binary size negligibly, but increase performance non-negligibly? (higher probability for non-keyword to hit an empty entry)

2.The code for GetToken:

inline Token::Value PerfectKeywordHash::GetToken(const char* str, int len) {

if (base::IsInRange(len, MIN_WORD_LENGTH, MAX_WORD_LENGTH)) {

unsigned int key = Hash(str, len) & 0x3f;

DCHECK_LT(key, arraysize(kPerfectKeywordLengthTable));

DCHECK_LT(key, arraysize(kPerfectKeywordHashTable));

if (len == kPerfectKeywordLengthTable[key]) {

const char* s = kPerfectKeywordHashTable[key].name;

while (*s != 0) {

if (*s++ != *str++) return Token::IDENTIFIER;

}

return kPerfectKeywordHashTable[key].value;

}

}

return Token::IDENTIFIER;

}

I wonder:

a. Is the manual char-by-char comparison possibly suboptimal to what `memcmp` would do? (Might be target machine dependent, but support for some level of SSE/SSE4.2 SIMDification?)

b. The length equality branch prior to string comparison might be a net negative? I guess it heavily depends on the ratio of keywords vs non-keywords in the scanned code, but it might be better to just do the string equality check first.

For a crude example of the version I have in mind:

Token GetToken2(const char* str, int len) {

  if (len - MIN_WORD_LENGTH <= MAX_WORD_LENGTH-MIN_WORD_LENGTH) {

    unsigned int key = Hash(str, len) & 0x3f;

    unsigned int key_len = kPerfectKeywordLengthTable[key];

    // crude branchless min, real would need casts

    unsigned int min_len = key_len + ((len-key_len) & (len-key_len)>>31);

    const char* s = kPerfectKeywordHashTable[key].name;

    if (memcmp (str, s, min_len) == 0) {

        if (len == key_len) {

            return kPerfectKeywordHashTable[key].value;

        }

    }

  }

  return Token::IDENTIFIER;

}

I'd like to ask:

1. Are there existing benchmarks that can be run?

2. I assume a perf improvement (if any) won't be drastic. Is it worth even trying out?
Put another way - if the code stays simple, with a slight perf gain - would that CL be accepted?

Cheers,

Yoni

[Marja Hölttä]

Hi, thanks for your email and taking interest in parsing performance!

We're generally interested in accepting contributions in this area, as long as they're not too tedious to review. Feel free to send them to ma...@chromium.org.

The categorical parsing benchmark is CodeLoad, part of Octane ( https://github.com/chromium/octane ). But in this case, using microbenchmarks for proving the performance improvement is also legit. Maybe take a realistic JS file as a benchmark, so that you're not artificially skewing the keyword frequencies or so. You can add the microbenchmark & results as a comment in the code review. Or dump them in a Google Doc.

Thanks again and looking forward to hearing whether your ideas worked out!

--
--
v8-dev mailing list
v8-...@googlegroups.com
http://groups.google.com/group/v8-dev
---
You received this message because you are subscribed to the Google Groups "v8-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to v8-dev+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/v8-dev/cee7bc26-50cd-49bf-8e2b-f29b01ac5adfn%40googlegroups.com.

--

Google Germany GmbH

Erika-Mann-Straße 33

80636 München

Geschäftsführer: Paul Manicle, Liana Sebastian.

Registergericht und -nummer: Hamburg, HRB 86891

Sitz der Gesellschaft: Hamburg

Diese E-Mail ist vertraulich. Falls sie diese fälschlicherweise erhalten haben sollten, leiten Sie diese bitte nicht an jemand anderes weiter, löschen Sie alle Kopien und Anhänge davon und lassen Sie mich bitte wissen, dass die E-Mail an die falsche Person gesendet wurde.

    

This e-mail is confidential. If you received this communication by mistake, please don't forward it to anyone else, please erase all copies and attachments, and please let me know that it has gone to the wrong person.

[Yoni Feigelson]

Thanks for the enthusiastic response Marja!

I have a bunch of things I want to try out.

If there's a definite improvement to be made, I'll submit a CR.

I'll share my learnings (if any) regardless.

I'm aware this work by the scanner/lexer isn't a significant perf portion for parsing a script, but I've fallen down a rabbit hole of performing static set membership checks as fast as possible.

You received this message because you are subscribed to a topic in the Google Groups "v8-dev" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/v8-dev/kCEgKwB6gNs/unsubscribe.
To unsubscribe from this group and all its topics, send an email to v8-dev+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/v8-dev/CAED6dUDMePpv42oEFbV3X%2BR7JyyUzbY3wEb6ns7Xq%2BLyTRuJng%40mail.gmail.com.