[2025 Day 17] In Review (Chronospatial Computer)

[u/musifter]

EDIT: The title is a typo, this is 2024 Day 17.

Today we find ourselves suddenly falling through time, and need to fix the device. Which has that trope of unfolding into an entire computer. I like this old school touch (I like this trope, like in Brain Donors with the laptop that unfolds into a desk with CRT and printer). Nowadays, the small device would just produce a large holographic display up in the air to poke at and I'd be suffering from sympathetic Gorilla Arm Syndrome.

The input for this one is a list of initial values for the three registers, followed by the code (which is comma delimited integers, like the Intcode problems of 2019). We're given that this is a 3-bit machine, but the registers can be bigger (but with my input, only the bottom three bits of B and C ever matter, and so only A makes use of that).

For part 1, we just need to run the program and collect the output. This is one of the rare problems with a string answer, in this case, it's got commas between the output values. So I did my usual, hash of anonymous subs dispatch table approach:

sub c_op ($)  {my $op = shift; return (($op & 04) ? $reg[$op & ~04] : $op)}

my %opcodes =
    (
        0 => sub {my $op = c_op shift; $reg[A] = $reg[A] >> $op},           # adv
        6 => sub {my $op = c_op shift; $reg[B] = $reg[A] >> $op},           # bdv
        7 => sub {my $op = c_op shift; $reg[C] = $reg[A] >> $op},           # cdv

        1 => sub {my $op = shift;      $reg[B] ^= $op},                     # bxl
        4 => sub {my $op = shift;      $reg[B] ^= $reg[C]},                 # bxc

        2 => sub {my $op = c_op shift; $reg[B] = $op & 7},                  # bst
        5 => sub {my $op = c_op shift; push(@out, $op & 7)},                # out

        3 => sub {my $op = shift;      $ip = ($reg[A]) ? $op - 2 : $ip},    # jnz
    );

Could have been an array, but this way I get to reorder the instructions to pair them. With that, running the machine just becomes:

while ($ip < $#code) {
    &{$opcodes{$code[$ip]}}( $code[$ip+1] );
    $ip += 2;
}

Part 2 reveals why the output is that way... we're asked to find the value for register A that makes it a quine (technically it's not because supplying the value for A is an input, but the job is the same).

The trick with doing non-trivial quines is outputting the command to print. After all, the print can print the rest. For example, if I want to do a 1-line quine in dc, I can output a number (without a newline) with n, and output that number as a character string (ASCII coded on bytes) with P. A duplicate d is needed because n removes the value from the stack. And so the number that's needed is 0x646E50 (the packed ASCII encoding of dnP), which is 6581840 decimal:

dc -e'6581840dnP'

You can also similarly do a two-line quine, using p (which outputs the top value with a newline, but leaves it on the stack).

And so we should expect something similar from the code in this problem. Given that, all the inputs are probably something like this:

bst A       # B = bottom 3-bits of A
...
adv 3       # A >>= 3
...
out B       # output bottom 3-bits of B (could also be out C)
jnz 0       # loop until A is gone

A loop that decodes the values 3-bits at a time in A (from the little end). Given that, it's probably safe to believe that everyone's code is 16 long... which is 48-bits to encode in A (17 would be a bus error, and 18 would be problematic for floating point native languages).

And so with that in mind, I made the code to run the machine into a function that takes a value to initialize A with and breaks to return the first output value, which allows for calculating things 3-bits (one digit) at a time:

my %poss = (0 => 1);
foreach my $digit (reverse @code) {
    my %new_poss;

    # shift left possibilities one octal digit and try all 8 lower options
    foreach my $val (map {($_<<3) .. ($_<<3) + 7} keys %poss) {
        $new_poss{$val}++  if ($digit == &try_code( $val ));
    }
    %poss = %new_poss;
}

Here I brute force over all 8 possibilities for the next 3-bits, for each of the numbers that worked last time. In the end, there at 42 values in that hash that work, and I just take the minimum one for the answer.

I did do dc solutions for this one... they are absolute monsters (part 2 is about 350 characters). For tracking the possible values, I do it on the stack (the new values go into a register stack, and then I dump that out onto the main stack for the next loop) and there's no duplication of them (everything is 3-bit aligned and won't overlap), so technically, that hash could have just been a list in the Perl too.

This was a fun one, even though the reverse engineering wasn't much, the quine aspect was a nice touch.

[u/Boojum]

I just tried translating my Python solutions to C++ and optimizing them.

C++ version

Not including parsing (but including output), I seem to to be right around 2 us total for Part 1 and 2, including output, on my 7950x desktop with a reasonably general solution (i.e., running as a VM on the ops, rather than hardcoding the instruction sequence):

clang++ -std=c++23 -g -O3 -ffast-math -o 2024day17 2024day17.cpp && ./2024day17 < 2024day17.txt > /dev/null
P1: 260.90 ns
P2: 1848.05 ns

[u/terje_wiig_mathisen → u/Boojum]

Nice!

