Improving resistor calculator (E-series) performance
129 views
Skip to first unread message
bebidek
Jul 25, 2023, 2:15:10 PM7/25/23
to KiCad Developers
I would like to improve the performance of the "E-series" tool in the PCB calculator.
At the moment, the solution implemented in the code is basically a brute-force algorithm, reaching O(n^4) time complexity (where n is the number of basic resistance values).
It can be easily improved to O(n^2 * log(n)) using a binary search approach, keeping current memory complexity of O(n^2).
The draft of the new algorithm is as follows ('X' means "+ or |", 2COMB means "some combination of 2 resistors"):
1. Prepare an array of all combinations of two resistors (that is, all possible values of 2COMB) and sort it
2. For 2-solutions, use single binary search in our array to find the two closest values (one less and one greater)
3. For 3-solutions, all possible variants are of the form: "R1 X 2COMB". Thus, we iterate over all values of R1, for each value calculate "perfect" values of that combination in parenthesis and look for it (bin-search) in the array.
4. For 4-solutions, it is either "(2COMB X 2COMB)", "R1 + (R2 | 2COMB)" or "R1 | (R2 + 2COMB)". The first one can be solved by iterating over 2COMB array, the second and third one by iterating over pairs (R1, R2).
Switching to this algorithm should make adding higher E-series possible (some people in other threads have suggested this, but performance issues made it impractical).
I believe that this algorithm is not too far from the most optimal possible. The problem of finding "series only" combinations is basically a 3-SUM problem for which we believe there is no O(n^a) algorithm for a<2 (the "3-SUM hypothesis"). It appears that finding general solutions should be at least that hard.
Additional benefit of that algorithm is that it correctly considers all possible combinations of up to 4 resistors, unlike the current one which cannot produce results of form R1 + (R2 | R3 | R4).
I would like to implement that algorithm if approved. It would involve rewriting RES_EQUIV_CALC class almost from scratch (this would also fix some code quality issues in the current implementation).
At the moment, the solution implemented in the code is basically a brute-force algorithm, reaching O(n^4) time complexity (where n is the number of basic resistance values).
It can be easily improved to O(n^2 * log(n)) using a binary search approach, keeping current memory complexity of O(n^2).
The draft of the new algorithm is as follows ('X' means "+ or |", 2COMB means "some combination of 2 resistors"):
1. Prepare an array of all combinations of two resistors (that is, all possible values of 2COMB) and sort it
2. For 2-solutions, use single binary search in our array to find the two closest values (one less and one greater)
3. For 3-solutions, all possible variants are of the form: "R1 X 2COMB". Thus, we iterate over all values of R1, for each value calculate "perfect" values of that combination in parenthesis and look for it (bin-search) in the array.
4. For 4-solutions, it is either "(2COMB X 2COMB)", "R1 + (R2 | 2COMB)" or "R1 | (R2 + 2COMB)". The first one can be solved by iterating over 2COMB array, the second and third one by iterating over pairs (R1, R2).
Switching to this algorithm should make adding higher E-series possible (some people in other threads have suggested this, but performance issues made it impractical).
I believe that this algorithm is not too far from the most optimal possible. The problem of finding "series only" combinations is basically a 3-SUM problem for which we believe there is no O(n^a) algorithm for a<2 (the "3-SUM hypothesis"). It appears that finding general solutions should be at least that hard.
Additional benefit of that algorithm is that it correctly considers all possible combinations of up to 4 resistors, unlike the current one which cannot produce results of form R1 + (R2 | R3 | R4).
I would like to implement that algorithm if approved. It would involve rewriting RES_EQUIV_CALC class almost from scratch (this would also fix some code quality issues in the current implementation).
Seth Hillbrand
Jul 25, 2023, 3:55:14 PM7/25/23
to dev...@kicad.org
You will probably gain by pre-computing 2COMB and storing the values in the source. However, this would be quite large above E96 and would not be realistic to store. You could pre-compute in source to reduce the time after the first calculation.
I'm skeptical of the gains to be made by this approach. Because 'n' is never very large, your greatest time sink is going to be in the prefactor. While the work may be of the order 'n', the multiplicative prefactor will dominate.
For that reason, if you are interested in improving the algorithm, I would look at early escape metrics in the loops. We end up checking many value combinations that we do not need and some smarter heuristics here will have outsized impact.
That said, if you have your heart set on the approach you laid out, I don't see the harm in testing it.
Seth
--
You received this message because you are subscribed to the Google Groups "KiCad Developers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to devlist+u...@kicad.org.
To view this discussion on the web visit https://groups.google.com/a/kicad.org/d/msgid/devlist/f204c4cf-b90c-460c-a59d-7f593cab37f5n%40kicad.org.
beb...@gmail.com
Aug 3, 2023, 11:28:33 AM8/3/23
to KiCad Developers, se...@kipro-pcb.com
I implemented that algorithm (without any pre-computation in source) and I'm quite optimistic. Benchmark results (on mobile i7-3610QM) are:
- 4R E12 - about 3ms
- 4R E24 - about 12ms
- 4R E96 - about 150ms
- 4R E192 - about 500ms
My fork with the implementation is at https://gitlab.com/bwaclawik/kicad/-/tree/new-resistor-substitution-algorithm
- 4R E12 - about 3ms
- 4R E24 - about 12ms
- 4R E96 - about 150ms
- 4R E192 - about 500ms
My fork with the implementation is at https://gitlab.com/bwaclawik/kicad/-/tree/new-resistor-substitution-algorithm
Seth Hillbrand
Aug 3, 2023, 3:43:05 PM8/3/23
to beb...@gmail.com, KiCad Developers
Hello Bartek-
I am happy to have been wrong here. Your changes look to be very promising.
I'd recommend adding them as a MR to the KiCad source code and we can do a full review.
Seth
JV
Aug 3, 2023, 4:54:37 PM8/3/23
to beb...@gmail.com, dev...@kicad.org
On 03.08.23 17:28, beb...@gmail.com wrote:
> I implemented that algorithm (without any pre-computation in source) and
> I'm quite optimistic. Benchmark results (on mobile i7-3610QM) are:
> - 4R E12 - about 3ms
> - 4R E24 - about 12ms
> - 4R E96 - about 150ms
> - 4R E192 - about 500ms
Obviously PC HW improved as this is much faster to what I tested a few
> I implemented that algorithm (without any pre-computation in source) and
> I'm quite optimistic. Benchmark results (on mobile i7-3610QM) are:
> - 4R E12 - about 3ms
> - 4R E24 - about 12ms
> - 4R E96 - about 150ms
> - 4R E192 - about 500ms
years ago. E24 was already prepared and I failed there with a progress
bar. The screen was only updated after calculation finished.
Therefore I dropped E24 and above. If you take the practical component
tolarances in account, there is hardly any use for further values
between E96.
Best
Jan
Reply all
Reply to author
Forward
0 new messages