Jakob Degen

mem: Add mini_vec crate and type Summary: `MiniVec` is a `Vec` but is a single pointer on the stack; the length and capacity are bitpacked into the *top* bits of the pointer if they're small, otherwise allocated in the heap. This does introduce high-bit pointer packing to buck2 which we have not had so far. Claude assures me that modern kernels do not hand out high addresses without a user explicitly asking for them and no one complained when I asked, so I guess the team is on board with this. I'll use this in a couple places, but the first thing we'll be able to do is replace all the `ThinBoxSlice` Reviewed By: jtbraun Differential Revision: D105465807 fbshipit-source-id: 65663fb277c1301be55a3b1e94ef831ae80d4f78

Replace Dice task internals Summary: This mostly rewrites the management of the per-key dice task state that manages cancellation, dependents, spawning the worker, etc. Chris initially did this because it unblocked an approach to paging that he was considering (described in the next diff). My understanding is that they have since picked a different direction, so this needs new justification. I do think that despite that change, the next diff is a well-motivated simplification on its own. It fixes a small memory issue I encountered elsewhere, but also having just the single map does seem quite a bit easier to reason about. As to whether this diff would be well-motivated on its own even without the next one is a bit less obvious (claude and I talked and interestingly we disagree somewhat). The new data structure is subtler and more complicated than any one thing that existed before, but in exchange for that there's only one thing; previously there were three differently synchronized things (an atomic and two locks) managing information equivalent to what is now the `DiceTaskInternal` contents. I tend to think that's an improvement. The current version has some sketchy things going on, but at least they're all in one place and I think a person has better odds of reasoning correctly about it (claude tells me the previous version of this was actually probably bug-free but idrk if I believe it). In other words, I like this because I think one explicitly complicated component is better than three implicitly complicated ones. There's one somewhat significant wart here in the form of the `AtomicList` type, which is simple but pretty poorly optimized. I may try to revisit that. ...and then after writing all that explanation I ran benchmarks on the next diff and saw it was -2.5% memory. So now this is all easily justified Reviewed By: jtbraun Differential Revision: D103355606 fbshipit-source-id: f8616468c3e8f94ed2c3a8fe8e5d0276a56b7748

