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

121–130 of 154 posts

Re: My Most Important Project Was a Bytecode Interpreter

#121

Post by Jasper_ »

Rexxar wrote: post #102
Jasper_ wrote: post #21

Earlier quoted context omitted.

Tracks I've done and suggested to friends and colleagues as learning experiences: * Compression (lossless, lossy, image, audio, texture, video) * Languages (bytecode interpreter, AST interpreter, parser/lexer for a simple language, simple JIT, understanding instruction scheduling) * DSP programming (writing programs for fast, branchless math) * Comfort with binary and binary formats (start with packfiles .zip/.tar, m…

Concerning last point, do you know nice example of non-scanline-based 2D renderers ?

2D renderers? Do you mean rendering 2D shapes? In that case, scanline is probably the most efficient thing you can do, but most renderers are not scanline. The only modern 2D scanline renderer I know of is in the Flash Player code.

For a 3D renderer, I recommend fgiesen's series as linked above, and the older series by Nicolas Capens: http://forum.devmaster.net/t/advanced-rasterization/6145

Re: My Most Important Project Was a Bytecode Interpreter

#122

Post by posterboy »

robertelder wrote: post #13

One of the moments where I really started to feel like I was starting to 'see the matrix' was when I was working on a regex engine to try to make my compiler faster (it didn't, but that's another story). The asymptotically fast way to approach regex processing actually involves writing a parser to process the regex, so in order to write a fast compiler, you need to write another fast compiler to process the regexes t…

A regular expression is by definition a regular grammar, the least mighty language in the chomsky hierarchy and realizable by finite state automaton.

You can get something similar to a virtual equivalent of a turing complete language, due to the fact that the tape of the turing machine is, contrary to the hypothetical theory, practically limit by recourses. CPUs are finite state automatons, yet we use them to solve problems of sufficiently low complexity in NP space.

I am not an expert, please correct me if I am wrong.

Re: My Most Important Project Was a Bytecode Interpreter

#123

Post by Lanzaa »

robertelder wrote: post #13

One of the moments where I really started to feel like I was starting to 'see the matrix' was when I was working on a regex engine to try to make my compiler faster (it didn't, but that's another story). The asymptotically fast way to approach regex processing actually involves writing a parser to process the regex, so in order to write a fast compiler, you need to write another fast compiler to process the regexes t…

If you spent much time looking at regexs you might enjoy this set of articles about improving regex engine performance:

https://swtch.com/~rsc/regexp/regexp1.html

Re: My Most Important Project Was a Bytecode Interpreter

#124

Post by criddell »

mynewtb wrote: post #116
0xcde4c3db wrote: post #114

Earlier quoted context omitted.

A screen-oriented text editor with undo and search/replace. Can you make it handle a 10MB file without "simple" operations having annoying delays? How about 100MB? 1GB? 100GB? With no line breaks in the file?

Is there any such editor?

I don't think so. Can a text editor do search and replace on a 100 GB file without a delay? You could construct an index, but that's not going to happen instantaneously either.

Re: My Most Important Project Was a Bytecode Interpreter

#125

Post by pooktrain »

shermanyo wrote: post #30
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?

A basic game engine! I was exposed to so many concepts over time, building on a code base I understood from the ground up. It was the first time my code (c++ no less!) felt completely deterministic, that I understood every piece of data down to the byte level, heap/stack/gpu locality at any point of execution, and especially the lifecycle and memory management. If anyone is interested in creating an indie/hobby game…

This seems like lots of fun - mind sharing the books that you alluded to?

Re: My Most Important Project Was a Bytecode Interpreter

#126

Post by mamcx »

richdougherty wrote: post #64
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?

* A database (transaction, lock managers, buffer/IO management, etc). * An MVC web framework. * A GUI validation library. * A JavaScript UI library. * An iteratee implementation. * An Erlang-style actors library in another language. * Implementing for-yield, async-await, etc on top of delimited continuations. * Interpreters, typecheckers, code generators. * Some of an ECMAScript implementation. * Concurrent data stru…

I haven't find a good introductory yet complete resource about build a complete database. I'm on the hunt for it (building also a relational language).

Re: My Most Important Project Was a Bytecode Interpreter

#127

Post by hawski »

0xcde4c3db wrote: post #114
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?

A screen-oriented text editor with undo and search/replace. Can you make it handle a 10MB file without "simple" operations having annoying delays? How about 100MB? 1GB? 100GB? With no line breaks in the file?

With both emacs and vim you can certainly edit 500MB file. I concatenated all sources of recent Linux kernel 4.6.3 once. From what I remember it was all .c, .h and .S files. Resulting file has 542MB and 19'726'498 lines. I did it to test the text editor I am working on.

