Skip to content

perf(gfql): hop's full loop re-dedups the accumulated matches every hop (O(hops × matches)) on labeled / min_hops shapes #2047

Description

@lmeyerov

Found in the #2036 dedup audit. graphistry/compute/hop.py full loop (the path taken when fast_path_enabled is off or the shape needs edge/node hop labels or min_hops) accumulates results with concat([matches_edges, hop_edges[[EDGE_ID]]]).drop_duplicates(subset=[EDGE_ID]) (hop.py ~632) and the same pattern for node labels (~685/695) on every hop, so each hop pays a hash pass over everything matched so far: O(H × M) for H hops. The fast loop already keeps visited sets (_domain_union / _domain_diff, hop.py ~566-576) and only touches the new frontier.

Not a wrong answer (contracts pinned by the hop semantics and rediscovery suites); a cost class distinct from #2036's removed O(E) dedup. Fix shape: move the full loop to the same visited-set accounting and pin it by extending test_hop_scaling_pin.py to a 4-hop labeled shape (cost must stay a bounded multiple of the fast loop). Owner priority: after the 0.60 stacks land.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions