Yedidya Feldblum

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

atomic_fetch_min, atomic_fetch_max Summary: Add `atomic_fetch_min` and `atomic_fetch_max` to mimic `std::atomic::fetch_min` and `std::atomic_fetch_max`, with fallbacks in terms of `atomic_fetch_modify`. Reviewed By: ot Differential Revision: D117391575 fbshipit-source-id: c2a40d5f89318e0a5ec690bf9aeb15fc537023a2

atomic_fetch_cond_{op} Summary: Add `atomic_fetch_min_cond`, `atomic_fetch_max_cond`, `atomic_fetch_set_cond`, and `atomic_fetch_reset_cond`, running parallel to the existing `atomic_fetch_{op}` operations. The distinction is that the existing operations are read-modify-writes: they store unconditionally, and so always produce a release edge and always take the cache line exclusively. The `_cond` forms do a trial load first and store only if the value is not already converged. That makes them the right form for high-water marks, min/max stats counters, and idempotent flag bits, where the common steady-state case is that nothing needs to change. This is a real semantic difference, not just an optimization, so the two families are spelled differently rather than one silently becoming the other. A caller which depends on the release edge, or on the operation appearing in the modification order, wants the unconditional form. The doc comments state which each one is. Both families keep the same memory-order parameters as before. It is up to the caller to understand the semantics and choose accordingly. Note there is deliberately no `atomic_fetch_flip_cond`: a flip always changes the bit, so there is nothing to elide. On the fallback path the guard is re-tested on every compare-exchange retry, not only before the loop. A racing writer which converges the value mid-loop therefore ends the loop rather than storing a value that is no longer an improvement. This matters for adoption: the hand-rolled loops these operations are meant to replace overwhelmingly re-test on retry, so without it the library form would be a behaviour change at those call sites rather than a drop-in. Uncontended microbenchmarks: ~19x faster when converged, ~10% slower when advancing, the latter being the cost of the extra trial load. Reviewed By: dmm-fb Differential Revision: D118286954 fbshipit-source-id: 2a43fd69e25d7aab4bd3062fe17b84b93e050244

fixes and tweaks to to_ascii Summary: * Fix `to_ascii_size_clzll`. It returned incorrect digit counts for most bases. `to_ascii_size_route` only sends power-of-two bases and base 10 to it, and for exactly those the old approximation was already exact, meaning that this bug was not seen in practice. But nevertheless. * Fix `char[N]` overloads. They `char[N]` overload of `to_ascii_with_route` bypassed the `kIsMobile` dispatch. * Fix various documentation errors. Reviewed By: dmm-fb Differential Revision: D117892814 fbshipit-source-id: b81ec5c0639f4c4906101f09645a05632a011830

support relaxed_atomic in atomic_fetch_* operations Summary: The `atomic_fetch_*` operations in `folly/synchronization/AtomicUtil.h` did not compile against `folly::relaxed_atomic`. `relaxed_atomic` deliberately omits the `std::memory_order` parameter from every member function, while the operations unconditionally passed one to `load` and to `compare_exchange_weak`. That is an awkward gap, since `relaxed_atomic` is exactly the type reached for on the stats counters and high-water marks which are the natural audience for `atomic_fetch_max` and `atomic_fetch_min`. Add trait `atomic_accepts_memory_order_v`, which gives whether the operations of a type which is atomic-like accept a memory order. It is detected via member `load`, under the convention that such a type accepts a memory order either on all of its operations or on none of them. Split each operation's single `operator()` with a defaulted memory-order parameter into two overloads: one taking no memory order, and one taking a memory order and constrained with `requires(atomic_accepts_memory_order_v<Atomic>)`. So passing a memory order to a `relaxed_atomic` is now ill-formed rather than silently ignored - for such a type there is no memory order to apply. This applies uniformly to `atomic_fetch_set`, `atomic_fetch_reset`, `atomic_fetch_flip`, `atomic_fetch_modify`, `atomic_fetch_min`, and `atomic_fetch_max`. For the bit operations, the `*_fallback` function objects gain overloads taking no memory order, and types which are order-free route to the fallback rather than to `*_native`. This costs nothing: every native path is selected by overload resolution on `std::atomic` or on atomic-ref, and `relaxed_atomic` derives from `std::atomic` protectedly, so it could never have bound to them. `atomic_fetch_min` and `atomic_fetch_max` additionally detect the 1-argument `fetch_min(T)` / `fetch_max(T)` member form. `relaxed_atomic` already declares these under the C++26 `__cpp_lib_atomic_min_max` gate, so without this it would have been stuck on the c/x-loop fallback even once that gate opens. `RelaxedAtomic.h` needs no change - `value_type`, `load`, and `compare_exchange_weak` are already accessible on all four of its shapes. Source-compatible with every existing call site: all of them pass a memory order and use `std::atomic` or `atomic_ref`, and the two overloads differ in arity, so no call becomes ambiguous. The two duck-typed fixtures in the test gain a `load`, which they had lacked only because no code path had previously needed one. Reviewed By: dmm-fb Differential Revision: D118182802 fbshipit-source-id: 99aa8f9908a831ede10761c17cf68d9189917f68

