9
\$\begingroup\$

the goal

Build an optimizing Brainfuck implementation. Whether it is a compiler, an interpreter, a JIT compiler, or whatever else is up to you.

scoring

A reference implementation (bfi) will be given. Each implementation will run the same program (mb.b) also given at the end.

Your score is

time spent to run `mb.b` translated by `bfi`
/ time spent to run `mb.b` translated by your implementation

rounded to 3 decimal digits.

If mb.b through bfi runs in 20 seconds and through yours in 7 seconds, the score is 20 / 7 = 2.8571.. rounded to 2.857.

If your implementation compiles mb.b to an intermediate or final form, such compilation time is not measured.

The time measurement will be done on your machine.(1)

requirements

Your implementation should work on at least one platform, which may be an obscure one or even a virtual environment, but it should be able to also run the reference implementation for comparison.

You can rely on an existing backend such as llvm, or even a source-to-source compiler is possible. You can use any external program during the translation of the Brainfuck program.

possible strategies

  • Compile to native code rather than interpret it.
  • Most machines can add or subtract arbitrary numbers very fast. You can replace a series of +, -, >, < to a single operation.
  • Postpone pointer movements. >+>-> can be translated to p[1] += 1; p[2] -= 1; p += 3;.
  • Remove loops. A common way to zero a cell is [-]. This is the same as p[0] = 0. [->+<] is p[1] += p[0]; p[0] = 0.

reference implementation

Compile the program with gcc version 9.3 or higher with the given flags. gcc 9.3 was released on March 12, 2020 and is ported to a variety of platforms. If you think this requirement is unreasonable for your target platform, let me know on the comments.

gcc -obfi -s -O3 -march=native bfi.c

bfi.c

#include <stdio.h>
#include <stddef.h>

typedef unsigned char byte;

static void interpret(byte *cp, byte *ip, int j) {
    byte *s[0x100];
    size_t i = -1;
    for (; *ip; ++ip) {
        if (!j) {
            switch (*ip) {
            case '>':
                ++cp;
                break;
            case '<':
                --cp;
                break;
            case '+':
                ++*cp;
                break;
            case '-':
                --*cp;
                break;
            case '.':
                putchar(*cp);
                break;
            case ',':
                *cp = getchar();
                break;
            case '[':
                if (*cp) {
                    s[++i] = ip;
                } else {
                    ++j;
                }
                break;
            case ']':
                if (*cp) {
                    ip = s[i];
                } else {
                    --i;
                }
            }
        } else if (*ip == '[') {
            ++j;
        } else if (*ip == ']') {
            --j;
        }
    }
}

int main() {
    static byte b[0x8000];
    FILE *f = fopen("mb.b", "r");
    fread(b + sizeof(b) / 2, 1, sizeof(b) / 2, f);
    fclose(f);
    interpret(b, b + sizeof(b) / 2, 0);
    return 0;
}

mb.b (pastebin, online interpreter)


(1) One may think that the scoring method is not fair because, I know, each machine has its own qualities and the score will be different across different machines. But, this is not a serious competition. I'm just providing a puzzle, some subject to think about, that might be interesting enough for some people to spend their time on. If someone comes up with an interesting algorithm, that is an interesting algorithm, nothing changes whether a fair score is there or not. The score is there just as a hint showing how effective the optimization was.

* While there are no rules to prevent you from optimizing too specifically for the test program, such as hard-coding the output directly, for example. I believe that won't be interesting to anyone including yourself, so please try to apply general optimizations if you'd like to participate.

\$\endgroup\$
14
  • 2
    \$\begingroup\$ I'm concerned about the test case - because there's no user input to the program the optimal implementation could simply print out the result without actually running the code. \$\endgroup\$
    – nununoisy
    Feb 25, 2022 at 15:26
  • \$\begingroup\$ @nununoisy The current rules technically doesn't prevent such a solution. I could either add some rules or add some test cases. My initial thought was that such solution wouldn't be interesting to anyone including the author. And this isn't a serious competition. I'm just providing an interesting puzzle to people who might be interested to think about it. \$\endgroup\$
    – xiver77
    Feb 25, 2022 at 15:34
  • 3
    \$\begingroup\$ I’m voting to close this question because, per codegolf.meta.stackexchange.com/a/12708/46076, individual contestants running code on their own computers is not an objective winning criterion. \$\endgroup\$ Feb 25, 2022 at 18:01
  • 1
    \$\begingroup\$ I wrote an optimizing BF compiler a few years ago, and I'd like to ask whether it's allowable to enter it, or to improve it and then enter it. \$\endgroup\$ Feb 25, 2022 at 19:56
  • 2
    \$\begingroup\$ @TheFifthMarshal There's a subtle distinction between Dennis's comment there and how this question works: The runtime of Solution A on Computer A cannot be compared to the runtime of Solution B on Computer B, but this challenge compares the runtime of Solution A on Computer A with the runtime of Reference Solution on Computer A. That said, it still has flaws, such as what l4m2 mentioned. OP, I think it would be best if you ran all of the solutions on the same computer for comparison, or else asked one of us to do it. \$\endgroup\$
    – DLosc
    Mar 4, 2022 at 17:20

