Optimizing Brainfuck interpreter in the C preprocessor | Hacker News Reader

Optimizing Brainfuck interpreter in the C preprocessor

github.com

45 pointsnamanyayg12 comments

Open articleView on HN

As per usual the qualifying question if it can handle the Mandelbrot renderer -

https://github.com/erikdubbelboer/brainfuck-jit/blob/master/...

Unlikely, given that hello world takes 20 minutes to run.

I think you may be looking at the wrong column. Hello World runs in 0.020s, per the benchmarks.

bfcpp[1] seems to be the most performant.

[1] https://github.com/Haruno19/bfcpp

The explanation document is interesting: https://github.com/camel-cdr/bfcpp/blob/main/TUTORIAL.md

> https://github.com/camel-cdr/bfcpp/blob/main/TUTORIAL.md#32-...

> loops like [-], [>] and [<] could even be completely reduced to a single operation.

This has got me wondering if it would make sense to pre-process the BF programs I've been using in genetic programming experiments. Loops are the #1 thing that slow down the search. But, I don't know that this optimization pass would be paid for in the typical case - at least not until the average complexity of the population reaches a certain point.

Optimising the program absolutely will win in general, because the optimisations are extremely cheap and very impactful. See https://github.com/john-h-k/rustfuck for an example of the sort of speedup differences you can get with different optimisation levels

Could the optimizer still help in the general case if you only ever intend to run each program one time?

If so, I probably need to spend a lot more time in this rabbit hole.

Yes. The biggest win (that you may already do) is recording branch positions, so when you hit a `[` or `]` knowing exactly where to jump through rather than going left/right. My interpreter above isn't the most advanced (it was a few hours while hungover because it seemed fun!), but try throwing it at your thing and I suspect it could help.

``` cargo install --git https://github.com/john-h-k/rustfuck

rustfuck <source> --lir # or --jit if you are on arm64 and don't need to read from stdin ```

Im curious about what you're working on. Do you have a repo for the project?

As for optimizations, I figure evolution-designed languages might come up with things that are hard to pattern match for more complex operations.

The core idea of what I am working on is to build a solution that can generate programs capable of converting arbitrary input to arbitrary output (bytes to bytes) based on a reasonable quantity of training data.

I'm trying to determine if a more symbolic approach may lend itself to broader generalization capabilities in lieu of massive amounts of training data. I am also trying to determine if dramatically simplified, CPU-only architectures could be feasible. I.e., ~8 interpreted instructions combined with clever search techniques (tournament selection & friends).

I don't have anything public yet. I am debating going wide open for better collaboration with others.

> I figure evolution-designed languages might come up with things that are hard to pattern match for more complex operations.

I think I agree with this - once you hit a certain level of complexity things would get really hard to anticipate. The chances you would hit good patterns would probably drop over time as the model improves.

I've been looking at an adjacent idea wherein a meta program is responsible for authoring the actual task program each time, but I haven't found traction here yet. Adding a 2nd layer really slows down the search. And, the fitness function for the meta program is a proxy at best unless you have a LOT of free time to critique random program sources.

I guess this is a good opportunity to show off my Zig comptime implementation of Brainfuck.

https://github.com/ginkgo/Zig-comptime-brainfuck

Reply on news.ycombinator.com