kicad-developers team mailing list archive

[John Beard <john.j.beard@xxxxxxxxx>]

Hi Frank,

I've got a very rough outline of the cost of courtyard calculations.
The timings are for "n" modules in various proportions of rectangular
and rounded rectangles.

The modules are each a single courtyard outline (no other features).
All are 1mm square and the round radius is 0.25mm. All modules on the
same side (front). Times in ms. Naturally, times will vary based on
the awesomeness of your computer!

  N       100%          75%       50%             0%
  --------------------------------------------------
   1        0.03        0.7        0.08         0.08
  10        1.0         1.2        1.3          1.5
 100       82          97        110          134
1000     8179        9642      11141        13415

This shows that this DRC check is quadratic in number of modules -
every 10-fold increase in the module count is a 100-fold time
increase. This is consistent with the DRC being a linear loop in N,
calling a function that takes linearly more time each iteration (as we
add to the Clipper polygon).

Notably, having rounded corners applies only a constant time factor to
the check, roughly proportional to the proportion of rounded modules.
This is smaller effect than I expected: even if 25% of all modules
have 4 rounded corners, this is only <25% slowdown at 1000 modules and
only about 50% slowdown if every module on the board is rounded. So
there is an effect, but it's not catastrophic.

The bigger issue here, I feel, is the generally slow nature of the
check which means the quadratic blow-up happens at a few hundred
modules, well within the realms of possibility for a larger board. The
current algorithm is ill-suited to parallelisation as it maintains
significant global state.

Cheers,

John