5 ms·

I wrote an LLVM-powered trace-based JIT for Brainfuck

64 points by Halienja 16y ago

davidw 16y ago
I don't know... "neat hack", but it seems there is so much out there that could actually have some kind of practical application that it's a bit of a waste to work on "silly" projects. I love to hack on things that don't have any immediately evident business model or real world application, but I think purposefully working on something that never will is perhaps a bit unfortunate. Yeah, he learned something for sure, but that's pretty much all it can be. To expand on that: if he'd written his own toy language, say, odds are it would never go anywhere, but, who knows... maybe it will find a niche. Using "brainfuck" pretty much guarantees that the code will never find a practical use.
- igravious 16y ago
  oh look! http://en.wikipedia.org/wiki/Art_for_arts_sake http://en.wikipedia.org/wiki/Art_for_arts_sake
  - davidw 16y ago
    Yeah, I don't think of programming as an art, but a craft, so that's why I have the point of view I do. There are tons of projects that will never go anywhere, done just for learning or as neat hacks, but why ensure that one won't?
    - StavrosK 16y ago
      It's the same as carpentry and sculpting. It's the same thing, but one is a craft and the other is an art. This guy just took time off making furniture to build a sculpture. Sure, he could have made a new kind of furniture, but making sculptures also has its merits (or not, depending on your viewpoint, I guess).
  - deleted 16y ago
    [deleted]
- eelco 16y ago
  That's not the point. These are the kind of projects programmers do for fun. Your comments is like saying "if this guy didn't go the zoo, but rather spent his day at work, he at least might have been productive". Now, I can imagine you wouldn't enjoy watching somebody else's pictures of zoo animals, unless you were very interested in zoo animals, like, say, some people are interested in compiler technology and/or esoteric languages. Because Brainfuck is an insanely simple language to compile/interpret it's actually makes for a nice small example!
  - davidw 16y ago
    I did a small language for fun: http://www.hecl.org http://www.hecl.org And it has actually turned out to be useful, besides being a lot of fun to work on. I am not saying fun projects need to be useful (I'd be the last one to say that), I'm saying "why ensure they'll never be useful?". Here's another language that is a 'fun project' that, who knows, might be quite useful some day: http://wiki.reia-lang.org/wiki/Reia_Programming_Language http://wiki.reia-lang.org/wiki/Reia_Programming_Language Edit and the classic "hobby project": > "I'm doing a (free) operating system (just a hobby, won't be big and professional like gnu) for 386(486) AT clones. Once again, by not tying a rock to his leg, it eventually went on to be just a bit more important than a hobby project.
    - buro9 16y ago
      > I am not saying fun projects need to be useful (I'd be the last one to say that), I'm saying "why ensure they'll never be useful?". Because some things are done for learning exercises and nothing more. Just because that code isn't going to do anything useful when executed, it does not mean that there is no value in the exercise of producing or sharing the code. Not that it needs that much justification, fun is a good enough reason.
      - davidw 16y ago
        Ok, you people are seriously failing to comprehend that which I am attempting to communicate to you. * I have no problems with 'fun projects'. I do them myself. * I have no problem with 'useless code'. Many fun projects are never useful. I have done these myself. * I have no problem with learning for learning's sake. I have engaged in lots of that. What I don't agree with is artificially limiting your project's potential. By choosing to implement brainfuck, instead of Tcl or Lua or Forth or Lisp or any number of other languages (even if it's just a toy version, and not the full spec), you've consigned your project to the dustbin before you've even finished it. To my way of thinking, that just doesn't make any sense. If you want to be artistic, go out and make your own language.
- vox 16y ago
  I'm assuming you've been downvoted because slightly more than 50% of HNers think of this project as an artistic/fun project. But the fact is, even a purely artistic/fun project will have some creativity or originality in it. I would consider a toy language or Brainf__k written for the first time as artistic. But this project is just a JIT for Brainf__k, there's no creativity in it, and all it did was give the author some experience writing JITs. In that sense this is an exercise project, and IMO exercise projects do not belong to HN.
  - StavrosK 16y ago
    Does HN censor the "fuck" in "Brainfuck", or was it just you? EDIT: Ah, it doesn't.
    - steveklabnik 16y ago
      Generally, as long as it's part of something constructive and adds rather than detracts from the message, the community won't downvote profanity. http://news.ycombinator.com/item?id=1636262 http://news.ycombinator.com/item?id=1636262
  - jrockway 16y ago
    exercise projects do not belong to [sic] HN You've used HN for 38 days and you are already saying what kinds of programming articles should and shouldn't be on HN? Sorry, but this is exactly the sort of thing we should see on HN. But this project is just a JIT for Brainfuck, there's no creativity in it, and all it did was give the author some experience writing JITs. How exactly do you define creative? The author applied his programming skills to create something that didn't exist before. That's creative.
  - travisa 16y ago
    As someone interested in compiler technology, I was happy to see a simple example of a tracing JIT in LLVM. See: http://lambda-the-ultimate.org/node/3851 http://lambda-the-ultimate.org/node/3851