Some stats:

  $ time vim -c 'edit kernel-total' -c q
  real	0m8.162s
  user	0m7.687s
  sys	0m0.398s
  $ vim kernel-total ^Z
  $ ps aux | awk "/kernel-total$/ || NR == 1"
  USER       PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND
  hawski   10467  2.7 17.1 805120 670988 pts/2   T    17:41   0:07 vim kernel-total
  $ time emacs kernel-total -f kill-emacs
  real	0m7.155s
  user	0m6.869s
  sys	0m0.237s
  $ emacs kernel-total ^Z
  $ ps aux | awk "/kernel-total$/ || NR == 1"
  USER       PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND
  hawski   10825 43.8 14.8 857484 581152 pts/2   T    17:47   0:07 emacs kernel-total
With vim editing is quite smooth and with emacs it feels laggy. I only edited a bit, like entering a new line here and there, moving few pages down, going to the end of the file and to the top again. Saving is sluggish.

Re: My Most Important Project Was a Bytecode Interpreter

#128

Post by dman »

Jasper_ wrote: post #21
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?

Tracks I've done and suggested to friends and colleagues as learning experiences: * Compression (lossless, lossy, image, audio, texture, video) * Languages (bytecode interpreter, AST interpreter, parser/lexer for a simple language, simple JIT, understanding instruction scheduling) * DSP programming (writing programs for fast, branchless math) * Comfort with binary and binary formats (start with packfiles .zip/.tar, m…

Any pointers / resources for DSP programming?

Re: My Most Important Project Was a Bytecode Interpreter

#129

Post by Jasper_ »

dman wrote: post #128
Jasper_ wrote: post #21

Earlier quoted context omitted.

Tracks I've done and suggested to friends and colleagues as learning experiences: * Compression (lossless, lossy, image, audio, texture, video) * Languages (bytecode interpreter, AST interpreter, parser/lexer for a simple language, simple JIT, understanding instruction scheduling) * DSP programming (writing programs for fast, branchless math) * Comfort with binary and binary formats (start with packfiles .zip/.tar, m…

Any pointers / resources for DSP programming?

I learned by reverse engineering DSP code in another platform which was used for obfuscation. I had a chat with a friend and he suggested the TI DSP starter kits. I'm not familiar with any of them, though.

Re: My Most Important Project Was a Bytecode Interpreter

#130

Post by loup-vaillant »

bonoboTP wrote: post #108
loup-vaillant wrote: post #105

Earlier quoted context omitted.

Dogma, Dogma, Dogma. Have you seen the size of the reference implementations for chacha20, blake2b, or poly1305? Those are tiny , a couple hundred lines for all three! There is very little room for errors to sneak in. Between test vectors, compiler warnings, and Valgrind, we can be pretty sure all bugs have been shaked out. Add in good old code review and the safety of this stuff is pretty much guaranteed. Of course,…

Even experts wouldn't do this on their own. It takes teams and a lot of time. A lot of thought can go into a few hundred lines of code. It needs math oriented people, it needs OS-oriented people, people who are experienced with exploiting systems. As I said, it's good to do it for fun and to learn, but there's no reason to do it for production. It's almost always a case of ignorance and overconfidence. The problem is…

> Even experts wouldn't do this on their own

Did you miss the part where I mentioned code review? And the one where I said I would never invent my own primitives?

> A lot of thought can go into a few hundred lines of code.

I can attest to that. I can also confirm that most such though went in the design of the primitive itself. Most implementations in pure C are pretty straightforward, almost naive. Seriously, take a look.

> It needs math oriented people,

Mostly to design the primitives, and perform modulo arithmetic on huge numbers. That's about it.

> it needs OS-oriented people,

Only if you're writing the random number generator of an OS kernel. For the rest, portable C code is enough. You don't even need heap allocation.

> people who are experienced with exploiting systems.

Not quite. You need people who are able to write correct code, thus avoiding undefined behaviour. By the way this applies to everything, not just crypto.

> there's no reason to do it for production.

Dependency management. It's not a very good reason, but if you only use one or two primitives, importing libsodium may not be worth it.

> The problem is that in computer security defense is a lot harder than offense. If you make just one mistake, it can often lead to a compromised system.

It doesn't have to be the crypto library's fault. A single buffer overrun anywhere, and you risk giving your keys to the attacker —if that didn't already served the whole server on a silver platter. You won't be secure just because you use OpenSSL or libsodium as intended. Even if your crypto library is bug free and immune to side-channel attacks.

The greater risk is not crypto code. It's user code. Implementing your own crypto code is not going to increase the risk by much —or at all, if you're sane enough to turn on warnings, use Valgrind/Purify, write tests, and have your code reviewed.

> Anyway, there's a lot of discussion on this topic around security.stackexchange, quora, reddit etc. The consensus is that it's a terrible idea.

With all due respect, fuck consensus. Read the expert's writings. Daniel J. Bernstein in particular has written some very good stuff on why he started to write the NaCl library. Or on how he designed his primitives to be simple, and as such easily analysable by his peers. Or on how easily one can avoid timing attacks (hint: don't use AES).

Post reply on HN