JMH结果和算法复杂性的java解释

Question

我试图通过使用基准数据来证明算法的复杂性。我要测试的算法是二进制搜索算法（声明的复杂度为O(log n)），我想使用JMH库进行基准测试

以下是测试示例：

public class BinarySearchTest {

private static SearchAlgorithm binaryIterative = new BinarySearchIterative();
private static SearchAlgorithm binaryRecursive = new BinarySearchRecursive();

@Test
public void runBenchmarks() throws Exception {
    Options options = new OptionsBuilder()
            .include(this.getClass().getName() + ".*")
            .mode(Mode.Throughput)
            .forks(1)
            .threads(1)
            .warmupIterations(0)
            .measurementIterations(1)
            .shouldFailOnError(true)
            .shouldDoGC(true)
            .build();

    new Runner(options).run();
}

@Benchmark
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public void binarySearchIterativeBenchmark(ExecutionPlan plan) {

    //given
    int size = randomPositiveIntLessThan(plan.arraySize);
    int[] array = generateUninterrupted(0, size);
    int target = randomPositiveIntLessThan(size);

    //when
    var result = binaryIterative.find(array, 0, array.length, target);

    //then
    assertTrue(result != -1);
}

这是一个具有算法实现的类：

public class BinarySearchIterative implements SearchAlgorithm {

@Override
public int find(int[] array, int start, int end, int target) {

    if (end > array.length) {
        return -1;
    }

    int left = start;
    int right = end;

    while (left <= right) {
        int median = left + (right - left) / 2;
        if (array[median] == target) {
            return median;
        }
        if (array[median] > target) {
            right = median - 1;
        }
        if (array[median] < target) {
            left = median + 1;
        }
    }
    return -1;
}

我使用带有@State注释的类来获取数组的大小：

@State(Scope.Benchmark)
public class ExecutionPlan {
    @Param({"100000", "200000", "300000", "400000", "500000",
            "1000000", "2000000", "3000000", "4000000", "5000000",
           "10000000", "20000000", "30000000", "40000000", "50000000"})
    public int arraySize;

所以我有下一个结果：

BinarySearchTest.binarySearchIterativeBenchmark 100000 thrpt
31.602 ops/ms BinarySearchTest.binarySearchIterativeBenchmark 200000 thrpt 14.520 ops/ms BinarySearchTest.binarySearchIterativeBenchmark 300000 thrpt
9.004 ops/ms BinarySearchTest.binarySearchIterativeBenchmark 400000 thrpt 6.896 ops/ms BinarySearchTest.binarySearchIterativeBenchmark 500000 thrpt
5.333 ops/ms BinarySearchTest.binarySearchIterativeBenchmark 1000000 thrpt 2.304 ops/ms BinarySearchTest.binarySearchIterativeBenchmark 2000000 thrpt
0.790 ops/ms BinarySearchTest.binarySearchIterativeBenchmark 3000000 thrpt 0.451 ops/ms BinarySearchTest.binarySearchIterativeBenchmark 4000000 thrpt
0.330 ops/ms BinarySearchTest.binarySearchIterativeBenchmark 5000000 thrpt 0.232 ops/ms BinarySearchTest.binarySearchIterativeBenchmark 10000000 thrpt
0.135 ops/ms BinarySearchTest.binarySearchIterativeBenchmark 20000000 thrpt 0.061 ops/ms BinarySearchTest.binarySearchIterativeBenchmark 30000000 thrpt
0.039 ops/ms BinarySearchTest.binarySearchIterativeBenchmark 40000000 thrpt 0.033 ops/ms BinarySearchTest.binarySearchIterativeBenchmark 50000000 thrpt
0.025 ops/ms

但是如果我绘制图表得分/排列，我得到的不是log（n），而是1/x图表。如果我使用Mode.AverageTime，则图形相当x^2

这是我上面提供的数据图表，y[ms/ops]，x[arraysize]：

如何从JMH获取操作单元或调整测试

Answer 1

你在策划和比较错误的东西

因此每1ms有个操作ops_ms，这或多或少是测量时间t除以个操作m。对于大小为n的二进制搜索：

m = ~log2(n)

为了获得复杂性和/或正确的绘图，您需要绘制测量的时间t与大小n的关系，但是您正在绘制ops_ms与n

因此首先我们需要获得测量的时间t（top是单个操作的时间）：

t = m*top
m = log2(n)
ops_ms = 1/top
       
top=1/ops_ms
t = log2(n)*top
       
t = log2(n)/ops_ms

因此，您需要将t绘制为y轴，将n绘制为x轴。然而，正如你所看到的，这种测量方法是毫无价值的，因为你需要知道你测量的是什么才能得到m，甚至这只是一个近似值。。。更好/更准确的方法是直接使用测量的时间，因为你的ops/ms把一切都搞糟了

当我对这样的数据使用measuring complexity时：

const double l2=3.3219280948873623478703194294894;
double binsearch[]= // n[-],t[ms]
    {
      100000,l2*log(  100000.0)/31.602,
      200000,l2*log(  200000.0)/14.520,
      300000,l2*log(  300000.0)/ 9.004,
      400000,l2*log(  400000.0)/ 6.896,
      500000,l2*log(  500000.0)/ 5.333,
     1000000,l2*log( 1000000.0)/ 2.304,
     2000000,l2*log( 2000000.0)/ 0.790,
     3000000,l2*log( 3000000.0)/ 0.451,
     4000000,l2*log( 4000000.0)/ 0.330,
     5000000,l2*log( 5000000.0)/ 0.232,
    10000000,l2*log(10000000.0)/ 0.135,
    20000000,l2*log(20000000.0)/ 0.061,
    30000000,l2*log(30000000.0)/ 0.039,
    40000000,l2*log(40000000.0)/ 0.033,
    50000000,l2*log(50000000.0)/ 0.025,
      0,0.000
    };

它导致了这样的结果：

binsearch O(n.log^4(n)) error = 0.398668

这仍然是太远的预期log2(n)但比其他选项更接近。这意味着额外的东西是平衡你的ops/ms价值观，这是我所期望的。。。你知道你有JRE体系结构，还有主机体系结构，它把测量与缓存、预取管道等混为一谈，而且最重要的是你的JMH可能也会做一些事情（比如为了某种目的平均或“增强”ops/ms值）

如果ops_ms实际上是binsearch/ms，正如其中一条评论所建议的那么时间是由1/ops_ms计算的，这可能是真的，因为结果稍微接近O(log(n))，但仍然太远了：

//   time              O(n)          uncertainity
log2(n)/ops_ms    O(n.log^4(n))    error = 0.398668 // m ops / ms
    (n)/ops_ms    O(n^2.log^3(n))  error = 0.398668 // n ops / ms
    (1)/ops_ms    O(n.log^3(n))    error = 0.398668 // binsearch / ms

所以我的建议是找到一种直接测量时间的方法，而不是使用ops/ms

<强> [Eddi1]我在C++中实现的

int find(int *array,int size,int start,int end,int target)
    {
    if (end >= size) return -1;
    int left = start;
    int right = end;
    while (left <= right)
        {
        int median = left + (right - left) / 2;
        if (array[median] == target) return median;
        if (array[median] > target)  right = median - 1;
        if (array[median] < target)  left = median + 1;
        }
    return -1;
    }

用法：

const int n=50000000;
double binsearch[]= // n[-],t[ms]
    {
      100000,1.0,
      200000,1.0,
      300000,1.0,
      400000,1.0,
      500000,1.0,
     1000000,1.0,
     2000000,1.0,
     3000000,1.0,
     4000000,1.0,
     5000000,1.0,
    10000000,1.0,
    20000000,1.0,
    30000000,1.0,
    40000000,1.0,
    50000000,1.0,
      0,0.000
    };
int *dat=new int[n],i,s;
Randomize();
for (s=0,i=0;i<n;i++)
    {
    s+=1+Random(10);
    dat[i]=s;
    }
for (i=0;binsearch[i];)
    {
    s=binsearch[i]; i++;
    tbeg(); // star measuring of time
    find(dat,s,0,s-1,dat[Random(s)]);
    tend(); // end measuring of time
    binsearch[i]=performance_tms; i++; // store measured time
    }
delete[] dat;

这将生成PRNG int升序数组并测试你的find。我打赌你的数据并不像我在评论中描述的那样是随机的。当我应用此方法时，结果与预期一致：

binsearch O(log(n)) error = 0.528393

因此，要么你的数组和/或目标选择不正确，要么你的时间度量包括它的生成，这会把事情搞砸

如果我看对了，你的数组生成要么{}要么{}与我的{}相反，因此如果它被包括在测量中，它将主导{}。。。结果是：

(1)/ops_ms    O(n.log^3(n))    error = 0.398668 // binsearch / ms

表明是这样的并且使用的生成大约是O(n.log(n))功率差异仅仅是由于使用的计算架构和时间测量不精确

Answer 2

我想我已经找到了这种行为的原因。以下是我的修复方法：

1. 将基准测试模式更改为Mode.AverageTime，因此现在基准测试输出平均时间，单位为ms/op
2. 切换到纳秒@OutputTimeUnit(TimeUnit.NANOSECONDS)
3. 在基准测试中添加了1次预热迭代
4. 将数组生成从测试移动到ExecutionPlan类，并更改了生成策略：现在生成随机整数值，而不是连续整数数组（这要感谢@Spektre）
5. 根据doc，将@Setup级别更改为Level.Trial。使用Level.Invocation有一些合理的警告
6. 增加了更多的分数（现在是30分）

以下是用于迭代二进制搜索的数据：

并用趋势线绘制图形：

有些点有很大的误差，但现在的趋势是O(log n)。我认为可以使用更多的迭代、预热和分叉来调整基准以获得更高的精度