Skip to content

Add fast paths for scalar element access - #599

Open
eriknw wants to merge 8 commits into
18-ss-namespace-refcyclefrom
19-scalar-fast-paths
Open

Add fast paths for scalar element access#599
eriknw wants to merge 8 commits into
18-ss-namespace-refcyclefrom
19-scalar-fast-paths

Conversation

@eriknw

@eriknw eriknw commented Aug 4, 2026

Copy link
Copy Markdown
Member

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_*_setElement fast 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.

  • Vector.get / Matrix.get (03161c3): 13-14x for plain integer indices
    (v.get(i) 5.05us to 0.38us; A.get(i, j) 6.67us to 0.49us).
  • contains, scalar setitem, ScalarIndexExpr.new() (a8ce0bc):
    7-10x on membership tests and integer-index assignment.
  • Plain-int fast lane in parse_index (f9ea991): skips two type checks
    on the common path; 10-19% on v[i] construction and .new().
  • Parity tests (64940d5): 211 tests comparing each fast lane against
    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.
  • v[i].value / float(v[i]) single-extract path (843bd13): resolves the
    nine read-only scalar attrs with one extractElement instead of two
    extracts plus nvals; 1.4-1.5x. .get(i) remains the fast API.
  • Gate the lanes on real integers (445830f): the fast lanes accepted
    any __index__-implementing object (for example a 0-d ndarray) that the
    expression path rejects. Both lanes now accept exactly int and
    np.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 CLIGive Feedback 💬

@eriknw eriknw changed the title 19 scalar fast paths Add fast paths for scalar element access Aug 4, 2026
@eriknw
eriknw marked this pull request as ready for review August 4, 2026 16:07
@eriknw
eriknw force-pushed the 19-scalar-fast-paths branch 3 times, most recently from d7cb7c6 to 51646e7 Compare August 5, 2026 03:18
@eriknw
eriknw force-pushed the 19-scalar-fast-paths branch from 51646e7 to b69beb4 Compare August 5, 2026 17:44
@eriknw
eriknw force-pushed the 19-scalar-fast-paths branch from b69beb4 to 94e3f47 Compare August 5, 2026 18:03
@eriknw
eriknw force-pushed the 19-scalar-fast-paths branch 2 times, most recently from 424bc8d to c2e3c77 Compare August 6, 2026 07:59
@eriknw
eriknw force-pushed the 19-scalar-fast-paths branch 2 times, most recently from d92d27f to 705c990 Compare August 6, 2026 15:41
@eriknw
eriknw force-pushed the 19-scalar-fast-paths branch 2 times, most recently from 3794f68 to ac640b1 Compare August 6, 2026 20:41
@eriknw
eriknw force-pushed the 19-scalar-fast-paths branch from ac640b1 to 599c70b Compare August 7, 2026 02:48
eriknw added 8 commits August 7, 2026 00:09
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
eriknw force-pushed the 19-scalar-fast-paths branch from 599c70b to fe14199 Compare August 7, 2026 05:09
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant