Skip to content

Performance PCB use of BOARD::GetMaxClearanceValue results in O(N^2) behaviour

Yon Uriarte requested to merge kicad3053404/kicad:pcb-n2 into master

Multiple instances where BOARD::GetMaxClearanceValue is called for each item in the board graphical model. BOARD::GetMaxClearanceValue itself will iterate over all items in the board logical model resulting in O(N^2) runtime.

Proposed is a scoped object that will cache BOARD::GetMaxClearanceValue's result and revert BOARD to it's normal behavior on scope exit, like std::scoped_lock.

This has been applied on multiple sites in the graphics system. Notably (the new, virtual) PCB_VIEW::UpdateItems will always trigger a caching, as VIEW::UpdateItems might do a full RTree rebuild, which is O(N^2) as each BBox calculation calls GetMaxClearanceValue.

It's important that caching won't happen over a logical BOARD model change, only over graphics's use of BOARD. I'm not familiar with the code and can't verify this is the case.

Not all sites where this might be useful are patched, as I didn't test the whole UI.

Some timings:

open file: PCB_BASE_EDIT_FRAME::SetBoard, line GetCanvas()->DisplayBoard( aBoard, aReporter );

From 73897ms 74445ms to 2518ms 2820ms 2744ms 2501ms

select all then move selection: EDIT_TOOL::doMoveSelection, loop for( EDA_ITEM* item : sel_items )

From 17771ms 18188ms 18407ms to 11ms 12ms 10ms

TODO: Undo in PCB_BASE_EDIT_FRAME::PutDataInPreviousState needs patching in PCB_VIEW::Add or better up the stack. I'd just drop a BOARD_UNLOCKER around the relevant loop but there are changes to the board logical model. I don't know if the max clearance value could be changing somehow.

Notes:

  • BOARD_UNLOCKER will always trigger a calculation.
  • No idea about thread safety.

TODO:

  • Remove profiling
  • patch Undo

overload_connected-2024-02-24_013508.zip

Edited by Yon Uriarte

Merge request reports