[Epic] Faster division in integer and decimal kernels #11421

Is your feature request related to a problem or challenge?

Many kernels divide every value in an array by the same divisor. The divisor is known before the loop starts, but not at compile time. In arrow-rs this includes integer / and % by a scalar (integer_op), decimal rescaling, the rescaling of each i256 product in multiply_fixed_point, time unit casts, and Display for i256.

LLVM turns division by a compile-time constant into a multiply and shifts, but it can't do that when the divisor is only known at run time, so each row pays for a full division. For i128 the call to __divti3 or __udivti3 stays even with a literal divisor such as 10^18 (rustc 1.98.1, aarch64).

The usual fix is to compute a reciprocal of the divisor once and turn each division into a high multiply, a shift, and a small correction. Downstream projects are already doing this on their own. @Dandandan added a hand-written StrengthReducedU64 (code) to DataFusion's hash repartitioning in apache/datafusion#21900, which made TPC-H SF10 queries up to 1.16x faster. Comet's WideDecimalBinaryExpr runs Knuth's Algorithm D twice per row to get a quotient and a remainder by the same power of ten (div_round_half_up). With these primitives in arrow-rs, arrow's own kernels could use them, and DataFusion and Comet would share one tested implementation.

Describe the solution you'd like

Precomputed divisors in arrow-buffer, next to i256 and its division code, that arrow's kernels and downstream projects can share. The design follows from the prototype measurements in the tasks below.

Method

Granlund-Montgomery (1994) at every width, with a mask or shift for powers of two. The width of the high multiply changes, from 32x32 to 64 bits for 32-bit types, which vectorizes, up to 256x256 to 512 bits for i256. Within a width, the form depends on the divisor and the target.

Times are prototype measurements in us per 8192-value batch. "Today" is arrow-arith's rem or div kernel for the integer rows, the current arrow-cast code for the Decimal128 rows, and Comet's current code for the i256 rows.

Scope

This epic changes division by a scalar. Division by an array, where each row has its own divisor, keeps today's methods, because a precomputed divisor would be used only once.

Where it plugs in

#11467 sets the API that the i128 and i256 types follow. Each divisor type is a #[non_exhaustive] enum whose variants are branch-free types, and the variant set differs by type. A kernel builds a divisor for each batch, matches on its variant once with a macro that lists the variants per type, and moves the variant into its closure.

