Skip to content

perf: optimize graph BFS traversal and reduce allocations - #3

Open
gandyhw wants to merge 1 commit into
mainfrom
refactor_graph
Open

perf: optimize graph BFS traversal and reduce allocations#3
gandyhw wants to merge 1 commit into
mainfrom
refactor_graph

Conversation

@gandyhw

@gandyhw gandyhw commented May 15, 2026

Copy link
Copy Markdown
Owner
  • Replace container/list with slice-based queue + head index to eliminate per-element list.Element heap allocations
  • Pre-allocate adjacency maps with len(G.Nodes) capacity to avoid rehash during BFS (was len(G.Edges) which caused massive over-allocation)
  • Change processEdges visited parameter from *map to map (idiomatic Go)
  • Extract 340-line mockGetTimeGraph() fixture to graph_mock_data.go (graph.go: 765 → 426 lines)
  • Add 17 unit tests covering NewGraph, GetNodeInfo, GetEdgeInfo, GraphToRows, addToBufMap, MultiHopFilter edge cases, and condition evaluation (4 functions 0% → 100% coverage)
  • Update sonic dependency for Go 1.26 compatibility

Benchmark (3-count, 10x benchtime):
Small graph (2w nodes, 2w edges): No condition: -3.0% latency, -6.8% memory With condition: -20.6% latency, -6.7% memory Large graph (2w nodes, 200w edges): No condition: -3.1% latency (7-run verified), -10.7% allocs With condition: -5.8% allocs Prop condition: -11.1% allocs

What problem does this PR solve?

Issue Number: close/fix/resolve/ref #xxx

What is changed and how it works?

Please describe how it works

How Has This Been Tested?

Please describe the tests that you ran to verify your changes. Provide instructions so we can reproduce. Please also list any relevant details for your test configuration

  • Test A
  • Test B
  • Test cases to be added
  • No code

Checklist:

  • My code follows the style guidelines of this project
  • I have performed a self-review of my own code
  • I have commented my code, particularly in hard-to-understand areas
  • I have made corresponding changes to the documentation
  • My changes generate no new warnings
  • I have added tests that prove my fix is effective or that my feature works
  • New and existing unit tests pass locally with my changes
  • Any dependent changes have been merged and published in downstream modules

- Replace container/list with slice-based queue + head index to
  eliminate per-element list.Element heap allocations
- Pre-allocate adjacency maps with len(G.Nodes) capacity to avoid
  rehash during BFS (was len(G.Edges) which caused massive over-allocation)
- Change processEdges visited parameter from *map to map (idiomatic Go)
- Extract 340-line mockGetTimeGraph() fixture to graph_mock_data.go
  (graph.go: 765 → 426 lines)
- Add 17 unit tests covering NewGraph, GetNodeInfo, GetEdgeInfo,
  GraphToRows, addToBufMap, MultiHopFilter edge cases, and condition
  evaluation (4 functions 0% → 100% coverage)
- Update sonic dependency for Go 1.26 compatibility

Benchmark (3-count, 10x benchtime):
  Small graph (2w nodes, 2w edges):
    No condition:  -3.0% latency,  -6.8% memory
    With condition: -20.6% latency, -6.7% memory
  Large graph (2w nodes, 200w edges):
    No condition:  -3.1% latency (7-run verified), -10.7% allocs
    With condition: -5.8% allocs
    Prop condition: -11.1% allocs

Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
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