perf(gfql): numpy form of the undirected seed-rediscovery rule (#2023) by lmeyerov · Pull Request #2024 · graphistry/pygraphistry

lmeyerov · 2026-09-04T07:36:06Z

Fixes #2023.

What

undirected_rediscovered_seed_ids (the #1918 wavefront rule: a seed survives iff another seed shares its component, or it lies on a cycle — self-loops plus the multigraph 2-core) was a pure-Python loop over every traversed edge, run on every undirected hop step by both the pandas/cuDF and the polars paths. On LiveJournal (34.7M edges), an undirected 2-hop from 50 seeds spent 108 s of 117 s in it under cProfile; the June tree ran the same query in 1.9 s.

Same rule, now as frame operations inside the caller's own engine (review round 1 asked for engine-generic code in its own module, cross-engine tests, no product perf pin, and a changelog entry):

graphistry/compute/gfql/seed_rediscovery.py — pandas and cuDF over DataFrameT (merge, isin, groupby via the existing dataframe_utils helpers); cuDF frames never leave the GPU.
graphistry/compute/gfql/lazy/engine/polars/seed_rediscovery.py — the polars twin (joins, anti-joins, group_by).
Rule A = multi-source label propagation from the seeds, then a pointer-jumping union over seed ranks for the labels that meet across an edge. Rule B = leaf peeling to the 2-core plus self-loops. Both iterate to a fixed point.
hop.py shrinks by ~100 lines to a five-line call site; hop_eager.py calls the polars twin.

Tests (`graphistry/tests/compute/gfql/test_seed_rediscovery_2023.py`, parametrized over pandas / cuDF / polars)

Each boundary pins a kept seed and a dropped seed for the same reason: acyclic path (alone vs two seeds), triangle vs pendant off it, parallel edges vs a single edge, self-loop vs its neighbour, star hub vs hub+leaf, absent seed alone vs beside a kept one, NULL endpoint; plus string ids, a narrower seed dtype, empty inputs, a 300-edge pendant path, and random multigraphs equal to the pure-Python oracle per engine. cuDF ran locally on the GPU box. test_hop_semantics_1918, test_hop, test_chain, test_varlen_bounded_engine_parity_1787: 400 passed / 73 skipped with cuDF enabled. Lint, type-hygiene and comment guards pass; changelog under ## [Development].

Measured

Rule alone, random graphs, local box (3-run min):

edges / seeds	pandas	polars	cuDF
200k / 50	138 ms	42 ms	66 ms
200k / 5k	211 ms	61 ms	87 ms
2M / 50	1,421 ms	314 ms	142 ms
2M / 50k	2,245 ms	513 ms	191 ms

End-to-end LJ undirected 2-hop from the 50 top-degree seeds (dgx-spark, same 26.02-gfql-polars container and script, polars engine, eager-bound, one warm run):

tree	hop1	hop2
June tree `cc0d665a1` (before the #1918 rule existed)	233 ms	1,933 ms
0.59.0 `3fb216dd`	327 ms	60,483 ms
this PR, engine-native (`2d181d223`)	233 ms	6,844 ms

The remaining gap to June is the rule itself (three evaluations per query over the traversed edge ball). A pyg-bench lane (benchmarks/hop_seed_rediscovery, merged as pyg-bench #233) carries the rule-alone points and this LJ query with a regression gate against its receipted baseline.

🤖 Generated with Claude Code

https://claude.ai/code/session_01WwMmVFo44ADiRRj5cxh7i1

lmeyerov · 2026-09-04T15:03:40Z

    return cast(List[Hashable], series.to_list())


+def _host_array(series: SeriesT) -> Union["np.ndarray", List[Hashable]]:


helper should go into a usual dateframeT/seriesT helper file

Done in 451a98b: the numpy helpers are gone. The rule now lives in graphistry/compute/gfql/seed_rediscovery.py (pandas/cuDF over DataFrameT with the existing dataframe_utils helpers) and lazy/engine/polars/seed_rediscovery.py (polars twin); hop.py only calls rediscovered_seed_ids(frame, src, dst, seeds_frame, id_col).

lmeyerov · 2026-09-04T15:04:04Z

+        return _host_list(series)
+
+
+IdSequence = Union[Sequence[Hashable], "np.ndarray"]


Same fix: IdSequence, _host_array and the numpy body are removed from hop.py (451a98b).

lmeyerov · 2026-09-04T15:04:41Z

+            nodes = nbrs[(deg[nbrs] <= 1) & ~removed[nbrs]]
+    in_core = touched & ~removed
+    in_core[u[loops]] = True
+    return np.flatnonzero(in_core)


this adds a lot of code to the main hop for a specialization, wrong location

Agreed. hop.py is now net -100 lines versus master: the specialization moved to its own module and the call site is five lines (451a98b).

lmeyerov · 2026-09-04T15:05:29Z

+    deg_all = np.bincount(ends, minlength=n)
+    indptr = np.zeros(n + 1, dtype=np.int64)
+    np.cumsum(deg_all, out=indptr[1:])
+    return np.concatenate([v, u])[order], np.concatenate([np.arange(len(u))] * 2)[order], deg_all, indptr


weird non-cross-platform -- all these should generally be engine-generic, and suggests testing of x-platform is insufficient, and review skill insufficeintly applied

Rewritten engine-native (451a98b): rule A is multi-source label propagation + a pointer-jumping union over seed ranks, rule B is leaf peeling to the 2-core, both as merge/isin/groupby on the caller's own frames, so cuDF stays on the GPU and polars stays in polars. Cross-engine tests now run the same boundary suite on pandas, cuDF (locally on the GPU box) and polars, and the random-multigraph oracle check runs per engine.

lmeyerov · 2026-09-04T15:06:54Z

+``undirected_rediscovered_seed_ids``; these pins hold the numpy form to the pure-Python
+reference on random multigraphs (parallel edges, self-loops, isolated seeds, string ids)
+and bound its wall time on a large traversal.
+"""


ensure we're doing sufficient positive/negative tests on either sides of the boundary here, including x-platfrom/engine

performance correctness likely needs to go into pyg-bench, shouldn't have regressions like this

New test_seed_rediscovery_2023.py: every boundary has a kept seed and a dropped seed for the same reason (acyclic path alone vs two seeds on it; triangle vs pendant off it; parallel edges vs single edge; self-loop vs its neighbour; star hub vs hub+leaf; absent seed alone vs beside a kept one; NULL endpoint), plus string ids, a narrower seed dtype, empty inputs, a 300-edge pendant path, and random multigraphs equal to the oracle, all parametrized over pandas / cuDF / polars. 2. The product perf pin is removed; the scale measurement moves to a pyg-bench lane (separate private PR) with a receipted baseline and a regression gate.

lmeyerov · 2026-09-04T15:08:01Z

-            out_edges.get_column(src).to_list(), out_edges.get_column(dst).to_list(),
-            seed_id_list,
+            out_edges.get_column(src).to_numpy(), out_edges.get_column(dst).to_numpy(),
+            seed.get_column(NID).to_numpy(),


should these stay engine-level vs cpu?

maybe need perf experiments at diff scales?

Yes, engine-level now: the polars path calls the polars twin (joins/anti-joins, no numpy). Scale experiment on the same random graphs, local box, engine-native rule alone: 200k edges / 50 seeds pandas 138 ms, polars 42 ms, cuDF 66 ms; 2M edges / 50 seeds pandas 1,421 ms, polars 314 ms, cuDF 142 ms; 2M edges / 50k seeds pandas 2,245 ms, polars 513 ms, cuDF 191 ms. The LJ end-to-end after-number for the reworked code will be re-measured on dgx once the current ladder rungs finish (the box is busy), and the pyg-bench lane will carry it going forward.

lmeyerov · 2026-09-04T15:08:58Z

missing changelog.md

lmeyerov · 2026-09-04T15:29:04Z

CHANGELOG.md entry added under ## [Development] (Fixed + Changed) in 451a98b. All six inline comments answered in-thread; summary of the rework is in the updated PR body.

lmeyerov · 2026-09-04T15:55:02Z

Measured the engine-native head (2d181d223) end-to-end on dgx-spark, same container and script as the before-numbers: LJ undirected 2-hop from 50 hub seeds 6,844 ms (0.59.0: 60,483 ms; June tree: 1,933 ms); hop1 233 ms. Table in the PR body.

…e the PageRank solver Vendor pyg-bench's GraphFrames ladder publication (LiveJournal and Orkut: host-Spark GraphFrames baselines, GFQL GPU PageRank with the solver stage as a component cell, and the released code's LJ filter/hop rows as diagnostic cells behind #2023). The page now prints cells only, with one multi-run provenance block; the June saved results and the stale parity file are gone. The chart generator reads the ladder cells (no results.json), draws the solver share as the solid part of each GFQL PageRank bar and the rest of the query as the light part, marks unmeasured systems, and is tested on a synthetic ladder. Friendster is named as the next rung with the reason it waits on #2024. Co-Authored-By: Claude Fable 5.1 <[email protected]> Claude-Session: https://claude.ai/code/session_01WwMmVFo44ADiRRj5cxh7i1

lmeyerov · 2026-09-04T16:23:50Z

CI is fully green on the reworked head (78 checks; the polars lane now runs test_seed_rediscovery_2023.py with a per-file coverage floor). Ready for re-review; every inline thread from round 1 has a reply naming the commit that addresses it.

…he measured ceiling Vendor pyg-bench's second ladder publication: GFQL filter/hop cells and ratios for LiveJournal and Orkut at the head of #2024 (disclosed as pre-landing in the provenance block), and the Friendster rung (1.8B edges, filter + 1-hop on the CPU streaming path, 106 GB peak of a 119 GB host). The page opens with that ceiling, prints wins and losses side by side (GPU PageRank 18.3x/12.5x; CPU faster on filter and 1-hop; GraphFrames wins 2-hop on both graphs; the GPU streaming executor loses every hop), gains a Friendster table and chart, and keeps the released code's 2-hop as a diagnostic before-state sentence. Co-Authored-By: Claude Fable 5.1 <[email protected]> Claude-Session: https://claude.ai/code/session_01WwMmVFo44ADiRRj5cxh7i1

lmeyerov · 2026-09-04T18:45:23Z

Perf-regression testing landed in pyg-bench: #233 (benchmarks/hop_seed_rediscovery/ scale lane + gate_seed_rediscovery.py, 1.5x median tolerance, kept-count/result-size drift fails) and #239 (baseline receipt results/hop-seed-rediscovery-baseline-20260904/receipt.json, measured on dgx at this PR's head e951e9a: rule alone 2M edges/50 seeds pandas 1,281.7 / polars 291.6 / cuDF 215.2 ms; LJ undirected 2-hop end-to-end pandas 51,521 / polars 6,973 / cuDF 4,746 ms). Gate: python benchmarks/hop_seed_rediscovery/gate_seed_rediscovery.py --baseline results/hop-seed-rediscovery-baseline-20260904/receipt.json --candidate <new receipt>.

undirected_rediscovered_seed_ids ran a pure-Python per-edge loop (adjacency dicts, component scan, 2-core peeling) on every undirected hop step, over every traversed edge; an undirected 2-hop from 50 seeds on LiveJournal spent 108 s of 117 s there. Same rule, now over factorized ids in numpy: multi-source BFS from the seeds plus union-find over the seed labels for the shared-component case, batched leaf peeling with CSR edge ids for the multigraph 2-core. The pure-Python form stays as the fallback for ids numpy cannot order and as the oracle the numpy form is pinned equal to on 6000 random multigraphs. Both callers now hand over host arrays instead of python lists. Co-Authored-By: Claude Fable 5.1 <[email protected]> Claude-Session: https://claude.ai/code/session_01WwMmVFo44ADiRRj5cxh7i1

Dense non-negative integer ids index themselves (no factorization sort); BFS labels and leaf peeling scan the edge list per round and fall back to CSR frontiers after 24 rounds; the seed-label union is pointer jumping instead of a Python union-find over deduplicated pairs; polars hands the seeds over as an array too. Co-Authored-By: Claude Fable 5.1 <[email protected]> Claude-Session: https://claude.ai/code/session_01WwMmVFo44ADiRRj5cxh7i1

#2023) Co-Authored-By: Claude Fable 5.1 <[email protected]> Claude-Session: https://claude.ai/code/session_01WwMmVFo44ADiRRj5cxh7i1

… review) Moves the undirected wavefront seed-rediscovery rule out of hop.py into graphistry/compute/gfql/seed_rediscovery.py (pandas/cuDF: merge, isin, groupby) and lazy/engine/polars/seed_rediscovery.py (polars joins), so each engine keeps its frames where they are (cuDF stays on the GPU) instead of copying ids to host numpy. Rule A (a seed shares a component with another seed) is multi-source label propagation plus a pointer-jumping union over seed ranks; rule B (a seed lies on a cycle) is leaf peeling to the 2-core plus self-loops. Callers pass frames in and get a one-column frame back. Tests: one cross-engine suite (pandas, cuDF, polars) with a kept and a dropped seed on each side of every boundary (acyclic path, shared component, isolated seed, triangle, pendant off a cycle, parallel edges, self-loop, star hub/leaf, absent seed, NULL endpoint), string ids, a narrower seed dtype, empty inputs, a 300-edge pendant path, and random multigraphs equal to the pure-Python oracle per engine. The product perf pin is gone; scale is measured in pyg-bench. Co-Authored-By: Claude Fable 5.1 <[email protected]> Claude-Session: https://claude.ai/code/session_01WwMmVFo44ADiRRj5cxh7i1

Co-Authored-By: Claude Fable 5.1 <[email protected]> Claude-Session: https://claude.ai/code/session_01WwMmVFo44ADiRRj5cxh7i1

…ured 100%) Co-Authored-By: Claude Fable 5.1 <[email protected]> Claude-Session: https://claude.ai/code/session_01WwMmVFo44ADiRRj5cxh7i1