Assertion failed on BigO simple linear complexity

[JoostvanPinxten]

I'm trying to benchmark some algorihtms, among one of which is a graph creation algorihtm which I know has linear execution time. The complexity example BM_StringCompare does report back the coefficient of the largest component though.

BENCHMARK(BM_graph)->RangeMultiplier(2)->Range(1<<0, 1<<12)->Complexity(benchmark::oN)->Unit(benchmark::kMicrosecond); shows the right benchmarks, but it fails to determine the BigO notation, although I know the equation is roughly 29 N - 88. Could the following issue be related to the negative intercept?

ComputeBigO: Check(run.complexity_n) > (0)' failed. Did you forget to call SetComplexityN?`

Benchmark              Time           CPU Iterations
----------------------------------------------------
BM_graph/1            12 us         12 us      64102
BM_graph/2            36 us         36 us      19509
BM_graph/4            88 us         88 us       7479
BM_graph/8           196 us        192 us       3739
BM_graph/16          419 us        424 us       1547
BM_graph/32          881 us        876 us        748
BM_graph/64         1778 us       1752 us        374
BM_graph/128        3769 us       3760 us        195
BM_graph/256        7289 us       7107 us         90
BM_graph/512       14461 us      14664 us         50
BM_graph/1024      29002 us      28364 us         22
BM_graph/2k        59003 us      58146 us         11

[dmah42]

Is it possible to share the code for BM_graph?

[JoostvanPinxten]

The example that I cooked up is the following:

#include <include/benchmark/benchmark.h>
#include <memory>

using vertex_descriptor = long long;

struct Item {
    vertex_descriptor id1, id2;
};

struct Vertex {
    unsigned int id;
    Item item;
    Vertex(int id, Item item) : id(id), item(item) {
    }
};

static void BM_graph_minimal(benchmark::State& state) {
    while (state.KeepRunning()) {
        vertex_descriptor lastId = 0;
        std::vector<std::shared_ptr<Vertex>> vertices;
        for(int i = 0; i < state.range(0); i++) {

            vertex_descriptor id = lastId++;
            std::shared_ptr<Vertex> v = std::make_shared<Vertex>(id, Item{1,1});
            vertices.push_back(v);
        }
    }
}
BENCHMARK(BM_graph_minimal)->RangeMultiplier(2)->Range(1<<0, 1<<12)->Complexity();

BENCHMARK_MAIN()

The ID part is not necessary, and the internal Item is also not necessary to reproduce the issue on my machine:

struct Vertex {
    unsigned int id;
};

static void BM_graph_minimal(benchmark::State& state) {
    while (state.KeepRunning()) {
        std::vector<std::shared_ptr<Vertex>> vertices;
        for(int i = 0; i < state.range(0); i++) {

            std::shared_ptr<Vertex> v = std::make_shared<Vertex>();
            vertices.push_back(v);
        }
    }
}

Note: I do get the warning: ***WARNING*** Library was built as DEBUG. Timings may be affected. Could be due to not omitting the frame-pointer?

[dmah42]

From the original message: "Did you forget to call SetComplexityN?"

I don't see a call to that in your example.

[JoostvanPinxten]

Wow, I completely missed that. Might be worth pointing out that for some unknown reason I was expecting that call to be added (implicitly) to: BENCHMARK(BM_graph_minimal)->RangeMultiplier(2)->Range(1<<0, 1<<12)->Complexity();.

I expected the first element in the state Range to default to N actually, and wasn't looking for the call inside the benchmark itself.