Skip to content

perf(erd): router rebuilds the obstacle grid and re-routes every edge on each drag move #1168

Description

@ZhuchkaTriplesix

Problem

While a card is dragged, every pointer move calls ErdRouter.route(schema, layout) (erd_view.dart: _dragMove → _setLayout), which re-routes every edge from scratch:

  • _Grid rebuilds _free by testing every grid node against every card: O(nodes × tables), allocating an Offset per test.
  • One A* per relation, with cost / prev / closed in HashMap<int, …> / Set<int> (boxing, GC pressure).
  • _segmentFree tests the segment midpoint against all cards on every expansion: O(expansions × 4 × tables × relations) in total.

By estimate (not measured), ~100 tables / ~150 relations cost tens to hundreds of ms per pointer move against an 8.3 ms frame. #1146 notes that large schemas "may feel slow".

Scope

  • Rasterize obstacles: for each inflated card rect, mark the index ranges it covers in xs / ys (binary search) into a node bitmap and two edge bitmaps (horizontal, vertical). _free and _segmentFree become O(1) lookups.
  • Flat search state: Float64List cost, Int32List prev, generation stamps instead of clearing, reused across the relations of one route() call.
  • Incremental re-route on drag: only edges incident to the moved table and edges whose segments intersect its old or new rect; nudging re-run on the affected grid lines.
  • One re-route per frame: coalesce pointer moves (schedule on the next frame); optional: simple dog-leg for incident edges while dragging, full route on drag end.
  • A micro-benchmark for route() on a generated schema (100 / 300 tables) in benchmark/, added to .github/workflows/benchmark.yml.

Acceptance

  • Routing output unchanged for the existing tests in test/features/erd/erd_test.dart.
  • Benchmark: full route() for 100 tables / 150 relations well under one frame; drag step (incremental) under 2 ms.

Activity

  1. added
    frontendTheme parser epic label: frontend
    performanceTheme parser epic label: performance
    P2Medium priority / Parity & Refactoring
    on Oct 8, 2026
  2. added a commit that references this issue on Oct 9, 2026
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

    P2Medium priority / Parity & RefactoringfrontendTheme parser epic label: frontendperformanceTheme parser epic label: performance

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions