profile_multiexp.cpp File Reference

#include "libff/algebra/curves/alt_bn128/alt_bn128_pp.hpp"
#include "libff/algebra/curves/curve_serialization.hpp"
#include "libff/algebra/scalar_multiplication/multiexp.hpp"
#include "libff/algebra/scalar_multiplication/multiexp_stream.hpp"
#include "libff/common/profiling.hpp"
#include "libff/common/rng.hpp"
#include <cstdio>
#include <fstream>
#include <sys/stat.h>
#include <vector>

Include dependency graph for profile_multiexp.cpp:

Go to the source code of this file.

Typedefs
template<typename GroupT >
using	run_result_t = std::pair< long long, GroupT >
template<typename T >
using	test_instances_t = std::vector< T >

Functions
template<typename GroupT >
test_instances_t< GroupT >	generate_group_elements (size_t num_elements)
template<typename FieldT >
test_instances_t< FieldT >	generate_scalars (size_t num_elements)
template<form_t Form, compression_t Comp>
std::string	base_elements_filename (const std::string &tag, const size_t num_elements, const size_t precompute_c=0)
template<form_t Form, compression_t Comp, typename GroupT >
void	create_base_element_file_for_config (const std::string &tag, const test_instances_t< GroupT > &base_elements)
template<form_t Form, compression_t Comp, typename GroupT >
void	create_precompute_file_for_config (const std::string &tag, const test_instances_t< GroupT > &base_elements)
template<typename GroupT >
void	create_base_element_files (const std::string &tag, const size_t num_elements)
template<typename GroupT >
test_instances_t< GroupT >	read_group_elements (const std::string &tag, const size_t num_elements)
template<typename GroupT , typename FieldT , multi_exp_method Method, multi_exp_base_form BaseForm = multi_exp_base_form_normal>
run_result_t< GroupT >	profile_multiexp (test_instances_t< GroupT > group_elements, test_instances_t< FieldT > scalars)
template<form_t Form, compression_t Comp, typename GroupT , typename FieldT >
run_result_t< GroupT >	profile_multiexp_stream (const std::string &tag, const std::vector< FieldT > &scalars)
template<form_t Form, compression_t Comp, typename GroupT , typename FieldT >
run_result_t< GroupT >	profile_multiexp_stream_with_precompute (const std::string &tag, const std::vector< FieldT > &scalars)
template<typename GroupT , typename FieldT >
void	print_performance_csv (const std::string &tag, size_t expn_start, size_t expn_end_fast, size_t expn_end_naive, bool compare_answers)
int	main (void)

Variables
constexpr size_t	NUM_ITERATIONS = 10
constexpr size_t	NUM_DIFFERENT_ELEMENTS = 32
constexpr form_t	FORM = form_montgomery
constexpr compression_t	COMP = compression_off

Typedef Documentation

run_result_t

template<typename GroupT >

using run_result_t = std::pair<long long, GroupT>

Definition at line 20 of file profile_multiexp.cpp.

test_instances_t

template<typename T >

using test_instances_t = std::vector<T>

Definition at line 22 of file profile_multiexp.cpp.

Function Documentation

base_elements_filename()

template<form_t Form, compression_t Comp>

std::string base_elements_filename	(	const std::string &	tag,
		const size_t	num_elements,
		const size_t	precompute_c = 0
	)

Definition at line 87 of file profile_multiexp.cpp.

{
    return std::string("multiexp_base_elements_") + tag +
           ((Form == form_plain) ? "_plain_" : "_montgomery_") +
           ((Comp == compression_on) ? "compressed_" : "uncompressed_") +
           std::to_string(num_elements) +
           ((precompute_c) ? ("_" + std::to_string(precompute_c)) : "") +
           ".bin";
}

create_base_element_file_for_config()

template<form_t Form, compression_t Comp, typename GroupT >

void create_base_element_file_for_config	(	const std::string &	tag,
		const test_instances_t< GroupT > &	base_elements
	)

Definition at line 101 of file profile_multiexp.cpp.

{
    const std::string filename =
        base_elements_filename<Form, Comp>(tag, base_elements.size());
 
    std::cout << "Writing file '" << filename << "' ...";
    std::flush(std::cout);
 
    std::ofstream out_s(
        filename.c_str(), std::ios_base::out | std::ios_base::binary);
    for (const GroupT &el : base_elements) {
        group_write<encoding_binary, Form, Comp>(el, out_s);
    }
    out_s.close();
 
    std::cout << " DONE\n";
}

