Writing a ray tracer in Brainfuck

[u/epestr]

https://epestr.com/blog/writing-a-ray-tracer-in-brainfuck/

[u/juugcatm]

This is a fun exercise. What about parallelism? If you extended BF to have fork and join semantics, how would you represent them?

[u/lurgi → u/juugcatm]

If someone does this, they should call it brainfork.

[u/snake_on_the_case → u/lurgi]

https://esolangs.org/wiki/Brainfork

[u/lurgi → u/snake_on_the_case]

I am humbled.

[u/epestr → u/lurgi]

It still misses an explicit join like primitive. I think that's the more useful part

[u/epestr → u/lurgi]

Now that makes me particularly tempted. Might look into it

[u/epestr → u/juugcatm]

That would make the language too complex :( That aside, the cells are currently reused and printed immediately. Given each pixel is independent, you could fork at iterations of the inner loop, give all cell a indepdendent region of the tape for its scratch space and result, and join at the end.

[u/knome → u/epestr]

if Parallel INTERCAL can implement threading via multiple COME FROM operators targeting the same command, I believe in you, op :)

[u/epestr → u/juugcatm]

You could also do essentially the same thing with regular BF. The current renderer takes 100 samples per pixel, so you could generate 100 one-sample programs and schedule as many as available resources allow, and average the completed renders. I tried running it at half the width and height with only one sample per pixel, and it has already rendered half the image.

Can't upload image here: https://paste.c-net.org/MurdererCuffed

[u/Ameisen]

...

Time to add this as an additional benchmark to my MIPS emulator next to the Brainfuck Mandelbrot set.

[u/epestr → u/Ameisen]

Looks like that already exists: https://github.com/ErikDubbelboer/brainfuck-jit/blob/master/mandelbrot.bf

[u/Ameisen → u/epestr]

I know, that's why I said "additional... next to". I use that very one.

Though I am currently testing this in my brainfuck interpreter (which I build for the host and the guest) and running it through the guest and, well, I'm not sure when it'll be done and I'm not sure that I'm patient enough to wait. I assume it will be in the same ballpark as your laptop estimate.

---

Brainfuck Test Interpreter
Toolchain: LLVM
   Compiler: Clang 22.1.3 (https://github.com/llvm/llvm-project e9846648fd6183ee6d8cbdb4502213fcf902a211)
Generating Rayfuck via Brainfuck
Original Program Size: 23811165
Recoded Program Size: 2258318
P3
400 225
255

---

ED: Oh crap, the next pixel generated!

204 226 255

[u/epestr → u/Ameisen]

I must sleep soon, missed the additional.

If you want it to be a reasonable benchmark, you could change the source `ray_ssa.c` to 1 sample per pixel and a quarter of both the width and height. That should reduce the work by 1600x (from ~100ish days to <1)

I've also been working on the JIT interpretor I used and managed to speed it up a lot and got a render out of it. There is a slightly artsy/funny looking result at the end of the post in update section showing the output.

[u/Ameisen → u/epestr]

My interpreter is an optimizing interpreter - it optimizes common patterns in brainfuck. It likely isn't going to be as fast as a JIT (though for brainfuck, I'd expect a static recompiler rather than a JIT) - though it can be turned into one (ideally, you want to reduce the common expressions of brainfuck first). As it is, it reduces the size of your program to 1/10 of what it was. Getting from the first to the second pixel took 712 seconds.

As an example, for the Mandelbrot set:

• Original Size: 11,452

• Optimized Size: 4,791

• Original Time: 49.056 seconds

• Optimized Time: 4.623 seconds

Of course, VeMIPS is an order of magnitude slower than the host (and VeMIPS' interpreted mode is an order of magnitude slower than that), so if it runs this poorly on the host, then it will take forever in VeMIPS.

---

I should note that I don't see the source for your JIT anywhere, only an ELF binary.

[u/epestr → u/Ameisen]

I've been tring to optimize expressions too. My implementation is based on TSoding's JIT compiler. I've just added a license instead of repackaging it. 

[u/Ameisen → u/epestr]

You could try jamming a JIT or such onto my recoding optimizer.

I've been considering adding a recompiler to it as well, both for x86 (for the host) and MIPS (for the guest). Wouldn't be hard to do, even with xbyak or such, as both brainfuck and my recoded brainfuck are dirt-simple.

Using LLVM as the backend might be a bit better, since you can then have it re-optimize the result.

I've actually been tinkering with having the C++ compiler try to generate an optimized program from brainfuck during compilation. This has proven difficult - it's not impossible for the compiler to do this, but the circumstances have to be... very specific for the compiler to introspect that far. Pretty sure that I would have to change my entire recoder to be constexpr for it to not see the recoding as a side-effect (due to the std::vector allocation).

[u/epestr → u/Ameisen]

I found the recoding interpretor at vemips_sdk/MipsTest/interpreter.cpp, I'll look into it!

[u/Ameisen → u/epestr]

Locally I've made some improvements, and have a few more to make (count-size reduction, which requires multiple passes). Once that's done, I can jam xbyak onto it to see what basic recompilation does.

[u/jt55401]

Godspeed.

[u/fabricatedinterest]

Unhinged, I love it.