3 Answers 3

4
\$\begingroup\$

C++, 17.497/0.720=24.301

#include <stdio.h>
#include <stdlib.h>
int main() {
    freopen("mb.b", "r", stdin);
    freopen("2g.c", "wb", stdout);
    puts("char b[100000]; int main(){ char*p = b+50000;");
    while (1) {
        switch (getchar()) {
        case '+': puts("++*p;"); break;
        case '-': puts("--*p;"); break;
        case '>': puts("++p;"); break;
        case '<': puts("--p;"); break;
        case '[': puts("while(*p){"); break;
        case ']': puts("}"); break;
        case ',': puts("*p=getchar();"); break;
        case '.': puts("putchar(*p);"); break;
        case -1: goto done;
        }
    } done:;
    puts("}");
    fclose(stdout);
    system("gcc -s -O3 -march=native 2g.c -o 2g");
}

Just use the optimization of gcc

\$\endgroup\$
3
  • \$\begingroup\$ If you don't mind, could you remeasure the time that takes to run bfi? I rewrote it without recursion and maximum memory usage about 32KB. \$\endgroup\$
    – xiver77
    Feb 25, 2022 at 19:03
  • \$\begingroup\$ @xiver77 New time is user time. If still real time it's 17.749/0.738 \$\endgroup\$
    – l4m2
    Feb 26, 2022 at 2:27
  • \$\begingroup\$ Interesting to see how modern desktop CPUs handle recursion so good. The recursion wasn't optimized out in the original version when I checked (a lot of push and pops between recursive calls), but still, even on my computer the time isn't much different with the new one. \$\endgroup\$
    – xiver77
    Feb 26, 2022 at 3:38
3
\$\begingroup\$

Java with ObjectWeb ASM, \${98.055\over19.52}\$ = 5.023

Compiles BF to JVM bytecode. Applies optimizations such as collapsing [-] and collapsing multiple <>+- into one operation.

One thing to note: On my computer, the reference program crashes after printing 2/3 of the set. It takes 65.37 seconds before crashing, so I have manually adjusted my score using \${2\over3} x = 65.37\$

import org.objectweb.asm.ClassWriter;
import org.objectweb.asm.Label;
import org.objectweb.asm.MethodVisitor;
import org.objectweb.asm.Opcodes;

import java.io.IOException;
import java.lang.reflect.Method;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.ListIterator;

public class Main implements Opcodes {

    public static void main(String[] args) throws IOException {
        String program = Files.readString(Paths.get("mb.b"));
        Files.write(Path.of("Main.class"), compile(program));
    }

