Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

My Most Important Project Was a Bytecode Interpreter

gpfault.net

Post reply on HN
Print view View original

81–90 of 154 posts

Re: My Most Important Project Was a Bytecode Interpreter

#81

Post by dan00 »

readittwice wrote: post #75
adrianratnapala wrote: post #53

Earlier quoted context omitted.

According to textbooks, lexers are the bottleneck because they are the only part that has to literally look at every byte of the source (I am including hashing as part of the lexing process). I am not sure if this is true any more. It probably depends on the language. Even as CPUs grow faster, code bases grow bigger, so the number-of-bytes argument is still important. On the other hand, heavy optimisations and diffic…

I think I read that too, but I am not sure that this is actually true. Please correct me if I am wrong, according to the Rust developers code generation seems to be the bottleneck. That's why they are working on incremental compilation to improve compilation times. They detect changes in the input files by comparing the AST to the old version. So parsing is always necessary but later stages can be cached. That seems…

> I think I read that too, but I am not sure that this is actually true. Please correct me if I am wrong, according to the Rust developers code generation seems to be the bottleneck.

You're both right. The problem of C++ is how '#include' works, that it just includes the content of all files and therefore there's more overhead on the lexing side.

Rust's "equivalent" of '#include' is 'use', which doesn't have this problem, because it doesn't concatenates files.

Re: My Most Important Project Was a Bytecode Interpreter

#82

Post by ab129c871xy »

adrianratnapala wrote: post #53
chrisseaton wrote: post #33

Earlier quoted context omitted.

I didn't think of lexer rules as regular expressions but I suppose they are of course. But I can't imagine a lexer would ever be the performance bottleneck in a compiler.

According to textbooks, lexers are the bottleneck because they are the only part that has to literally look at every byte of the source (I am including hashing as part of the lexing process). I am not sure if this is true any more. It probably depends on the language. Even as CPUs grow faster, code bases grow bigger, so the number-of-bytes argument is still important. On the other hand, heavy optimisations and diffic…

Perhaps in an ancient one-pass C compiler. Modern compilers build many trees, usually one for each pass. Later stages do expensive operations on sets (even without optimization one has to do basic register allocation), so I'd say the lexing stage is entirely negligible.

Re: My Most Important Project Was a Bytecode Interpreter

#83

Post by elcct »

I did something similar in the distant past, that is I wrote subset of C compiler (functions, standard types, pointers) to imaginary assembler and then bytecode interpreter. It was awesome fun, but also I got so into it my - then - girlfriend started to question my commitment to the relationship. So be careful, this is really interesting thing to do :)

Re: My Most Important Project Was a Bytecode Interpreter

#84

Post by bachback »

wahern wrote: post #27

Two approaches are severely underused in the software world: 1) Domain-specific languages (DSLs) 2) Virtual machines (or just explicit state machines more generally) What I mean is, alot of problems could be solved cleanly, elegantly, more safely, and more powerfully by using one (or both) of the above. The problem is that when people think DSL or VM, they think big (Scheme or JVM) instead of thinking small (printf).…

Yes, absolutely agree. In LISP its obvious.

1. Every function is a tiny VM already. Every macro is a layer on top of a "compiler" to let you redesign a language. LISP gives much more power, precisely because every program is its own DSL, and all power of the language within that DSL is available. http://www.paulgraham.com/avg.html

2. In SICP they show how to build anything from LISP constructs. The elegant thing is that LISP actually only needs very few machine primitives. https://mitpress.mit.edu/sicp/full-text/book/book-Z-H-30.htm...

The most powerful constructs I've seen is a combination of these 2: Clojure/async is a macro which transforms any program to state machines. I think that kind of power gives you 20-30x advantage in business type applications. In fact I've seen C++ programmers spending a decade on discovering similar things by themselves. I strongly believe everyone should know at least a little about LISP.

Re: My Most Important Project Was a Bytecode Interpreter

#85

Post by barrkel »

readittwice wrote: post #75
adrianratnapala wrote: post #53

Earlier quoted context omitted.

According to textbooks, lexers are the bottleneck because they are the only part that has to literally look at every byte of the source (I am including hashing as part of the lexing process). I am not sure if this is true any more. It probably depends on the language. Even as CPUs grow faster, code bases grow bigger, so the number-of-bytes argument is still important. On the other hand, heavy optimisations and diffic…

I think I read that too, but I am not sure that this is actually true. Please correct me if I am wrong, according to the Rust developers code generation seems to be the bottleneck. That's why they are working on incremental compilation to improve compilation times. They detect changes in the input files by comparing the AST to the old version. So parsing is always necessary but later stages can be cached. That seems…

