Optimize dummy lookup of downsampling (slow on large samples)

[nagimov]

This dummy lookup loops through the entire array (~30,000 samples per second of execution) once per value of downsampled array: https://github.com/nagimov/adxl345spi/blob/master/adxl345spi.c#L263

pi@raspberrypi:~/adxl345spi $ time sudo ./adxl345spi -f 3200 -t 5 -s out.csv
Reading 16000 samples in 5.0 seconds with sampling rate 3200.0 Hz...
4.00 seconds left...
3.00 seconds left...
2.00 seconds left...
1.00 seconds left...
0.00 seconds left...
Writing to the output file...
Done

real    2m23.326s
user    2m23.150s
sys     0m0.630s

[nagimov]

partly resolved by #2, still has room for imrovement

[dmbutyugin]

BTW, the commit f0c59b0ef31354c82d56676e68f6a63f8eb501c2 has a small bug: this 'else' branch

                    else {
                        if (tError > tErrorPrev) {  // if the error starts growing
                            break;                  // break the loop since the minimal error point passed
                        }
                    }

does not update tError and tErrorPrev, so the condition tError > tErrorPrev can never be achieved, and break does not happen. Which makes it still O(N^2), 2x faster than the previous version. The fix can be to remove that extra if condition entirely (and possibly change the inequality in the first check to if (fabs(rt[j] - tCurrent) <= tError)).

[nagimov]

@dmbutyugin thanks! Is that what you mean? https://github.com/nagimov/adxl345spi/commit/ad9a889536b7a04e1fdf2ddcfcc75791b43a68a8

[dmbutyugin]

Yes. That looks about right, right?

[nagimov]

Yes my mental gcc didn't raise any flags. I'll test this properly when I get my pi in the mail Thanks!

[nagimov]

Runtime is reduced from a minute to 5.5 seconds, i.e. downsampling now takes 0.5s instead of 55s :smile: Thanks again @dmbutyugin :+1:

Tested on 2020-08-20-raspios-buster-armhf-lite.

Before the fix:

pi@raspberrypi:~/adxl345spi $ time sudo adxl345spi -f 3200 -t 5 -s out.csv
Reading 16000 samples in 5.0 seconds with sampling rate 3200.0 Hz...
4.00 seconds left...
3.00 seconds left...
2.00 seconds left...
1.00 seconds left...
0.00 seconds left...
Writing to the output file...
Done

real    0m59.418s
user    0m59.229s
sys 0m0.515s

After the fix:

pi@raspberrypi:~/adxl345spi $ time sudo adxl345spi -f 3200 -t 5 -s out.csv
Reading 16000 samples in 5.0 seconds with sampling rate 3200.0 Hz...
4.00 seconds left...
3.00 seconds left...
2.00 seconds left...
1.00 seconds left...
0.00 seconds left...
Writing to the output file...
Done

real    0m5.565s
user    0m5.303s
sys 0m0.554s