    private static byte[] compile(String program) {
        ClassWriter writer = new ClassWriter(ClassWriter.COMPUTE_FRAMES);
        writer.visit(V16, ACC_PUBLIC + ACC_SUPER, "Main", null, "java/lang/Object", null);
        writer.visitSource("Main.bf", null);

        // filter out unnecessary characters
        StringBuilder programBuilder = new StringBuilder();
        for (char c : program.toCharArray()) {
            if ("[]<>+-.,".indexOf(c) != -1) {
                programBuilder.append(c);
            }
        }
        program = programBuilder.toString();

        program = program.replace("[-]", "z");

        Deque<JumpPair> recurStack = new ArrayDeque<>();

        MethodVisitor mv = writer.visitMethod(ACC_PUBLIC + ACC_STATIC,
            "main",
            "([Ljava/lang/String;)V", null, null);
        mv.visitCode();

        // pointer, in var 0
        mv.visitInsn(ICONST_0);
        mv.visitVarInsn(ISTORE, 0);

        // memory, in var 1
        mv.visitLdcInsn(1000);
        mv.visitIntInsn(NEWARRAY, T_INT);
        mv.visitVarInsn(ASTORE, 1);

        ListIterator<Character> programIterator = program.chars().mapToObj(c -> (char) c).toList().listIterator();
        while (programIterator.hasNext()) {
            char c = programIterator.next();
            switch (c) {
                case '>' -> mv.visitIincInsn(0, count(c, programIterator));
                case '<' -> mv.visitIincInsn(0, -count(c, programIterator));
                case '+' -> {
                    mv.visitVarInsn(ALOAD, 1);
                    mv.visitInsn(DUP);
                    mv.visitVarInsn(ILOAD, 0);
                    mv.visitInsn(IALOAD);
                    chooseNumberInsn(count(c, programIterator), mv);
                    mv.visitInsn(IADD);
                    mv.visitVarInsn(ILOAD, 0);
                    mv.visitInsn(SWAP);
                    mv.visitInsn(IASTORE);
                }
                case '-' -> {
                    mv.visitVarInsn(ALOAD, 1);
                    mv.visitInsn(DUP);
                    mv.visitVarInsn(ILOAD, 0);
                    mv.visitInsn(IALOAD);
                    chooseNumberInsn(count(c, programIterator), mv);
                    mv.visitInsn(ISUB);
                    mv.visitVarInsn(ILOAD, 0);
                    mv.visitInsn(SWAP);
                    mv.visitInsn(IASTORE);
                }
                case '.' -> {
                    mv.visitFieldInsn(GETSTATIC, "java/lang/System", "out", "Ljava/io/PrintStream;");
                    load(mv);
                    mv.visitMethodInsn(INVOKEVIRTUAL, "java/io/PrintStream", "print", "(C)V", false);
                }
                case ',' -> {
                    mv.visitVarInsn(ALOAD, 1);
                    mv.visitVarInsn(ILOAD, 0);
                    mv.visitFieldInsn(GETSTATIC, "java/lang/System", "in", "Ljava/io/InputStream;");
                    mv.visitMethodInsn(INVOKEVIRTUAL, "java/io/InputStream", "read", "()I", false);
                    mv.visitInsn(IASTORE);
                }
                case '[' -> {
                    JumpPair jumpPair = new JumpPair(new Label(), new Label());
                    recurStack.push(jumpPair);
                    load(mv);
                    mv.visitJumpInsn(IFEQ, jumpPair.nextLabel());
                    mv.visitLabel(jumpPair.thisLabel());
                }
                case ']' -> {
                    JumpPair jumpPair = recurStack.pop();
                    load(mv);
                    mv.visitJumpInsn(IFNE, jumpPair.thisLabel());
                    mv.visitLabel(jumpPair.nextLabel());
                }
                case 'z' -> {
                    mv.visitVarInsn(ALOAD, 1);
                    mv.visitVarInsn(ILOAD, 0);
                    mv.visitInsn(ICONST_0);
                    mv.visitInsn(IASTORE);
                }
            }
        }

        mv.visitInsn(RETURN);
        mv.visitMaxs(0, 0);
        mv.visitEnd();

        writer.visitEnd();

        return writer.toByteArray();
    }

    private static record JumpPair(Label thisLabel, Label nextLabel) {
    }

    private static int count(char c, ListIterator<Character> programIterator) {
        int count = 1;
        while (programIterator.hasNext() && programIterator.next() == c) {
            count++;
        }
        programIterator.previous();
        return count;
    }

    private static void chooseNumberInsn(int number, MethodVisitor mv) {
        switch (number) {
            case -1 -> mv.visitInsn(ICONST_M1);
            case 0 -> mv.visitInsn(ICONST_0);
            case 1 -> mv.visitInsn(ICONST_1);
            case 2 -> mv.visitInsn(ICONST_2);
            case 3 -> mv.visitInsn(ICONST_3);
            case 4 -> mv.visitInsn(ICONST_4);
            case 5 -> mv.visitInsn(ICONST_5);
            default -> {
                if (number > Byte.MIN_VALUE && number < Byte.MAX_VALUE) {
                    mv.visitIntInsn(BIPUSH, number);
                } else if (number > Short.MIN_VALUE && number < Short.MAX_VALUE) {
                    mv.visitIntInsn(SIPUSH, number);
                } else {
                    mv.visitLdcInsn(number);
                }
            }
        }
    }