You can make codegen faster by doing less work and producing less sophisticated code. You can't not look at every byte. It's the limiting factor in fastest possible compilation, not what takes the most time in most production compilers.

Re: My Most Important Project Was a Bytecode Interpreter

#86

Post by vidarh »

ender7 wrote: post #22
chrisseaton wrote: post #17

Earlier quoted context omitted.

I don't get it - what do regexps have to do with compilers and how do they make compilers faster?

The first step in compilation is lexing -- converting a character stream to a stream of semantic "tokens", where a token might be "a number literal" or "the 'while' keyword" or a single character token like "{". This process is usually done via regexs.

It is rare for lexers to use actual regex engines, in my experience, as it's impractical if you want to do proper error reporting unless you write your own regex engine in which case people tend to opt for hand-writing lexer rules.

It's not unheard of, and I have the impression it's getting more common, but still only a small proportion of the compilers I've seen over the years explicitly use regexps.

Re: My Most Important Project Was a Bytecode Interpreter

#87

Post by pertymcpert »

signa11 wrote: post #78
chrisseaton wrote: post #33

Earlier quoted context omitted.

I didn't think of lexer rules as regular expressions but I suppose they are of course. But I can't imagine a lexer would ever be the performance bottleneck in a compiler.

> But I can't imagine a lexer would ever be the performance bottleneck in a compiler. one rather trivial way to observe the effects of avoiding building a source file is to use ccache. ccache avoids the recompilation (even if you do a make clean, or some such), and it is not uncommon to observe speed ups of factor of 5 or so. however, once you have crossed that barrier, you hit the linking wall. which is where you wo…

No chance, modern compilers spend most of their time in the optimization stages. Lexing is peanuts.

Re: My Most Important Project Was a Bytecode Interpreter

#88

Post by adrianratnapala »

readittwice wrote: post #75
adrianratnapala wrote: post #53

Earlier quoted context omitted.

According to textbooks, lexers are the bottleneck because they are the only part that has to literally look at every byte of the source (I am including hashing as part of the lexing process). I am not sure if this is true any more. It probably depends on the language. Even as CPUs grow faster, code bases grow bigger, so the number-of-bytes argument is still important. On the other hand, heavy optimisations and diffic…

I think I read that too, but I am not sure that this is actually true. Please correct me if I am wrong, according to the Rust developers code generation seems to be the bottleneck. That's why they are working on incremental compilation to improve compilation times. They detect changes in the input files by comparing the AST to the old version. So parsing is always necessary but later stages can be cached. That seems…

Rust uses LLVM, a heavyweight backend with fearsomely thorough optimisation.

It might be that for non-optimised output, the parser becomes the bottleneck again. Or it might be that LLVM just imposes overhead even for the unoptimised case, that pays for itself in the optimised case.

Re: My Most Important Project Was a Bytecode Interpreter

#89

Post by titzer »

ender7 wrote: post #22
chrisseaton wrote: post #17

Earlier quoted context omitted.

I don't get it - what do regexps have to do with compilers and how do they make compilers faster?

The first step in compilation is lexing -- converting a character stream to a stream of semantic "tokens", where a token might be "a number literal" or "the 'while' keyword" or a single character token like "{". This process is usually done via regexs.

Not all parsers do a lexing step. Such ones are called "scannerless parsers" and can be much, much faster than parsers with a separate lexing step.

Re: My Most Important Project Was a Bytecode Interpreter

#90

Post by titzer »

adrianratnapala wrote: post #53
chrisseaton wrote: post #33

Earlier quoted context omitted.

I didn't think of lexer rules as regular expressions but I suppose they are of course. But I can't imagine a lexer would ever be the performance bottleneck in a compiler.

According to textbooks, lexers are the bottleneck because they are the only part that has to literally look at every byte of the source (I am including hashing as part of the lexing process). I am not sure if this is true any more. It probably depends on the language. Even as CPUs grow faster, code bases grow bigger, so the number-of-bytes argument is still important. On the other hand, heavy optimisations and diffic…

Depending on how source programs are split up into files, parsing can be easily parallelized (think one thread per file), while other compilation tasks are harder due to interdependencies. E.g. semantic analysis requires building type representations, global namespaces, etc. Code generation is (usually) parallelizable as well, but there are a couple very serial steps in the middle, too.

My experience is that parsers for source languages can reach into the 1-10mb/s range, and depending on how complex the IRs and transformations are after that, code generation is usually around 0.5mb-5mb/s. The stuff in the middle (dealing with IRs) is harder to measure in terms of bytes.

Post reply on HN