QuantEcon / QuantEcon.py / 29307752988

94%

push

github

PERF: Vectorize the update loop in _pivoting (#861)

* PERF: Vectorize the update loop in _pivoting

Copy the normalized pivot row into a buffer: reading it from `tableau`
inside the update loop creates a potential-aliasing hazard with the
row being updated, which prevented the loop from being vectorized.
Also divide once instead of per element, with an explicit cleanup pass
to keep the pivot column an exact unit vector (previously ensured by
x/x == 1 holding exactly).

1.7-1.9x per pivot for tableaus with >= 50 rows; lemke_howson end to
end: 1.9x at n >= 50.

Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>

* FIX: Normalize the pivot row by direct division

Reciprocal multiplication overflows where direct division stays
finite, e.g. for a subnormal float64 pivot; _pivoting itself imposes
no lower bound on the pivot element (the tolerance guards live in the
ratio tests of its callers). Dividing in the buffered normalization
costs nothing measurable, as the ncols divisions amortize over the
nrows x ncols update, and makes the kernel's output bitwise identical
to the previous implementation. Add a focused test file for _pivoting:
a direct-division reference comparison, the exact-unit-pivot-column
invariant, and the subnormal regression.

Found in external review of #861 by ChatGPT.

Co-Authored-By: Claude Fable 5 <noreply@anthropic.com>

---------

Co-authored-by: Claude Fable 5 <noreply@anthropic.com>

36 of 36 new or added lines in 1 file covered. (100.0%)

8242 of 8799 relevant lines covered (93.67%)

0.94 hits per line