Improve CMedianFilter algorithm #25221
Conversation
This will allow us to measure any potential performance improvement in the 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`
|
Thanks for your contribution. However, |
|
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers. ConflictsReviewers, this pull request conflicts with the following ones:
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. |
|
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. |
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.
Let's give it some time. |
|
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. |
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.