*As of today, our solutions are able to solve all 49 problems in <1ms!*

I have obtained consent from all the top participants to post their solutions to a shared repo, for the community to review and learn from! *All solutions are now available at the linked GitHub repo!*

Our solutions have a total runtime of *988936ns*!

# Context/Caveats

- All submissions were run on the same hardware (Ryzen 5950X) to ensure consistency, with the same compiler flags and features available. This was on rustc nightly (updated throughout the course of the contest), and with CPU speed capped at 3400 MHz with boost clock disabled.

- AVX-512 was not available on the machine so none (?) of the solutions utilize that particular set of accelerated instructions, but there is plenty of other SIMD in use.

- All submissions were run against the same inputs to ensure consistency.

- Caching anything that has been fed with input was not allowed to prevent cheating and/or trivial solutions like `Map`.

- For the same reason, inputs were not directly available to the participants, and were not provided at compile-time.

- Participants were allowed to use compile-time tricks in their answers. Due to limitations in the benchmark bot, the runtime of these optimizations could not be measured. This was considered acceptable as the compiled binaries were expected to otherwise work correctly for arbitrary inputs. This means that participants are allowed to use look-up tables (LUTs) in their answers, but those LUTs are expected to work for arbitrary inputs, not just specific ones.

- I/O is trivial, and was thus not measured as part of the benchmark. That is, participants were provided with an `&str` or `&[u8]` input (their choice) and expected to provide an `impl Display` as part of their result. Therefore, input parsing was measured.

If you are interested, join us in #advent-of-code-2024 on the Discord server for further discussion :)

# Further Reading

If you would like a more in-depth explanation of some of the optimization techniques used, I highly recommend you check out this article by ameo [0] (one of our participants). It covers the process they used to optimize their solution for Day 9 Part 2, and how they got it to the top of our leaderboard. The article provides incredible information on the process of both high-level and micro optimization.

# Credits:

- Thank you to the members of the `Rust Programming Language Community` and `Serenity-rs` Discord servers and everyone else who participated in the challenge!

- Thank you to Eric Wastl for hosting AoC every year!

- Thank you to Noxim [1] for writing the original version of our benchmark bot [2].

- Extra special thank you to yuyuko [3], bend-n [4], and giooschi [5] for their help in maintaining and improving our benchmark bot.

[0]: https://cprimozic.net/blog/optimizing-advent-of-code-2024/

[1]: https://github.com/noxime

[2]: https://github.com/indiv0/ferris-elf

[3]: https://github.com/ultrabear

[4]: https://github.com/bend-n/

[5]: https://github.com/SkiFire13/

Comments URL: https://news.ycombinator.com/item?id=42568894

Points: 6

# Comments: 1

Now if only Intel would stop crippling AVX-512...

The video (if I recall correctly) goes a bit further, attacking patents/IP law as anti-creative.

[0]: https://www.youtube.com/watch?v=nJPERZDfyWc

I'm using `clang` from `pkgs.pkgsCross.musl64.llvmPackages_latest.stdenv` to cross-compile Rust binaries from ARM macos to `x86_64-unknown-linux-musl`. It _works_, but every time I update my `flake.nix` it rebuilds *the entire LLVM toolchain*. On an M2 air, that takes something like 4 hours. It's incredibly frustrating and makes me wary of updating my dependencies or my flake file.

The alternative is to switch to dockerized builds but:

1) That adds a fairly heavyweight requirement to the build process

2) All the headache of writing dockerfiles with careful cache layering

3) Most importantly, feels like admitting defeat.

- the company that developed Madsim (RisingWave) [0] [1] is tries hardest to eliminate non-determinism with the broadest scope (stubbing out syscalls, etc.)

- sled [2] itself has an interesting combo of deterministic tests combined with quickcheck+failpoints test case auto-discovery

- Dropbox [3] uses a similar approach but they talk about it a bit more abstractly.

Sans-IO is more documented in Python [4], but str0m [5] and quinn-proto [6] are the best examples in Rust I’m aware of. Note that sans-IO is orthogonal to deterministic test frameworks, but it composes well with them.

With the disclaimer that anything I comment on this site is my opinion alone, and does not reflect the company I work at —— I do work at a rust shop that has utilized these techniques on some projects.

TigerBeetle is an amazing example and I’ve looked at it before! They are really the best example of this approach outside of FoundationDB I think.

[0]: https://risingwave.com/blog/deterministic-simulation-a-new-e...

[1]: https://risingwave.com/blog/applying-deterministic-simulatio...

[2]: https://dropbox.tech/infrastructure/-testing-our-new-sync-en...

