Baymine opened a new pull request, #66391:
URL: https://github.com/apache/doris/pull/66391
### What problem does this PR solve?
Issue Number: no issue
Problem Summary:
`wide::integer` division (backing Decimal256 and other >128-bit integer
types)
always fell back to a generic bit-by-bit binary long-division loop that
iterates
~Bits times (256 shift/compare/subtract rounds for a 256-bit value), even
when
the operands are small. Decimal256 arithmetic and the CEIL/ROUND `x / 10^k`
rounding paths hit this hot loop constantly with operands that are far
narrower
than 256 bits, so the general algorithm dominates the cost.
This adds three stacked fast paths in front of the generic loop, each
bit-exact
with it (verified against native `__int128` oracles and via q*d+r==n
identities),
and each writing the remainder back into `numerator` so `operator%` stays
correct:
1. Both operands fit in 128 bits (the common money/count magnitude): perform
a
single native `unsigned __int128` divide. Placed first because it is the
cheapest and most frequently hit.
2. Divisor fits in a single 64-bit limb (e.g. `x / 10^k`): schoolbook
word-by-word
long division, one hardware 128/64 divide per limb -- O(item_count)
divides
instead of ~Bits iterations.
3. Divisor fits in two 64-bit limbs (65..128-bit divisor): route through a
new
`divide_knuth()` helper implementing Knuth's Algorithm D (Hacker's Delight
`divmnu`) in base 2^32, which keeps every intermediate product within a
uint64_t and stays overflow-safe.
Divisors wider than 128 bits and the zero-divisor throw are unchanged and
fall
through to the existing generic path. On a fast-path miss the only added
cost is
a short limb scan.
### Release note
None
### Check List (For Author)
- Test: Unit Test
- Added/extended `be/test/core/wide_integer_test.cpp` (18 new cases:
single-limb, two-limb Knuth, both-fit-128, signed, boundary,
divide-by-zero,
and randomized differential/ground-truth fuzz against native __int128).
All 23 WideInteger tests pass locally (ASAN build).
- Behavior changed: No (pure performance optimization; results are bit-exact
with
the previous slow path)
- Does this need documentation: No
--
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]
