Add fast paths for scalar element access - #599
Open
eriknw wants to merge 8 commits into
Open
Conversation
eriknw
marked this pull request as ready for review
August 4, 2026 16:07
eriknw
force-pushed
the
19-scalar-fast-paths
branch
3 times, most recently
from
August 5, 2026 03:18
d7cb7c6 to
51646e7
Compare
eriknw
force-pushed
the
19-scalar-fast-paths
branch
from
August 5, 2026 17:44
51646e7 to
b69beb4
Compare
eriknw
force-pushed
the
19-scalar-fast-paths
branch
from
August 5, 2026 18:03
b69beb4 to
94e3f47
Compare
eriknw
force-pushed
the
19-scalar-fast-paths
branch
2 times, most recently
from
August 6, 2026 07:59
424bc8d to
c2e3c77
Compare
eriknw
force-pushed
the
19-scalar-fast-paths
branch
2 times, most recently
from
August 6, 2026 15:41
d92d27f to
705c990
Compare
eriknw
force-pushed
the
19-scalar-fast-paths
branch
2 times, most recently
from
August 6, 2026 20:41
3794f68 to
ac640b1
Compare
eriknw
force-pushed
the
19-scalar-fast-paths
branch
from
August 7, 2026 02:48
ac640b1 to
599c70b
Compare
For a plain integer index, with a non-UDT dtype and no active Recorder, call
GrB_*_extractElement directly instead of building an extract expression, a
Scalar, and converting through Scalar.value.
Semantics are unchanged: the same IndexError messages and negative-index
handling as parse_index, bool indices still rejected, UDTs and active
Recorders falling back to the expression path, and TransposedMatrix (which
reuses Matrix.get) extracting the mirrored element.
Measured on an Apple M5 Pro with timeit, best-of-7, warm, while other test
suites were running (load average about 4.5), so indicative rather than
clean-room:
v.get(i) 5.05us -> 0.38us (13x)
A.get(i, j) 6.67us -> 0.49us (14x)
A bare GrB_Vector_extractElement_FP64 call through cffi measures about
0.06us on the same machine, so most of the remaining 0.38us is Python call
and argument handling rather than GraphBLAS work.
…xpr.new()
Applies the Vector/Matrix.get recipe from the previous commit to three more
scalar access paths, calling GrB_*_extractElement or GrB_*_setElement
directly instead of building an extract expression, an Updater, and a Scalar.
Only exact-fit Python int, float, bool and complex values take the setitem
fast path, so dtype inference and cffi coercion match the Updater path
exactly. Masks, accum, opts, UDTs and an active Recorder all fall back to
the full path. TransposedMatrix has no __setitem__, so the setitem fast path
cannot be reached through a transposed view.
An out-of-range index falls through from the fast lane to the expression
path, so membership raises the same IndexError, with the same message, from
either lane. Assignment likewise raises IndexError, in the fast lane as
before.
Measured on an Apple M5 Pro with timeit, best-of-7, warm, while other test
suites were running (load average about 5), so these are indicative rather
than clean-room:
0 in v 3.95us -> 0.40us (9.9x)
(0, 0) in A 5.57us -> 0.53us (10.4x)
v[i] = 5 3.69us -> 0.50us (7.3x)
A[i, j] = 5 5.12us -> 0.62us (8.2x)
The ScalarIndexExpr.new() path gains only the skipped per-argument
marshalling in the `call` wrapper. That difference did not clear measurement
noise on a loaded machine, so no figure is quoted for it; the change stands
on doing strictly less work, not on a measured win.
A `typ is int` branch ahead of the np.issubdtype machinery skips two type
checks costing about 125ns each for the overwhelmingly common case of a plain
Python int index. output_type maps only the exact `int` type to `int`, so
bool and numpy integer indices keep their existing handling. Error messages,
negative wrapping, and the returned AxisIndex are unchanged, and a plain int
is always signed, so the negative branch matches the signedinteger branch it
bypasses.
Measured on an Apple M5 Pro with timeit, min of 15 runs of 20000 calls, warm,
while other test suites were running (load average about 5.7). Before and
after were taken back to back with the same protocol:
v[i] construction 1.85us -> 1.50us (-19%)
v[i].new() 3.48us -> 3.13us (-10%)
A[i, j].new() 5.04us -> 4.34us (-14%)
These are small percentages, so the measurement is worth qualifying: min and
median differed by under 2% on every case, and each saving (0.35us, 0.35us,
0.70us) is many times that spread, in the direction the diff predicts and of
the size two skipped 125ns checks predict. List, slice, and array extracts
are unchanged, since they never took the int branch.
The fast lanes for get, __contains__, integer __setitem__, scalar extract, and plain-int index parsing were checked only by hand-run equivalence scripts that CI never executes. A fast lane that drifts from the expression path it stands in for returns a wrong answer rather than a slow one, so the comparison belongs in the suite where a refactor will trip over it. 211 tests compare each fast path against the expression path across the builtin dtypes (13 of them where complex is supported), hits and misses, negative and out-of-range indices, exception type and message parity, coercion and overflow edges, UDT and Recorder fallback, and TransposedMatrix. They run in the fast tier, in well under a second. The TransposedMatrix case for Matrix.get was absent from this file and is added here. It is not the only guard: test_matrix.py::test_get already asserts A.T.get(1, 0), and deleting the mirroring swap from the get fast path fails that test as well as this one. What the new case adds is shape and breadth. It uses a non-square 3x4 matrix, where equal dimensions cannot hide a row/column swap, and it sweeps every cell against the expression path rather than checking two positions.
The .value, __float__, __int__ and related accessors on an index-extract
expression (v[i], A[i, j]) resolved through automethods._get_value, which
called .new() to build a GrB_Scalar (extract number one) and then read
Scalar.value off it (extract number two, plus nvals). For the nine
read-only scalar attrs that only need the raw element, resolve with a single
extractElement straight into a cscalar through a new private
ScalarIndexExpr._extract_fast hook.
_get_value consults the hook only for _fast_scalar_attrs and only when the
expression defines it, so every other expression type is unchanged and falls
to .new() as before. UDT values, which need numpy conversion in
Scalar.value, and active Recorders fall back to .new().
Measured on an Apple M5 Pro with timeit, min of 15 runs of 20000 calls,
warm, before and after taken back to back while other test suites were
running (load average about 5):
v[i].value 4.72us -> 3.14us (1.50x)
float(v[i]) 4.88us -> 3.18us (1.53x)
A[i, j].value 5.93us -> 4.29us (1.38x)
v[i].new() was measured alongside as a control and did not move, which is
what this diff predicts since it does not touch that path. .get(i), at
about 0.38us, remains the fast API; this only helps the older v[i].value and
float(v[i]) idiom, whose floor is the cost of building the v[i] expression.
The hook region sits above the autogenerate markers, so regenerating
automethods.py leaves it in place. Private surface only (_extract_fast,
_fast_scalar_attrs).
The fast lanes for Vector/Matrix get, __contains__, and integer-key __setitem__ accepted any object implementing __index__, while the expression path (IndexerResolver.parse_index) accepts only exact int and np.integer scalars. Anything else implementing __index__, such as a 0-d ndarray, answered on the fast lane but raised on the slow path. Reproduced at 5581edc8 (fast vs slow), where the slow-path error is TypeError: Invalid number of dimensions for index: 0: Vector.get(np.array(5)) -> 2.5 vs TypeError np.array(5) in v -> True vs TypeError v[np.array(5)] = 1.0 -> sets vs TypeError Matrix.get(np.array(1), np.array(2)) -> 20 vs TypeError (np.array(1), np.array(2)) in A -> True vs TypeError A[np.array(1), np.array(2)] = 1.0 -> sets vs TypeError A custom class implementing __index__ diverged the same way in all six lanes; for it the slow path raises TypeError: Invalid type for index: ...; unable to convert to list. Replace the duck-typed __index__ probe in all six lanes with the type check parse_index applies: exact int or np.integer (bool has its own exact type; np.bool_ is not an np.integer). Anything else now falls through to the expression path and gets its canonical error. Bounds checks and negative wrapping are unchanged for accepted types. The remaining fast lanes on this branch cannot see such inputs: the parse_index int lane already dispatches on exact type, and ScalarIndexExpr.new / _extract_fast run only on indices that parse_index has already validated. Tests: add a 0-d ndarray and an __index__-implementing class to the bad-input parity cases for get, __contains__, and __setitem__ on both Vector and Matrix (17 new cases). With the gate reverted, exactly these 17 fail; with it, test_fastpath_parity.py goes 230 -> 247 passed and the pinned suite 1034 -> 1051 passed, 141 skipped.
eriknw
force-pushed
the
19-scalar-fast-paths
branch
from
August 7, 2026 05:09
599c70b to
fe14199
Compare
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Single-element reads and writes previously built an extract expression, a
Scalar, and sometimes an Updater per call. This branch adds direct
GrB_*_extractElement/GrB_*_setElementfast lanes for the common cases,plus a parity test suite that pins every fast lane to the expression path it
stands in for. UDTs, masks, accum, opts, and an active Recorder all fall back
to the expression path; semantics and error messages are unchanged.
(v.get(i) 5.05us to 0.38us; A.get(i, j) 6.67us to 0.49us).
7-10x on membership tests and integer-index assignment.
on the common path; 10-19% on v[i] construction and .new().
the expression path across dtypes, hits and misses, negative and
out-of-range indices, exception type and message parity, coercion and
overflow edges, UDT and Recorder fallback, and TransposedMatrix.
nine read-only scalar attrs with one extractElement instead of two
extracts plus nvals; 1.4-1.5x.
.get(i)remains the fast API.any
__index__-implementing object (for example a 0-d ndarray) that theexpression path rejects. Both lanes now accept exactly
intandnp.integer; everything else falls through to the canonical error.17 new parity cases.
Timings were taken with timeit on a loaded Apple M5 Pro, so they are
indicative rather than clean-room; the commit messages carry the protocol
and caveats.
Stack created with GitHub Stacks CLI • Give Feedback 💬