folly — Engineering Performance

uint_divisor, lifted from thrift Fast64BitRemainderCalculator Summary: Lift `apache::thrift::frozen::detail::Fast64BitRemainderCalculator` into a new public header `folly/math/Division.h` as `folly::uint_divisor<Word>`, generalized to all unsigned integer types. Uses Lemire's constant-divisor technique (credited in doc-comments). Key changes vs. the thrift original: - Support all unsigned integer types, possibly falling back to integer division. - Support zero divisors since the optimized algorithm does not perform division. - Calculates composite division and remainder, division, or remainder. - `constexpr` construction and invocation. - Invocable-object usage with `operator()` in addition to `divrem`. Mathematical operator usage with `operator/` and `operator%` in addition to `div` and `rem`. - Thrift uses Lemire’s direct fast-remainder algorithm: multiply by a precomputed reciprocal, then perform another widened multiply to recover the remainder. uint_divisor uses the same reciprocal to compute the exact quotient and derives the remainder as dividend - quotient * divisor. For 64-bit words this reduces the hot path from roughly four multiplies to three while remaining branchless. Narrow types retain Lemire’s direct remainder path where it benchmarks faster. - Hold the original divisor in addition to the computed multiplier to support mathematical operator usage. This increases in-situ object size. - Add `uint_divisor<Word>::calc` that does not hold the original divisor; let both `uint_divisor` and `Fast64BitRemainderCalculator` delegate to it. Reviewed By: iahs Differential Revision: D115907214 fbshipit-source-id: de6d55b8dac71489f4f36b382eeb9e065380cad1

cli_apply_args_files Summary: In the context of CLI args-parsing, a facility to apply args-files to an args vector. An arg beginning with `@` but not with `@@` is treated as a filename, relative to the current directory if relative, after the `@`. That arg is then replaced by parsing the file into a sequence of arguments, recursively. Reviewed By: hchokshi Differential Revision: D92167066 fbshipit-source-id: 9652db02b04202fa258f6589d468568d5f51d3d5

`benchmark_ab.py`: multi-binary benchmark A/B reports Summary: `benchmark_ab.py` is a new tool to simplify iterating on changes that affect several benchmark binaries. It handles three recurring chores: - Finds benchmark binaries from Buck target patterns. - Aggregates repeated A/B runs into one report. - Prioritizes wins and regressions with absolute and relative thresholds. Read the file docblock for more. ```text $ folly/tool/benchmark_ab.py measure --before=bc56e16776 --after=0097974dca \ //folly/result/... ... High-priority regressions: 15.2+11.2ns (+73.5%): try_to_result_error fbcode//folly/result/test:result_bench 15.2+11.2, 15.2+11.3, 15.2+11.1, 15.2+11.2, 15.4+11.2 ``` Reviewed By: janondrusek Differential Revision: D112568029 fbshipit-source-id: 544b93f75660e791285743188150a3eec38b1e1e

AsyncSocketTest: parametrize with IoUringBackend Summary: Validate native AsyncSocket support with IoUringBackend. Parametrize most tests (that make sense) with the backend, testing both the standard libevent backend and the io_uring backend. Reviewed By: vishwanath1306 Differential Revision: D90996725 fbshipit-source-id: a60b1702f1b6efe8d089ef1f2cb8e5b2d8207f42

`AsyncClosure.h` implement `async_closure` with async RAII Summary: Here's the short rationale for `async_closure()`. The header has a user-facing tl;dr, and `docs/` provide far more context. - It provides a robust solution to the "async cleanup" / "async RAII" problem. `co_cleanup_capture` allows the closure to await multiple cleanup steps on exit (like `co_scope_exit`), but the cleanup is actually enforced to be memory-safe (unlike `co_scope_exit`). - Async scopes owned by a closure can support "natural" cancellation, without incurring additional cost for it the way you would with `CancellableAsyncScope`. - It supports compile-time-checked "safe" reference-passing from ancestors to descendants. From a user's perspective, they just pass `capture`s into child closures, and it works. Or when it fails to compile, this means there may be a memory-safety bug. --- The integration of `MemberTask` with `async_closure` is a bit magic, in two ways: - A special branch lets us use the pre-existing `FOLLY_INVOKE_MEMBER` "overload set" convention with `capture` and `AsyncObjectPtr` wrappers that require dereferencing. We could avoid this by introducing a separate macro like `FOLLY_INVOKE_MEMBER_INDIRECT` or `FOLLY_INVOKE_MEMBER_TASK`, but the current UX feels comfortable, and I don't see a big risk. - (true as of the prior diff) As with `ClosureTask`, `async_closure` implicitly re-wraps `MemberTask` making it movable and upgrading its `SafeTask` safety level. PS We should eventually have a linter that enforces that `MemberTask` is only used for non-static member functions, but this seems low-risk for now. *The user-facing explanation of this is in `APIBestPractices.md` (D65408249).* Reviewed By: ispeters Differential Revision: D63299858 fbshipit-source-id: a3519b3873c7b0e9859db9f848a4cde916a950bf

