Improve CMedianFilter algorithm #25221

pull antoinedesbois wants to merge 2 commits into bitcoin:master from antoinedesbois:timedata_bench changing 6 files +209 −32

antoinedesbois commented at 5:15 AM on May 26, 2022: none
1. Add benchmarks for median computation.
2. Improve median computation algorithm 2.1. Write unit tests to ensure new median computation has the same behavior as the previous implementation 2.2. Ensure benchmarks are improved
The new median algorithm takes its |max_size| as a template parameter and relies on a ring buffer to keep track of the current values the median needs to be computed on. Instead of sorting the values from scratch on every new insertion, the new algorithm finds where the new value needs to be inserted and where the now outdated value needs to be removed. It then rotates the elements of the vector to perform the sorted insertion.

The test |util_MedianFilter_rand| proves that the new behavior is the same as doing the sorting on every iteration.

Add benchmarks for CMedianFilter

This will allow us to measure any potential performance improvement in
the CMedianFilter algorithm

5e82ba19ce

Improve CMedianFilter algorithm

Instead of sorting on every iteration, leverage the already sorted array
from the previous iteration and perform a memory shift to insert the new
element at the right location.

Add a new unit test to confirm the algorithm returns the same result as
if we were to sort at every iteration.

Benchmarks on my Intel x86.
Before:

| ns/op        |   op/s    | err% | total | benchmark
_______________________________________________________________________
| 63,212.50    | 15,819.66 | 0.3% | 0.01 | `ComputeMedian10_1000`
| 208,300.00   | 4,800.77  | 0.2% | 0.01 | `ComputeMedian20_1000`
| 4,531,600.00 | 220.67    | 0.2% | 0.05 | `ComputeMedian256_1000`

After:

| ns/op     |   op/s    | err% | total | benchmark
_______________________________________________________________________
| 17,671.93 | 56,586.92 | 1.0% | 0.01 | `ComputeMedian10_1000`
| 23,482.05 | 42,585.72 | 0.3% | 0.01 | `ComputeMedian20_1000`
| 55,605.56 | 17,983.81 | 0.2% | 0.01 | `ComputeMedian256_1000`

1c2aaed7d1

laanwj commented at 5:38 AM on May 26, 2022: member

Thanks for your contribution. However, CMedianFilter is only used for timedata, for a very limited number of values. Also, timedata is part of P2P time adjustment which is in the process of being removed on the longer term. Adding tests is nice but i'm not sure about changing the algorithm at this point.
Raulnori77 approved
laanwj added the label Utils/log/libs on May 26, 2022
DrahtBot commented at 8:53 AM on May 26, 2022: contributor


The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.



Conflicts

Reviewers, this pull request conflicts with the following ones:
- #24697 (refactor address relay time by MarcoFalke)
- #24606 (Change -maxtimeadjustment default from 70 minutes to 0 by jonatack)
If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.
antoinedesbois commented at 4:32 PM on May 26, 2022: none

Your call, I do not know what the timeline looks like for the removal of the time adjustment. If there is no other use case for this algorithm, I am fine with dropping this PR. We can merge the benchmarks and/or tests since those have no effect on production software, let me know if you think that'd be useful.
fanquake commented at 11:53 AM on May 27, 2022: member

Your call, I do not know what the timeline looks like for the removal of the time adjustment.

One of the related PRs is #24662, and some semi-related refactoring is in #24697. I agree with @laanwj that refactoring timedata-only related code at this point is likely not worthwhile.
laanwj commented at 7:34 PM on May 27, 2022: member

Your call, I do not know what the timeline looks like for the removal of the time adjustmen

To be honest, I don't know either, and this isn't a NACK, i just think review time can be spend more productively. So will leave it up to other people.

We can merge the benchmarks and/or tests since those have no effect on production software, let me know if you think that'd be useful.

Let's give it some time.
fanquake commented at 9:37 AM on July 27, 2022: member

Thanks for the contribution @antoinedesbois, however I'm going to close this PR for now. Given it's likely the refactors in #24662 will go ahead. If that doesn't happen, this PR could be re-opened later on.
fanquake closed this on Jul 27, 2022
bitcoin locked this on Jul 27, 2023

Contributors

Labels

Improve CMedianFilter algorithm #25221

Conflicts