Yeah that is nice too, and that should also skip all the test code. I think all the clippy warnings on tests for unwrapping and such when working locally would bug me though. And at least the eglot LSP client tends to get bogged down when there are more than a thousand or so clippy warnings/errors, I have found.
This year, some members of the Rust Programming Language Community Server on Discord set out to solve AoC in under 1ms. I'm pleased to announce that through the use of LUTs, SIMD, more-than-questionable `unsafe`, assertions, LLVM intrinsics, and even some inline ASM that goal has been reached (for real this time)!
*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<Input, Output>`.
- 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.
Incredibly detailed and fun read! I love love love seeing this kind of performance analysis. IMO one of the most fun and creative areas of programming is finding new avenues to squeeze out every extra nanosecond.
Reminds me of one of my favourite video essays -- "Everything is a Remix" [0]. The video and this article cover the same ideas albeit with different examples. Which is funny on a meta level -- the article could be called a remix of the video.
The video (if I recall correctly) goes a bit further, attacking patents/IP law as anti-creative.
There's a fine line though. Led Zeplin didn't remix, they flat out ripped off other artists lyrics and melody. Changing the musical genre doesn't wash IMHO.
Is this meaningfully different from Conductor (which they archived a while back)? Browsing through the code I see quite a few similarities. Plus the use of JSON as the workflow definition language.
Hydra not populating with cross compile builds is the bane of my existence.
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
Not sure if this applies to your situation, but I believe you can avoid a full rebuild by modularizing the flake.nix derivations into stages (calling a separate *.nix for each stage in my case). That is how it appears to be working for me on a project (I am building a cc toolchain without pkgscross).
I pass the output of each stage of a toolchain as a dependency to the next stage. By chaining the stages, changes made to a single stage only require a rebuild of each succeeding stage. The final stage is the default of the flake, so you can easy get the complete package.
In addition, I can debug along the toolchain by entering a single stage env with nix develop <stage>
Not sure if this is the most optimal way, but it appears to work in modularizing the rebuild.(using 23.11)
I've been super interested in this field since finding out about it from the `sled` simulation guide [0] (which outlines how FoundationDB does what they do).
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!
> you can test hundreds of thousands of subtle failure cases in I/O, event ordering, timeouts, dropped packets, filesystem failures, etc.
As cool as all this is, I can't stop but wonder how often the culture of micro-services and distributed computing is ill advised. So much complexity I've seen in such systems boils down to calling a "function" is: async, depends on the OS, is executed at some point or never, always returns a bunch of strings that need to be parsed to re-enter the static type system, which comes with its own set of failure modes. This makes the seemingly simple task of abstracting logic into a named component, aka a function, extremely complex. You don't need to test for any of the subtle failures you mentioned if you leave the logic inside the same process and just call a function. I know monoliths aren't always a good idea or fit, at the same time I'm highly septical whether the current prevalence of service based software architectures is justified and pays off.
> I can't stop but wonder how often the culture of micro-services and distributed computing is ill advised.
You can't get away from distributed computing, unless you get away from computing. A modern computer isn't a single unit, it's a system of computers talking to each other. Even if you go back a long time, you'll find many computers or proto-computers talking to each other, but with a lot stricter timings, as the computers are less flexible.
If you save a file to a disk, you're really asking the OS (somehow) to send a message to the computer on the storage device, asking it to store your data, and it will respond with success or failure and it might also write the data. (sometimes it will tell your os success and then proceed to throw the data away, which is always fun)
That said, keeping things together where it makes sense, is definitely a good thing.
I see your point. Even multithreading can be seen as a form of distributed programming. At the same time, in my experience these parts can often be isolated. You trust your DB to handle such issues, and I'm very happy we are getting a new era of DBs like Tigerbetle, FoundationDB and sled that are designed to survive Jepsen. But how many teams are building DBs? That point is a bit ironic, given I'm currently building an in-memory DB at work. But it's a completely different level of complexity. And your example with writing a file, that too is a somewhat solved problem, use ZFS. I'd argue there are many situations where the fault tolerant distributed requirements can be served by existing abstractions.
TigerBeetle is actually another customer of ours. You might ask why, given that they have their own, very sophisticated simulation testing. The answer is that they're so fanatical about correctness, they wanted a "red team" for their own fault simulator, in case a bug in their tests might hide a bug in their database!
I gotta say, that is some next-level commitment to writing a good database.
Sure! I mentioned a few orthogonal concepts that go well together, and each of the following examples has a different combination that they employ:
- 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.
That's the nicest counter-example to my example, thanks for that! I wasn't familiar with take_while() (looks like that's Rust, and looks like Python has a similar itertools.takewhile() ), TIL a neat FP version of break. My example was quite trivial, it's not always so obvious how to break up a convoluted loop, but it should always be possible.
A buddy of mine got hit by one of these recently. He got a message from a friend asking him to try a demo of new video game. His friend is a video game developer so this didn't seem suspicious. The "video game" had a landing page and everything. Turns out that his friend's account had already been hacked and the "video game" was a stealer like this. TL;DR: he lost his account and that same hacker tried to get me with the same scheme.
Discord support has been completely unhelpful, because he didn't have 2FA enabled before and the hacker added it.
"oops I got hacked when I hacked and/or tried to hack you" is a pretty old trick... I would be cautious about this friend.
At least it was just discord. I'd treat this as a valuable lesson on the virtue of 2FA especially if they have a habit of running untrusted executables (especially with admin permissions...)
I don't think you should feel safe just because you have 2FA enabled. Local malware can wait until the next time you have to provide your second factor, and then use it to disable 2FA, etc.
My main takeaway from looking at some of the repositories is that they are deathly afraid of being run in a VM, because they think that means someone is trying to reverse engineer them. (Which I suppose makes sense; test untrusted software in a VM, if it doesn't do anything evil, then run it outside of the VM.)
At the end of the day, running local exes is about trust. Having 2FA enabled reduces the attack surface you have exposed, even if it doesn't eliminate it as you point out.
I think they just mean that recovering the account post-compromise was not possible because they didn't have 2fa already setup to authorize them as the true owner of the account, not that 2fa would've prevented the issue
