Performance PCB use of BOARD::GetMaxClearanceValue results in O(N^2) behaviour
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