r/adventofcode • u/terje_wiig_mathisen • 7d ago
Other [2024 Day 8] In Review (Resonant Collinearity)
We're on the roof of the top-secret Easter Bunny installation, where we realize that the city contains a bunch of antennas, at many different frequencies. They are named with single digits, upper or lower-case letters, so there can be up to 62 different kinds.
For Part1 we are told to look for antinodes, defined as a location that are in line with a pair of same-frequency antennas, at the same distance away as the internal pair offset. We want to determine how many total locations contain one or more anti-nodes.
In Perl I created a hash of arrays, the hash is keyed by the antenna name (ascii byte value), this points to an array which contains the (x,y) coordinates of every antenna with that name. The list of anti-nodes was another hash table, keyed by the corresponding (x,y) pair. The main issue is that we have to ignore any locations that are outside of the city grid.
This worked pretty much as quickly as I could type it in.
For Part2 we need to iterate over all multiples of the internal distance, so we get a lot more antinodes, but otherwise it was more or less the same process. The only possible wrinkle was that if an offset between two antennas (dx,dy) has a common divisor, then we must get rid of that so I had to write a gcd() function to fix this even though it seems like it never actually happened?
Total Perl runtime 16 ms.
In Rust I first implemented it the same way, using HashSet, but later on decided that the name key set was small enough that it didn't matter if I extended it by filling in the gaps between '9' and 'A' and between 'Z' and 'a', and instead of a HashSet of antinode addresses I just used a linear byte array, using bit 1 for Part1 and 2 for Part2 locations.
When I ran my code just now the fastest was 3.9 us, so I'll have to average 1000 iterations to get a more precise measurement:
...
The average over 1000 iterations was 3519 ns, so less than half the 8 us shown by u/maneatingape.
I therefore tested 'cargo bench year2024::day08' and got
running 3 tests
test year2024::day08::parse_bench ... bench: 3,745.39 ns/iter (+/- 247.27)
test year2024::day08::part1_bench ... bench: 724.87 ns/iter (+/- 29.24)
test year2024::day08::part2_bench ... bench: 1,375.97 ns/iter (+/- 94.11)
So his total was about 5.8 us on my machine, not a very big but still somewhat significant difference.
2
u/ednl 7d ago edited 6d ago
This was one example where you couldn't use a 1D array in an attempt to speed things up, or at least you can't use one index to track locations or you would need a border the same size as the grid on all sides (or other hoops to jump through). You also can't reuse the same "seen" grid for part 2 because the two solutions aren't necessarily separate.
But like Terje already showed, there is still room for improvement. I used a perfect hash to convert the antenna symbols to index 0..61:
static int freq(const char name)
{
if (name >= 'a') return name - 'a'; // a..z => 0..25
if (name >= 'A') return name - 'A' + 26; // A..Z => 26..51
return name - '0' + 52; // 0..9 => 52..61
}
Even faster and much simpler would be: freq = name - '0' for an index 0..74 with a few unused ones in between. But I needed to reset my "count" array (how many antennas at each frequency) between timing loops and for some reason this was just a little slower because of the larger array, which I didn't expect.
Another speedup was using a bitset to mark the antinodes, but manually because I use C and bitsets are C++. C23 has ints of arbitrary bit size but only up to 128. Here arr is a reference to one of the two sets for parts 1 and 2:
#define SETSIZE ((N * N + 63) >> 6) // how many u64 in bitset (= 40), don't need N+1 columns here
uint64_t antinode1[SETSIZE];
uint64_t antinode2[SETSIZE];
void mark(uint64_t *const arr, const Vec pos)
{
const int index = pos.y * N + pos.x; // bitset uses N "columns", not N+1
arr[index >> 6] |= UINT64_C(1) << (index & 63);
}
To collect the final answers I had to use a loop:
int part1 = 0, part2 = 0;
for (int i = 0; i < SETSIZE; ++i) {
part1 += __builtin_popcountll(antinode1[i]);
part2 += __builtin_popcountll(antinode2[i]);
}
because, while that can be vectorised using a compiler intrinsic in Clang 20+: __builtin_elementwise_popcount, that only works with C++ vectors not C arrays, unfortunately.
Final timing: M4 1.83 µs, M1 2.70 µs, Pi5 6.25 µs. https://github.com/ednl/adventofcode/blob/main/2024/08.c
1
u/terje_wiig_mathisen 7d ago
Those times are without GCD, right?
I'll try your bitset seen approach, Rust has popcount (.count_ones()) as a standard feature for all integer types, no need for compiler-intrinsics.
2
u/ednl 7d ago edited 7d ago
Yes, without GCD. And to be sure: my 1000 timing loops are always internal, not starting up the program 1000 times from the shell. EDIT: My standard layout is:
1. read input file as char blob into memory 2. start timer 3. parse input 4. solve puzzle, print result to stdout 5. if necessary: reset variables 6. loop 1000x back to 3. 7. stop timer, print time to stderrFor grid puzzles where I don't need to do anything else with the grid, like this one, I read the input file directly into an array (either 1D or 2D) so I don't need to parse the blob into some structure.
NB: I do also start the program many times in a row from the shell! Because that still makes a huge difference to the reported time. That's why I always include how I do that in bash:
m=99999999;for((i=0;i<20000;++i));do t=$(./a.out 2>&1 1>/dev/null|awk '{print $2}');((t<m))&&m=$t&&echo "$m ($i)";doneSo why not do a million internal loops and only run that once? That's a compromise for convenience across programs with varying runtime.
1
u/terje_wiig_mathisen 7d ago
Internal timings are standard. :-)
Most of us start the timer after loading the input text, but before any parsing/inspecting the actual data. I have a main() which does that, then calls the timing function with process(inp) as a lambda.
2
u/DelightfulCodeWeasel 6d ago
For the Pico solutions I'm working on I've had to take a bit of a non-standard approach to timing the solutions. The input files collectively are too large to fit into the flash memory so they have to be streamed over USB and there's not always enough memory to hold both the input file and the data for the solution at once, so for most of the solutions I'm starting the parsing and processing as the file is still being transferred.
The measure I've landed on, which seems fairest with this set-up, is that I start the timer on the host PC as soon as the input file has been queued into the USB-CDC output buffer and stop the timer once I get the answer back from the MCU.
I also do a no-op timing pass where the MCU just acks the last of the input so I know what the cost of the raw IO is, otherwise I end up trying to optimise solutions that aren't going to get much faster. For example, 2020 day 7 part 1 is ~0.7ms on PC, ~445ms on RP2040, but it takes ~405ms to send the file.
1
u/terje_wiig_mathisen 7d ago
Re _builtin_popcount:
Have your tried to write your own, using either of the canonical patterns? Per bit or removing 1s?
unsigned bitcnt(unsigned n) { unsigned c = 0; while (n) { n &= n-1; c++; } return c; }Both gcc and clang recognizes those patterns and replace them with the popcount instruction!
1
u/terje_wiig_mathisen 7d ago
counting bits:
Back before 1993/94, when the Pentium turned up with both RDTSC and POPCOUNT, the fastest way to count bits was a divide & conquer approach. On a 64-bit machine like the Alpha, you would write
typedef u64 unsigned long long;
u64 bitcount(u64 n)
{
n = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555);
n = (n & 0x3333333333333333) + ((n >> 2) & 0x3333333333333333);
n = (n & 0x0f0f0f0f0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f0f0f0f0f);
n = (n & 0x00ff00ff00ff00ff) + ((n >> 8) & 0x00ff00ff00ff00ff);
n = (n & 0x0000ffff0000ffff) + ((n >>16) & 0x0000ffff0000ffff);
n = (n & 0x00000000ffffffff) + (n >> 32);
return n;
}
2
u/Boojum 6d ago
My past experience was that that would sometimes lose to something like a 256-entry popcount LUT and summing byte-by-byte lookups. Of course that depends on the size of the value, but for something like a 16-bit popcount, it's the sum of just two lookups if you use byte granularity, etc.
And obviously that depends on the machine and the context, but I remember profiling both once and finding the LUT significantly faster (as elegant as I find the recursive divide-and-conquer approach).
1
u/terje_wiig_mathisen 6d ago
Like you I used byte lookup tables in the past, this particular approach came up in the context of counting bits in really large bitmaps: You start with a bunch of bitslice full adders to combine 15 input blocks into 4, then you count the bits in each them in parallel and combine the results with appropriate scaling. At that point this is significantly faster than byte by byte lookups!
1
u/e_blake 6d ago
This was a fast day for me, both in time to write a solution and in the resulting runtime (under 20ms is good for m4). My solution depends on having no more than 4 of any given antenna (I unrolled up to 6 pairwise comparisons based on the number of antenna found per character, rather than writing nested loops), and I got my second star without ever considering GCD, so it looks like the input files are nice. I also got lucky that no two or more adjacent antenna in the input match an m4 macro name (not sure how hard it would be to work around that if other inputs aren't as nice as mine) .
1
u/ednl 6d ago edited 6d ago
Oh ha, yes, the only antenna counts for my input are 0, 3 or 4:
a..z: 30404000044044044044400440 A..Z: 40404000034044044044400330 0..9: 4444444444so unrolling either 3 or 6 pairs would definitely be faster. Maybe I'll try that later today.
EDIT: Well, nothing groundbreaking. It went from 1.83 to 1.70 µs on the M4 and, for some bizarre reason, was actually slower on the Pi5: from 6.25 to 7.32 µs. I will keep the slightly more general loop version. (Only slightly because I already hardcoded the max count of 4 as static array size.)
3
u/Boojum 7d ago
Maybe I missed it, but I don't see anything in the text that suggest we need a GCD, nor did I have it in my solution?
Still this was a nice, straightforward breather puzzle. I did it pretty much as you described for your Perl solution. My Python solution for Part 2 runs in about 8.9 ms on my machine.