create_base_element_files()

template<typename GroupT >

void create_base_element_files	(	const std::string &	tag,
		const size_t	num_elements
	)

Definition at line 153 of file profile_multiexp.cpp.

{
    test_instances_t<GroupT> base_elements =
        generate_group_elements<GroupT>(num_elements);
    create_base_element_file_for_config<FORM, COMP>(tag, base_elements);
    create_precompute_file_for_config<FORM, COMP>(tag, base_elements);
}

create_precompute_file_for_config()

template<form_t Form, compression_t Comp, typename GroupT >

void create_precompute_file_for_config	(	const std::string &	tag,
		const test_instances_t< GroupT > &	base_elements
	)

Definition at line 121 of file profile_multiexp.cpp.

{
    using Field = typename GroupT::scalar_field;
    const size_t c = bdlo12_signed_optimal_c(base_elements.size());
    const size_t entries_per_base_element = (Field::num_bits + c - 1) / c;
 
    const std::string filename =
        base_elements_filename<Form, Comp>(tag, base_elements.size(), c);
 
    std::cout << "Writing file '" << filename << "' ...";
    std::flush(std::cout);
 
    std::ofstream out_s(
        filename.c_str(), std::ios_base::out | std::ios_base::binary);
    for (GroupT el : base_elements) {
        // Write the base element itself, followed by each factor
        group_write<encoding_binary, Form, Comp>(el, out_s);
        for (size_t i = 0; i < entries_per_base_element - 1; ++i) {
            // Multiply the base element by 2^c, and write
            for (size_t j = 0; j < c; ++j) {
                el = el.dbl();
            }
            group_write<encoding_binary, Form, Comp>(el, out_s);
        }
    }
    out_s.close();
 
    std::cout << " DONE\n";
}

generate_group_elements()

template<typename GroupT >

test_instances_t<GroupT> generate_group_elements

(

size_t

num_elements

)

Definition at line 25 of file profile_multiexp.cpp.

{
    test_instances_t<GroupT> result;
    result.reserve(num_elements);
    assert(result.size() == 0);
 
    // Generating a random group element is expensive, so for now we only
    // generate NUM_DIFFERENT_ELEMENTS, and repeat them. Note, some methods
    // require input to be in special form.
 
    size_t i;
    for (i = 0; i < NUM_DIFFERENT_ELEMENTS; ++i) {
        GroupT x = GroupT::random_element();
        x.to_special();
        result.push_back(x);
    }
    assert(result.size() == NUM_DIFFERENT_ELEMENTS);
 
    for (; i < num_elements; ++i) {
        assert(result.size() == i);
        result.push_back(result[i % NUM_DIFFERENT_ELEMENTS]);
    }
 
    assert(result.size() == num_elements);
    return result;
}

generate_scalars()

template<typename FieldT >

test_instances_t<FieldT> generate_scalars

(

size_t

num_elements

)

Definition at line 53 of file profile_multiexp.cpp.

{
    // Use SHA512_rng because it is much faster than FieldT::random_element()
    test_instances_t<FieldT> result;
    result.reserve(num_elements);
    for (size_t i = 0; i < num_elements; i++) {
        result.push_back(SHA512_rng<FieldT>(i));
    }
 
    assert(result.size() == num_elements);
    return result;
}

main()

int main

(

void

)

Definition at line 401 of file profile_multiexp.cpp.

{
    print_compilation_info();
 
    alt_bn128_pp::init_public_params();
 
    print_performance_csv<G1<alt_bn128_pp>, Fr<alt_bn128_pp>>(
        "alt_bn128_g1", 8, 20, 14, true);
 
    print_performance_csv<G2<alt_bn128_pp>, Fr<alt_bn128_pp>>(
        "alt_bn128_g2", 8, 20, 14, true);
 
    return 0;
}

Here is the call graph for this function:

print_performance_csv()

template<typename GroupT , typename FieldT >

void print_performance_csv	(	const std::string &	tag,
		size_t	expn_start,
		size_t	expn_end_fast,
		size_t	expn_end_naive,
		bool	compare_answers
	)

Definition at line 276 of file profile_multiexp.cpp.