    private static void load(MethodVisitor mv) {
        mv.visitVarInsn(ALOAD, 1);
        mv.visitVarInsn(ILOAD, 0);
        mv.visitInsn(IALOAD);
    }
}
```
\$\endgroup\$
8
  • \$\begingroup\$ Huh? What kind of crash is it? a segfault? Could you try again by changing static byte b[0x8000]; to static byte b[0x10000];? But I don't think this will fix it if it really does crash.. I checked the program and ran some tests, but it really runs fine on my computer.. \$\endgroup\$
    – xiver77
    Mar 2, 2022 at 17:55
  • \$\begingroup\$ Also, what is your platform? Maybe fread isn't reading the input fully? Could you check the return value of fread? It should be about 11669. \$\endgroup\$
    – xiver77
    Mar 2, 2022 at 17:59
  • \$\begingroup\$ Using Windows 10, I have no idea what kind of crash. Running the exe in PowerShell prints 2/3 of the output and then Windows says that the exe stopped working. \$\endgroup\$
    – Seggan
    Mar 2, 2022 at 18:40
  • 1
    \$\begingroup\$ Strangely enough, using WSL prints the entire thing and then crashes the program. \$\endgroup\$
    – Seggan
    Mar 2, 2022 at 18:41
  • \$\begingroup\$ fread reports 11594 \$\endgroup\$
    – Seggan
    Mar 2, 2022 at 18:49
2
\$\begingroup\$

Python 3 / gcc, 17.737/0.527 = 33.657

This simple solution is based on @l4m2's, compiling to C which is then compiled by gcc. It collapses blocks composed only of <, >, + and - as much as possible and also squashes the simplest possible loops, those which contain one block between [ and ], have no overall data pointer movement, and change the loop counter by \$\pm 1\$.

A few years ago I wrote a much more complicated optimizing BF compiler (see comments above for the link) but the result is no faster than this on the Mandelbrot program.

#
# Python 3
#

import os
import sys

src = open('/tmp/bf.c', 'w')

print("""#include <stdio.h>

unsigned char b[100000];

int main(void)
{
  unsigned char *p = b + 50000;
  int c;
""", file=src)


def output_bb():
    global bb, ptr
    if start == '[':
        print("  while (*p != '\\0') {", file=src)
    elif start == ']':
        print("  }", file=src)
    elif start == '.':
        print("  putchar(*p);", file=src)
    elif start == ',':
        print("  *p = ((c = getchar()) == EOF ? '\\0' : (unsigned char)c);", file=src)
    else:
        assert start == '*'
    for ofs, diff in bb.items():
        if diff != 0:
            print(f"  p[{ofs}] += {diff};", file=src)
    if ptr != 0:
        print(f"  p += {ptr};", file=src)
    bb = {}
    ptr = 0


def optimize_bb():
    global bb, ptr
    for ofs, diff in bb.items():
        if diff != 0 and ofs != 0:
            print(f"  p[{ofs}] += {-diff * bb.get(0, 0)} * p[0];", file=src)
    print("  *p = '\\0';", file=src)
    bb = {}
    ptr = 0


bb = {}
ptr = 0
start = '*'

for ch in sys.stdin.read():
    if ch not in {'[', ']', '+', '-', '<', '>', ',', '.'}:
        continue

    if ch == ']' and start == '[' and ptr == 0 and bb.get(0, 0) in {1, -1}:
        optimize_bb()
        start = '*'
    elif ch == '+':
        bb[ptr] = bb.get(ptr, 0) + 1
    elif ch == '-':
        bb[ptr] = bb.get(ptr, 0) - 1
    elif ch == '<':
        ptr -= 1
    elif ch == '>':
        ptr += 1
    else:
        output_bb()
        start = ch

output_bb()

print("""  return 0;
}""", file=src)
src.close()

os.system("gcc -s -Wpedantic -W -Wall -Wextra -O3 -march=native -o /tmp/bf /tmp/bf.c")
\$\endgroup\$
2
  • 1
    \$\begingroup\$ I'll test later if your original optimizer is really "no more faster than this", but how could it be? Last time when I tested, I had to set the left and right range of cells, and set access outside the range as "undefined". Then, bfdb (is the name correct?) would emit a C program with the compile command. I then compiled the C program through GCC with all optimizations. This way, the C program given to GCC should have gone through more transformations from the BF program compared to the case of just running this short Python script. \$\endgroup\$
    – xiver77
    Mar 3, 2022 at 18:57
  • 1
    \$\begingroup\$ bfdb goes to a lot more trouble and produces more concise C as output, but this doesn't result in better runtime, at least with my computer, version of gcc (9.3.0) and choice of compiler flags. \$\endgroup\$ Mar 7, 2022 at 2:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.