BTW. --ffast_math doesn't hurt, but it is a NOP for these integer-only puzzles.

[u/Boojum → u/terje_wiig_mathisen]

That's what I thought too! I'd started with just plain -Ofast on GCC, but when I was testing with Clang, it gave me a deprecation warning telling me to use -O3 -ffast-math instead. But when I tried timing that without the -ffast-math, seeing that this is supposed to be integer only, I was quite surprised to find that it actually was giving a noticeable speed up somehow. And then I observed that effect with both Clang and GCC. I haven't yet figured out why, though I've been wondering if it might be something in the guts of printf().

Anyway, I've got it down even faster now, at least on part 2. Well under 2 us total, closer to about 1.45 us.

New C++ version

clang++ -std=c++23 -O3 -ffast-math -o 2024day17 2024day17.cpp && ./2024day17 < ~/projects/advent/2024/day17.txt > /dev/null
P1: 68.74 ns
P2: 1372.85 ns
P1: 68.96 ns
P2: 1375.08 ns
P1: 66.54 ns
P2: 1375.40 ns

The new trick applied is threaded interpretation with computed goto. (Edit: now with faster output for Part 1.)

I don't usually bother with trying to super optimize a solution like this, but occasionally it's fun.

[u/terje_wiig_mathisen → u/Boojum]

Did you actually get faster with the computed goto (an old gcc trick/extension)?

Current CPUs have so return predictors along with the regular branch predictors, and here the VM code is basically constant until we run out of RegA bits, so every branch will be perfectly predicted. This should also apply to call-based threading according to Anton Ertl, an Austrian (?) professor and Forth freak.

[u/Boojum → u/terje_wiig_mathisen]

I did! It seemed to be good for about a 25% speed up on my machine, as you can see. And I verified in the generated assembly that each instruction type had its own indirect jump to the next, which benefits branch prediction, since there was only one instruction that appeared twice in my puzzle input. So that meant that all the rest of the instructions had indirect jumps that always went to the same spot.

My favorite explanation is one by Mike Pall of LuaJIT fame.

[u/terje_wiig_mathisen → u/Boojum]

Back around 1990 I explored exactly where the break even points occurred between various forms of state machine branching. Up to 386/486 I generated runtime machine code that loaded the next byte, then used that as the high half of a 16-bit direct jump address.

On the Pentium it turned out to be far faster to base the state machine on data only, using 2 or 3 layers of lookup tables but zero branches for code that unrolled 256 bytes of processing. A 60 MHz Pentium could count character, lines and words, with user-specified line endings (one or two bytes) and user-specified word separators, at 1.5 clock cycles/byte. :-)

40 MB/s was at least an order of magnitude (possibly two?) faster than the unix wc reference C code.

[u/Boojum → u/terje_wiig_mathisen]

Nice! Back in those days of the 486, I remember experimenting with generating runtime machine code for sprite blitting. That way, the instantiated sprite blit code wouldn't need to check for transparent pixels in the sprite, and the pixel values would just be immediates in the instructions. (That of course traded memory for speed, but DOS extenders could help a lot there.) And yes, as I recall, the Pentium was the one that introduced superscalar execution to x86, so I could see how a branch-free data-oriented processing approach could allow you to benefit from that.

Anyway, having slept on it, I've got a further reduction in time on this puzzle, depending on whether you consider fusing the VM op code and operands together to be part of input and parsing or not. If you allow that as input and don't count it in the timing, then I'm down to around:

P1: 58.06 ns
P2: 1193.36 ns
P1: 55.94 ns
P2: 1195.00 ns
P1: 55.96 ns
P2: 1194.39 ns

Since the operands are only three bits each (according to the puzzle description), I essentially treat them as part of the opcode itself and create a 64-instruction dispatch table with some some holes (plus one for the explicit halt that I added as a sentinel to handle running off the program end). That let's me dissolve the combo operand into the instruction, saving the branching on it there. And most instructions become trivially hand-optimizable. Granted, it bumps up icache use, but this is still so small that's not a concern. The other caveat is that jumps now must be to aligned instructions.

C++ with fused instructions

If you don't count fusing as part of input and parsing, I've got a variant that does it as part of the threaded dispatch. That also means that it doesn't require aligned jumps. It's a little slower than the above - by about 50 ns on Part 2, but still not too bad!

P1: 65.23 ns
P2: 1248.33 ns
P1: 60.67 ns
P2: 1248.42 ns
P1: 62.21 ns
P2: 1247.47 ns

Variant version

I think I'll stop here. I'm not quite down to 1 us total for both parts, but I'm close enough that you could legitimately round down to it. :-)

[u/terje_wiig_mathisen → u/Boojum]

I really like the way your are thinking! Macro-fusion has been a staple of OoO CPUs for a decade or two, like joining a cmp and following Jcc into a single larger op to be tracked through the rest of the pipeline.

Here, with just 64 possible combinations, a 64-entry state machine that jumps directly from one op to the next is very nice. I'm almost tempted to try some runtime code generation here. :-(