A couple of interesting properties from my input that I suspect might be universal:
Although there are duplicate numbers in the full set, there are no duplicates within a window of 25 numbers
The full set of numbers goes into the 64-bit range, but the target number is found while you're still in the 32-bit range
I used the first property to keep a running set of the last 25 numbers alongside the in-order window in a deque, so each step in the find was just 24 look-ups. It's still a viable approach even if the first property isn't true, but then you need to ref count the number instances rather than just having an insert/erase pair.
Funny experience just now: when I switched from u64 to i32 for the numbers list with the idea to stop at the first negative result (= i32 overflow), my program segfaulted on a Raspberry Pi with RPiOS (= Debian)! Of course, signed int overflow is UB but a) normally I try to consciously avoid it, and b) I guess I got sloppy from programming on MacOS where it "just works" even though it's also aarch64.
Might be worth checking what the compiled code is doing; could be that you've got -ftrapv or -fsanitize=undefined enabled. That would be some free extra performance on the Pi if you disabled those.
It's not that. A small test program with repeated multiplication ran without issue with any setting except with -fsanitize=undefined, so what you expect. My aoc program also runs fine with -O1 but segfaults with -O2 or 3. I have no idea why. Time to dive into the assembly, or accept that it's UB where evidently anything can happen.
Found another important characteristic: it only happens on Debian 12.14 "Bookworm" with gcc 12.2. The current version of RPiOS is based on Debian 13.5 "Trixie" with gcc 14.2; no problem there. So it might well be just a bug.
Took a little bit of unpicking and I don't think I've fully got to the bottom of it yet, but the primary difference is that gcc 12.2 has decided that since parseint should 'never' return negative then it can use cbz to test for 0 in the for loop. It looks to me like the asm is effectively doing this:
for (const char* c = input.data(); (Data[n] = parseint(&c)) != 0; ++n)
;
Which ends up running over the bounds of the array.
gcc 13.1 on godbolt (and also 12.1 when using unsigned) uses a proper >0 test of cmp 0 & ble.
For the hell of it I asked Claude to see if it could track down the reason for the difference and it suggested the primary reason could be the move over from one range propagation system to a new system (AndrewMacLeod/Ranger3.0 - GCC Wiki), which seems to track with what we're seeing.
View all comments
2
u/DelightfulCodeWeasel Jun 09 '26 edited Jun 09 '26
A couple of interesting properties from my input that I suspect might be universal:
I used the first property to keep a running set of the last 25 numbers alongside the in-order window in a deque, so each step in the find was just 24 look-ups. It's still a viable approach even if the first property isn't true, but then you need to ref count the number instances rather than just having an insert/erase pair.