neilconway opened a new pull request, #10668: URL: https://github.com/apache/arrow-rs/pull/10668
# Which issue does this PR close? - Closes #10664 - Closes #10665 - Closes #10666 # Rationale for this change The previous implementation of `parse_string_to_decimal_native` used a string-manipulation approach: it trimmed the input string, split it based on `"."`, parsed both havings with `i256::from_string`, converted the result back to a string with `format!`, and parsed that _again_ with `i256::from_string`. Instead, we can implement the parse by doing a single pass over the input bytes. A simple state machine walks over the input digits, accumulating a running sum. This avoids all of the string manipulation and heap allocation of the previous approach. We further optimize this by accumulating the running sum in a `u64`, and then periodically folding that partial value into the running `decimal` value. That trades a bit of redundant computation for doing more work in `u64` and much less work in `decimal`, which is a clear win. Finally, we can ignore the suffix of the string; values beyond the target type's scale don't contribute to the result value; only the first digit influences rounding behavior. This new approach also fixes two correctness bugs (#10664 and #10665) in the previous implementation. **Benchmarks** Parser microbenchmarks (arrow-cast/benches/parse_decimal.rs): - string decimal128 integer: ~111 ns → 15.8 ns, −85.8% - string decimal128 exact scale: ~109 ns → 15.2 ns, −86.0% - string decimal128 padded scale: ~116 ns → 15.3 ns, −86.8% - string decimal128 rounded scale: ~175 ns → 15.7 ns, −91.0% - string decimal128 signed: 201.8 ns → 15.7 ns, −92.2% - string decimal128 38 digits: 116.8 ns → 27.2 ns, −76.8% - string decimal256 76 digits: 174.4 ns → 61.9 ns, −64.5% - string decimal256 rounded scale: 440.0 ns → 62.3 ns, −85.8% End-to-end cast kernel (arrow/benches/cast_kernels.rs, 512-row string array, safe mode): - cast string to decimal128(38, 3): 558 µs → 68.4 µs, −87.0% - cast string to decimal256(76, 3): 519 µs → 80.1 µs, −84.4% # What changes are included in this PR? * Rewrite `parse_string_to_decimal_native` as described above * Add benchmark coverage * Add unit tests * Clarify / extend comments on accepted syntax and rounding behavior * Replace a `Vec` + `unsafe` with `PrimitiveBuilder`, which saves an allocation # Are these changes tested? Yes; existing tests pass, and new tests have been added. I also tested the new implementation against a naive oracle built using the [num-bigint](https://docs.rs/num-bigint/latest/num_bigint/) crate; the new implementation was consistent with `num-bigint` for 120M tested randomly generated inputs. # Are there any user-facing changes? No, aside from fixed bugs. # AI usage Iterated with the help of Claude Fable; I reviewed and understand the resulting code. -- 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]
