Mentions légales du service

Skip to content

Benchmarks: make `_nearest_benchmark_ipc` efficient

Théophile BASTIAN requested to merge tbastian/efficient_nearest_bench_ipc into master

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) )

Merge request reports