Benchmarks: make `_nearest_benchmark_ipc` efficient
Unless I'm mistaken, this algorithm does exactly the same thing as the old _nearest_benchmark_ipc
, but is in worst case linear, and in most cases O(1)
. It also considers over-approximating (and not only under-approximating).
If I'm correct, we want to solve the following problem:
Let M be a measure, in number of cycles (measure
in the code).
Let I be a set of instructions, with repetitions (x_i).
Let P ∈ [1, MAX_PRECISION] \cap ℕ
We want to find the value of Σ_i λ_i (x_i/P) such that abs( Σ_i λ_i (x_i/P) - M ) is minimal, with λ_i positive integers.
We propose the following solution:
- assume x_i is sorted in descending order, and further assume that the repetitions in the list (x_i) are stripped (we can just sum the corresponding λ_i). Then, λ_i = ceil( (M - Σ_j<i λ_j x_j/P) / (x_i/P) )