- api 16y ago
  This is an awesome project to look at to learn how to write a JIT. BF is simple enough that it's easy to see what's going on. Learning is silly and useless?
  - davidw 16y ago
    > Learning is silly and useless? Yes, that's precisely what I said, isn't it.
- jrockway 16y ago
  I can't disagree more. This is a great project for learning how to use LLVM because there is nothing to add complexity. There is no need for a runtime library. There is no need for a complicated parser. With those parts gone, all that matters is building the compiler, JIT core, tracing algorithm, and so on. Now that the author knows how to do all that, he's mentally prepared to be productive when taking on a more complex task, like writing his own language or improving an existing one. You seem to think that because it's on Github you're supposed to use it. Incorrect. Github is just a public backup and a way of sharing something with your friends. Kind of like posting your drunken photos on Facebook. Productive? No. Fun? Yes.
  - davidw 16y ago
    > You seem to think that because it's on Github you're supposed to use it. Actually, if you read my post, you would have understood that that is not the case:-/ Your point about it being a "minimum viable language" is a good one though, but I find it difficult to think there isn't something else he could have chosen.
    - jrockway 16y ago
      find it difficult to think there isn't something else he could have chosen Why do you care? How does this affect you in any way?
      - davidw 16y ago
        It's obviously not my place to say what other people do with their time. It just seems like wasted effort to me; that's all. I guess arguing against the groupthink (replete with reddit style mob downvoting) is an even bigger waste of time, though.
        jrockway 16y ago
        Seems like you have 18,000 more upvotes than downvotes, so maybe you are just in a bad mood today. Deep breath and smile!
- resistor 16y ago
  Hey, I'm the actual author of this. I actually work on LLVM-proper during my day job. This was just a fun exercise to demonstrate that it was possible. I also have plans to write a tutorial based on it.
- InclinedPlane 16y ago
  Nothing wrong with having some fun now and again. Not all of our time should belong to others. If it did life would be a dreary experience indeed.
VMG 16y ago
Nice work - can you give us some data on how it is?
- VMG 16y ago
  (how fast it is of course)
udzinari 16y ago
I wish I had free time too! brainfuck is boring though.. why not some stack based language with lisp like syntax or something like that.
danieldk 16y ago
Nice work! Let me make a tiny plug for a short Sunday project as well... Brainf*ck in Prolog: http://github.com/danieldk/brainfuck-pl/ http://github.com/danieldk/brainfuck-pl/ One nice thing is that unit testing is really simple: http://github.com/danieldk/brainfuck-pl/blob/master/unittests.pl http://github.com/danieldk/brainfuck-pl/blob/master/unittest... And for some very trivial outputs, it can generate the program to create that output. ?- brainfuck:interpret([A,B],[],[0],[0],[1,0]). A = <, B = + ? Ps. Yes, it's easy to improve generation...
mathgladiator 16y ago
Is anyone else oddly inspired to make an OCaml to Brainfk translator just to build a staggeringly awesome rube goldberg machine?
- koenigdavidmj 16y ago
  I can not find it, but I have seen a C to brainfuck compiler. Don't ask.
  - RodgerTheGreat 16y ago
    Here's the best reference page for the project: http://esolangs.org/wiki/C2BF http://esolangs.org/wiki/C2BF
resistor 16y ago
Hey folks, I'm the actual author of this. I actually work on LLVM-proper during my day job. This was just a fun exercise to demonstrate that it was possible. I also have plans to write a tutorial based on it.
- resistor 16y ago
  Also an example of how to implement a direct-threaded interpreter. Some performance data from a Brainfuck mandelbrot benchmark. Interpreter: 37.787s Tracing JIT: 11.716s Static Compiler: 2.402s The tracing JIT loses out to the static compiler largely because there's no dynamic dispatch in Brainfuck for the tracer to optimize out. There's probably some performance to be recovered by tuning the tracer thresholds and minor optimizations, but I would be shocked if it ever beat the static compiler at least for Brainfuck.
  - samps 16y ago
    Thanks for writing this -- it's awesome to see JIT principles boiled down to the point where you can easily understand the whole system. Please let us know if you publish the tutorial; I'd love to see more detail on the JIT. In particular, it would be the perfect template to demonstrate feedback-directed optimization opportunities and to measure the overhead of tracing; it would be incredibly interesting to see what has to be done to make the JIT outperform the AOT compiler.
    - resistor 16y ago
      The tracing overheads are pretty huge. Running with tracing but without compilation takes 107s.
      - samps 16y ago
        Hefty! As an exercise, any sense in inlining the tracing into compiled code? That way you sacrifice the startup time benefits of the JIT (by AOT compiling at start) but still retain trace specialization.

