Skip to content

viable/strict/1787914523

viable/strict/1787914523: Fix integer overflow in at::divup (#195035)
@malfet malfet tagged this 28 Aug 06:09 
`at::divup(x, y)` computes `(x + y - 1) / y`. The addition overflows for large `x` or `y`, and the result then silently rounds **down** instead of up — `divup(2, INT64_MAX)` returns `0`, not `1`. Guarded with `c10::add_overflows`, falling back to a form that cannot overflow.

Every caller today passes loop extents and chunk counts, so for most of them this is latent. One caller does reach it: `PoolingParams1D::valid_output_end` bounds the `max_pool1d` output range with `divup`, and a large stride there yields a window starting past the end of the input — a segfault. That is the stacked PR on top of this one; splitting it out because `divup` is used well beyond pooling (softmax, moments, the parallel-loop chunking itself) and deserves its own CI signal.

## Performance

Free on the happy path. Measured on an M-series arm64 laptop, `-O3`. Both variants live in **one binary** and are **raced round-robin within each trial**, so thermal drift and frequency changes hit them equally — A/B-ing two libtorch builds measures code layout instead of the change, and gave me a spurious ~9% swing that reproduces as same-build drift. Cycles are from a calibrated dependent-add chain (~4.4 GHz). Numbers below reproduce to three decimals across runs; discard the first run of any such benchmark, it is thermal warm-up.

| | old `(x+y-1)/y` | guarded | delta |
|---|---|---|---|
| **y runtime** (holds an `sdiv`), throughput | 0.448 ns | 0.449 ns | +0.2% |
| **y runtime**, latency | 2.629 ns | 2.407 ns | **−8.4%** |
| **y compile-time constant** (=16), throughput | 0.171 ns | 0.209 ns | +22.2% |
| **y compile-time constant** (=16), latency | 1.330 ns | 1.334 ns | +0.3% |

**Runtime divisor — free, and the loop is divider-bound, not issue-bound.** A bare `sdiv` with nothing else in the loop measures **0.449 ns / ~1.9 cyc**, which is exactly what both variants cost, so the guard's extra instructions are absorbed entirely by the divider's throughput. Latency actually *improves*: the guard's `adds` replaces the old `add`/`sub` pair ahead of the divide.

```asm
old                      guarded
  add  x8, x0, x1          sub  x8, x1, #1
  sub  x8, x8, #1          adds x8, x0, x8
  sdiv x0, x8, x1          b.vs  <fallback>     ; predicted not-taken
                           sdiv x0, x8, x1
```

**Constant divisor — where the cost is.** With `y` a compile-time constant there is no division at all; it folds to a shift, leaving 5 cheap ALU ops, and the guard's 2 extra instructions are a real +22% — of **+0.038 ns/call**. Only `moments_utils.h` (`kChunkSize = 16`) has such a constant among the callers; `SoftMaxKernel.cpp`'s `CHUNK_SIZE` is a runtime `std::min(...)` and takes the free path above. In `moments_utils.h`, `divup` runs once per row of a reduction, ahead of that row's entire Welford loop — in a replica of that shape the difference does not clear the noise floor at any row size.

I also tried `x / y + (x % y > 0)`, which needs no guard at all. It is equivalent on throughput but ~34% worse on runtime-divisor latency, because it puts `msub`/`cmp`/`cinc` *after* the divide instead of ahead of it. Happy to switch if the extra header include is a concern.

🤖 Generated with [Claude Code](https://claude.com/claude-code)
Pull Request resolved: https://github.com/pytorch/pytorch/pull/195035
Approved by: https://github.com/Skylion007

Co-authored-by: Claude Opus 5 <noreply@anthropic.com>
Assets 2
Loading