Repository navigation
perf(gfql): precomputed in/out degree facts (C2 groundwork) - #1870
Merged
Merged
Conversation
The last board L is q8@100k. Measured levers: per-type col-stats reach 11.37ms (1.13x, just outside the tie band, VALID lane); reformulating the kernel buys ~2.5% and is not enough. The kernel core is an O(E) bincount+gather = 6.76ms of 13.50. Precomputed degree makes it dot(indeg, outdeg), O(N) = 0.046ms -- 148x less query work. Complexity class, not constant factor. TYPED, not global: q8 counts over one relationship type, so a global degree array is the wrong denominator. Keys on the existing (src, dst, type_column, type_value) shape. Staleness is a WRONG ANSWER for this fact kind, which is new -- a stale min/max costs a scan, a stale degree returns a confident miscount. So the identity+fingerprint contract is the correctness guard here, and an endpoint outside the proved interval DECLINES rather than clamping. This lands the fact + builder + pins; the kernel consult follows, so nothing changes behaviour yet. Co-Authored-By: Claude Fable 5 <[email protected]> Claude-Session: https://claude.ai/code/session_01MF7uRZLKZaD6Q9FGWSmyXi
CI mypy: ArrayLike is a deliberately small numpy/cupy surface and did not declare min/max, which the degree builder uses for its interval precondition. Added them to the PROTOCOL rather than casting or ignoring at the call site -- they are universal on both backends, so the protocol was simply incomplete. Typed SupportsInt, not Any: every caller does int(arr.min()), so that is the actual contract and it keeps the explicit-any ratchet clean. Co-Authored-By: Claude Fable 5 <[email protected]> Claude-Session: https://claude.ai/code/session_01MF7uRZLKZaD6Q9FGWSmyXi
pull Bot
pushed a commit
to admariner/pygraphistry
that referenced
this pull request
Aug 12, 2026
…n O(N) dot Wires the facts graphistry#1870 landed. sum_e indeg(src(e)) == dot(indeg, outdeg), so with per-type degrees resident the kernel answers without touching the edges: 6.76ms of query work becomes 0.046ms at board scale. Targets q8@100k (the board's last LOSS) and q9 (same shape, slowest cell). Two design points found while wiring, both pinned because a VALUE test cannot see either: - The node-label <-> relationship-type pairing is QUERY-dependent, not resolvable at index time (labels and rel types are different vocabularies). So degrees are built over the whole dense node interval and the consult SLICES to the proved domain -- sound because the bounds proof already guarantees every filtered endpoint lies inside it. An off-by-one there silently MISCOUNTS. - Identity must anchor to the BOUND edge frame, not the per-type subset the fact was counted over. Anchoring to the subset made every lookup miss: facts built, never used, answers still correct. Only an engagement probe revealed it. Gapped node spaces build nothing -- arrays are indexed by id - lo. 13 pins incl. slice-exactness across four domain shapes and a differential vs the scan on random typed graphs. Whole-tree mypy clean apart from two pre-existing degrees.py errors present on a clean tree. Co-Authored-By: Claude Fable 5 <[email protected]> Claude-Session: https://claude.ai/code/session_01MF7uRZLKZaD6Q9FGWSmyXi
This was referenced Aug 12, 2026
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
1 participant
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.
Groundwork for the board's last remaining loss. No behaviour change yet — this lands the fact, the builder and the pins; the kernel consult follows.
Why this and not more tuning
The kernel core is an O(E)
bincount+ gather = 6.76 ms of 13.50. Precomputed degrees make the identical answerdot(indeg, outdeg)— O(N) = 0.046 ms, 148× less query work. That is a complexity-class change. The profile agrees independently: 48% self-time in the kernel, and a 2.4M-element numpy bincount is memory-bandwidth bound, so no reformulation closes the gap.Board audit says this lands two cells: q8 (the verdict) and q9 ("as q8", 41.4 ms — the slowest query on the board, ~3.6× more absolute time than q8).
Typed, not global
q8 counts over one relationship type, so a global degree array is the wrong denominator. Keys on the existing
(src, dst, type_column, type_value)registry shape.Staleness is a wrong answer here — that is new
A stale min/max fact costs a scan; a stale degree fact returns a confident miscount. So identity+fingerprint is the correctness guard for this type, not an optimization guard, and it refuses on any mismatch. Likewise an endpoint outside the proved interval declines rather than clamping — a clamp would silently miscount.
Pins: dot-vs-gather-sum equivalence on hand and random graphs, every decline, rebind/engine invalidation, typed-vs-global key separation.
🤖 Generated with Claude Code
https://claude.ai/code/session_01MF7uRZLKZaD6Q9FGWSmyXi