System::CalculateRank() is slow #386
Description
System information
SolveSpace version: master, 9d1601e
Operating system: Debian stable
In a file I'm working on (I'll attach it tomorrow when I'll have more proofs), adding a 'same length' constraint between the top of the 1st square of 1st line and the top of the 1st square of 2nd line is extremely slow (on my low end computer).
Using LD_PRELOAD, I've nailed the problem to the method in the title, and implemented some optimisations.
I don't have enough tests to have reliable numbers, but the number of samples gperftools took moved from 47.3% of 3009 to 36.8% of 827 (those numbers make it obvious to me that I need more numbers).
I am opening this ticket in advance to ask for hints about how to automate the runs, which would provide me more reliable numbers, and to provide a 1st patch of the optimized code I have so far (too lazy to do a usual fork/clone/create branch/commit/merge/push/pull request, for just 10 lines of code):
diff --git a/src/system.cpp b/src/system.cpp
index e90611a..24d9ebe 100644
--- a/src/system.cpp
+++ b/src/system.cpp
@@ -146,22 +146,31 @@ int System::CalculateRank() {
for(i = 0; i < mat.m; i++) {
// Subtract off this row's component in the direction of any
// previous rows
+ double* curr_mat_num;
+ double* prev_mat_num;
+ const auto num_mat = mat.n;
for(iprev = 0; iprev < i; iprev++) {
if(rowMag[iprev] <= tol) continue; // ignore zero rows
double dot = 0;
- for(j = 0; j < mat.n; j++) {
- dot += (mat.A.num[iprev][j]) * (mat.A.num[i][j]);
+ prev_mat_num = mat.A.num[iprev];
+ curr_mat_num = mat.A.num[i];
+ for(j = 0; j < num_mat; ++j, ++curr_mat_num, ++prev_mat_num) {
+ dot += (*prev_mat_num) * (*curr_mat_num);
}
- for(j = 0; j < mat.n; j++) {
- mat.A.num[i][j] -= (dot/rowMag[iprev])*mat.A.num[iprev][j];
+ double tmp = dot/rowMag[iprev];
+ prev_mat_num = mat.A.num[iprev];
+ curr_mat_num = mat.A.num[i];
+ for(j = 0; j < num_mat; ++j, ++curr_mat_num, ++prev_mat_num) {
+ (*curr_mat_num) -= tmp*(*prev_mat_num);
}
}
// Our row is now normal to all previous rows; calculate the
// magnitude of what's left
double mag = 0;
- for(j = 0; j < mat.n; j++) {
- mag += (mat.A.num[i][j]) * (mat.A.num[i][j]);
+ curr_mat_num = mat.A.num[i];
+ for(j = 0; j < num_mat; j++, ++curr_mat_num) {
+ mag += pow( *curr_mat_num, 2 );
}
if(mag > tol) {
rank++;If there are other things to improve, feel free to say so.