{
    std::cout << "Profiling " << tag << "\n";
    printf(
        "\t%16s\t%16s\t%16s\t%16s\t%16s\t%16s\t%16s\n",
        "bos-coster",
        "djb",
        "djb_signed",
        "djb_signed_mixed",
        "from_stream",
        "from_stream_precompute",
        "naive");
    for (size_t expn = expn_start; expn <= expn_end_fast; expn++) {
        printf("%ld", expn);
        fflush(stdout);
 
        try {
            test_instances_t<GroupT> group_elements =
                read_group_elements<GroupT>(tag, 1 << expn);
 
            test_instances_t<FieldT> scalars =
                generate_scalars<FieldT>(1 << expn);
 
            run_result_t<GroupT> result_bos_coster =
                profile_multiexp<GroupT, FieldT, multi_exp_method_bos_coster>(
                    group_elements, scalars);
            printf("\t%16lld", result_bos_coster.first);
            fflush(stdout);
 
            run_result_t<GroupT> result_djb =
                profile_multiexp<GroupT, FieldT, multi_exp_method_BDLO12>(
                    group_elements, scalars);
            printf("\t%16lld", result_djb.first);
            fflush(stdout);
 
            if (compare_answers &&
                (result_bos_coster.second != result_djb.second)) {
                fprintf(stderr, "Answers NOT MATCHING (bos coster != djb)\n");
            }
 
            run_result_t<GroupT> result_djb_signed = profile_multiexp<
                GroupT,
                FieldT,
                multi_exp_method_BDLO12_signed>(group_elements, scalars);
            printf("\t%16lld", result_djb_signed.first);
            fflush(stdout);
 
            if (compare_answers &&
                (result_djb.second != result_djb_signed.second)) {
                fprintf(stderr, "Answers NOT MATCHING (djb != djb_signed)\n");
            }
 
            run_result_t<GroupT> result_djb_signed_mixed = profile_multiexp<
                GroupT,
                FieldT,
                multi_exp_method_BDLO12_signed,
                multi_exp_base_form_special>(group_elements, scalars);
            printf("\t%16lld", result_djb_signed_mixed.first);
            fflush(stdout);
 
            if (compare_answers &&
                (result_djb_signed.second != result_djb_signed_mixed.second)) {
                fprintf(
                    stderr,
                    "Answers NOT MATCHING (djb_signed != djb_signed_mixed)\n");
            }
 
            run_result_t<GroupT> result_stream =
                profile_multiexp_stream<FORM, COMP, GroupT, FieldT>(
                    tag, scalars);
            printf("\t%16lld", result_stream.first);
            fflush(stdout);
 
            if (compare_answers &&
                (result_djb_signed_mixed.second != result_stream.second)) {
                fprintf(
                    stderr,
                    "Answers NOT MATCHING (djb_signed_mixed != stream)\n");
            }
 
            run_result_t<GroupT> result_stream_precomp =
                profile_multiexp_stream_with_precompute<
                    FORM,
                    COMP,
                    GroupT,
                    FieldT>(tag, scalars);
            printf("\t%16lld", result_stream_precomp.first);
            fflush(stdout);
 
            if (compare_answers &&
                (result_stream.second != result_stream_precomp.second)) {
                fprintf(
                    stderr,
                    "Answers NOT MATCHING (stream != stream_precomp)\n");
            }
 
            if (expn <= expn_end_naive) {
                run_result_t<GroupT> result_naive =
                    profile_multiexp<GroupT, FieldT, multi_exp_method_naive>(
                        group_elements, scalars);
                printf("\t%16lld", result_naive.first);
                fflush(stdout);
 
                if (compare_answers &&
                    (result_bos_coster.second != result_naive.second)) {
                    fprintf(
                        stderr, "Answers NOT MATCHING (bos coster != naive)\n");
                }
            }
 
            printf("\n");
 
        } catch (const std::ifstream::failure &e) {
            std::cout << "(Generating files for 1<<" << expn << ")\n";
            create_base_element_files<GroupT>(tag, 1 << expn);
            continue;
        }
    }
}

Here is the call graph for this function:

profile_multiexp()

template<typename GroupT , typename FieldT , multi_exp_method Method, multi_exp_base_form BaseForm = multi_exp_base_form_normal>

run_result_t<GroupT> profile_multiexp	(	test_instances_t< GroupT >	group_elements,
		test_instances_t< FieldT >	scalars
	)

Definition at line 189 of file profile_multiexp.cpp.