64 points by Halienja 16y ago

I don't know... "neat hack", but it seems there is so much out there that could actually have some kind of practical application that it's a bit of a waste to work on "silly" projects. I love to hack on things that don't have any immediately evident business model or real world application, but I think purposefully working on something that never will is perhaps a bit unfortunate. Yeah, he learned something for sure, but that's pretty much all it can be. To expand on that: if he'd written his own toy language, say, odds are it would never go anywhere, but, who knows... maybe it will find a niche. Using "brainfuck" pretty much guarantees that the code will never find a practical use.

igravious 16y ago
oh look! http://en.wikipedia.org/wiki/Art_for_arts_sake http://en.wikipedia.org/wiki/Art_for_arts_sake
- davidw 16y ago
  Yeah, I don't think of programming as an art, but a craft, so that's why I have the point of view I do. There are tons of projects that will never go anywhere, done just for learning or as neat hacks, but why ensure that one won't?
  - StavrosK 16y ago
    It's the same as carpentry and sculpting. It's the same thing, but one is a craft and the other is an art. This guy just took time off making furniture to build a sculpture. Sure, he could have made a new kind of furniture, but making sculptures also has its merits (or not, depending on your viewpoint, I guess).
- deleted 16y ago
  [deleted]
eelco 16y ago
That's not the point. These are the kind of projects programmers do for fun. Your comments is like saying "if this guy didn't go the zoo, but rather spent his day at work, he at least might have been productive". Now, I can imagine you wouldn't enjoy watching somebody else's pictures of zoo animals, unless you were very interested in zoo animals, like, say, some people are interested in compiler technology and/or esoteric languages. Because Brainfuck is an insanely simple language to compile/interpret it's actually makes for a nice small example!
- davidw 16y ago
  I did a small language for fun: http://www.hecl.org http://www.hecl.org And it has actually turned out to be useful, besides being a lot of fun to work on. I am not saying fun projects need to be useful (I'd be the last one to say that), I'm saying "why ensure they'll never be useful?". Here's another language that is a 'fun project' that, who knows, might be quite useful some day: http://wiki.reia-lang.org/wiki/Reia_Programming_Language http://wiki.reia-lang.org/wiki/Reia_Programming_Language Edit and the classic "hobby project": > "I'm doing a (free) operating system (just a hobby, won't be big and professional like gnu) for 386(486) AT clones. Once again, by not tying a rock to his leg, it eventually went on to be just a bit more important than a hobby project.
  - buro9 16y ago
    > I am not saying fun projects need to be useful (I'd be the last one to say that), I'm saying "why ensure they'll never be useful?". Because some things are done for learning exercises and nothing more. Just because that code isn't going to do anything useful when executed, it does not mean that there is no value in the exercise of producing or sharing the code. Not that it needs that much justification, fun is a good enough reason.
    - davidw 16y ago
      Ok, you people are seriously failing to comprehend that which I am attempting to communicate to you. * I have no problems with 'fun projects'. I do them myself. * I have no problem with 'useless code'. Many fun projects are never useful. I have done these myself. * I have no problem with learning for learning's sake. I have engaged in lots of that. What I don't agree with is artificially limiting your project's potential. By choosing to implement brainfuck, instead of Tcl or Lua or Forth or Lisp or any number of other languages (even if it's just a toy version, and not the full spec), you've consigned your project to the dustbin before you've even finished it. To my way of thinking, that just doesn't make any sense. If you want to be artistic, go out and make your own language.
vox 16y ago
I'm assuming you've been downvoted because slightly more than 50% of HNers think of this project as an artistic/fun project. But the fact is, even a purely artistic/fun project will have some creativity or originality in it. I would consider a toy language or Brainf__k written for the first time as artistic. But this project is just a JIT for Brainf__k, there's no creativity in it, and all it did was give the author some experience writing JITs. In that sense this is an exercise project, and IMO exercise projects do not belong to HN.
- StavrosK 16y ago
  Does HN censor the "fuck" in "Brainfuck", or was it just you? EDIT: Ah, it doesn't.
  - steveklabnik 16y ago
    Generally, as long as it's part of something constructive and adds rather than detracts from the message, the community won't downvote profanity. http://news.ycombinator.com/item?id=1636262 http://news.ycombinator.com/item?id=1636262
- jrockway 16y ago
  exercise projects do not belong to [sic] HN You've used HN for 38 days and you are already saying what kinds of programming articles should and shouldn't be on HN? Sorry, but this is exactly the sort of thing we should see on HN. But this project is just a JIT for Brainfuck, there's no creativity in it, and all it did was give the author some experience writing JITs. How exactly do you define creative? The author applied his programming skills to create something that didn't exist before. That's creative.
- travisa 16y ago
  As someone interested in compiler technology, I was happy to see a simple example of a tracing JIT in LLVM. See: http://lambda-the-ultimate.org/node/3851 http://lambda-the-ultimate.org/node/3851
api 16y ago
This is an awesome project to look at to learn how to write a JIT. BF is simple enough that it's easy to see what's going on. Learning is silly and useless?
- davidw 16y ago
  > Learning is silly and useless? Yes, that's precisely what I said, isn't it.
jrockway 16y ago
I can't disagree more. This is a great project for learning how to use LLVM because there is nothing to add complexity. There is no need for a runtime library. There is no need for a complicated parser. With those parts gone, all that matters is building the compiler, JIT core, tracing algorithm, and so on. Now that the author knows how to do all that, he's mentally prepared to be productive when taking on a more complex task, like writing his own language or improving an existing one. You seem to think that because it's on Github you're supposed to use it. Incorrect. Github is just a public backup and a way of sharing something with your friends. Kind of like posting your drunken photos on Facebook. Productive? No. Fun? Yes.
- davidw 16y ago
  > You seem to think that because it's on Github you're supposed to use it. Actually, if you read my post, you would have understood that that is not the case:-/ Your point about it being a "minimum viable language" is a good one though, but I find it difficult to think there isn't something else he could have chosen.
  - jrockway 16y ago
    find it difficult to think there isn't something else he could have chosen Why do you care? How does this affect you in any way?
    - davidw 16y ago
      It's obviously not my place to say what other people do with their time. It just seems like wasted effort to me; that's all. I guess arguing against the groupthink (replete with reddit style mob downvoting) is an even bigger waste of time, though.
      - jrockway 16y ago
        Seems like you have 18,000 more upvotes than downvotes, so maybe you are just in a bad mood today. Deep breath and smile!
resistor 16y ago
Hey, I'm the actual author of this. I actually work on LLVM-proper during my day job. This was just a fun exercise to demonstrate that it was possible. I also have plans to write a tutorial based on it.
InclinedPlane 16y ago
Nothing wrong with having some fun now and again. Not all of our time should belong to others. If it did life would be a dreary experience indeed.

VMG 16y ago

Nice work - can you give us some data on how it is?

VMG 16y ago
(how fast it is of course)

udzinari 16y ago

I wish I had free time too! brainfuck is boring though.. why not some stack based language with lisp like syntax or something like that.

danieldk 16y ago

Nice work! Let me make a tiny plug for a short Sunday project as well... Brainf*ck in Prolog: http://github.com/danieldk/brainfuck-pl/ http://github.com/danieldk/brainfuck-pl/ One nice thing is that unit testing is really simple: http://github.com/danieldk/brainfuck-pl/blob/master/unittests.pl http://github.com/danieldk/brainfuck-pl/blob/master/unittest... And for some very trivial outputs, it can generate the program to create that output. ?- brainfuck:interpret([A,B],[],[0],[0],[1,0]). A = <, B = + ? Ps. Yes, it's easy to improve generation...

mathgladiator 16y ago

Is anyone else oddly inspired to make an OCaml to Brainfk translator just to build a staggeringly awesome rube goldberg machine?

koenigdavidmj 16y ago
I can not find it, but I have seen a C to brainfuck compiler. Don't ask.
- RodgerTheGreat 16y ago
  Here's the best reference page for the project: http://esolangs.org/wiki/C2BF http://esolangs.org/wiki/C2BF

resistor 16y ago

Hey folks, I'm the actual author of this. I actually work on LLVM-proper during my day job. This was just a fun exercise to demonstrate that it was possible. I also have plans to write a tutorial based on it.

resistor 16y ago
Also an example of how to implement a direct-threaded interpreter. Some performance data from a Brainfuck mandelbrot benchmark. Interpreter: 37.787s Tracing JIT: 11.716s Static Compiler: 2.402s The tracing JIT loses out to the static compiler largely because there's no dynamic dispatch in Brainfuck for the tracer to optimize out. There's probably some performance to be recovered by tuning the tracer thresholds and minor optimizations, but I would be shocked if it ever beat the static compiler at least for Brainfuck.
- samps 16y ago
  Thanks for writing this -- it's awesome to see JIT principles boiled down to the point where you can easily understand the whole system. Please let us know if you publish the tutorial; I'd love to see more detail on the JIT. In particular, it would be the perfect template to demonstrate feedback-directed optimization opportunities and to measure the overhead of tracing; it would be incredibly interesting to see what has to be done to make the JIT outperform the AOT compiler.
  - resistor 16y ago
    The tracing overheads are pretty huge. Running with tracing but without compilation takes 107s.
    - samps 16y ago
      Hefty! As an exercise, any sense in inlining the tracing into compiled code? That way you sacrifice the startup time benefits of the JIT (by AOT compiling at start) but still retain trace specialization.