basics.bench.cpp

Go to the documentation of this file.

 
#include "barretenberg/commitment_schemes/commitment_key.hpp"
#include "barretenberg/common/op_count.hpp"
#include "barretenberg/common/thread.hpp"
#include "barretenberg/ecc/curves/bn254/bn254.hpp"
#include "barretenberg/numeric/random/engine.hpp"
#include "barretenberg/polynomials/polynomial.hpp"
#include "barretenberg/srs/global_crs.hpp"
#include <benchmark/benchmark.h>
 
using namespace benchmark;
using namespace bb;
namespace {
using Curve = curve::BN254;
using Fr = Curve::ScalarField;
#define MAX_REPETITION_LOG 12
 
void parallel_for_field_element_addition(State& state)
{
    numeric::RNG& engine = numeric::get_debug_randomness();
    size_t num_cpus = get_num_cpus();
    std::vector<std::vector<Fr>> copy_vector(num_cpus);
    for (size_t i = 0; i < num_cpus; i++) {
        for (size_t j = 0; j < 2; j++) {
            copy_vector[i].emplace_back(Fr::random_element(&engine));
            copy_vector[i].emplace_back(Fr::random_element(&engine));
        }
    }
    for (auto _ : state) {
        state.PauseTiming();
        size_t num_external_cycles = 1 << static_cast<size_t>(state.range(0));
        size_t num_internal_cycles = 1 << (MAX_REPETITION_LOG - static_cast<size_t>(state.range(0)));
        state.ResumeTiming();
        for (size_t i = 0; i < num_external_cycles; i++) {
            parallel_for(num_cpus, [num_internal_cycles, &copy_vector](size_t index) {
                for (size_t i = 0; i < num_internal_cycles; i++) {
                    copy_vector[index][i & 1] += copy_vector[index][1 - (i & 1)];
                }
            });
        }
    }
}
 
void ff_addition(State& state)
{
    numeric::RNG& engine = numeric::get_debug_randomness();
    std::vector<Fr> copy_vector(2);
    for (size_t j = 0; j < 2; j++) {
        copy_vector.emplace_back(Fr::random_element(&engine));
        copy_vector.emplace_back(Fr::random_element(&engine));
    }
 
    for (auto _ : state) {
        state.PauseTiming();
        size_t num_cycles = 1 << static_cast<size_t>(state.range(0));
        state.ResumeTiming();
        for (size_t i = 0; i < num_cycles; i++) {
            copy_vector[i & 1] += copy_vector[1 - (i & 1)];
        }
    }
}
 
void ff_multiplication(State& state)
{
    numeric::RNG& engine = numeric::get_debug_randomness();
    std::vector<Fr> copy_vector(2);
    for (size_t j = 0; j < 2; j++) {
        copy_vector.emplace_back(Fr::random_element(&engine));
        copy_vector.emplace_back(Fr::random_element(&engine));
    }
 
    for (auto _ : state) {
        state.PauseTiming();
        size_t num_cycles = 1 << static_cast<size_t>(state.range(0));
        state.ResumeTiming();
        for (size_t i = 0; i < num_cycles; i++) {
            copy_vector[i & 1] *= copy_vector[1 - (i & 1)];
        }
    }
}
 
void ff_sqr(State& state)
{
    numeric::RNG& engine = numeric::get_debug_randomness();
    std::vector<Fr> copy_vector(2);
    for (size_t j = 0; j < 2; j++) {
        copy_vector.emplace_back(Fr::random_element(&engine));
        copy_vector.emplace_back(Fr::random_element(&engine));
    }
 
    for (auto _ : state) {
        state.PauseTiming();
        size_t num_cycles = 1 << static_cast<size_t>(state.range(0));
        state.ResumeTiming();
        for (size_t i = 0; i < num_cycles; i++) {
            copy_vector[0] = copy_vector[0].sqr();
        }
    }
}
 
void ff_invert(State& state)
{
    numeric::RNG& engine = numeric::get_debug_randomness();
    auto element = Fr::random_element(&engine);
 
    for (auto _ : state) {
        state.PauseTiming();
        size_t num_cycles = 1 << static_cast<size_t>(state.range(0));
        state.ResumeTiming();
        for (size_t i = 0; i < num_cycles; i++) {
            element = (element + Fr::one()).invert();
        }
    }
}
 
void ff_to_montgomery(State& state)
{
    numeric::RNG& engine = numeric::get_debug_randomness();
    auto element = Fr::random_element(&engine);
 
    for (auto _ : state) {
        state.PauseTiming();
        size_t num_cycles = 1 << static_cast<size_t>(state.range(0));
        state.ResumeTiming();
        for (size_t i = 0; i < num_cycles; i++) {
            element = element.to_montgomery_form();
        }
    }
}
void ff_from_montgomery(State& state)
{
    numeric::RNG& engine = numeric::get_debug_randomness();
    auto element = Fr::random_element(&engine);
 
    for (auto _ : state) {
        state.PauseTiming();
        size_t num_cycles = 1 << static_cast<size_t>(state.range(0));
        state.ResumeTiming();
        for (size_t i = 0; i < num_cycles; i++) {
            element = element.from_montgomery_form();
        }
    }
}
 
void ff_reduce(State& state)
{
    numeric::RNG& engine = numeric::get_debug_randomness();
    auto element = Fr::random_element(&engine);
 
    for (auto _ : state) {
        state.PauseTiming();
        size_t num_cycles = 1 << static_cast<size_t>(state.range(0));
        state.ResumeTiming();
        for (size_t i = 0; i < num_cycles; i++) {
            element = (element + element).reduce_once();
        }
    }
}
 
void projective_point_addition(State& state)
{
    numeric::RNG& engine = numeric::get_debug_randomness();
    std::vector<Curve::Element> copy_vector(2);
    for (size_t j = 0; j < 2; j++) {
        copy_vector.emplace_back(Curve::Element::random_element(&engine));
        copy_vector.emplace_back(Curve::Element::random_element(&engine));
    }
 
    for (auto _ : state) {
        state.PauseTiming();
        size_t num_cycles = 1 << static_cast<size_t>(state.range(0));
        state.ResumeTiming();
        for (size_t i = 0; i < num_cycles; i++) {
            copy_vector[i & 1] += copy_vector[1 - (i & 1)];
        }
    }
}
 
void projective_point_accidental_doubling(State& state)
{
    numeric::RNG& engine = numeric::get_debug_randomness();
    std::vector<Curve::Element> copy_vector(2);
    for (size_t j = 0; j < 2; j++) {
        copy_vector.emplace_back(Curve::Element::random_element(&engine));
        copy_vector.emplace_back(Curve::Element::random_element(&engine));
    }
 
    for (auto _ : state) {
        state.PauseTiming();
        size_t num_cycles = 1 << static_cast<size_t>(state.range(0));
        state.ResumeTiming();
        for (size_t i = 0; i < num_cycles; i++) {
            copy_vector[0] += copy_vector[0];
        }
    }
}
 
void projective_point_doubling(State& state)
{
    numeric::RNG& engine = numeric::get_debug_randomness();
    std::vector<Curve::Element> copy_vector(2);
    for (size_t j = 0; j < 2; j++) {
        copy_vector.emplace_back(Curve::Element::random_element(&engine));
        copy_vector.emplace_back(Curve::Element::random_element(&engine));
    }
 
    for (auto _ : state) {
        state.PauseTiming();
        size_t num_cycles = 1 << static_cast<size_t>(state.range(0));
        state.ResumeTiming();
        for (size_t i = 0; i < num_cycles; i++) {
            copy_vector[0] = copy_vector[0].dbl();
        }
    }
}
 
void scalar_multiplication_bench(State& state)
{
    numeric::RNG& engine = numeric::get_debug_randomness();
    Curve::Element element = Curve::Element::random_element(&engine);
    Fr scalar = Fr::random_element(&engine);
 
    for (auto _ : state) {
        state.PauseTiming();
        size_t num_cycles = 1 << static_cast<size_t>(state.range(0));
        state.ResumeTiming();
        for (size_t i = 0; i < num_cycles; i++) {
            element = element * scalar;
            scalar += scalar;
        }
    }
}
void cycle_waste(State& state)
{
 
    for (auto _ : state) {
        state.PauseTiming();
        size_t num_cycles = 1 << static_cast<size_t>(state.range(0));
        state.ResumeTiming();
        for (volatile size_t i = 0; i < num_cycles;) {
            i = i + 1;
        }
    }
}
 
void sequential_copy(State& state)
{
 
    numeric::RNG& engine = numeric::get_debug_randomness();
    for (auto _ : state) {
        state.PauseTiming();
        size_t num_cycles = 1 << static_cast<size_t>(state.range(0));
        std::vector<Fr> input(num_cycles);
        for (size_t i = 0; i < num_cycles; i++) {
            *(uint256_t*)&input[i] = engine.get_random_uint256();
        }
        std::vector<Fr> output(num_cycles);
 
        state.ResumeTiming();
        for (size_t i = 0; i < num_cycles; i++) {
            output[i] = input[i];
        }
    }
}
 
void uint_multiplication(State& state)
{
    numeric::RNG& engine = numeric::get_debug_randomness();
    std::vector<uint256_t> copy_vector(2);
    for (size_t j = 0; j < 2; j++) {
        copy_vector.emplace_back(engine.get_random_uint256());
        copy_vector.emplace_back(engine.get_random_uint256());
        copy_vector[0] += (1 - copy_vector[0].get_bit(0));
        copy_vector[1] += (1 - copy_vector[1].get_bit(0));
    }
 
    for (auto _ : state) {
        state.PauseTiming();
        size_t num_cycles = 1 << static_cast<size_t>(state.range(0));
        state.ResumeTiming();
        for (size_t i = 0; i < num_cycles; i++) {
            copy_vector[i & 1] *= copy_vector[1 - (i & 1)];
        }
    }
}
 
void uint_extended_multiplication(State& state)
{
    numeric::RNG& engine = numeric::get_debug_randomness();
    std::vector<uint256_t> copy_vector(2);
    for (size_t j = 0; j < 2; j++) {
        copy_vector.emplace_back(engine.get_random_uint256());
        copy_vector.emplace_back(engine.get_random_uint256());
        copy_vector[0] += (1 - copy_vector[0].get_bit(0));
        copy_vector[1] += (1 - copy_vector[1].get_bit(0));
    }
 
    for (auto _ : state) {
        state.PauseTiming();
        size_t num_cycles = 1 << static_cast<size_t>(state.range(0));
        state.ResumeTiming();
        for (size_t i = 0; i < num_cycles; i++) {
            auto [r0, r1] = copy_vector[i & 1].mul_extended(copy_vector[1 - (i & 1)]);
            state.PauseTiming();
            copy_vector[i & 1] += r0;
            copy_vector[1 - (i & 1)] += r1;
            copy_vector[0] += (1 - copy_vector[0].get_bit(0));
            copy_vector[1] += (1 - copy_vector[1].get_bit(0));
            state.ResumeTiming();
        }
    }
}
 
/*
 * @brief Load srs for pippenger
 *
 */
static void DoPippengerSetup(const benchmark::State&)
{
    bb::srs::init_file_crs_factory(bb::srs::bb_crs_path());
}
 
void pippenger(State& state)
{
    numeric::RNG& engine = numeric::get_debug_randomness();
    for (auto _ : state) {
        state.PauseTiming();
        size_t num_cycles = 1 << static_cast<size_t>(state.range(0));
        Polynomial<Fr> pol(num_cycles);
        for (size_t i = 0; i < num_cycles; i++) {
            *(uint256_t*)&pol.at(i) = engine.get_random_uint256();
            pol.at(i).self_reduce_once();
            pol.at(i).self_reduce_once();
            pol.at(i).self_reduce_once();
        }
 
        CommitmentKey<curve::BN254> ck(num_cycles);
        state.ResumeTiming();
        benchmark::DoNotOptimize(ck.commit(pol));
    }
}
 
void bn254fr_random(State& state)
{
    numeric::RNG& engine = numeric::get_randomness();
    for (auto _ : state) {
        state.PauseTiming();
        size_t num_cycles = 1UL << static_cast<size_t>(state.range(0));
        state.ResumeTiming();
        for (size_t i = 0; i < num_cycles; i++) {
            benchmark::DoNotOptimize(fr::random_element(&engine));
        }
    }
}
} // namespace
 
