Skip to content

v1.6.0 — scalability: O(1) blocked-set + heap priority queue

Choose a tag to compare

View all tags
@ultramcu ultramcu released this 24 May 08:23
· 9 commits to main since this release
v1.6.0
1823190

Performance release for larger graphs. Public API and search results unchanged.

  • O(1) blocked-set: the blocked-vertex set is now a map, so the per-edge "is blocked?" check is constant time. Searches with many blocked vertices scale much better (10,000-vertex grid, ~10% blocked: ~43 ms → ~6 ms).
  • Binary-heap priority queue: O(log n) push/pop that reuses its backing array, replacing the O(n) sorted slice whose dequeue reslicing caused heavy reallocation. Allocation per search stays flat as the graph grows (10,000 vertices: ~1.5 MB → ~64 KB), keeping GC pauses small. Equal-weight entries still dequeue in insertion order.

Trade-off: very small graphs (tens of vertices) are marginally slower in raw CPU but allocate less. See CHANGELOG.md.

Assets 2
Loading