[3]: https://github.com/spacejam/sled

[4]: https://fractalideas.com/blog/sans-io-when-rubber-meets-road...

[5]: https://github.com/algesten/str0m

[6]: https://docs.rs/quinn-proto/0.10.6/quinn_proto/struct.Connec...

Currently bringing a similar kind of testing in to our workplace by writing our services to run on top of `madsim` [1]. This lets us continue writing async/await-style services in tokio but then (in tests) replace them with a deterministic executor that patches all sources of non-determinism (including dependencies that call out to the OS). It's pretty seamless.

The author of this article isn't joking when they say that the startup cost of this effort is monumental. Dealing with every possible source of non-determinism, re-writing services to be testable/sans-IO [2], etc. takes a lot of engineering effort.

Once the system is in place though, it's hard to describe just how confident you feel in your code. Combined with tools like quickcheck [3], you can test hundreds of thousands of subtle failure cases in I/O, event ordering, timeouts, dropped packets, filesystem failures, etc.

This kind of testing is an incredibly powerful tool to have in your toolbelt, if you have the patience and fortitude to invest in it.

As for Antithesis itself, it looks very very cool. Bringing the deterministic testing down the stack to below the OS is awesome. Should make it possible to test entire systems without wiring up a harness manually every time. Can’t wait to try it out!

[0]: https://sled.rs/simulation.html

[1]: https://github.com/madsim-rs/madsim?tab=readme-ov-file#madsi...

[2]: https://sans-io.readthedocs.io/

[3]: https://github.com/BurntSushi/quickcheck?tab=readme-ov-file#...

    things
        .iter()
        .filter(|t| !t.is_yellow())
        .take_while(|t| !t.is_rainbow())
        .for_each(|t| t.thingify());

Discord support has been completely unhelpful, because he didn't have 2FA enabled before and the hacker added it.

I don’t have the exact numbers on me right now but I can share them tomorrow (along with the benchmark code) if you’re interested.

> The German Federal Institute for Risk Assessment toxicology review in 2013 found that with regard to positive correlations between exposure to glyphosate formulations and risk of various cancers, including non-Hodgkin lymphoma, "the available data is contradictory and far from being convincing".[11] A meta-analysis published in 2014 identified an increased risk of NHL in workers exposed to glyphosate formulations.[12] In March 2015, the World Health Organization's International Agency for Research on Cancer (IARC) classified glyphosate as "probably carcinogenic in humans" (category 2A) based on epidemiological studies, animal studies, and in vitro studies.[8][13][14][15] In contrast, the European Food Safety Authority concluded in November 2015 that "the substance is unlikely to be genotoxic (i.e. damaging to DNA) or to pose a carcinogenic threat to humans", later clarifying that while carcinogenic glyphosate-containing formulations may exist, studies "that look solely at the active substance glyphosate do not show this effect."[16][17] In 2017, the European Chemicals Agency (ECHA) classified glyphosate as causing serious eye damage and as toxic to aquatic life, but did not find evidence implicating it as a carcinogen, a mutagen, toxic to reproduction, nor toxic to specific organs.[18]

Personally I trust a jury of 6-12 laypeople or the *European Chemicals Agency* over a company with a vested interest in keeping their product on the market.

There is an outstanding issue [0] that I've encountered on two separate machines running in this setup. The issue occurs when using ZFS Native Encryption + (NVMe?) SSDs. The issue appears to be snapshots getting corrupted (or maybe failing to create?) occasionally. It happens roughly 1/1000 snapshots in my case. I take a lot of snapshots so this occurs weekly.

I haven't lost any data yet but this issue is annoying because I get spooky alerts from ZFS warning me about "potential data corruption". To clear them I have to manually intervene by deleting the corrupt snapshots, restart the machine, then scrub.

What's most annoying is that this breaks ZFS send/recv until I intervene. send/recv was the whole reason I went with native encryption instead of LUKS in the first place.

Again, no data corruption so far (if you don't count the snapshots that get lost, which I don't, because I have so many of them). Just very annoying and tedious.

[0]: https://github.com/openzfs/zfs/issues/12014

Similarly (and I have no way of proving this, but I believe it 100%), TikTok seems to alter your feed to incorporate videos from other people watching TikTok near you. My friends and I have made a game of this where we cast TikTok to a TV, watch videos, and try to guess which of us the video was intended for.

I've never once had a "oh wow that's a neat content discovery method" moment from Facebook/Instagram/YouTube but it has happened multiple times with TikTok. I'm not saying TikTok is the end-all-be-all of social media, but it's a good window into what social media could be, if they stopped chasing ad revenue and anger-driven content.