mem: Change how `DiceTransaction` -> `DiceComputation` works Summary: We want to have `&'c mut DiceComputations<'d>` return `&'d Value`s. Right now, it can't do that because `DiceTransaction` derefs to `DiceComputations<'static>` and obviously we can't get back `'static` things. We instead need a conversion like `&'d DiceTransaction -> DiceComputations<'d>` and this diff does that. We remove the deref impl (since the signature is no longer right), add `.ctx() -> DiceComputations<'d>` instead, and then go and fix all the compiler errors. As a part of that, we can actually change the representation of `BaseComputeCtx` to just directly hold a `CoreCtx`, which makes a bit more sense. I'll do some renames towards the end of this stack to help justify why things are the way they are (note also that the use of `ModernComputeCtx::Parallel` is fine here and actually has nothing to do with `Parallel` specifically) Reviewed By: NavidQar Differential Revision: D110626399 fbshipit-source-id: 4ba0db607a88e3456ccb7b091b6c2bf5402566c7

mem: Implement improved `join_all` and `try_join_all` futures Summary: We currently use `futures` for this which is extremely inefficient for little good reason. Reimplement it better. Details are in the code as always, but I'll say that I actually am pretty happy with where this landed in terms of complexity to benefit ratio. The one little index table trick is basically the only clever thing going on here, and in exchange we have memory use that's like `80 + N * (max(future size, return size) + 1)` (compared to `futures` which allocates like 80 bytes of bookkeeping for each future). I'll send some follow ups later to use this in other parts of buck2 as well, but will stick to the current stuff in dice for a bit longer first. Reviewed By: jtbraun Differential Revision: D111267627 fbshipit-source-id: bb3891e360b50afa622a482c74b4c5c1600900ec

writes: Refactor cmd_args tests Summary: Split these tests up into more files and also add a bunch more tests primarily reproducing the behavior when multiple options are applied in sequence. Repros a whole bunch of bugs Reviewed By: IanChilds Differential Revision: D105514102 fbshipit-source-id: ac1346bae46585bb2dabc4c5bd933853def2914c

mem: Fix up the linear recompute APIs for lifetime changes Summary: I apologize, I screwed this stack up and wrote it all out of order, it was really hard to keep this all in my head at the same time. I did end up somewhere good at the end, but at this point it's a mess. This diff fixes up the linear recompute APIs to something that we can better support under the new lifetime model and fixes a minor bug around a bad assert in the previous model. I don't really know if it's worth trying to explain this too hard, the way to review this is I guess to look at the changes to the dice APIs, decide that they're reasonable, notice that the `.into_inner().unwrap()` is gone, and trust me that it's useful for the rest of the changes? Reviewed By: jtbraun Differential Revision: D111267628 fbshipit-source-id: 5b5470a0614e8c4b976ae7793707596354a0521c

mem: Migrate most parallel futures to async closures Summary: Complete most of the migration from the previous diff. As a part of this we rename the old APIs to `_boxed`, rename the new APIs to unprefixed, and then migrate nearly everything to use the new APIs. All the things that are migrated here were completely trivial and could have been done by sed, which speaks to the ergonomics wins. There's a handful of remaining holdouts that are not migrated yet because they looked like they'd need a tiny bit more attention, doing those next. Reviewed By: jtbraun Differential Revision: D111267639 fbshipit-source-id: e3347b4ca3e537f431c54298f523e809acf217dc

docs: Start some perf docs, add a bunch for memory profiling Summary: Claude and I did some memory profiling. Write down what we found and how we used it for next time I went through all of the md content in reasonable detail (not the scripts) I didn't touch the old heap profiling docs yet, will do that next diff Reviewed By: Nero5023 Differential Revision: D105392804 fbshipit-source-id: af1f4a30916af66a05e350c92777828cfb14abf6

mem: Redo the way projection tasks are handled Summary: We currently use the same storage and task type to handle both projection and regular keys. Stop doing that - make a different task type for projection keys evaluations that has like only half the infrastructure, have different storage for that task, etc. This has a little bit of copy and paste and a little bit of its own complexity, but that complexity is very much fundamental and now much more explicit than it was before. This diff does take a revised approach to the way it handles cancellations - that approach was mosty decided after writing the rest of the stack, where far more detailed analysis lead me to the conclusion that this was the best direction to go in Reviewed By: jtbraun, ericweb2 Differential Revision: D110626416 fbshipit-source-id: 5ae99393b9d0327b9556db5345fccc5efb8e78e3

mem: Add `AtomicWakerSet` primitive for waker sets Summary: Like it says in the title. Simple, doesn't allocate a bunch of memory, fast enough for our use cases. Details in the diff. Use it in one place immediately, next diff gets another use Reviewed By: jtbraun Differential Revision: D110626439 fbshipit-source-id: a6e4ba1f322bf1cc934d4757147161853e6eaa01

tokio: Emit detailed tokio metrics Summary: So that when tokio related things are causing slowdowns in builds, we have a chance of understanding why A previous version of this diff had a superconsole component to visualize this, but actually the data here is kind of "raw" and aggregating this into useful insights is not so easy, and needing to make that compatible with terminal limitations is a tall ask. So I didn't bother, next diff just does web stuff for this On my 192 worker devserver (a lot more than in most sandcastle jobs) this increases snapshot events from 1KB/s to 3KB/s post compression. That seems ok, I think Reviewed By: jtbraun Differential Revision: D104518327 fbshipit-source-id: ccd40be366a2eee430dcf21ff3fff3e9b2512ae2

writes: Rewrite command line formatting Summary: This diff rewrites `CommandLineFormatter` and the command line options handling in `cmd_args` (and a few other places). Before, the way this worked is basically two traits `CommandLineContext` and `CommandLineBuilder`, everything was dynamically dispatched on these, and `cmd_args` options used a wrapper struct that did its own processing and forwarding. This was extremely hard to reason about as things were kind of non-local across these impls, as proven by the bugs. Instead, all of this is now done statically in `CommandLineFormatter`. It maintains stacks of in-scope options and whenever an arg is pushed applies them in the expected order. `CommandlineBuilder` stays but is much simplified, only acting as the "sink" at the bottom of the option stack. All of the ad-hoc usage of things like `AbsoluteCommandLineContext` and `SpaceSeparatedCommandLineBuilder` are replaced with direct flags (for absolute) or just manually specifying the space-separated option in the options stack Unfortunately I don't really know that it's possible to split this up so I didn't try. There are a couple intentional behavior changes in here. The first is a bunch of bug-fixes, some of which are reproduced in tests, I think there's probably others. The second is that `absolute_prefix` and `absolute_suffix`, when nested, now just have the inner one override the outer one, compared to the previous behavior where they both applied but in the opposite of the order you'd expect. A quick grep shows that this won't break anything. The original behaviors were all clearly not by-design, so I'm not going to make a post, though I may write some documentation later. D103142010 is the one thing that I had to fix to get this building things, and it was pretty clearly relying on buggy behavior Reviewed By: IanChilds Differential Revision: D105514110 fbshipit-source-id: 3038bdaa174213907d47134baaacc559e653cf3c

mem: Redo much cancellation handling Summary: Ughhh, I screwed this up. Didn't realize until too late though. So here's what I did: Our cancellation code today has a bunch of bugs, mostly because it's concurrent code and unless you're very intentional about how you write it, "bugs" is the default outcome. One of the main causes of those bugs is that we basically made no attempt to really reason about the semantics (in terms of the dice API) of cancellations. This diff fixes that by removing the `CancellationReason` enum in favor of types that distinguish the semantic meaning of cancellation. There are two such types, representing that dice has two kinds of cancellation: - `WorkerCancelled` indicates that a dice worker was cancelled, for any of the reasons that a dice worker was cancelled - `TransactionCancelled` indicates that the entire transaction was cancelled We distinguish everywhere which type of cancellation we are dealing with and handle the two quite differently in some contexts. Most of the rest of this is explained in comments as appropriate; the interesting parts of this diff are 1) the definition of particularly `TransactionCancelled`, and 2) all of the changes to `task/dice.rs` that were needed to handle this. The second category of changes implies a couple bugfixes to the transaction cancelling case, the evidence for that being that there used to be code like ``` if task.is_pending() { task.cancel(); } ``` Which is always an obvious race condition. All the other changes are plumbing. So now for the screwup - I was 99% done with this diff before I realized that we should have done something else instead: Just removed transaction cancellation. There's basically no good reason that you need it, you should be able to rely on everything being automatically cancelled when you discard the top-level `compute` futures. The only reason that you can't just do that in a super naive way is because you do need to do something slightly smarter to be able to detect idle states. Also you'd need to fix the bug from the previous diff. I'm submitting this diff anyway because I think it's an improvement particularly in combination with the stacked stuff and I don't have time to make that change. Reviewed By: ericweb2 Differential Revision: D110626397 fbshipit-source-id: 9f470c351602bb4f9513755b371e1e49d496bcb3

sketches: Better weighted sketching algorithm Summary: Replace the existing two sketch algorithms with one that provides the best of all worlds: Full locality sensitivity and marginal correctness, O(log W) perf. Adopt this even for the unweighted case, which actually gets faster on account of no longer needing the `FyShuffle` All details in comments Reviewed By: cbnilrem Differential Revision: D111647599 fbshipit-source-id: b29ec7ae1062bb57e7de757703455d50822c90dd

mem: Allocate whole `DiceComputations` in the arena Summary: We currently have a layout where each parallel branch future holds a `DiceComputations { RecordingDepsTracker }`, a self referential pointer to that `DiceComputations`, and a pointer to a `RecordedDeps` in an arena into which the deps are written when the future finishes. The self-referential nature of this means 1) we need the HRTB bounds in the API, and 2) the entire thing needs to be boxed (inside `OwnedFuture`) to get pointers stable for the self-referential thing. We also waste a bunch of memory because we simultaneously make room for both a `RecordedDeps` and `RecordingDepsTracker`. This diff primarily makes the change of using the aforementioned arena to store the entire `DiceComputations`. This removes the duplication across `RecordingDepsTracker` and `RecordedDeps`, the self referential thing, and the `OwnedFuture`. In the process of doing all that, we also replace the `TypedArena` - which is quite memory inefficient - with a small hand-written thing, taking advantage of the exact size iterator. This has one small memory drawback insofar that we're now very marginally worse at cleaning up when one future in the branch has finished but another has not, in particular we don't replace the `RecordedDepsTracker` with a `RecordedDeps` yet. Memory is massively improved in every other way though, as mentioned, and overall this comes out very positive. This diff itself has some very sketchy unsafe around a couple of the lifetimes. The problem is as follows; if you have a `ctx: &'a mut DiceComputations<'d>; ctx.compute_many(|ctx2| ...)`, the inner `ctx2` ends up with type `DiceComputations<'a>`, but the arena holding that thing is created (ish) when the outer `DiceComputations<'d>` is prepared at which point `'a` doesn't exist yet. There would be some ways to do this differently, but we're not going to bother right now because that problem goes away in two diffs. Reviewed By: jtbraun Differential Revision: D111267625 fbshipit-source-id: 63bbc3ee9e7d45135590b194e4c500097a314085