algorithms for byte-sized find_first_of, find_first_not_of Summary: Includes a selection of scalar and vector algorithms all implementing `find_first_of` and `find_first_not_of`. May be useful to accelerate select parsers. Reviewed By: DenisYaroshevskiy Differential Revision: D61775260 fbshipit-source-id: 32fdd8e7c02c66a54764b0ae847aec1fa9564678

result<T>: value-or-exception_wrapper type & short-circuiting coro Summary: ## Pitch for "working programmers" `result<T>` is a more ergonomic, safer `Try<T>` replacement for code that, for reasons of performance or reliability, chooses to explicitly propagate errors via `return`. Consider this "idiomatic `Try` code": ```cpp // Bug farm: what if this accidentally throws? Try<int> mayFail() { ... } Try<float> alsoFallible() { Try<int> tryN = mayFail(); float v = 5.0; if (tryN.hasValue()) { v += *tryN; } else if (tryN.hasError()) { return Try<float>(tryN.error()); } else { // This bug is easy to make, since `Try` default-constructs as empty! LOG(DFATAL) << "BUG: `mayFail()` returned an empty Try"; } return Try<float>(v); } ``` With `result`, both potential bugs are prevented, and the code is *just* business logic: - "What if `mayFail()` accidentally throws?" is a non-issue since `alsoFallible()` is a `result` coroutine, and thus automatically wraps any uncaught exceptions. - "Empty `Try`" bugs go away since `result` is almost-never-empty [*] ```cpp result<int> mayFail() { ... } result<float> alsoFallible() { co_return 5.0 + co_await mayFail(); } ``` [*] Until we have `std::expected` in C++23, `result<T>` is implemented via `folly::Expected<T, exception_wrapper>`, which is merely "almost-never-empty", rather than "never empty". That said, you will be hard-pressed to hit the empty state with well-formed types -- I tried and failed to construct one naturally in `result_test.cpp` (and settled for "synthetic" objects in an empty state). If you **do** manage hit the empty state, the `result` accessors are carefully crafted to degrade gracefully, so the end user really doesn't have to test for it. --- ## Cancellation -- library-author considerations Looking ahead to C++26 and [P2300](https://wg21.link/p2300), note that receivers have 3 completion states: value/error/stopped. In `folly::coro`, the latter 2 are fused -- cancelled tasks finish with exception `OperationCancelled`. On the other hand, [P2300](https://wg21.link/p2300) takes pains to separate them. That thinking derives from [P1677](https://wg21.link/p1677). The central "working programmer" problem that "cancellation is not an exception" tries to address is, in paraphrase: > "Child stopped" should NOT be handled by exception catch-alls, since a higher-level orchestrator decided the work is no longer needed. The right behavior is to free the resources from this tree of execution as quickly as possible. So, by letting "stopped" state bypass regular exception-handling, [P1677](https://wg21.link/p1677) / [P2300](https://wg21.link/p2300) aim to prevent the class of bugs where cancellation gets accidentally caught and "handled". Today's users of `folly` expect only 2 states: value & error (possibly `OperationCancelled`). Since `result` is a new API, this stack takes the opportunity to add some forward-compatibility. First, D72181807 and D72074521 take some steps to discourage the use of raw `OperationCancelled` by end-users -- `result` is one of the suggested solutions. Second, the top-level `result<T>` API is sort-of bi-state -- it exposes only `has_value()` as a primary test. The "error" and "stopped" state are deliberately hidden in a `non_value()` sub-structure. Yes, `result` also has `has_stopped()`, but that's just shorthand for `!has_value() && non_value().has_stopped()`. This two-level design works quite well to reconcile the goals of "good UX today" and "forward-compatibility with value/error/stopped semantics": - Getting values is easy & safe -- `co_await ...` / `co_await coro::co_ready(...)`. These recommended idioms auto-propagate unhandled errors & cancellation. - Testing specific errors is easy & safe -- `get_exception<Ex>(res)`. - Manually propagating unhandled errors & cancellation is also easy & safe -- `return std::move(res).non_value()`. On the other hand, `result` do **not** provide an easy catch-all -- it would be prone to accidentally catching the cancellation exception! Rather, `result` **deliberately** omits `has_error()` or `error()` -- you have to access `non_value()` to get at those, meaning that you're more likely to correctly test `has_stopped()`. From a user perspective, `result` is `variant<T, variant<stopped, error>>`. However, the implementation is just `Expected<T, exception_wrapper>` -- and it efficiently ingests exceptions from `folly::coro` and `Try`, which don't treat "stopped" separately. Here's how that works: - We use `make_legacy_...` and `get_legacy_...` methods to interact with old-school implementations like `folly::coro` & `Try`. These methods expect an `expection_wrapper` which **may** be an `OperationCancelled`. - In contrast, using normal **end-user** APIs, debug builds will **terminate** if you store `OperationCancelled` in, or retrieve an `error()` from a stopped-state `result` / `non_value_result`. The error says to use `has_stopped()` and `stopped_result` instead. Finally, `result` also prohibits `error()` from being an empty `exception_wrapper` -- that unconditionally terminates if you try to re-throw it! This creates some option value -- once we actively go after `OperationCancelled` deprecation, we can potentially co-opt this empty state as a cheap cancellation signal. Reviewed By: ispeters Differential Revision: D71522263 fbshipit-source-id: 8ae98c979c61e5cd9a26dfc26fbf86dd36471b3f

Add --bm_mode=adaptive; change default --bm_min_usec=1000 Summary: # `--bm_mode=adaptive` I got frustrated with manually retrying benchmark runs to avoid system performance oscillations, and with manually aggregating these runs to get a reasonably precise number. Existing modes (regular or `--bm_estimate_time`) weren't working very well for me -- too noisy, too slow, or both. The new `--bm_mode=adaptive` tries to automate a "statistically sound measurement" for a system that is not short-term stationary. Think of it is "automatic noise cancellation" for the modern reality of working on multi-tenant VMs. If you're used to doing best-of-5 -- this is the same idea, but better. Read `docs/BenchmarkAdaptive.md` for a proper description, and the caveats. --- # `--bm_min_usec` default change: 100μs -> 1ms **This makes default runs 3-8x slower, but they'll stop being wrong.** Here are 5 back-to-back runs with `--bm_min_usec=100 -bm_max_secs=30` on a quiet system. I raise "max_secs" because the default under-samples with larger `min_usec`, giving even more noise. ``` LegacyCaseInsensitiveCheck 9.23us 108.33K CurrentCaseInsensitiveCheck 1.41us 711.35K LegacyCaseInsensitiveCheck 9.23us 108.33K CurrentCaseInsensitiveCheck 1.54us 650.59K LegacyCaseInsensitiveCheck 9.23us 108.33K CurrentCaseInsensitiveCheck 1.40us 712.26K LegacyCaseInsensitiveCheck 8.41us 118.87K CurrentCaseInsensitiveCheck 1.54us 650.26K LegacyCaseInsensitiveCheck 9.23us 108.33K CurrentCaseInsensitiveCheck 1.41us 710.83K ``` Wildly inconsistent! Each took 1.6 seconds, so 8 seconds total, and we're none the wiser about the true distribution. And it's much slower than the typical 1-2 sec for `adaptive` on the same 2 benchmarks, which *does* produce consistent results, fast. ``` $ time buck run @//mode/opt fbcode//folly/test:ascii_case_insensitive_benchmark -- --bm_mode=adaptive ... LegacyCaseInsensitiveCheck 8.54us 117.09K CurrentCaseInsensitiveCheck 1.40us 714.48K real 0m0.870s ``` With 100μs slices above, the regular runs shows cache interference from the benchmark harness code (I'm 80% sure that's the cause, from my experiments). Going to `--bm_min_usec=1000` hides that, and makes regular runs consistent too. With 1ms slices, regular-mode runs look like this, but they now take **~12 seconds** each (only 4 with default `max_secs`, but that's noisier). But hey, at least you get usable data! ``` LegacyCaseInsensitiveCheck 8.50us 117.60K CurrentCaseInsensitiveCheck 1.39us 718.93K LegacyCaseInsensitiveCheck 8.50us 117.61K CurrentCaseInsensitiveCheck 1.42us 704.37K ``` The timings differ slightly, since `adaptive` measures p33 by default, while regular always measures p0. If 1ms is deemed "too slow by default", 500μs is borderline -- you still see unacceptable interference, but not as much. I could imagine landing with that for the regular/legacy mode, and giving `adaptive` a better default. It'd be cool to redesign of the benchmark setup to skip timing the first few iterations of each slice to mitigate this more generally, but I'm not sure the cost-benefit is favorable. Reviewed By: yfeldblum Differential Revision: D92348138 fbshipit-source-id: 92dda73d6753a07aeac9b51cb4efb155cd1f6143

