Optimize integer truncation by constant rationals
| Affects | Status | Importance | Assigned to | Milestone | |
|---|---|---|---|---|---|
| SBCL |
Triaged
|
Wishlist
|
Unassigned | ||
Bug Description
Generalization/
I've been doing some thinking, and we can handle (truncate [unsigned-word] (/ [unsigned-word] [unsigned-word])) fairly efficiently when the second argument is constant and the result is an unsigned word.
For an example of efficiency, it takes ~60% as much time to (truncate x (/ (rational pi))) than to (truncate (* x pi)) when only the first return value is computed. The code also includes improvements for regular truncated division, and is able to exploit the range derived for X to generate smaller code sequences than Granlund & Montgomery (i.e. better than gcc ;).
Downside: the patch is on the heavy side (a few hundred LOC, without comments), and exploits unpublished tricks that haven't been verified by anyone else yet.
I'm opening this ticket to update it with the patch's (and documentation's) progress.
| Paul Khuong (pvk) wrote | #1 |
| Paul Khuong (pvk) wrote | #2 |
| Changed in sbcl: | |
| status: | New → Won't Fix |
| assignee: | Paul Khuong (pvk) → nobody |
| Paul Khuong (pvk) wrote | #3 |
| Changed in sbcl: | |
| status: | Won't Fix → In Progress |
| assignee: | nobody → Paul Khuong (pvk) |
| Changed in sbcl: | |
| importance: | Low → Wishlist |
| status: | In Progress → Triaged |
| assignee: | Paul Khuong (pvk) → nobody |
Seems way too slow to be practical.