mem: Non-zero version number Summary: Make `Option<VersionNumber>` also 8 bytes Reviewed By: jtbraun Differential Revision: D105465797 fbshipit-source-id: ebbfca847eb18262620188a48ba4a83fe8f96346

mem: Check in fragmentation profiler Summary: I reviewed the buck side of this but not the mem_frag side of this, that's all claude. Results of this I'd shared separately Reviewed By: jtbraun Differential Revision: D111273560 fbshipit-source-id: 30f18c734bf308d57b87215f8b3d9d54633cf2cc

logs: `log shed select-events` command Summary: Subcommand to make it possible to re-generate a new event event log with some of the events removed/only some included. Using this in other parts of the stack to be able to evaluate some things about event log sizes Reviewed By: jtbraun Differential Revision: D104518328 fbshipit-source-id: 9016832fda6335f6b972462712be2cce8729d421

mem: Redo our size assertion macros Summary: Our size assertions are soon going to become dependent on mini_vec pointer packing being enabled, so have some macros that are auto-disabled if it's not. At the same time, make some improvements to the APIs for these size assertions to be a bit more opinionated. Reviewed By: jtbraun Differential Revision: D108570683 fbshipit-source-id: c37d242641066c5eb516d5368ae55067eafadad2

fs: Implement `RelativePath` in buck2 Summary: Like discussed This is a nearly direct re-implementation, with the one exception being that we roll in some of the workarounds we already had for `relative_path`s inconsistent path separator normalization on windows. There's lots more to do here but it's all in one giant FIXME at the top Reviewed By: IanChilds Differential Revision: D105505954 fbshipit-source-id: 7e5346c9ef37ddeb34e41856916b38a2f7a05bc6