benchmark to_ascii_size over mixed digit widths Summary: Every existing `to_ascii_size` benchmark pins one digit width per `BENCHMARK_PARAM`, so the data-dependent exit branch in the looping implementations is trained to near-perfect prediction in all of them. That hides the misprediction cost which is the whole of the case for the branchless `to_ascii_size_clzll`, and so systematically biases the comparison that `to_ascii_size_route` turns on. Add benchmarks that draw their inputs from a fixed pseudorandom sequence whose digit widths vary, covering all four size implementations -- `imuls`, `idivs`, `array`, `clzll`. The width distribution is geometric, equivalently power law in the value, parameterized by its half-life: the number of digits over which its mass halves. Three are benchmarked: * `inf`, flat, which is log-uniform in the value and the worst case for a per-digit loop; * `4`, halving every fourth digit; and * `1`, halving every digit, as for counters and indices. Uniform is the limit as the half-life grows without bound, so it has no finite spelling. `inf` names that limit, and is the largest `size_t` rather than a value out of band, so that ordering by half-life still orders by flatness. Half-life 4 exists because 1 alone is too steep to cover the range: `(1/2)^20` is small enough that, of 4096 base-10 draws, none at all fall beyond twelve digits. At a half-life of four the whole range is sampled, 666 draws at one digit down to 19 at twenty. Truncation to `[1, to_ascii_size_max]` is by rejection rather than by clamping, which would pile every overshoot onto the widest width as a spike -- 3% of base-10 draws and 6% of base-16 draws at a half-life of four. The sequence is 4096 values long rather than a cycle over the existing `inputs<Base>` table, since a period-21 pattern is short enough for the branch predictor to learn. No behavior change; benchmarks only. ___ Differential Revision: D118547711 fbshipit-source-id: ea31f181a3533a447db0f57712c378582d08e501

make linked hazptr traversal callback-based Summary: Replace the `hazptr_obj_base_linked::push_links` customization point with `for_each_link`, which invokes a callback for each outgoing link. This separates link enumeration from the internal traversal worklist, enabling subsequent worklist optimizations without exposing its container type. Traversal behavior and data structures remain unchanged. landed-with-radar-review Reviewed By: instw Differential Revision: D118348028 fbshipit-source-id: efd2e0318a038439a4825e56420c6a40f4d7e796

add benchmarks for linked hazard-pointer traversal Summary: Add HazptrBench coverage for linked-object retirement and reclamation. The benchmarks measure immutable chain and tree unlinking, along with mutable-chain reclamation, while excluding object construction and teardown from the timed regions. These workloads provide baselines for evaluating traversal-worklist optimizations across production-shaped chains and branching structures. ___ Differential Revision: D118348029 fbshipit-source-id: e0d6adb2af077874d6b370fe41dc6048fcc9b4ec

test to_ascii_size over every base, via the router and the array path Summary: `ToAsciiTest.cpp` tests its four size implementations at two very different depths. All four get spot checks plus an exhaustive hammer over the first four digits at bases 8, 10, and 16, and a comparison against `std::to_string` at base 10. Only `to_ascii_size_clzll` gets the deep treatment: boundary probes at every power of two and every power of the base, and a bit-length sweep, over all 39 bases. `to_ascii_size_array` sees three bases, and `to_ascii_size_idivs` serves as the oracle for the deep helpers rather than being driven by them. Nothing calls the public `folly::to_ascii_size` for any base but 10 either, so `to_ascii_size_route` is untested: every every-base test calls an implementation directly and bypasses the router. Generalize the every-base applier over the implementation and add two suites, giving the router and the array path the coverage `clzll` already has. All four implementations agree on every input, so these pass whichever way the router happens to be wired. Also revive a dead block. The loop commented "all powers of 10" in `to_ascii_size_u64_10_compare` computes `constexpr_pow(uint64_t(2), p)`, which makes it a strict subset of the powers-of-2 loop just above it, so its assertions assert nothing. Of the 60 probes at `10^k` and its neighbors for k in 0..19, 44 were reached by no test at all for `imuls`, `idivs`, and `array`; the first fully unprobed decade was `10^6`, and the gap ran to `10^19 + 1`. One character closes all 44: `10^19 + 1 < 2^64` so nothing overflows, and `p == 0, n == -1` yields 0, a valid input. Verified by perturbing `to_ascii_size_array` to be wrong for `v` in `[10^6, 10^6 + 1000)`, a window no power of two lands in -- the fixed loop catches it, the original does not. ___ Differential Revision: D118588019 fbshipit-source-id: 298d83ad679c31cdf019733267bac14f3b2ec0ed

leak the global regexes in folly::Uri Summary: At process shutdown, if they are not leaked then they get destroyed. And their memory can get reused by other things occurring during shutdown. If URI parsing occurs during shutdown, this would be use-after-destruction and use-after-free and cause crashes. The easiest solution is simply to leak the global regex objects so that they are never destroyed. Reviewed By: joshkehn Differential Revision: D115584671 fbshipit-source-id: cb2f9529a91ebb94fdb04aad0cf7edd69f007c1e