Reproducible floating-point summations Summary: Introduce ReproducibleFloatingAccumulator. Header-only C++ library for reproducible (order-independent) floating-point summation using binned floating-point arithmetic, adapted from ReproBLAS v2.1.0. Key features of the accumulator: - Reproducible summation independent of summation order - Accuracy at least as good as conventional summation, and tunable via FOLD - Handles overflow, underflow, NaN, and infinity reproducibly - Single read-only pass over summands; minimal memory (2*FOLD floats - usually 6 since FOLD=3 is sufficient for most purposes) Public interface: - Default, copy, and implicit scalar construction - operator+=/-= for scalars and accumulators - Binary operator+/- (including scalar-accumulator mixed expressions) - operator== for bitwise equality - Explicit conversion to native float via operator ftype() and value() - Batch add() via iterator pairs, C++20 ranges, or single values - Manual unsafe_add/renorm path for performance-critical loops - Error bound computation - fmt::formatter specialization (always available via fmt/format.h) - static_assert(FOLD >= 2) to catch invalid instantiation # Example ``` ReproducibleAccumulator<double> rfa; for (const auto& x : kDoubleData) { rfa += x; } rfa.value(); // Same result irrespective of ordering of kDoubleData ``` # Benchmark ``` ============================================================================ [...]/ReproducibleAccumulatorBenchmark.cpp relative time/iter iters/s ============================================================================ SumDouble_OneAtATime_10 50.69ns 19.73M SumDouble_BatchAdd_10 55.744% 90.93ns 11.00M ---------------------------------------------------------------------------- SumDouble_OneAtATime_1000 4.11us 243.32K SumDouble_BatchAdd_1000 132.29% 3.11us 321.88K ---------------------------------------------------------------------------- SumDouble_OneAtATime_1M 4.11ms 243.12 SumDouble_BatchAdd_1M 137.09% 3.00ms 333.30 ---------------------------------------------------------------------------- SumFloat_OneAtATime_1M 4.14ms 241.69 SumFloat_BatchAdd_1M 137.35% 3.01ms 331.96 ---------------------------------------------------------------------------- SumDouble_NaiveBaseline_1M 1.03ms 975.29 SumFloat_NaiveBaseline_1M 1.02ms 975.89 ---------------------------------------------------------------------------- SumDouble_Kahan_1M 13.31ms 75.11 SumFloat_Kahan_1M 13.32ms 75.10 ---------------------------------------------------------------------------- SumDouble_LongDouble_1M 2.39ms 418.41 SumFloat_LongDouble_1M 2.39ms 418.72 ``` Reviewed By: yfeldblum Differential Revision: D97780214 fbshipit-source-id: 07399b5f905f3a021252560ad80df47fe53db21a

cstring_view, operator""_csv Summary: A class like `string_view`, but representing a pair of a C string and its precalculated size. Similar to [p3655r3](https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/p3655r3.html). Reviewed By: ilvokhin Differential Revision: D84381600 fbshipit-source-id: c793679ea6ebd95f2db80b8afd182384af476d36