mirror of
https://github.com/carbon-language/carbon-lang.git
synced 2026-11-15 03:18:32 +00:00
Chandler Carruth
0421bf3b43
Currently, these lookup the token in its `ValueStore`, and then access the kind and flag from that. This is near-optimal in the lexer while _writing_ the tokens, but ends up being considerably slower in parsing when the overhead of digging the token out of the value store dominates the actual use case. This PR does an struct-of-arrays reorganization of the kinds and whitespace flags, but only after lexing. This lets lexing write a linear series of info structs, and only afterward re-organize into a query-optimized representation that is a struct of arrays. However, to make this a net performance gain, we have to create the arrays _very_ efficiently. We can avoid hand-written assembly here by very carefully and precisely writing the inner loop to build these arrays so that LLVM will vectorize it into high-quality SIMD code for us across both x86 and Arm. We also need the arrays to have a particular shape (for example, using a `SmallVector<bool>` rather than a `BitVector`) in order to preserve this vectorized creation. It burns a tiny amount of memory, but is key to the whole thing being a net win of 5% to 10% across parsing. Benchmark results (./scripts/bench_runner.py --runs=12, -march=x86-64-v3): - BM_CompileApiFileDenseDecls<Lang::Carbon, Phase::Parse>/16384: CPU Time: -9.045% - BM_CompileApiFileDenseDecls<Lang::Carbon, Phase::Parse>/65536: CPU Time: -6.526% - BM_CompileImplFile<Lang::Carbon, Phase::Parse>/16384: CPU Time: -9.275% - BM_CompileImplFile<Lang::Carbon, Phase::Parse>/65536: CPU Time: -8.382% Assisted-by: Antigravity with both Gemini and Claude