github-actions[bot] commented on code in PR #66391: URL: https://github.com/apache/doris/pull/66391#discussion_r3861181700
########## be/benchmark/benchmark_wide_integer_division.hpp: ########## @@ -0,0 +1,256 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. +// +// Benchmarks for wide::integer<256> division (Decimal256 backing type). +// Each optimized divide() path is measured against a local copy of the +// generic bit-by-bit binary long-division loop that was the only +// implementation before commit d6a5448 ("fast paths for wide-integer +// division"). Both share the same operands in the same TU, so the +// LegacyGeneric vs Default numbers directly quantify the speedup. + +#pragma once + +#include <benchmark/benchmark.h> + +#include <cstdint> +#include <random> +#include <stdexcept> +#include <vector> + +#include "core/types.h" + +namespace doris { +namespace { + +using wide::operator&; +using wide::operator|; +using wide::operator-; +using wide::operator~; + +// --------------------------------------------------------------------------- +// Generic binary long division -- the pre-fast-path implementation. Operates +// on the public operator surface of wide::integer; throws std::domain_error +// instead of doris::Exception to keep the benchmark TU dependency-light. +// There is intentionally only ONE generic loop here (used for both / and %), +// matching the old code shape where operator% reused divide(). +// --------------------------------------------------------------------------- +template <size_t Bits> +wide::integer<Bits, unsigned> divide_generic(wide::integer<Bits, unsigned> numerator, + wide::integer<Bits, unsigned> denominator) { + const wide::integer<Bits, unsigned> zero = 0; + if (denominator == zero) { + throw std::domain_error("Division by zero"); + } + wide::integer<Bits, unsigned> x = 1; + wide::integer<Bits, unsigned> quotient = 0; + const wide::integer<Bits, unsigned> one_al = 1; + + while (!(denominator > numerator) && ((denominator >> (Bits - 1)) & one_al) == zero) { + x = x << 1; + denominator = denominator << 1; + } + while (x != zero) { + if (!(denominator > numerator)) { + numerator = numerator - denominator; + quotient = quotient | x; + } + x = x >> 1; + denominator = denominator >> 1; + } + // quotient is returned; numerator now holds the remainder (same contract + // as _impl::divide, though callers of this helper only see the quotient). + return quotient; +} + +// --------------------------------------------------------------------------- +// Workload set. Each case constructs N (dividend, divisor) pairs that hit +// exactly one code path of the optimized divide(): +// 0 BothFit128 -- n,d < 2^128 -> path 1 (native __int128) +// 1 SingleLimb -- d < 2^64, wide n -> path 2 (word-by-word, x/10^k) +// 2 TwoLimbKnuth -- 2^64<=d<2^128, wide n -> path 3 (Knuth Algorithm D) +// 3 TrulyWide -- d >= 2^128 -> generic loop (unchanged) +// For every case we run (op in {Div,Mod}) x (impl in {Default,LegacyGeneric}). +// --------------------------------------------------------------------------- +struct DivisorCase { + const char* name; + std::vector<wide::UInt256> numerators; + std::vector<wide::UInt256> divisors; +}; + +wide::UInt256 random_wide_with_low_bits(std::mt19937_64& rng, unsigned low_bits) { + // Uniform value strictly below 2^low_bits (multiple of 64: 128, 192, 256 + // in these benchmarks). limb(i) is offset from the little-endian limb array. + wide::UInt256 v = 0; + for (unsigned i = 0; i < low_bits / 64; ++i) { + v = v | (wide::UInt256(rng()) << (64 * i)); + } + return v; +} + +wide::UInt256 pow10_int256(unsigned k) { + wide::UInt256 r = 1; + for (unsigned i = 0; i < k; ++i) { + r = r * 10; + } + return r; +} + +DivisorCase make_case(int case_id, size_t n) { + std::mt19937_64 rng(0x9e3779b97f4a7c15ULL + case_id); + DivisorCase c; + c.numerators.resize(n); + c.divisors.resize(n); + switch (case_id) { + case 0: { // BothFit128: money/count magnitudes + c.name = "BothFit128"; + for (size_t i = 0; i < n; ++i) { + c.numerators[i] = random_wide_with_low_bits(rng, 128); + wide::UInt256 d = random_wide_with_low_bits(rng, 128); + c.divisors[i] = (d == 0) ? wide::UInt256(1) : d; + } + break; + } + case 1: { // SingleLimb: x/10^k rounding path, wide dividends, d=10^k + c.name = "SingleLimb"; + // 10^19 < 2^64; vary k over the Decimal256 scale range used by + // round/ceil (10^1..10^19) and mix in random 64-bit divisors. + for (size_t i = 0; i < n; ++i) { + c.numerators[i] = random_wide_with_low_bits(rng, 256); + if (i % 2 == 0) { + const unsigned k = 1 + static_cast<unsigned>(rng() % 19); + c.divisors[i] = pow10_int256(k); + } else { + wide::UInt256 d(rng()); + c.divisors[i] = (d == 0) ? wide::UInt256(1) : d; + } + } + break; + } + case 2: { // TwoLimbKnuth: 65..128-bit divisors, wide dividends + c.name = "TwoLimbKnuth"; + for (size_t i = 0; i < n; ++i) { + c.numerators[i] = random_wide_with_low_bits(rng, 256); + wide::UInt256 d = random_wide_with_low_bits(rng, 128); + // Ensure the divisor genuinely needs two limbs (bit 64 set) so it + // misses the single-limb path and lands in divide_knuth. + d = d | (wide::UInt256(1) << 64); + c.divisors[i] = d; + } + break; + } + case 3: { // TrulyWide: divisor >= 2^128, unchanged generic loop + c.name = "TrulyWide"; + for (size_t i = 0; i < n; ++i) { + // Divisor=2^192 forces generic loop; placing den in the 3rd limb + // keeps all fast paths (single-limb, two-limb Knuth) off. + wide::UInt256 num = random_wide_with_low_bits(rng, 256) | (wide::UInt256(1) << 255); + wide::UInt256 den = random_wide_with_low_bits(rng, 192) | (wide::UInt256(1) << 132); + c.numerators[i] = num; + c.divisors[i] = den; + } + break; + } + } + return c; +} + +template <bool UseLegacyGeneric> +void bench_div(benchmark::State& state, int case_id) { + const DivisorCase c = make_case(case_id, state.range(0)); + const size_t batch = c.numerators.size(); + size_t idx = 0; + for (auto _ : state) { + for (size_t k = 0; k < batch; ++k) { + wide::UInt256 n = c.numerators[idx]; + const wide::UInt256 d = c.divisors[idx]; + idx = (idx + 1) & (batch - 1); // batch is always 4096 (power of 2) + if constexpr (UseLegacyGeneric) { + wide::UInt256 q = divide_generic(n, d); + benchmark::DoNotOptimize(q); + } else { + // divide() writes the remainder into its first argument, so each + // iteration must restart from a fresh copy of the dividend. + wide::UInt256 q = n / d; + benchmark::DoNotOptimize(q); + } + } + } + state.SetItemsProcessed(state.iterations() * static_cast<int64_t>(batch)); +} + +template <bool UseLegacyGeneric> +void bench_mod(benchmark::State& state, int case_id) { + const DivisorCase c = make_case(case_id, state.range(0)); + const size_t batch = c.numerators.size(); + size_t idx = 0; + for (auto _ : state) { + for (size_t k = 0; k < batch; ++k) { + wide::UInt256 n = c.numerators[idx]; + const wide::UInt256 d = c.divisors[idx]; + idx = (idx + 1) & (batch - 1); // batch is always 4096 (power of 2) + if constexpr (UseLegacyGeneric) { + // Old behavior: operator% could not go faster than divide() since + // it consumed divide()'s remainder slot without extra lanes. + wide::UInt256 q = n; + wide::UInt256 sink = divide_generic(q, d); Review Comment: [P2] Keep the legacy remainder observable here. `divide_generic` takes its numerator by value, so this call mutates only a private copy: `sink` is the quotient and `q` remains the original dividend. Consequently `Mod_LegacyGeneric` keeps the same output live as the division benchmark, while `Mod_Default` keeps the actual remainder live, so this is not an equivalent old-vs-new `%` comparison. Give the helper the original mutable-remainder contract and observe that mutated remainder in this branch (with result equivalence checked outside the timed loop). ########## be/benchmark/benchmark_main.cpp: ########## @@ -32,7 +32,11 @@ #include "benchmark_hll_merge.hpp" #include "benchmark_hybrid_set.hpp" #include "benchmark_json_extract.hpp" +#include "benchmark_pdep_unpack.hpp" +#include "benchmark_string.hpp" Review Comment: [P1] Remove this registration or fix its unity linkage before enabling the benchmark target. `benchmark_string.hpp` directly includes `function_string.cpp`, while `benchmark_test` also links the `Exprs` archive. With the default unity build, `function_string.cpp` shares the 161-168 batch with `function_string_basic/digest/mask/search.cpp`; the included copy calls those registrations, which pulls that unity object and introduces a second strong `register_function_string` definition. Thus `BUILD_BENCHMARK` cannot link under the default configuration. This unrelated include should be removed here, or the string benchmark must stop including the production `.cpp` / receive the documented unity exclusion in its own change. ########## be/test/core/wide_integer_test.cpp: ########## @@ -194,4 +197,470 @@ TEST(WideInteger, Shift) { #endif } +TEST(WideInteger, SingleLimbDivisorFastPath) { + // A 256-bit dividend with all four 64-bit limbs populated. + const UInt256 n = (UInt256(0xFEDCBA9876543210ULL) << 192) | + (UInt256(0x1122334455667788ULL) << 128) | + (UInt256(0x99AABBCCDDEEFF00ULL) << 64) | UInt256(0x0123456789ABCDEFULL); + + // Divisors that all fit in a single 64-bit limb (exercise the fast path). + const UInt256 single_limb_divisors[] = { + UInt256(1ULL), + UInt256(2ULL), + UInt256(3ULL), + UInt256(7ULL), + UInt256(10ULL), + UInt256(1000000000ULL), + UInt256(1000000000000000000ULL), // 10^18 + UInt256(0x8000000000000000ULL), // 2^63 + UInt256(0xFFFFFFFFFFFFFFFFULL), // 2^64 - 1, the largest single limb + }; + for (const UInt256& d : single_limb_divisors) { + const UInt256 q = n / d; + const UInt256 r = n % d; + // q * d + r must reconstruct n, and the remainder must be strictly less than d. + ASSERT_EQ(q * d + r, n); + ASSERT_TRUE(r < d); + } +} + +TEST(WideInteger, MultiLimbDivisorBoundary) { + const UInt256 n = (UInt256(0xFEDCBA9876543210ULL) << 192) | + (UInt256(0x1122334455667788ULL) << 128) | + (UInt256(0x99AABBCCDDEEFF00ULL) << 64) | UInt256(0x0123456789ABCDEFULL); + + // Divisors that need two or more limbs must take the general path, not the fast path. + const UInt256 multi_limb_divisors[] = { + UInt256(1ULL) << 64, // 2^64: first value past single limb + (UInt256(1ULL) << 64) + UInt256(1ULL), // 2^64 + 1 + (UInt256(1ULL) << 100) + UInt256(12345ULL), + (UInt256(1ULL) << 192) + UInt256(0xDEADBEEFULL), + }; + for (const UInt256& d : multi_limb_divisors) { + const UInt256 q = n / d; + const UInt256 r = n % d; + ASSERT_EQ(q * d + r, n); + ASSERT_TRUE(r < d); + } +} + +TEST(WideInteger, SingleLimbKnownAnswers) { + // 10^38 / 10^19 == 10^19 exactly (10^19 fits in a single 64-bit limb). + const UInt256 p19 = UInt256(10000000000000000000ULL); // 10^19 + const UInt256 p38 = p19 * p19; // 10^38 + ASSERT_EQ(p38 / p19, p19); + ASSERT_EQ(p38 % p19, UInt256(0ULL)); + + // Exact division and non-zero remainder with a small divisor. + ASSERT_EQ(UInt256(1000ULL) / UInt256(7ULL), UInt256(142ULL)); + ASSERT_EQ(UInt256(1000ULL) % UInt256(7ULL), UInt256(6ULL)); + + // Dividend smaller than divisor -> quotient 0, remainder is the dividend. + ASSERT_EQ(UInt256(5ULL) / UInt256(9999999967ULL), UInt256(0ULL)); + ASSERT_EQ(UInt256(5ULL) % UInt256(9999999967ULL), UInt256(5ULL)); +} + +TEST(WideInteger, SingleLimbSignedDivision) { + // The fast path runs on the unsigned magnitudes; sign handling stays in the wrappers. + const Int256 n = (Int256(0x0011223344556677LL) << 128) | Int256(0x8899AABBCCDDEEFFLL); + const Int256 d = 1000000007; // prime, single limb + + ASSERT_EQ((-n) / d, -(n / d)); + ASSERT_EQ(n / (-d), -(n / d)); + ASSERT_EQ((-n) / (-d), n / d); + + // Truncation-toward-zero semantics for the remainder sign. + ASSERT_EQ((-n) % d, -(n % d)); + ASSERT_EQ(n % (-d), n % d); +} + +TEST(WideInteger, TwoLimbDivisorDifferential) { + // Cross-check the 128-bit-divisor Knuth path against the compiler's native + // unsigned __int128 division. Both operands fit in 128 bits so the quotient + // and remainder are exactly representable and comparable. + std::mt19937_64 rng(0xC0FFEE1234ULL); + auto rnd = [&rng]() { return rng(); }; + for (int iter = 0; iter < 20000; ++iter) { + const unsigned __int128 num = (static_cast<unsigned __int128>(rnd()) << 64) | rnd(); + // Force a genuine 2-limb divisor: the high 64 bits must be non-zero. + unsigned __int128 den = (static_cast<unsigned __int128>(rnd()) << 64) | rnd(); + if ((den >> 64) == 0) { + den |= (static_cast<unsigned __int128>(1) << 64); + } + + const unsigned __int128 expected_q = num / den; + const unsigned __int128 expected_r = num % den; + + const UInt256 q = UInt256(num) / UInt256(den); Review Comment: [P2] Make this differential test enter the Knuth path. Both `num` and `den` are constructed from `unsigned __int128`, so their upper 128 bits are zero and `divide()` returns through the earlier both-fit-128 branch; these calls never exercise `divide_knuth` as the comment claims. The tests that do reach Knuth only check fixed-width `q*d+r==n`/`r<d`, which is not independent: for the tested `d=2^127`, adding `2^129` to a bad quotient changes a writable quotient digit but leaves the product unchanged modulo 2^256. Please force the dividend above bit 128 and compare quotient and remainder with an independent 256-bit oracle (including normalization/correction/add-back cases). -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