The i256 variants are the exception: they branch on the shift, because a branch-free shift was slower on every runner (#12232). For a batch whose values fit in the next narrower type, a kernel builds that type's divisor instead. #12232 has no separate narrow variant.

What every kernel PR must do

• Report before and after numbers from the benchmark bot, on x86_64 and arm64, and at x86-64-v3 for kernels Comet's x86 builds use.
• Divide with unary for every divisor except -1, and test for -1 once outside the loop. A zero divisor and MIN / -1 are the only failures, and the divisor alone says whether either is possible. try_unary visits valid slots one at a time when there are nulls (measurements).
• Keep today's behavior for nulls. [NULL, NULL] / 0, [] / 0 and [NULL, NULL] % 0 return Ok because try_unary skips null slots, and [1, NULL] / 0 returns DivideByZero. Build the divisor only once there's a valid value to divide.
• Turn failures into nulls in the kernel when the caller asks for it (casts with safe: true), the way unary_opt maps None to null today.
• For i128 and i256, check the batch's magnitude and divide batches that fit in the next narrower type with that type's divisor. On such values the wide divisor was as slow as or slower than / and % in perf(arrow-buffer): add precomputed divisors for i128 and i256 #12232, down to 0.55x.
• Include benchmark cases with more than half of the values null and choose the unary versus try_unary threshold from them. unary divides every slot, so its cost doesn't fall as nulls increase, and in perf(arrow-arith): divide integers by a scalar with a precomputed divisor #12076 it was 0.27x to 0.72x of the existing kernel with nine tenths null on x86.

Tasks

Steps that don't need a precomputed divisor, or that remove costs that would hide the divisor's gains in the kernel benchmarks:

• feat(arrow-buffer): add i256::wrapping_div_rem and i256::checked_div_rem #11425
• perf(arrow-array): move the closure into the iterator in PrimitiveArray::unary #11525
• perf(arrow-arith): don't build an error for each decimal div value that overflows when scaled #11479
• try_unary calls the decimal_op closure out of line for every value #11529 (PR perf(arrow-arith): inline decimal div and rem by a scalar into try_unary #12080)
• bench(arrow-cast): add decimal downscale and decimal to integer cast benchmarks #11426
• bench(arrow-arith): add integer and decimal division by scalar benchmarks #11427
• Divide once per row in multiply_fixed_point #11453 (PR perf(arrow-arith): divide once per row in multiply_fixed_point #11526)
• Add combined division and remainder to ArrowNativeTypeOp #11454 (PR feat(arrow-array): add div_rem_wrapping and div_rem_checked to ArrowNativeTypeOp #11528)
• Speed up i256 division #11451
  • PR perf(arrow-buffer): inline bits, add_assign and sub_assign in i256 division #11457
  • PR perf(arrow-buffer): divide i256 magnitudes below 2^128 with one u128 division #11530
  • PR perf(arrow-buffer): divide i256 by a single word with a reciprocal on 64-bit targets other than x86_64 #11580

Steps that use the divisor:

• perf(arrow-buffer): add precomputed divisors for 32-bit and 64-bit integers #11467
• Add precomputed divisors for i128, u128 and i256 #12167 (PR perf(arrow-buffer): add precomputed divisors for i128 and i256 #12232)
• Add rounding helpers on top of the precomputed divisors #12168
• Integer / and % by a scalar (PR perf(arrow-arith): divide integers by a scalar with a precomputed divisor #12076)
• Use precomputed divisors in decimal downscale casts #12169
• Use a precomputed divisor in multiply_fixed_point #12170
• Use precomputed divisors in decimal / and % by a scalar #12171
• Use a precomputed divisor in decimal to integer casts #12172
• Use a precomputed divisor in time unit casts #12173
• Speed up Display for i256 with a constant 10^38 divisor #12174

Optional follow-ups:

• Signed forms for the i32 and i64 divisors (draft PR perf(arrow-buffer): use unsigned high products for signed divisors #11979 by @sdf-jkl). The bot results were faster at the baseline x86-64 target and slower at x86-64-v3 and on arm64, so figure 5.1 stays (reply). The unsigned form on |n| wasn't faster at 128 bits either (perf(arrow-buffer): add precomputed divisors for i128 and i256 #12232). The kernel PRs can revisit it if the baseline x86-64 target matters.

Follow-ups in other repos

• DataFusion could replace StrengthReducedU64 once it uses an arrow release that has the u64 divisor. A power-of-two case in the divisor type covers what partition_indices does today. The swap needs a repartition benchmark to show there's no regression.
• Comet could use the i256 divisor in WideDecimalBinaryExpr, with the i128 variant chosen per batch, and the u32 divisor in pmod, where it was 4.0x faster than today in the prototype (see below). Comet depends on arrow 59.2.0 and DataFusion 55.2.0, so it would adopt these later than DataFusion.
• Two Comet changes need no arrow-rs release (perf: divide once per row in pmod and div_round_half_up datafusion-comet#6781).
• datafusion-spark's mod and pmod expand a scalar divisor to an array, so a literal divisor never reaches the scalar path from perf(arrow-arith): divide integers by a scalar with a precomputed divisor #12076. The fix keeps the divisor a Scalar (mod and pmod expand a scalar divisor to an array, so arrow-rs never takes its scalar divisor path datafusion-spark#100).
• datafusion-spark's decimal floor, ceil, and round divide by 10^scale once per value, and could use the i128 divisor once it is released. unix_timestamp would need the signed i64 form (Use precomputed divisors in decimal floor, ceil, and round, and in unix_timestamp datafusion-spark#99).
• Backport the divisors and the kernels to 59.x as one batch once more of this epic has landed (asked by @timsaucer on perf(arrow-arith): divide integers by a scalar with a precomputed divisor #12076).

Describe alternatives you've considered

Lemire, Kaser and Kurz compute the remainder from a 2N-bit reciprocal, as DataFusion's StrengthReducedU64 does. In the prototype it beat Granlund-Montgomery only on the 64-bit path of the Decimal128 rounding (9.7 vs 13.5 us per batch, where Granlund-Montgomery is still 1.6x to 1.8x faster than today), tied on UInt64Array % 13, and lost at 32 bits, where Granlund-Montgomery vectorizes. That one gain isn't worth a second algorithm's code and tests. #11467 does use the paper's observation in section 3.1 that the remainder doesn't depend on the sign of the divisor.

Depending on strength_reduce would avoid carrying the code. It supports unsigned types only and has no 256-bit type. In the arrow-cast measurements in #12169 it was slower than the fastest hand-written variant in every case except the fallible cast. Its last release (0.2.4) was in November 2022.

This epic is about how a division is computed, not about decimal result types. Precision-loss decimal arithmetic stays out of scope, as @tustvold decided in #4664.

Additional context

The prototype is on a fork (diff), and its README explains how to reproduce each table. divproto/ is a standalone crate with the divisors, their tests and the microbenchmarks. Prototype numbers are from an Apple M5 Max (aarch64), release builds and criterion, against main at 6b34163. Each task's PR reports its own numbers from the benchmark bot.

Comet's pmod on 8192 hash values, in us per batch. Today is Comet's code, which divides twice for negative hashes. "One division" replaces the second % with r + n. The biased method adds 2^31 to the hash so that one unsigned remainder gives the result.