astral-sh / astral-sh/ruff

New lint rules for Strength Reduction optimizations

Open
#14,636 5 comments 2 reactions 0 assignees View on GitHub
needs-decision rule
Dominant language
Rust
Stars
49.7k
Forks
2.4k
Avg merge
2d 1h
Merged PRs (30d)
458

Description

Please consider adding new lint rules for [strength reduction](https://en.wikipedia.org/wiki/Strength_reduction) optimizations. All of the types of optimizations included in the below examples would improve the performance of Python code, some significantly, especially when the numbers are large. Ruff is fast, so lets help make Python fast as well! A few of the examples would also improve the accuracy/precision of the expression. They should hopefully not decrease the readability of the code and in a few cases might even improve it by simplifying the expressions. Most of them are language agnostic, but they are particularly important in Python, as there is of course typically no compiler to perform the optimizations automatically (at least in CPython). The indented ones are just additional examples of what the proposed new lint rules could fix.

### Power of 2 integer optimizations
```py
x * 2 # ⇒ x + x or x << 1
x * 8 # ⇒ x << 3
x // 2 # ⇒ x >> 1
x // 8 # ⇒ x >> 3
x % 2 # ⇒ x & 1
x % 8 # ⇒ x & 7
2 ** x # ⇒ 1 << x
pow(2, x)
y * 2 ** x # ⇒ y << x
8 ** 3 # ⇒ 8 << 6 or 1 << 9
```
### Exponentiation and Modular optimizations
```py
(x * x) % y # ⇒ pow(x, 2, y)
(x ** 2) % y
(x * x * x) % y # ⇒ pow(x, 3, y)
(x ** 3) % y
pow(x, 3) % y
x ** 2 # ⇒ x * x
pow(x, 2)
pow(x, y) # ⇒ x ** y
q, r = x // y, x % y # ⇒ q, r = divmod(x, y)
q = x // y; r = x % y
len(bin(x)[2:]) # ⇒ x.bit_length() # Python 3.1+
len(bin(x).lstrip("-0b"))
```
Also see the `FURB161` rule.
### Math library related, improves accuracy
```py
math.ceil(x / y) # ⇒ -(x // -y) # int only
int(math.sqrt(x)) # ⇒ math.isqrt(x) # Python 3.8+
x ** 0.5 # ⇒ math.sqrt(x)
x ** (1 / 2)
pow(x, 0.5)
math.pow(x, 0.5)
x ** (1 / 3) # ⇒ math.cbrt(x) # Python 3.11+
pow(x, 1 / 3)
math.pow(x, 1 / 3)
math.e ** x # ⇒ math.exp(x)
pow(math.e, x)
math.pow(math.e, x)
2.0 ** x # ⇒ math.exp2(x) # float only # Python 3.11+
pow(2.0, x)
math.pow(2.0, x)
math.exp(x) - 1 # ⇒ math.expm1(x) # Python 3.2+
(math.e ** x) - 1
pow(math.e, x) - 1
math.pow(math.e, x) - 1
x % y # ⇒ math.fmod(x, y) # float only
(x * y) + z # ⇒ math.fma(x, y, z) # float only # Python 3.13+
math.pi * 2 # ⇒ math.tau # Python 3.6+
functools.reduce(operator.mul, (x, y, z), 1) # ⇒ math.prod((x, y, z)) # Python 3.8+
```
These are similar to the existing rule `FURB163`.
### Mathematical identities

- [ ] #19518

May be useful in combination with other autofixes to simplify expressions or when refactoring
```py
x * -1 # ⇒ -x
x / -1.0 # ⇒ -x # float only
x // -1 # ⇒ -x # int only
x * 0 # ⇒ 0
x * 1 # ⇒ x
x + 0 # ⇒ x
x - 0 # ⇒ x
x - -y # ⇒ x + y
x + -y # ⇒ x - y
+x # ⇒ x
x / 1.0 # ⇒ x # float only
x // 1 # ⇒ x # int only
x ** 0 # ⇒ 1
x ** 1 # ⇒ x
x / y / z # ⇒ x * z / y # float only
x / 0.0 # ⇒ ERROR!
x // 0 # ⇒ ERROR!
x % 0 # ⇒ ERROR!
```
Using [DeMorgan’s theorem](https://en.wikipedia.org/wiki/De_Morgan%27s_laws) to further simplify boolean expressions, similar to the [simplify-boolean-expr](https://clang.llvm.org/extra/clang-tidy/checks/readability/simplify-boolean-expr.html) rule in Clang Tidy, would be very helpful here. Also see #15447 and https://github.com/tonybaloney/perflint/issues/50.
### Opinionated, but improves performance
```py
# Replace division with multiplication of the reciprocal
x / 2.0 # ⇒ x * 0.5 # float only
# Prefer separate lines for assignments, unless tuple unpacking or the expressions depend on each other
x, y = x + z, a * b # ⇒ x += z; y = a * b
# Unnecessary trivial comprehensions
(y for y in x) # ⇒ iter(x)
(func(y) for y in x) # ⇒ map(func, x)
(func(*z) for z in zip(x, y))# ⇒ map(func, x, y)
(y for y in x if y) # ⇒ filter(None, x)
(y for y in x if not y) # ⇒ itertools.filterfalse(None, x)
(y for y in x if func(y)) # ⇒ filter(func, x)
(y for y in x if not func(y))# ⇒ itertools.filterfalse(func, x)
# Precompute small constant expressions
60 * 60 * 24 # ⇒ 86400
(1 << 32) - 1 # ⇒ 0xFFFFFFFF
"0" * 8 # ⇒ "00000000"
# Use float literals in exponential notation
10.0 ** 3.0 # ⇒ 1e3 # float only
2.0 * 10.0 ** 3.0 # ⇒ 2e3
```
Also see the `FURB140` rule and https://github.com/adamchainz/flake8-comprehensions/issues/503.

---
All of these should also work with `PLR6104` (#8877), so for example `x * 2` above should also catch `x *= 2` and offer to replace it with `x <<= 1`. There are of course more examples, but these are some of the ones I see most frequently in code reviews. As noted above, some of these may require type inference, but I believe an unsafe autofix would still be acceptable in many cases where the chance of a false positive would be low.

I could see some of these proposed rules being added to the existing `UP`, `PL`, `PERF`, `FURB` and `RUF` categories, among others. Please let me know if you think I should file this request with one of those upstream linters instead.

For a real world example, see this Python function to calculate the Jacobi symbol [before](https://rosettacode.org/wiki/Jacobi_symbol#Python) and [after](https://github.com/tdulcet/AutoPrimeNet/blob/d92313f882ec6dc11e9d79bd55f99ecee2645258/gimps_status.py#L611-L630) manually applying several of these strength reduction optimizations, which approximately doubled the resulting performance of the code.

Contributor guide

Open the contributing guide

Research direction

Start by reviewing the existing FURB163 and FURB140 rules, the PLR6104 proposal, and linked issues #19518, #15447, and #8877. Narrow the many suggested transformations into a defined rule scope; done means the selected cases have agreed diagnostics and autofix behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
python, rust
Domain
performance, tooling
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
20/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.