Good to see you kicking around and here in a thread about things small enough to think about! I've not seen any blog posts from you in a while Kartik but I come back to your lua musings from time to time.
Really interesting writeup. What stood out to me most was the shift from the earlier node execution path to the streamed path. The benchmark gap between execute_r_nodes and execute_stream is huge, and the latter getting relatively close to the handwritten C++ baseline is the part I keep thinking about.
After building this, where do you think most compiler complexity actually comes from? My impression from your post is that a lot of the “millions of lines” are not from the core syntax-to-execution path itself, but from language surface area, tooling, diagnostics, optimization passes, and long-tail ecosystem baggage.
The streaming (essentially a JIT) was actually from the early architecture three weeks ago. Though I'm glad you've read even the first post. On the current architecture performance hasn't been a target yet, though the core hasn't changed, I could build a MIX that streams and it would reach the same benchmark.
And I love the question. A lot of the complexity is coming from the management of seams, places where we have to go from one representation of information to another. The tooling, diagnostics, and optimization passes are as large as they are precisely because of these seams. Consider a liveness pass in LLVM, which spends a lot of time reconstructing information thrown away by the compiler so it could emit SSA. In GDSL, a liveness pass is simply handlers in the e_stage, in the example I snuck into GDSL-C print statements stamp liveness tokens onto their children via qualifiers and at assignment nodes, those without such tokens are killed. I can do the logic in a straightforward manner because we have all the information to work with, no seams, no SSA to derive scopes from, thus why a subset of it fits in 80 lines instead of 80,000.
GDSL is written in C++ with use of STL, templates and lambdas, so it's 2600 lines of such C++ source code. There is no self-hosting: neither the LISP compiler nor the C compiler can compile itself. No operating system is implemented, the word kernel in the title means something else.
FYI Here is a 700-line subset-of-C compiler which can compile itself: https://github.com/valdanylchuk/xcc700 . FYI The linker and the libc are not included.
Sparkie is correct, and an actually fully working C compiler in GDSL would probably be 12,000 lines or so total, possibly much more.
The point in showing this is that so much of the size of these compilers just comes from managing seams, as I discuss in the essays, and by preserving information through the compiler they shrink dramatically.
I would encourage you to compare the implementation of GDSL-C's identifiers to GCC, for a good example of how information availability allows me to link and disambiguate in just 80 lines what GCC takes upwards of a thousand spread across many files to do.
11 comments
[ 3.2 ms ] story [ 32.6 ms ] threadHere's my similar project from a few years ago, in case you want to compare notes:
https://github.com/akkartik/mu
https://akkartik.name/akkartik-convivial-20200607.pdf
After building this, where do you think most compiler complexity actually comes from? My impression from your post is that a lot of the “millions of lines” are not from the core syntax-to-execution path itself, but from language surface area, tooling, diagnostics, optimization passes, and long-tail ecosystem baggage.
And I love the question. A lot of the complexity is coming from the management of seams, places where we have to go from one representation of information to another. The tooling, diagnostics, and optimization passes are as large as they are precisely because of these seams. Consider a liveness pass in LLVM, which spends a lot of time reconstructing information thrown away by the compiler so it could emit SSA. In GDSL, a liveness pass is simply handlers in the e_stage, in the example I snuck into GDSL-C print statements stamp liveness tokens onto their children via qualifiers and at assignment nodes, those without such tokens are killed. I can do the logic in a straightforward manner because we have all the information to work with, no seams, no SSA to derive scopes from, thus why a subset of it fits in 80 lines instead of 80,000.
FYI Here is a 700-line subset-of-C compiler which can compile itself: https://github.com/valdanylchuk/xcc700 . FYI The linker and the libc are not included.