u/mttdin r/Compilers • Recommends
Modernizing Compiler Design for Carbon Toolchain - Chandler Carruth - CppNow 2023
0:00 / 0:00
Modernizing Compiler Design for Carbon Toolchain - Chandler Carruth - CppNow 2023
CppNow
39K subscribers • 42 videos on Hallway • Conference channel
- Recommended by 4 people: 1 on Hacker News, 1 on Lobsters and 2 in engineering communities.
- Presented by Chandler Carruth, Carbon language lead
Advanced. Deep dive for people who know the field.
70K views3 years ago4 recommendations
Systems programmingProgramming languagesCompilers and interpretersPerformance and optimizationData-oriented design
Chandler Carruth explains how the Carbon toolchain uses data-oriented design and flat ASTs to achieve high-performance lexing and parsing.
cppnow.org linkedin.com/company/cppnow --- Modernizing Compiler Design for Carbon Toolchain - Chandler Carruth - CppNow 2023 Slides: github.com/boostcon --- The algorithms and data structures used for parsing and compiling in most compilers today are rooted in 50 year old computer architectures and language design realities. What would a modernized compiler design, based on modern computer architectures, leveraging data-oriented design, and targeting modern languages look like in order to maximize performance while retaining flexibility? This talk will provide an overview of the traditional model for designing a compiler in C++ and highlight some of the key limitations of these design patterns. Then it will introduce a new set of design patterns that we are using to build the Carbon toolchain's compiler, and describe why we think they can help us reach unprecedented compile times (for a C++-like programming language). It will also show specific programming techniques that have proven useful and how we have overcome some of the traditional limitations and challenges of implementing a parser or compiler in C++. While this talk focuses on the design and implementation of the Carbon compiler, it will also touch on the Carbon *language* because achieving our goals for the compiler interacted with the design of the language grammar. --- Chandler Carruth Chandler Carruth is the technical lead for Google's programming languages and software foundations. He has worked extensively on the C++ programming language and the Clang and LLVM compiler infrastructure. Previously, he worked on several pieces of Google's distributed build system and made guest appearances helping maintain a few core C++ libraries across Google's codebase. He received his M.S. and B.S. in Computer Science from Wake Forest University, but disavows all knowledge of the contents of his Master’s thesis. When not hammering away on a weirdly shaped keyboard, he enjoys sushi, fine dining, brown spirits, and everything about wine. --- think-cell develops one of the world’s leading PowerPoint applications, with C++ at the core of everything we build, from layout algorithms to deep integration with Microsoft Office. Interested in working on challenging C++ problems with real-world impact? Explore our open roles: think-cell.com/en/career/tech--- Videos Filmed & Edited By Bash Films: bashfilms.com/ YouTube Channel Managed & Optimized By Digital Medium Ltd: events.digital-medium.co.uk --- CppNow 2024 cppnow.org twitter.com/cppnow --- #boost #cpp #compiler_designWhy it's here
4 people recommend thisWhat people say. Recommended for its insights into modern compiler performance and data-oriented AST design.
Moments people linked to
u/agumonkeyin r/Compilers • Recommends
Modernizing Compiler Design for Carbon Toolchain - Chandler Carruth - CppNow 2023
di4naon Hacker News • Recommends
On “How to speed up the Rust compiler in August 2023”
No but it is endemic to how we think about compilers up to now, and especially when the rust compiler arch was massively developed, more than 10 years ago. I recommend a watch of this for a recent take on trying to change how we think of these. It is an open research field link to this video
u/levodelellisin r/ProgrammingLanguages • Mentions
Carbon wants 10M lexing+parsing, how fast have you gotten?
Around 24m Chandler says he wants 10M lines for lexing and parsing link to this video That number isn't even a little realistic to me (my compiler is currently a magnitude faster than his goal, so high numbers are usually believable to me).
In my own compiler parsing takes about 1/3rd of the total time. If I run my compiler with the syntax only flag (which includes semantic analysis) I can get 4.5M per second (a debug build with the tcc backend is 3M per second). In my situation the parsing is slow because there's a bottleneck writing data to main memory and for whatever reason data keep falling out of my L1 and L2 cache (such as keywords tha…
u/not_a_novel_accountin r/C_Programming • Mentions
On “Usability of code from "Compiler Design in C" by Allen Holub on modern compilers”
Frankly I don't see a lot of value in learning from an ANSI-C compiler book in 2023 for many reasons, not the least of which because how we build compilers has changed _a lot_ since then.
Quick list of things from a brief look at the linked repo:
* This code is structured around a yacc-generated LL(1) parser which is how effectively zero major compilers operate. CPython uses a PEG grammar, Haskell (GHC) uses an LALR(1), and almost everyone else uses recursive descent (V8, GCC, Clang, Zig, Rust, many many others). Modern compiler design is heavily biased towards recursive descent because it allows for high performance and also context-specific, readable error messages for users.
* A lot of…
u/oxcrowxin r/ProgrammingLanguages • Mentions
…w,
* The LL(1) Recursive descent Pratt parser I wrote can parse 1 Million LoCs in \~0.25 seconds. (Performance is IO bound: My HDD is old).
* To Accelerate *Type-Inference*, I want to store the *Expression* nodes by flattening the AST into a linear array, and storing it in post-order / depth-first form *(Similar to what Carbon is using* *\[3\*](link to this video
***Now comes the difficult part:*** *How do I uniquely hash the string identifiers?*
*Specifically, I want to convert the string identifiers to Unique Integer IDs (UIDs). If possible I would want to hash the strings into uint32 UIDs, but due to risk of possible hash collisions, will also be happy with uint64 UIDs.*
*Example: A section of…
u/matthieumin r/ProgrammingLanguages • Mentions
On “Made a tokenizer”
…there's overhead emitting each token -- but since the tokenizer is likely to scan every byte, input size definitely matters too. Consider, for example, that comments until end of line, or strings, can be dozens to hundreds of bytes long, yet represented as a single token.
You may be interested in Chandler's Carruth CppNow 2023 talk about Carbon: link to this video
The slides are available at https://chandlerc.blog/slides/2023-cppnow-compiler/index.html (though they do not display so well for me), and in particular performance targets at
https://chandlerc.blog/slides/2023-cppnow-compiler/index.html#/27/1/3:
- Parse & Lex: 10MLoc/s.
- Semantic: 1MLoc/s.
- CodeGen: 0.1MLoc/s.
So... 400k tokens/s is…
u/javascriptin r/ProgrammingLanguages • Mentions
On “Monomophisation should never be slow to compile (if done explicitly)”
If you like that, you also might like these:
link to this video
link to this video
link to this video
link to this video
:D
u/Karyo_Tenin r/C_Programming • Mentions
On “Project: Making a C compiler”
Chandler Carruth disagrees, link to this video parsers starts around 6min and there is a question about C++ parsing specificities where he mentioned that recursive descent is not enough.
pason Hacker News • Mentions
On “Rhombus: Macro-extensible language with conventional syntax built on Racket”
Cache the position of quotes/apostrophes, etc. Optimizing for your edge case would require everyone writing and reading code to conform to this extra thing, which seems completely unnecessary. Machines are pretty fast. link to this video Modernizing Compiler Design for Carbon Toolchain - Chandler Carruth - CppNow 2023
wrsh07on Hacker News • Mentions
On “Flattening ASTs and other compiler data structures (2023)”
Chandler discusses it in this video though! link to this video You get some traversals for free with this layout (preorder, reverse post order). Can search for subtrees with string searching algorithms or more complex things with regex.
norskeldon Hacker News • Mentions
On “Strategies for Fast Lexers”
Is lexing ever a bottleneck though? Even if you push for lexing and parsing 10M lines/second 1, I'd argue that semantic analysis and codegen (for AOT-compiled languages) will dominate the timings. That said, there's no reason not to squeeze every bit of performance out of it! 1: In this talk about the Carbon language, Chandler Carruth shows and explains some goals/challenges regarding performance: link to this video
u/JonMeow47in r/ProgrammingLanguages • Mentions
On “Flat AST and states machine over recursion: is worth it?”
The data structures and the iterative approach are really separate issues (the parse tree was originally recursively constructed).
We wanted to switch to iterative approaches; there's Clang experience on the team with generated C++ code routinely discovering recursion limits in the compiler and having to fix those (as Clang gets new features, those can add new recursion paths). Switching early just means we have less to fix.
[Modernizing Compiler Design for Carbon Toolchain - Chandler Carruth - CppNow 2023] has some good commentary on the data structures (though this is more of a parse tree or concrete syntax tree than AST). A few points I'd highlight briefly are:
- The array layout is ve…
u/JonMeow47in r/ProgrammingLanguages • Mentions
On “Flat AST and states machine over recursion: is worth it?”
From a "goals" perspective, \Chandler says\ lex+parse 10M LOC/second and semantic analysis 1M LOC/second (lowering is more a question of LLVM performance). I know he watches the numbers, and I think we're doing okay on lex+parse, though semantic analysis might be a little slower. There are some concrete lex benchmarks on PRs (\#3365\ has a full set), but the thing Chandler's doing for other timing measures hasn't been put into a benchmark.
u/caim_hsin r/ProgrammingLanguages • Mentions
On “Flat AST and states machine over recursion: is worth it?”
In the same link of Carbon, they talk about it I think, but there's Chandler's talk here:
[video
There are other talks on LLVM about it and threads in the LLVM forum.
I don't know if the point was clear, but with recursive functions, each time you call a function, its address is added to the stack frame, so the calle knows where to go back. And since the stack size is limited to 40MB in most platforms (though you can increase it, you may end up messing with malloc), but since the stack is used to local variables, etc, most compilers limit this number by a lower bound. LLVM limits the call stack frame by 256 KiB and so does GCC.
https://clang.llvm.org/doxygen/Stack\_8cpp\_source.html…