{
    long long start_time = get_nsec_time();
 
    GroupT answer;
    for (size_t iter = 0; iter < NUM_ITERATIONS; ++iter) {
        answer = multi_exp<GroupT, FieldT, Method, BaseForm>(
            group_elements.cbegin(),
            group_elements.cend(),
            scalars.cbegin(),
            scalars.cend(),
            1);
    }
 
    long long time_delta = get_nsec_time() - start_time;
 
    return run_result_t<GroupT>(time_delta, answer);
}

Here is the call graph for this function:

Here is the caller graph for this function:

profile_multiexp_stream()

template<form_t Form, compression_t Comp, typename GroupT , typename FieldT >

run_result_t<GroupT> profile_multiexp_stream	(	const std::string &	tag,
		const std::vector< FieldT > &	scalars
	)

Definition at line 210 of file profile_multiexp.cpp.

{
    const size_t num_elements = scalars.size();
    const std::string filename =
        base_elements_filename<Form, Comp>(tag, num_elements);
 
    struct stat s;
    if (stat(filename.c_str(), &s)) {
        throw std::ifstream::failure("no file: " + filename);
    }
 
    std::ifstream in_s(
        filename.c_str(), std::ios_base::in | std::ios_base::binary);
    in_s.exceptions(
        std::ios_base::eofbit | std::ios_base::badbit | std::ios_base::failbit);
 
    GroupT answer;
 
    long long start_time = get_nsec_time();
 
    for (size_t iter = 0; iter < NUM_ITERATIONS; ++iter) {
        in_s.seekg(0llu);
        answer = multi_exp_stream<Form, Comp, GroupT, FieldT>(in_s, scalars);
    }
 
    long long time_delta = get_nsec_time() - start_time;
 
    return run_result_t<GroupT>(time_delta, answer);
}

Here is the call graph for this function:

profile_multiexp_stream_with_precompute()

template<form_t Form, compression_t Comp, typename GroupT , typename FieldT >

run_result_t<GroupT> profile_multiexp_stream_with_precompute	(	const std::string &	tag,
		const std::vector< FieldT > &	scalars
	)

Definition at line 242 of file profile_multiexp.cpp.

{
    const size_t num_elements = scalars.size();
    const size_t c = bdlo12_signed_optimal_c(num_elements);
    const std::string filename =
        base_elements_filename<Form, Comp>(tag, num_elements, c);
 
    struct stat s;
    if (stat(filename.c_str(), &s)) {
        throw std::ifstream::failure("no file: " + filename);
    }
 
    std::ifstream in_s(
        filename.c_str(), std::ios_base::in | std::ios_base::binary);
    in_s.exceptions(
        std::ios_base::eofbit | std::ios_base::badbit | std::ios_base::failbit);
 
    GroupT answer;
 
    long long start_time = get_nsec_time();
 
    for (size_t iter = 0; iter < NUM_ITERATIONS; ++iter) {
        in_s.seekg(0llu);
        answer = multi_exp_stream_with_precompute<Form, Comp, GroupT, FieldT>(
            in_s, scalars, c);
    }
 
    long long time_delta = get_nsec_time() - start_time;
 
    return run_result_t<GroupT>(time_delta, answer);
}

Here is the caller graph for this function:

read_group_elements()

template<typename GroupT >

test_instances_t<GroupT> read_group_elements	(	const std::string &	tag,
		const size_t	num_elements
	)

Definition at line 163 of file profile_multiexp.cpp.

{
    const std::string filename =
        base_elements_filename<FORM, COMP>(tag, num_elements);
 
    test_instances_t<GroupT> elements;
    elements.reserve(num_elements);
 
    std::ifstream in_s;
    in_s.exceptions(std::ifstream::badbit | std::ifstream::failbit);
    in_s.open(filename, std::ios_base::in | std::ios_base::binary);
    for (size_t i = 0; i < num_elements; ++i) {
        GroupT v;
        group_read<encoding_binary, FORM, COMP>(v, in_s);
        elements.push_back(v);
    }
 
    return elements;
}

Variable Documentation

COMP

constexpr compression_t COMP = compression_off

constexpr

Definition at line 18 of file profile_multiexp.cpp.

FORM

constexpr form_t FORM = form_montgomery

constexpr

Definition at line 17 of file profile_multiexp.cpp.

NUM_DIFFERENT_ELEMENTS

constexpr size_t NUM_DIFFERENT_ELEMENTS = 32

constexpr

Definition at line 15 of file profile_multiexp.cpp.

NUM_ITERATIONS

constexpr size_t NUM_ITERATIONS = 10

constexpr

Definition at line 14 of file profile_multiexp.cpp.