Skip to content

clang::Lexer::LexIdentifierContinue #1

Open

Description

@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).

Activity

  1. bwendling commented on Aug 18, 2022

    @bwendling
    Contributor

    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...)

  2. nickdesaulniers commented on Nov 29, 2022

    @nickdesaulniers
    MemberAuthor

    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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions