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

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

github.com

Post reply on HN
Print view View original

51–56 of 56 posts

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

#51

Post by resistor »

samps wrote: post #49
resistor wrote: post #48

Earlier quoted context omitted.

The tracing overheads are pretty huge. Running with tracing but without compilation takes 107s.

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.

You could certainly do that, though the interface between statically JIT'd code and trace JIT'd code would get hairy. Plus, as I said above, there's simply not a whole lot of trace specialization going on in the first place, since Brainfuck lacks dynamic dispatch.

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

#52

Post by InclinedPlane »

davidw wrote: post #2

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,…

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.

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

#53

Post by InclinedPlane »

steveklabnik wrote: post #31
jrockway wrote: post #17

Earlier quoted context omitted.

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 com…

> This is a great project for learning how to use LLVM because there is nothing to add complexity. Speaking as someone who's written a very simple Brainfuck interpreter, this is absolutely spot-on. As someone who'd never written an interpreter before, I didn't want to have to think about the language itself, just focus on getting the absolute fundamentals down.

More so, because it's Brainfuck you don't have to worry about people mistaking it for a serious project, so you can concentrate on the educational aspect rather than fine-tuning the performance, fixing every single bug, etc.

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

#54

Post by mikemike »

resistor wrote: post #48
samps wrote: post #44

Earlier quoted context omitted.

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…

The tracing overheads are pretty huge. Running with tracing but without compilation takes 107s.

The performance problems originate in the design of your trace compiler, not in static vs. dynamic dispatch. Some suggestions:

* The interpreter should have a fast profiling mode (hashed counting of loop backedges) and a slower recording mode (for every instruction call the recorder first, then execute the instruction). Either implement it twice (it's small enough), use a modifiable dispatch table and intercept the dispatch in recording mode (indirect threading), or compute branch offsets relative to a base (change the base to switch modes).

* Don't record traces for a long time and then compile everything together. Do it incrementally:

- Detect a hot loop, switch into recording mode, record a trace, compile it, attach it to the bytecode, switch to profiling mode (which may call your compiled trace right away).

- Make the side exits branch to external stubs which do more profiling (one counter per exit). Start recording hot traces and continue until it hits an existing trace or abort if it hits an uncompiled loop.

- If you completely control the machine code generation (i.e. not with LLVM), you can attach the side traces to their branch points by patching the machine code. Otherwise you may need to use indirections or recompile clusters of the graph after a certain threshold is reached.

- Region selection has a major impact on performance, so be prepared to carefully tune the heuristics.

* Sink all stores, especially updates of the virtual PC, data pointers etc. Don't count on the optimizer to do this for you.

* Due to the nature of the source language you may need to preprocess the IR or you need to teach the optimizer some additional tricks.

- E.g. the loop [-] should really be turned into 'data[0] = 0'.

- Or the loop [->>>+- It's unlikely any optimizer handles all of these cases, since no sane programmer would write such code ... oh, wait. :-)

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

#55

Post by resistor »

mikemike wrote: post #54
resistor wrote: post #48

Earlier quoted context omitted.

The tracing overheads are pretty huge. Running with tracing but without compilation takes 107s.

The performance problems originate in the design of your trace compiler, not in static vs. dynamic dispatch. Some suggestions: * The interpreter should have a fast profiling mode (hashed counting of loop backedges) and a slower recording mode (for every instruction call the recorder first, then execute the instruction). Either implement it twice (it's small enough), use a modifiable dispatch table and intercept the d…

> * The interpreter should have a fast profiling mode (hashed counting of loop backedges) and a slower recording mode (for every instruction call the recorder first, then execute the instruction).

It already does this. The recording method is specialized for '[' (since loop headers can only be '['). All other opcodes go through a fast path that simply checks if we're in recording mode and stores to the trace buffer.

> * Don't record traces for a long time and then compile everything together.

The tricky part with this is knowing how to start up the profiler when we hit a side-exit. PC 123 may occur at multiple places in the trace tree. If we want to extend the tree on side-exit, we need to be able to recreate the path through the trace tree that led to that point. In essence, we need the compiled trace to continue updating the trace buffer. Certainly possible, but doesn't seem like a great idea offhand.

> * Sink all stores, especially updates of the virtual PC, data pointers etc. Don't count on the optimizer to do this for you.

Because I'm using tail-call based direct threading, there are no stores to the virtual PC or the data pointer. They're passed in registers to the tail-callee.

> * Due to the nature of the source language you may need to preprocess the IR or you need to teach the optimizer some additional tricks.

Yes, there's a whole range of pre-processing tricks that could be used to accelerate both the interpreter and the traces. I haven't even scratched the surface of that.

Post reply on HN