I got here just in time
Advent Of Code 2024 is a wonderful collection of 25 little coding challenges, allowing hundrets of thousands of aspiring and established programmers to learn something new, or just have a lot of fun solving puzzles under holiday lights.
On Day 17 - Chronospatial Computer, we were asked to calculate the output for a simple 3-bit (micro-) computer program, that was using a very limited instruction set.
Here's how I slowly created the fastest solution to this delightful puzzle.
Divide by 2
The following example program was provided:
Program: 0,1,5,4,3,0These 6 numbers, together with the given instruction set descriptions decode to the following steps:
- 0, 1: Divide the value in register "A" by 2^1 (also known as the number 2).
- 5, 4: Output the value of register "A", modulo 8
- 3, 0: If register "A" is not zero, jump back to the first instruction (instruction 0).
Simple enough
The following C++ code shows the initial solution to the problem. A simple virtual machine implementation that parses the input program string of numbers, and performs the relevant commands:
``C++
while (pc < program.size()) {
const auto op = program.at(pc++);
const auto arg = program.at(pc++);
switch (op) {
case OpCode::ADV: RA() = RA() / (1 << COMBO(arg)); break;
case OpCode::BXL: RB() ^= arg; break;
case OpCode::BST: RB() = COMBO(arg) & 0x7; break;
case OpCode::JNZ: pc = RA() != 0 ? arg : pc+1; break;
case OpCode::BXC: RB() ^= RC(); break;
case OpCode::OUT: OUT8(COMBO(arg)); break;
case OpCode::BDV: RB() = RA() / (1 << COMBO(arg)); break;
case OpCode::CDV: RC() = RA() / (1 << COMBO(arg)); break;
default: return;
}
}
CODEBLOCK1 C++
auto allocateWritable() -> std::array<uint8_t, SIZE>* {
void* mmaped = mmap(nullptr, SIZE, PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
return new (mmaped) std::array<uint8_t, SIZE>{};
}
CODEBLOCK2 C++
void emit_OUT(uint8_t operand, auto&& emit) {
if (isLiteral(operand)) {
emit(std::array<uint8_t, 8>{
0x48, 0xc1, 0xe0, 0x03, // shl $0x3,%rax
0x48, 0x83, 0xc8, literal(operand) // or <op>,%rax
});
} else {
const auto ra_rb_rc = std::array<uint8_t, 3>{0xf8, 0xf0, 0xd0};
const auto from = ra_rb_rc[operand - 4];
emit(std::array<uint8_t, 14>{
0x48, 0xc1, 0xe0, 0x03, // shl $0x3,%rax
0x49, 0x89, from, // mov <from>,%r8
0x49, 0x83, 0xe0, 0x07, // and $0x7,%r8
0x4c, 0x09, 0xc0, // or %r8,%rax
});
}
}
CODEBLOCK3 C++
mprotect(program, program->size(), PROT_READ | PROT_EXEC)
CODEBLOCK4 C++
using chronospatial_computer = size_t (*)(size_t, size_t, size_t);
auto* compute = reinterpret_cast<chronospatial_computer>(x86);
CODEBLOCK5 C++
auto result = (compute)(10, 20, 30);
``
Are we fast now?
So, after all this and a full JIT compiler implementation, complete with unit tests later, are we fast now?
Yes! It's super fast now. I would contend, this is the fastest possible way to run the micro-computer program provided by the puzzle on this architecture. Sure, the assembly could be optimized more, sure, we could also compile to SIMD instructions somehow. There are many caveats to the fastest claim. But it will be way faster to execute than any implemntation trying to read the program every time.
Can we brute force now?
Uhm, no. Even if the run time of the program is now measured in microseconds, it would take many years to arrive at the given solution for part 2 of the advent puzzle in time. :)
JIT was necessary, though, right?!
Nope. Not at all.
For part 1 of the problem, the program must be executed only once. So doing a just-in-time compilation first and THEN running the program is actually slower than just running it :).
For part 2, a simple algorithm does need a few thousand runs of the program potentially to arrive at a solution, which even when interpreting every time can be done in milliseconds on modern hardware.
Was it worth it?
Absolutely! While not being helpful in the slightest for solving the actual Advent of Code puzzle, this was a fantastic opportunity to learn / brush up on the concepts of Just-in-time compilation, actually build a compiler with a tiny instruction set, learn about memory protection and brush up on x8664 assembly (which is an absulte pain....).
Reference
Advent of Code puzzle and description: https://adventofcode.com/2024/day/17
Full code and unit tests here: https://github.com/int2str/advent2024public/blob/main/17/day17vm.hh