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

71–80 of 154 posts

Re: My Most Important Project Was a Bytecode Interpreter

#71

Post by robewald »

Hydraulix989 wrote: post #67
wyager wrote: post #65

Earlier quoted context omitted.

Hence "not to be confused with PCREs", which most pseudo-regex implementations are based off of.

I'll ask the "dumb question" then: What is a PCRE? How is it different than a "true" regex?

PCREs are Perl Compatible Regular Expressions, they have backreferences and other constructs. Almost all languages that have Regular Expressions have similar constructs. "Computer Science" Regular Expressions are more limited and implement a "regular language" as defined in https://en.wikipedia.org/wiki/Chomsky_hierarchy. This gives some guarantees, which go out the window with PCREs.

Re: My Most Important Project Was a Bytecode Interpreter

#72

Post by jbangert »

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…

C++ compilers (at least on most current code bases that don't need modules) still need to parse and lex headers though -- so actual executable code is pretty rare. Most compilations are also debug builds which don't optimize(but creating debug information can also be slow; the really slow step is usually linking)

Re: My Most Important Project Was a Bytecode Interpreter

#73

Post by jbangert »

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…

C++ compilers (at least on most current code bases that don't need modules) still need to parse and lex headers though -- so actual executable code is pretty rare. Most compilations are also debug builds which don't optimize(but creating debug information can also be slow; the really slow step is usually linking)

Re: My Most Important Project Was a Bytecode Interpreter

#75

Post by readittwice »

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…

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 to confirm that parsing is not the bottleneck, at least not for Rust.

OTOH that probably also depends on your use case, JS for example needs to get parsed at every page load. Some JS-VMs only parse the source code lazily, at first the parser only detects function boundaries. Only if this function is really executed, the function gets parsed completely.

Re: My Most Important Project Was a Bytecode Interpreter

#76

Post by reidrac »

I wrote a VM for the 6502 for fun and it was one of most interesting and satisfying projects I've ever made in my free time.

It is very close to a bytecode interpreter, only that it comes with a specification that is actually the opcode list for the MOS 6502 (and few details you need to take into account when implementing that CPU).

Besides there are cross-compilers that allows you to generate 6502 code from C for your specific VM (see cc65).

Re: My Most Important Project Was a Bytecode Interpreter

#77

Post by bonoboTP »

sillysaurus3 wrote: post #3

Also: a software rasterizer. Most people refuse to write one because it's so easy not to. Why bother? It will make you a better coder for the rest of your life. Let's make a list of "power projects" like this. A bytecode interpreter, a software rasterizer... What else?

* Implementing Internet protocols (TCP, IP, SMTP etc)

* Floating point manipulation and numerical computation

* Rolling some own crypto (strictly for fun use)

Re: My Most Important Project Was a Bytecode Interpreter

#78

Post by signa11 »

chrisseaton wrote: post #33
ender7 wrote: post #22

Earlier quoted context omitted.

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.

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 would end up spending a large portion of time. gold (https://en.wikipedia.org/wiki/Gold_(linker)) optimizes that i.e. supports incremental linking, but unfortunately, i haven't had any experience in large code-bases where it is being used.

Re: My Most Important Project Was a Bytecode Interpreter

#79

Post by dspillett »

stephengillie wrote: post #31
tominous wrote: post #8

I love the author's meta-idea of refusing to accept that unfamiliar things are black boxes full of magic that can't be touched. A great example of this mindset is the guy who bought a mainframe. [1] Refuse to be placed in a silo. Work your way up and down the stack and you'll be much better placed to solve problems and learn from the patterns that repeat at all levels. [1] https://news.ycombinator.com/item?id=1137671…

Everything is made from smaller components. Understand each of those components better and you'll understand the entire system better. Sometimes, you can use end-errors to tell which component has the issue. For instance, if a web site gives a 502 error, the problem is likely with the load balancer or lower network stack on the web server. 404 would often be a file system level issue on the web server. 500 is frequen…

> Everything is made from smaller components. Understand each of those components better and you'll understand the entire system better.

This. No matter how specialised you are (or want to be) always strive to have at least a basic understanding of the full stack and everything else that your work touches through a couple of levels of indirection (including the wetware such as, in commercial contexts, having a good understanding of your client's business even if you aren't even close to being client-facing) because it will help you produce much more useful/optimal output and can be a lot more helpful when your colleagues/compatriots/partners/what-ever his a technical problem. Heck, at the logical extreme a little cross discipline understanding could even lead you to discovering a better method of doing X that strips out the need for Y altogether, revolutionising how we do Z.

Of course don't go overboard unless you are truly a genius... Trying to keep up with everything in detail is a sure-fire route to mental burn-out!

Re: My Most Important Project Was a Bytecode Interpreter

#80

Post by usrusr »

sillysaurus3 wrote: post #3

Also: a software rasterizer. Most people refuse to write one because it's so easy not to. Why bother? It will make you a better coder for the rest of your life. Let's make a list of "power projects" like this. A bytecode interpreter, a software rasterizer... What else?

Reading from a raw filesystem dump was both interesting and rewarding as it works on a problem domain that exists in reality, not just on some simplified playground. If you target something as primitive as FAT, the challenge isn't terribly high.
Post reply on HN