clang::Lexer::LexIdentifierContinue

[nickdesaulniers]

most time is spent in this loop:

  5.52 │ 40:┌─→add    $0x1,%rbp                                                                                                   ▒
  2.35 │    │  mov    %rbp,0x8(%rsp)                                                                                              ▒
  1.64 │    │  mov    0x8(%rsp),%rbp                                                                                              ▒
 14.04 │ 4e:│  movzbl 0x0(%rbp),%eax                                                                                              ▒
 22.93 │    │  movzwl 0x0(%r13,%rax,2),%ecx                                                                                       ▒
  0.72 │    ├──test   $0xe8,%cl                                                                                                   ▒
  5.49 │    └──jne    40                                                                                                          ▒
 10.61 │       cmp    $0x3f,%al 

which is isAsciiIdentifierContinue. $0xe8 == (CHAR_UPPER|CHAR_LOWER|CHAR_DIGIT|CHAR_UNDER).

I bet we can do something better than a table lookup. (Edit: I was curious if glibc had any clever tricks; they also do table lookup: https://sourceware.org/git/?p=glibc.git;a=blob;f=ctype/isctype.c;h=dd6ca328899b9c68f83d0d2e69f68fd65ecc3bba;hb=HEAD#l25) Terrible idea: solve the 7 input kmap for the ascii table: https://www.mathematik.uni-marburg.de/~thormae/lectures/ti1/code/karnaughmap/

(0x3f == '?', from getCharAndSize calling isObviouslySimpleCharacter).

[bwendling]

One possibility: take an unsigned long amount of the string and perform the check on that as a whole:

const char *str = S.data();
size_t size = S.size();
int i;
for (i = 0; i < S.size(); i += 8) {
  if (*(unsigned long*)&str[i] & 0xe8e8e8e8e8e8e8e8)
    return false;
}
/* check the remaining bytes. */

(I may have been looking at too much Linux code...)

[nickdesaulniers]

Also, we get nice branchless code with:

bool is_upper(int c) {
    return (unsigned)(c - 'A') < 26U;
}
bool is_lower(int c) {
    return (unsigned)(c - 'a') < 26U;
}
bool is_alpha(int c) {
    return is_upper(c) | is_lower(c);
}
bool is_digit(int c) {
    return (unsigned)(c - '0') < 10U;
}
bool is_alnum(int c) {
    return is_alpha(c) | is_digit(c);
}
bool isAsciiIdentifierContinue(int c) {
    return is_alnum(c) | (c == '_');
}

Those seem more concise than doing an indirect table lookup through the GOT; unfortunately it doesn't seem faster according to llvm-mca for -mcpu=skylake: https://godbolt.org/z/K8zYxfYbE