r/adventofcode • u/askalski • Oct 20 '20
Upping the Ante [2019] Optimized solutions in C++ (9 ms total)
According to the About page:
Nor do you need a fancy computer; every problem has a solution that completes in at most 15 seconds on ten-year-old hardware.
Continuing the tradition of keeping u/topaz2078 honest, I have completed my third annual set of optimized solutions, this time clocking in at just under 9 milliseconds to solve all puzzles.
The C++ code is on GitHub. All solutions are single-threaded. Only one solution (Day 12) makes use of SIMD instructions, but unlike last year, this has only the modest requirement of SSSE3.
As always, if you have a question or are curious about how a solution works, please ask.
Timings by day (i9-9980HK laptop):
Day 1 4 μs
Day 2 4 μs
Day 3 41 μs
Day 4 7 μs
Day 5 7 μs
Day 6 84 μs
Day 7 8 μs
Day 8 14 μs
Day 9 913 μs
Day 10 248 μs
Day 11 220 μs
Day 12 765 μs
Day 13 1,379 μs
Day 14 136 μs
Day 15 164 μs
Day 16 345 μs
Day 17 468 μs
Day 18 346 μs
Day 19 45 μs
Day 20 203 μs
Day 21 1,466 μs
Day 22 11 μs
Day 23 607 μs
Day 24 233 μs
Day 25 1,195 μs
-----------------
Total: 8,913 μs17
u/topaz2078 (AoC creator) Oct 20 '20
Fun fact, running these solutions (re)uses only about 2600km == 1660mi of copper: https://www.wolframalpha.com/input/?i=8.913+light-milliseconds
6
u/Endorphion Oct 20 '20
That would merely cost $1.1 million for enough coax to put your claims to the test.
(16¢ per foot was the first hit I got on google)
15
10
Oct 20 '20
All Python developers just times their solutions for context, and were very disappointed
5
Oct 21 '20
I seemingly lost my 2019 code, but I re-wrote the first one and just timed it in at 150 μs....rip
1
u/VikeStep Oct 28 '20
I was curious to see if these timings included file read time and I see that the files are all loaded by mmap before the timing starts. Is there any reason you loaded them by mmap rather than just reading the whole file into memory normally?
I'm not too familiar with how mmap works though, so I might be misunderstanding the code that reads the file.
2
u/askalski Oct 29 '20
Loading the file by mmap is something I carried over from the two previous years I made optimized solution sets. It's a habit I picked up a decade ago while solving the Facebook Puzzle Master problems (does anybody remember those?)
I did it for speed at the time, but I don't remember if the speed difference back then was actually a consequence of avoiding library calls (scanf, etc) for parsing input. The only thing it really saves is copying the input into a userspace buffer. Because as you point out, I don't include mapping the input file in the timing,
Presently, it's more for memory safety than anything else. I map a zero-filled 1MB read-only region, then overlay the input (also read-only) on top of that. If a solution inadvertently accesses past the end of the input, it will still be in a safe area of memory.
I exclude reading the input file from the time mainly because I don't find that part relevant to what I'm trying to optimize, and it's hard enough getting accurate timings without throwing a few system calls into the mix.
Just to see what would happen, I switched load_input over to a simple read into a buffer (fopen/fread/fclose), then included both load_input and free_input in the timings. It ended up slightly faster than what I was doing with mmap (8750 microseconds.) As for why the mmap method would be slower even though the system calls were excluded from the timing... who knows. Maybe the kernel has some extra work to do when the mapped pages are first accessed.
I may rework how I handle input next time for portability.
1
u/Wastedmind123 Nov 29 '20
I've always just copied input into code as statics. You would have to rebuild for a different input and get a larger binary but it's portable and you don't even have to think about reading files, syscalls and all that jazz.
1
u/mjgtwo Nov 06 '20
hey im a little out of practice with cpp development. how do you go about compiling this? I see you have a file called CMakeLists.txt so i tried make CMakeLists.txt and make -f CMakeLists.txt with no progress in understanding the errors.
Thanks :)
1
u/askalski Nov 08 '20
You will need to install cmake if you don't already have it. Then you just run
cmake .to build the Makefile, then runmaketo compile.Or you can skip all that and just do:
clang++ -std=c++17 -O3 -march=native -o advent2019 src/*.cppIf you don't have Clang,g++will also work, but I've had better luck with Clang's optimizer. Testing them side-by-side just now, Clang seems to give a couple hundred microseconds faster run time.
3
2
u/S1ant- Oct 31 '20
Props to you, my part 2 that I coded up quickly took about 15s to run in javascript. I looked at how you figured out how to do it and it's truly ingenious, hats off to you my man! I just spent the last 20 minutes writing it all out on my iPad and I still barely understand it, just wow!
8
u/leftylink Oct 21 '20
Hello, so I would like to hear about the day 16 formulae! So, you have:
And I understand how to combine n%2 and n%5 into n%10 (Chinese remainder theorem)
I'd like to know what principles are used to get those rules for C(k+99, k). Was it done by experimentation, or are there some relevant theorems I can read about?