32
\$\begingroup\$

Until now has been limited to big problems - problems that take seconds if not minutes. This was simply needed to choose a winner fairly despite measurement errors. Often these challenges were decided on asymptotic behavior alone. I felt that this left one particular aspect very much neglected: micro-optimization.

For this reason I created the GOLF. The GOLF is a toy CPU with a simple instruction set that is easy to learn and to program in. The exact specification of the GOLF can be found on Github. Each instruction on the GOLF takes a fixed amount of clock cycles.

The advantage of this toy CPU is that we can write programs in GOLF assembly, compile them, and run them in a GOLF virtual machine. After the program is done we can get the exact number of cycles that the program ran for. This allows for exact scoring of submissions.

I am working on a couple of challenges that use the GOLF for submission scoring (under the tag), and I invite others to do so too.


If you have any questions or suggestions about GOLF, please post here. If you've found a bug in the reference GOLF implementation, please post it on the Github issue tracker.

\$\endgroup\$
  • 1
    \$\begingroup\$ One thing that bothers me beyound comprehention: to load bytes, it is 5 cycles, but only 1 to store? It is always slower to write than to read. Unless you write to the registers. In that case, reading and loading has the same speed. Or am I wrong? \$\endgroup\$ – Ismael Miguel Apr 24 '15 at 23:17
  • \$\begingroup\$ Also, on the specification: "Memory address 0xffffffffffffffff is special - stores to this address will be written to the virtual machine's stdin, reads come from stdout". You write to STDIN and you read from STDOUT? \$\endgroup\$ – Ismael Miguel Apr 24 '15 at 23:21
  • 2
    \$\begingroup\$ @IsmaelMiguel I'll fix that documentation issue. I'm not certain what you mean about the loading/storing though. On most CPUs stores are a lot faster than reads, because a store doesn't have to wait on a cache miss. I don't know what you mean with 'writing to the registers'. \$\endgroup\$ – orlp Apr 24 '15 at 23:42
  • 4
    \$\begingroup\$ Nice! This makes me want to write a C to GOLF compiler so we can use C, and then compile CPython in GOLF so we can use Python.. \$\endgroup\$ – Claudiu Apr 26 '15 at 20:41
  • \$\begingroup\$ In the spec, 'Memory and I/O' list, you have an LSU that should be LIU (I'm not trying to be picky, I'm trying to port the VM to C# so I double check every word) \$\endgroup\$ – edc65 Apr 28 '15 at 13:20
  • 1
    \$\begingroup\$ Question, why did you choose to make the instructions not reside in writable memory? That disallows self-modifying programs which could be really interesting, I think .. \$\endgroup\$ – Claudiu May 11 '15 at 17:13
  • 2
    \$\begingroup\$ @Claudiu Because it could make finding optimal solutions too complicated, and could allow for abuse by jumping to data as mov-ing immediates, instead of using the regular expensive lw. Also it does not model real-world CPUs well. Self-modifying code is very expensive. \$\endgroup\$ – orlp May 11 '15 at 17:34
  • 1
    \$\begingroup\$ @Claudiu Basically, the only way I could implement self-modifying code realistically and without abuse is to make the GOLF a pipelined CPU, but that would make all the design incredibly more complicated, and much harder to optimize for. \$\endgroup\$ – orlp May 11 '15 at 17:36
  • \$\begingroup\$ -1 There is already Redcode \$\endgroup\$ – Akangka Feb 7 '16 at 8:18
  • \$\begingroup\$ @Claudiu Redcode. \$\endgroup\$ – Akangka Feb 7 '16 at 9:30
8
\$\begingroup\$

This project has intrigued me so I've been working on it a bit. All my code so far is available here. I'm not sure if this is the right place to post this, so if it isn't, let me know and I'll remove it.

Faster back-end (GOLF -> C assembler)

The more interesting result so far has been creating a GOLF to C assembler. The input is golf assembly, and the output is C code which does the equivalent thing. This C code can then be compiled by GCC to be run natively. For example, given a primality tester in isprime.golf, the output is isprime.golf.c:

$ python3 assemble2c.py isprime.golf
    $ gcc -O2 -o isprime isprime.golf.c
$ echo 5 | ./isprime
    y
    Ran for 129 cycles
    $ echo 55 | ./isprime
n
Ran for 189 cycles

Compare:

$ echo 5 | python3 golf-cpu/golf.py -d isprime.bin
    y
    Execution terminated after 129 cycles with exit code 0.
    $ echo 55 | python3 golf-cpu/golf.py -d isprime.bin
n
Execution terminated after 189 cycles with exit code 0.

The speed-up is massive:

          input         |    cycles     | Python VM |   assembled C code
 -----------------------+---------------+-----------+---------------------
                      5 |           129 |    0.117s |       0.006s
              9,149,419 |        30,517 |    0.151s |       0.003s
            377,333,773 |       194,593 |    0.630s |       0.004s
         77,777,677,777 |     2,789,249 |    8.732s |       0.006s
      8,284,590,452,353 |    28,783,405 | 1m28.105s |       0.019s
    979,853,562,951,413 |   313,026,621 |     x     |       0.179s
777,777,722,155,555,333 | 8,819,171,305 |     x     |       5.479s

Basically the standard VM runs about 320,000 cycles/second of this program, while the converted version runs about 1.7 billion/second.

C -> GOLF compiler

If you looked at isprime.golf you may have noticed that it looked to be automatically generated. That's because it was, from isprime.golfc:

$ python compile.py -S isprime.golf examples/isprime.golfc

This is a bit less interesting because hand-optimized code will likely work better anyway, but I like the recursivity of it. Essentially I wrote some C code, which I compiled to GOLF assembly, which I think assembled into C code, which I compiled and ran on my machine. Fun stuff!

Interestingly the 777777722155555333 test-case runs in 0.008s if I compile the original C file, so that's ~687.5x faster than the golf-C shenanigans.

\$\endgroup\$
  • \$\begingroup\$ I'd suggest using gist.github.com instead of pastebin. \$\endgroup\$ – orlp May 13 '15 at 19:38
  • \$\begingroup\$ @orlp: Good idea, I updated the links. \$\endgroup\$ – Claudiu May 13 '15 at 19:44
2
\$\begingroup\$

Suggestion: Shared Libraries

Motivation: It would be nice to have access to functions like printf and scanf without having to re-write them each time.


In thinking about how to compile C code to GOLF assembly, or writing an LLVM back-end, the issue of compiling separate modules and linking them together came up. Static libraries would be entirely a compiler issue, since the resulting binary would contain all the code it needed. But shared libraries could be implemented by the VM. I think they would have to be, if code can't modify other code.

It would also be good if the VM would print different cycle counts for each library the cycles were spent in. For example, 2935 cycles in libc, 349,546 cycles in main. That way people would not have to compete on how efficient their standard library functions are. Standard loopholes would prohibit exploiting this by offloading computations to the stdlib. Or maybe it could all be counted together anyway since the cycles in main should dwarf the cycles spent in the stdlib.

I am not sure how to go about implementing it. As it is now the binaries jump to offsets, not to labels. There would have to be an additional dynamic linking phase. Maybe the assembler could produce half-finished binaries (jumps to labels instead of offsets), and at run-time the VM assembles all the stdlibs together with the half-finished binary and converts the label jumps in the half-finished binary to offset jumps.

\$\endgroup\$
  • \$\begingroup\$ Look in the .dbg files. The .dbg files contain a dictionary, the field "lines" is the source file split by lines, the "labels" field contains a dictionary mapping labels to offsets (this is what you want for a dynamic linker), and it contains integer offsets, linking offsets with lines of code. \$\endgroup\$ – orlp May 15 '15 at 17:13
2
\$\begingroup\$

Assembler Enhancements

None of these proposals affect scoring or execution speed; they are only possibilities to improve code readability.

sz and snz instructions

I've often found myself writing patterns like this:

# adds c,d to a,b
add_128:
  add b, b, d
  leu d, b, d
  jz skip_carry, d
  add a, a, 1
skip_carry:
  add a, a, d
  ret a, b

Personally, I don't like that extra label floating around.

(This particular case would be rendered trivial by an adc instruction, but I think introducing a status register goes against the goals of GOLF.)

I propose two new psuedo-instructions:

sz   a       ' |    1  | skip on zero        | Skips the next instruction if a is zero.
snz  a       ' |    1  | skip on non-zero    | Skips the next instruction if a is non-zero.

These would get transformed to jz and jnz instructions by the assembler, with the address to jump to set to the current address + two instructions. The previous sample could become:

# adds c,d to a,b
add_128:
  add b, b, d
  leu d, b, d
  sz d
  add a, a, 1
  add a, a, d
  ret a, b

#include directive

As a simpler alternative to the dynamic/static linking proposals, you could add a function include(filename) that would cause the assembler to insert the contents of the specified file at the location of the function call. This would allow splitting utility functions and lookup tables into different files without two much trouble.

Precomputed data offsets

My submission for "Testing if a number is a square" included this snippet:

  add x, x, data(lookup_table)
  sub x, x, 2**10

I could have saved one cycle if the assembler allowed me to do something like:

  add x, x, data(lookup_table) - 2**10

I could have edited the binary myself, but as it was, a 0.2-cycle (on average) optimization was not worth it. However I could see places where this could be useful.

Automatic loop unrolling:

The same submission also included the following snippet:

  and c, x, 0xFFFFFFFF00000000
  jnz skip32, c
  shl x, x, 32
  sub b, b, 16
skip32:
  and c, x, 0xFFFF000000000000
  jnz skip16, c
  shl x, x, 16
  sub b, b, 8
skip16:
  and c, x, 0xFF00000000000000
  jnz skip8, c
  shl x, x, 8
  sub b, b, 4
skip8:
  and c, x, 0xF000000000000000
  jnz skip4, c
  shl x, x, 4
  sub b, b, 2
skip4:
  and c, x, 0xC000000000000000
  jnz skip2, c
  shl x, x, 2
  sub b, b, 1
skip2:

Hard to read and prone to mistakes. What if we could do something like:

for i in range(5,0,-1):
    and c, x, 2**64 - 2**(64 - 2**i)
    jnz skip<i>, c
    shl x, x, 2**i
    sub b, b, 2**(i-1)
  skip<i>:
end

The syntax needs some work (especially the labels), but you get the idea. Here it's not so bad, but if you want to unroll (say) a 129-bit long division algorithm, where eliminating the conditional and jump would save ~20% on each cycle? Priceless.

Access to python libraries

In order to create the lookup table for the above problem, I did

lookup_table = bytes(int((16*n)**0.5) for n in range(2**10, 2**12))

But what if I wanted to make a lookup table for sin(x)? If the assembler allowed an equivalent of include math I could just use math.sin. As it is I have to prepare the lookup table ahead of time and then paste it in as a huge string: not very pretty.

\$\endgroup\$
  • \$\begingroup\$ I like the skip instructions, although I'd implement them as sz a, 1 or sz a, 2, where the amount of instructions to skip must be immediate. Precomputed offsets are kind of complicated to implement with the current 'Python eval' system, but I see their merit. I guess I can import math for the eval as well. I don't like the other features - I don't want to turn the GOLF assembler into a fully fledged macro assembler. \$\endgroup\$ – orlp Jul 4 '15 at 2:24
  • \$\begingroup\$ Math's library and skip instructions implemented. \$\endgroup\$ – orlp Jul 17 '15 at 5:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .