Optimization of 32-bit Unsigned Division by Constants on 64-bit Targets
2026/04/09 by Shigeo Mitsunari, Takashi Hoshino · 14 voices
#cs.PL #cs.AR
paper · pdf
Abstract
Granlund and Montgomery proposed an optimization method for unsigned integer division by constants [3]. Their method (called the GM method in this paper) was further improved in part by works such as [1] and [7], and is now adopted by major compilers including GCC, Clang, Microsoft Compiler, and Apple Clang. However, for example, for x/7, the generated code is designed for 32-bit CPUs and therefore does not fully exploit 64-bit capabilities. This paper proposes an optimization method for 32-bit unsigned division by constants targeting 64-bit CPUs. We implemented patches for LLVM/GCC and achieved speedups of 1.67x on Intel Xeon w9-3495X (Sapphire Rapids) and 1.98x on Apple M4 (Apple M-series SoC) in the microbenchmark described later. The LLVM patch has already been merged into llvm:main [6], demonstrating the practical applicability of the proposed method.
Discussions
- Optimization of 32-bit Unsigned Division by Constants on 64-bit Targets [hn, 110 points, 14 comments]
- Optimization of 32-bit Unsigned Division by Constants on 64-bit Targets [lobsters, 9 points, 0 comments]
- Optimization of 32-bit Unsigned Division by Constants on 64-bit Targets. LLVM and GCC patches. arxiv.org/abs/2604.07902 [bsky, 4 points, 0 comments]
- Optimization of 32-bit Unsigned Division by Constants on 64-bit Targets [hn, 3 points, 0 comments]
- Optimization of 32-bit Unsigned Division by Constants on 64-bit Targets [hn, 1 points, 0 comments]
- Optimization of 32-bit Unsigned Division by Constants on 64-bit Targets https://lobste.rs/s/wm1uxw #math #compilers [bsky, 0 points, 0 comments]
- [2604.07902] Optimization of 32-bit Unsigned Division by Constants on 64-bit Targets [bsky, 0 points, 0 comments]
- Discover the latest advancements in optimizing 32-bit unsigned division by constants for 64-bit architectures. This research sheds light on techniques that enhance performance and efficiency, paving t [bsky, 0 points, 0 comments]
- Optimization of 32-bit Unsigned Division by Constants on 64-bit Targets #HackerNews https://arxiv.org/abs/2604.07902 [bsky, 0 points, 0 comments]
- Optimization of 32-bit Unsigned Division by Constants on 64-bit Targets https:// arxiv.org/abs/2604.07902 # arxiv [mastodon, 0 points, 0 comments]
- Optimization of 32-bit Unsigned Division by Constants on 64-bit Targets https:// arxiv.org/abs/2604.07902 # HackerNews # optimization # unsigneddivision # 64bit # computing # arxiv # technews [mastodon, 0 points, 0 comments]
- Optimization of 32-bit Unsigned Division by Constants on 64-bit Targets https://arxiv.org/abs/2604.07902 https://news.ycombinator.com/item?id=47737542 [bsky, 0 points, 0 comments]
- https://bsky.app/profile/hackernews.com.web.brid.gy/post/3mjebnpextan2 [bsky, 0 points, 0 comments]
- Optimization of 32-bit Unsigned Division by Constants on 64-bit Targets https://arxiv.org/abs/2604.07902 [bsky, 0 points, 0 comments]
Related