BENCHMARK(parallel_for_field_element_addition)->Unit(kMicrosecond)->DenseRange(0, MAX_REPETITION_LOG);
BENCHMARK(ff_addition)->Unit(kMicrosecond)->DenseRange(12, 30);
BENCHMARK(ff_multiplication)->Unit(kMicrosecond)->DenseRange(12, 27);
BENCHMARK(ff_sqr)->Unit(kMicrosecond)->DenseRange(12, 27);
BENCHMARK(ff_invert)->Unit(kMicrosecond)->DenseRange(12, 19);
BENCHMARK(ff_to_montgomery)->Unit(kMicrosecond)->DenseRange(12, 27);
BENCHMARK(ff_from_montgomery)->Unit(kMicrosecond)->DenseRange(12, 27);
BENCHMARK(ff_reduce)->Unit(kMicrosecond)->DenseRange(12, 29);
BENCHMARK(projective_point_addition)->Unit(kMicrosecond)->DenseRange(12, 22);
BENCHMARK(projective_point_accidental_doubling)->Unit(kMicrosecond)->DenseRange(12, 22);
BENCHMARK(projective_point_doubling)->Unit(kMicrosecond)->DenseRange(12, 22);
BENCHMARK(scalar_multiplication_bench)->Unit(kMicrosecond)->DenseRange(12, 18);
BENCHMARK(cycle_waste)->Unit(kMicrosecond)->DenseRange(20, 30);
BENCHMARK(sequential_copy)->Unit(kMicrosecond)->DenseRange(20, 25);
BENCHMARK(uint_multiplication)->Unit(kMicrosecond)->DenseRange(12, 27);
BENCHMARK(uint_extended_multiplication)->Unit(kMicrosecond)->DenseRange(12, 27);
BENCHMARK(pippenger)->Unit(kMicrosecond)->DenseRange(16, 20)->Setup(DoPippengerSetup)->Iterations(5);
BENCHMARK(bn254fr_random)->Unit(kMicrosecond)->DenseRange(10, 20);
BENCHMARK_MAIN();