| commit | c06d0ff806b72b1cfbca6306a2bc4f5f2922b01b | [log] [tgz] |
|---|---|---|
| author | Simon Tatham <simon.tatham@arm.com> | Tue Feb 04 08:57:41 2025 +0000 |
| committer | GitHub <noreply@github.com> | Tue Feb 04 08:57:41 2025 +0000 |
| tree | 3f1a61f92359734b25f3d0d6b69ed2af8d80290f | |
| parent | dcb7a695004c49aaef02c3171343864870009961 [diff] |
[libc] Optimize BigInt→decimal in IntegerToString (#123580) When IntegerToString converts a BigInt into decimal, it determines each digit by computing `n % 10` and then resets n to `n / 10`, until the number becomes zero. The div and mod operations are done using `BigInt::divide_unsigned`, which uses the simplest possible bit-by-bit iteration, which is a slow algorithm in general, but especially so if the divisor 10 must first be promoted to a BigInt the same size as the dividend. The effect is to make each division take quadratic time, so that the overall decimal conversion is cubic – and the division is quadratic in the number of _bits_, so the constant of proportionality is also large. In this patch I've provided custom code to extract decimal digits much faster, based on knowing that the divisor is always 10, and processing a word at a time. So each digit extraction is linear-time with a much smaller constant of proportionality. Full comments are in the code. The general strategy is to do the reduction mod 10 first to determine the output digit; then subtract it off, so that what's left is guaranteed to be an exact multiple of 10; and finally divide by 10 using modular-arithmetic techniques rather than reciprocal-approximation-based ordinary integer division. I didn't find any existing tests of IntegerToString on a BigInt, so I've added one.
Welcome to the LLVM project!
This repository contains the source code for LLVM, a toolkit for the construction of highly optimized compilers, optimizers, and run-time environments.
The LLVM project has multiple components. The core of the project is itself called “LLVM”. This contains all of the tools, libraries, and header files needed to process intermediate representations and convert them into object files. Tools include an assembler, disassembler, bitcode analyzer, and bitcode optimizer.
C-like languages use the Clang frontend. This component compiles C, C++, Objective-C, and Objective-C++ code into LLVM bitcode -- and from there into object files, using LLVM.
Other components include: the libc++ C++ standard library, the LLD linker, and more.
Consult the Getting Started with LLVM page for information on building and running LLVM.
For information on how to contribute to the LLVM project, please take a look at the Contributing to LLVM guide.
Join the LLVM Discourse forums, Discord chat, LLVM Office Hours or Regular sync-ups.
The LLVM project has adopted a code of conduct for participants to all modes of communication within the project.