diff options
Diffstat (limited to 'benchmark')
65 files changed, 3272 insertions, 0 deletions
diff --git a/benchmark/CMakeLists.txt b/benchmark/CMakeLists.txt new file mode 100644 index 000000000000..0f9061aa3cd3 --- /dev/null +++ b/benchmark/CMakeLists.txt @@ -0,0 +1,128 @@ + +# Config +# ====== + +option(CHECK_BENCHMARKS "Run benchmarks on check target" off) +option(BENCHMARK_DISABLE_GC "Disable gc during a measurement") + +set(BENCHMARK_PARAM "N:1000" CACHE STRING "Benchmark parameters") +set(BENCHMARK_SAMPLES "20" CACHE STRING "Benchmark samples") + +# Dependencies +# ============ + +find_package(RRB) + +if (NOT RRB_FOUND) + message(STATUS "Disabling benchmarks") + return() +endif() + +# These are expected to be in the include path, the nix-shell +# environment installs them: +# +# https://github.com/marcusz/steady +# https://github.com/deepsea-inria/chunkedseq.git +# https://github.com/rsms/immutable-cpp.git + +# Targets +# ======= + +add_custom_target(benchmarks + COMMENT "Build all benchmarks.") + +execute_process( + COMMAND git log -1 --format=%h + WORKING_DIRECTORY ${CMAKE_SOURCE_DIR} + OUTPUT_VARIABLE immer_git_commit_hash + OUTPUT_STRIP_TRAILING_WHITESPACE) + +execute_process( + COMMAND git status --porcelain + WORKING_DIRECTORY ${CMAKE_SOURCE_DIR} + OUTPUT_VARIABLE immer_git_status + OUTPUT_STRIP_TRAILING_WHITESPACE) + +if (NOT immer_git_status STREQUAL "") + set(immer_git_commit_hash "${immer_git_commit_hash}+") +endif() + +site_name(immer_hostname) + +get_filename_component(immer_compiler_name "${CMAKE_CXX_COMPILER}" NAME) + +set(immer_benchmark_report_base_dir "${CMAKE_SOURCE_DIR}/reports") +set(immer_benchmark_report_dir "${immer_benchmark_report_base_dir}/report_\ +${immer_git_commit_hash}_\ +${immer_hostname}_\ +${immer_compiler_name}_\ +${BENCHMARK_PARAM}_\ +s${BENCHMARK_SAMPLES}") + +if(DISABLE_FREE_LIST) + set(immer_benchmark_report_dir "${immer_benchmark_report_dir}_nofl") +endif() + +if(DISABLE_THREAD_SAFETY) + set(immer_benchmark_report_dir "${immer_benchmark_report_dir}_nots") +endif() + +if(BENCHMARK_DISABLE_GC) + set(immer_benchmark_report_dir "${immer_benchmark_report_dir}_nogc") +endif() + +if(CHECK_BENCHMARKS) + add_dependencies(check benchmarks) +endif() + +add_custom_target(benchmark-report-dir + COMMAND ${CMAKE_COMMAND} + -E make_directory ${immer_benchmark_report_dir}) + +file(GLOB_RECURSE immer_benchmarks "*.cpp") +foreach(_file IN LISTS immer_benchmarks) + immer_target_name_for(_target _output "${_file}") + add_executable(${_target} EXCLUDE_FROM_ALL "${_file}") + set_target_properties(${_target} PROPERTIES OUTPUT_NAME ${_output}) + add_dependencies(benchmarks ${_target}) + add_dependencies(${_target} benchmark-report-dir) + target_compile_options(${_target} PUBLIC -Wno-unused-function) + target_compile_definitions(${_target} PUBLIC + NONIUS_RUNNER + IMMER_BENCHMARK_LIBRRB=1 + IMMER_BENCHMARK_STEADY=1 + IMMER_BENCHMARK_EXPERIMENTAL=0 + IMMER_BENCHMARK_DISABLE_GC=${BENCHMARK_DISABLE_GC} + IMMER_BENCHMARK_BOOST_COROUTINE=${ENABLE_BOOST_COROUTINE}) + target_link_libraries(${_target} PUBLIC + immer-dev + ${RRB_LIBRARIES}) + target_include_directories(${_target} SYSTEM PUBLIC + ${RRB_INCLUDE_DIR}) + if(CHECK_BENCHMARKS) + add_test("benchmark/${_output}" "${CMAKE_SOURCE_DIR}/tools/with-tee.bash" + ${immer_benchmark_report_dir}/${_target}.out + "${CMAKE_CURRENT_BINARY_DIR}/${_output}" -v + -t ${_target} + -r html + -s ${BENCHMARK_SAMPLES} + -p ${BENCHMARK_PARAM} + -o ${immer_benchmark_report_dir}/${_target}.html) + endif() +endforeach() + +set(immer_ssh_method + ssh -p 5488 + -o StrictHostKeyChecking=no + -i ${CMAKE_SOURCE_DIR}/tools/travis/ssh-key) + +add_custom_target(upload-benchmark-reports + COMMAND + rsync -av -e \"${immer_ssh_method}\" + ${immer_benchmark_report_base_dir} + raskolnikov@sinusoid.es:public/misc/immer/) + +add_custom_target(copy-benchmark-reports + COMMAND + rsync -av ${immer_benchmark_report_base_dir} + ~/public/misc/immer/) diff --git a/benchmark/config.hpp b/benchmark/config.hpp new file mode 100644 index 000000000000..c32ef5812ff8 --- /dev/null +++ b/benchmark/config.hpp @@ -0,0 +1,55 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include <nonius.h++> + +#include <immer/heap/gc_heap.hpp> +#include <immer/memory_policy.hpp> + +namespace { + +NONIUS_PARAM(N, std::size_t{1000}) + +struct gc_disable +{ + gc_disable() + { +#if IMMER_BENCHMARK_DISABLE_GC + GC_disable(); +#else + GC_gcollect(); +#endif + } + ~gc_disable() + { +#if IMMER_BENCHMARK_DISABLE_GC + GC_enable(); + GC_gcollect(); +#endif + } + gc_disable(const gc_disable&) = delete; + gc_disable(gc_disable&&) = delete; +}; + +template <typename Meter, typename Fn> +void measure(Meter& m, Fn&& fn) +{ + gc_disable guard; + return m.measure(std::forward<Fn>(fn)); +} + +using def_memory = immer::default_memory_policy; +using gc_memory = immer::memory_policy<immer::heap_policy<immer::gc_heap>, immer::no_refcount_policy>; +using gcf_memory = immer::memory_policy<immer::heap_policy<immer::gc_heap>, immer::no_refcount_policy, immer::gc_transience_policy, false>; +using basic_memory = immer::memory_policy<immer::heap_policy<immer::cpp_heap>, immer::refcount_policy>; +using safe_memory = immer::memory_policy<immer::free_list_heap_policy<immer::cpp_heap>, immer::refcount_policy>; +using unsafe_memory = immer::memory_policy<immer::unsafe_free_list_heap_policy<immer::cpp_heap>, immer::unsafe_refcount_policy>; + +} // anonymous namespace diff --git a/benchmark/extra/refcounting.cpp b/benchmark/extra/refcounting.cpp new file mode 100644 index 000000000000..c7c5183e6264 --- /dev/null +++ b/benchmark/extra/refcounting.cpp @@ -0,0 +1,146 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include <immer/detail/ref_count_base.hpp> + +#include <nonius.h++> +#include <boost/intrusive_ptr.hpp> + +#include <atomic> +#include <cstdlib> +#include <iterator> +#include <memory> +#include <utility> +#include <array> +#include <vector> + +NONIUS_PARAM(N, std::size_t{1000}) + +constexpr auto benchmark_size = 32u; + +struct object_t : immer::detail::ref_count_base<object_t> +{}; + +auto make_data() +{ + auto objs = std::array<std::unique_ptr<object_t>, benchmark_size>(); + std::generate(objs.begin(), objs.end(), [] { + return std::make_unique<object_t>(); + }); + auto refs = std::array<object_t*, benchmark_size>(); + std::transform(objs.begin(), objs.end(), refs.begin(), [](auto& obj) { + return obj.get(); + }); + return make_pair(std::move(objs), + std::move(refs)); +} + +NONIUS_BENCHMARK("intrusive_ptr", [] (nonius::chronometer meter) +{ + auto arr = std::array<boost::intrusive_ptr<object_t>, benchmark_size>{}; + auto storage = std::vector< + nonius::storage_for< + std::array<boost::intrusive_ptr<object_t>, benchmark_size>>> ( + meter.runs()); + std::generate(arr.begin(), arr.end(), [] { + return new object_t{}; + }); + meter.measure([&] (int i) { + storage[i].construct(arr); + }); +}) + +NONIUS_BENCHMARK("generic", [] (nonius::chronometer meter) +{ + auto data = make_data(); + auto& refs = data.second; + object_t* r[benchmark_size]; + + meter.measure([&] { + std::transform(refs.begin(), refs.end(), r, [] (auto& p) { + if (p) p->ref_count.fetch_add(1, std::memory_order_relaxed); + return p; + }); + return r; + }); +}) + +NONIUS_BENCHMARK("manual", [] (nonius::chronometer meter) +{ + auto data = make_data(); + auto& refs = data.second; + object_t* r[benchmark_size]; + + meter.measure([&] { + for (auto& p : refs) + if (p) p->ref_count.fetch_add(1, std::memory_order_relaxed); + std::copy(refs.begin(), refs.end(), r); + return r; + }); +}) + +NONIUS_BENCHMARK("manual - unroll", [] (nonius::chronometer meter) +{ + auto data = make_data(); + auto& refs = data.second; + object_t* r[benchmark_size]; + + meter.measure([&] { + auto e = refs.end(); + for (auto p = refs.begin(); p != e;) { + (*p++)->ref_count.fetch_add(1, std::memory_order_relaxed); + (*p++)->ref_count.fetch_add(1, std::memory_order_relaxed); + (*p++)->ref_count.fetch_add(1, std::memory_order_relaxed); + (*p++)->ref_count.fetch_add(1, std::memory_order_relaxed); + } + std::copy(refs.begin(), refs.end(), r); + return r; + }); +}) + +NONIUS_BENCHMARK("manual - nocheck", [] (nonius::chronometer meter) +{ + auto data = make_data(); + auto& refs = data.second; + object_t* r[benchmark_size]; + + meter.measure([&] { + for (auto& p : refs) + p->ref_count.fetch_add(1, std::memory_order_relaxed); + std::copy(refs.begin(), refs.end(), r); + return r; + }); +}) + +NONIUS_BENCHMARK("manual - constant", [] (nonius::chronometer meter) +{ + auto data = make_data(); + auto& refs = data.second; + object_t* r[benchmark_size]; + + meter.measure([&] { + for (auto i = 0u; i < benchmark_size; ++i) + refs[i]->ref_count.fetch_add(1, std::memory_order_relaxed); + std::copy(refs.begin(), refs.end(), r); + return r; + }); +}) + +NONIUS_BENCHMARK("manual - memcopy", [] (nonius::chronometer meter) +{ + auto data = make_data(); + auto& refs = data.second; + object_t* r[benchmark_size]; + + meter.measure([&] { + for (auto& p : refs) + if (p) p->ref_count.fetch_add(1, std::memory_order_relaxed); + std::memcpy(r, &refs[0], sizeof(object_t*) * benchmark_size); + return r; + }); +}) diff --git a/benchmark/set/access.hpp b/benchmark/set/access.hpp new file mode 100644 index 000000000000..8605c0ff453c --- /dev/null +++ b/benchmark/set/access.hpp @@ -0,0 +1,175 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include "benchmark/config.hpp" + +#include <immer/set.hpp> +#include <hash_trie.hpp> // Phil Nash +#include <boost/container/flat_set.hpp> +#include <set> +#include <unordered_set> + +namespace { + +template <typename T=unsigned> +auto make_generator_ranged(std::size_t runs) +{ + assert(runs > 0); + auto engine = std::default_random_engine{13}; + auto dist = std::uniform_int_distribution<T>{0, (T)runs-1}; + auto r = std::vector<T>(runs); + std::generate_n(r.begin(), runs, std::bind(dist, engine)); + return r; +} + +template <typename Generator, typename Set> +auto benchmark_access_std() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + auto g1 = Generator{}(n); + auto g2 = make_generator_ranged(n); + + auto v = Set{}; + for (auto i = 0u; i < n; ++i) + v.insert(g1[i]); + + measure(meter, [&] { + auto c = 0u; + for (auto i = 0u; i < n; ++i) + c += v.count(g1[g2[i]]); + volatile auto r = c; + return r; + }); + }; +} + +template <typename Generator, typename Set> +auto benchmark_access_hamt() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + auto g1 = Generator{}(n); + auto g2 = make_generator_ranged(n); + + auto v = Set{}; + for (auto i = 0u; i < n; ++i) + v.insert(g1[i]); + + measure(meter, [&] { + auto c = 0u; + for (auto i = 0u; i < n; ++i) { + auto& x = g1[g2[i]]; + auto leaf = v.find(x).leaf(); + c += !!(leaf && leaf->find(x)); + } + volatile auto r = c; + return r; + }); + }; +} + + +template <typename Generator, typename Set> +auto benchmark_access() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + auto g1 = Generator{}(n); + auto g2 = make_generator_ranged(n); + + auto v = Set{}; + for (auto i = 0u; i < n; ++i) + v = v.insert(g1[i]); + + measure(meter, [&] { + auto c = 0u; + for (auto i = 0u; i < n; ++i) + c += v.count(g1[g2[i]]); + volatile auto r = c; + return r; + }); + }; +} + +template <typename Generator, typename Set> +auto benchmark_bad_access_std() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + auto g1 = Generator{}(n*2); + + auto v = Set{}; + for (auto i = 0u; i < n; ++i) + v.insert(g1[i]); + + measure(meter, [&] { + auto c = 0u; + for (auto i = 0u; i < n; ++i) + c += v.count(g1[n+i]); + volatile auto r = c; + return r; + }); + }; +} + +template <typename Generator, typename Set> +auto benchmark_bad_access_hamt() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + auto g1 = Generator{}(n*2); + + auto v = Set{}; + for (auto i = 0u; i < n; ++i) + v.insert(g1[i]); + + measure(meter, [&] { + auto c = 0u; + for (auto i = 0u; i < n; ++i) { + auto& x = g1[n+i]; + auto leaf = v.find(x).leaf(); + c += !!(leaf && leaf->find(x)); + } + volatile auto r = c; + return r; + }); + }; +} + + +template <typename Generator, typename Set> +auto benchmark_bad_access() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + auto g1 = Generator{}(n*2); + + auto v = Set{}; + for (auto i = 0u; i < n; ++i) + v = v.insert(g1[i]); + + measure(meter, [&] { + auto c = 0u; + for (auto i = 0u; i < n; ++i) + c += v.count(g1[n+i]); + volatile auto r = c; + return r; + }); + }; +} + +} // namespace diff --git a/benchmark/set/access.ipp b/benchmark/set/access.ipp new file mode 100644 index 000000000000..f026d9cfa736 --- /dev/null +++ b/benchmark/set/access.ipp @@ -0,0 +1,30 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "access.hpp" + +#ifndef GENERATOR_T +#error "you must define a GENERATOR_T" +#endif + +using generator__ = GENERATOR_T; +using t__ = typename decltype(generator__{}(0))::value_type; + +NONIUS_BENCHMARK("std::set", benchmark_access_std<generator__, std::set<t__>>()) +NONIUS_BENCHMARK("std::unordered_set", benchmark_access_std<generator__, std::unordered_set<t__>>()) +NONIUS_BENCHMARK("boost::flat_set", benchmark_access_std<generator__, boost::container::flat_set<t__>>()) +NONIUS_BENCHMARK("hamt::hash_trie", benchmark_access_hamt<generator__, hamt::hash_trie<t__>>()) +NONIUS_BENCHMARK("immer::set/5B", benchmark_access<generator__, immer::set<t__, std::hash<t__>,std::equal_to<t__>,def_memory,5>>()) +NONIUS_BENCHMARK("immer::set/4B", benchmark_access<generator__, immer::set<t__, std::hash<t__>,std::equal_to<t__>,def_memory,4>>()) + +NONIUS_BENCHMARK("bad/std::set", benchmark_bad_access_std<generator__, std::set<t__>>()) +NONIUS_BENCHMARK("bad/std::unordered_set", benchmark_bad_access_std<generator__, std::unordered_set<t__>>()) +NONIUS_BENCHMARK("bad/boost::flat_set", benchmark_bad_access_std<generator__, boost::container::flat_set<t__>>()) +NONIUS_BENCHMARK("bad/hamt::hash_trie", benchmark_bad_access_hamt<generator__, hamt::hash_trie<t__>>()) +NONIUS_BENCHMARK("bad/immer::set/5B", benchmark_bad_access<generator__, immer::set<t__, std::hash<t__>,std::equal_to<t__>,def_memory,5>>()) +NONIUS_BENCHMARK("bad/immer::set/4B", benchmark_bad_access<generator__, immer::set<t__, std::hash<t__>,std::equal_to<t__>,def_memory,4>>()) diff --git a/benchmark/set/insert.hpp b/benchmark/set/insert.hpp new file mode 100644 index 000000000000..be679b4de342 --- /dev/null +++ b/benchmark/set/insert.hpp @@ -0,0 +1,55 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include "benchmark/config.hpp" + +#include <immer/set.hpp> +#include <hash_trie.hpp> // Phil Nash +#include <boost/container/flat_set.hpp> +#include <set> +#include <unordered_set> + +namespace { + +template <typename Generator, typename Set> +auto benchmark_insert_mut_std() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + auto g = Generator{}(n); + + measure(meter, [&] { + auto v = Set{}; + for (auto i = 0u; i < n; ++i) + v.insert(g[i]); + return v; + }); + }; +} + +template <typename Generator, typename Set> +auto benchmark_insert() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + auto g = Generator{}(n); + + measure(meter, [&] { + auto v = Set{}; + for (auto i = 0u; i < n; ++i) + v = v.insert(g[i]); + return v; + }); + }; +} + +} // namespace diff --git a/benchmark/set/insert.ipp b/benchmark/set/insert.ipp new file mode 100644 index 000000000000..6717ccd57ea7 --- /dev/null +++ b/benchmark/set/insert.ipp @@ -0,0 +1,28 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "insert.hpp" + +#ifndef GENERATOR_T +#error "you must define a GENERATOR_T" +#endif + +using generator__ = GENERATOR_T; +using t__ = typename decltype(generator__{}(0))::value_type; + +NONIUS_BENCHMARK("std::set", benchmark_insert_mut_std<generator__, std::set<t__>>()) +NONIUS_BENCHMARK("std::unordered_set", benchmark_insert_mut_std<generator__, std::unordered_set<t__>>()) +NONIUS_BENCHMARK("boost::flat_set", benchmark_insert_mut_std<generator__, boost::container::flat_set<t__>>()) +NONIUS_BENCHMARK("hamt::hash_trie", benchmark_insert_mut_std<generator__, hamt::hash_trie<t__>>()) + +NONIUS_BENCHMARK("immer::set/5B", benchmark_insert<generator__, immer::set<t__, std::hash<t__>,std::equal_to<t__>,def_memory,5>>()) +NONIUS_BENCHMARK("immer::set/4B", benchmark_insert<generator__, immer::set<t__, std::hash<t__>,std::equal_to<t__>,def_memory,4>>()) +#ifndef DISABLE_GC_BENCHMARKS +NONIUS_BENCHMARK("immer::set/GC", benchmark_insert<generator__, immer::set<t__, std::hash<t__>,std::equal_to<t__>,gc_memory,5>>()) +#endif +NONIUS_BENCHMARK("immer::set/UN", benchmark_insert<generator__, immer::set<t__, std::hash<t__>,std::equal_to<t__>,unsafe_memory,5>>()) diff --git a/benchmark/set/iter.hpp b/benchmark/set/iter.hpp new file mode 100644 index 000000000000..91dd48644367 --- /dev/null +++ b/benchmark/set/iter.hpp @@ -0,0 +1,111 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include "benchmark/config.hpp" + +#include <immer/set.hpp> +#include <immer/box.hpp> +#include <immer/algorithm.hpp> +#include <hash_trie.hpp> // Phil Nash +#include <boost/container/flat_set.hpp> +#include <set> +#include <unordered_set> +#include <numeric> + +namespace { + +template <typename T> +struct iter_step +{ + unsigned operator() (unsigned x, const T& y) const + { + return x + y; + } +}; + +template <> +struct iter_step<std::string> +{ + unsigned operator() (unsigned x, const std::string& y) const + { + return x + (unsigned) y.size(); + } +}; + +template <> +struct iter_step<immer::box<std::string>> +{ + unsigned operator() (unsigned x, const immer::box<std::string>& y) const + { + return x + (unsigned) y->size(); + } +}; + +template <typename Generator, typename Set> +auto benchmark_access_std_iter() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + auto g1 = Generator{}(n); + + auto v = Set{}; + for (auto i = 0u; i < n; ++i) + v.insert(g1[i]); + + using step_t = iter_step<typename decltype(g1)::value_type>; + measure(meter, [&] { + volatile auto c = std::accumulate(v.begin(), v.end(), 0u, step_t{}); + return c; + }); + }; +} + +template <typename Generator, typename Set> +auto benchmark_access_reduce() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + auto g1 = Generator{}(n); + + auto v = Set{}; + for (auto i = 0u; i < n; ++i) + v = v.insert(g1[i]); + + using step_t = iter_step<typename decltype(g1)::value_type>; + measure(meter, [&] { + volatile auto c = immer::accumulate(v, 0u, step_t{}); + return c; + }); + }; +} + +template <typename Generator, typename Set> +auto benchmark_access_iter() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + auto g1 = Generator{}(n); + + auto v = Set{}; + for (auto i = 0u; i < n; ++i) + v = v.insert(g1[i]); + + using step_t = iter_step<typename decltype(g1)::value_type>; + measure(meter, [&] { + volatile auto c = std::accumulate(v.begin(), v.end(), 0u, step_t{}); + return c; + }); + }; +} + +} // namespace diff --git a/benchmark/set/iter.ipp b/benchmark/set/iter.ipp new file mode 100644 index 000000000000..f8c3cb9695cd --- /dev/null +++ b/benchmark/set/iter.ipp @@ -0,0 +1,25 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "iter.hpp" + +#ifndef GENERATOR_T +#error "you must define a GENERATOR_T" +#endif + +using generator__ = GENERATOR_T; +using t__ = typename decltype(generator__{}(0))::value_type; + +NONIUS_BENCHMARK("iter/std::set", benchmark_access_std_iter<generator__, std::set<t__>>()) +NONIUS_BENCHMARK("iter/std::unordered_set", benchmark_access_std_iter<generator__, std::unordered_set<t__>>()) +NONIUS_BENCHMARK("iter/boost::flat_set", benchmark_access_std_iter<generator__, boost::container::flat_set<t__>>()) +NONIUS_BENCHMARK("iter/hamt::hash_trie", benchmark_access_std_iter<generator__, hamt::hash_trie<t__>>()) +NONIUS_BENCHMARK("iter/immer::set/5B", benchmark_access_iter<generator__, immer::set<t__, std::hash<t__>,std::equal_to<t__>,def_memory,5>>()) +NONIUS_BENCHMARK("iter/immer::set/4B", benchmark_access_iter<generator__, immer::set<t__, std::hash<t__>,std::equal_to<t__>,def_memory,4>>()) +NONIUS_BENCHMARK("reduce/immer::set/5B", benchmark_access_reduce<generator__, immer::set<t__, std::hash<t__>,std::equal_to<t__>,def_memory,5>>()) +NONIUS_BENCHMARK("reduce/immer::set/4B", benchmark_access_reduce<generator__, immer::set<t__, std::hash<t__>,std::equal_to<t__>,def_memory,4>>()) diff --git a/benchmark/set/string-box/access.cpp b/benchmark/set/string-box/access.cpp new file mode 100644 index 000000000000..c3deffbb0636 --- /dev/null +++ b/benchmark/set/string-box/access.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "generator.ipp" +#include "../access.ipp" diff --git a/benchmark/set/string-box/generator.ipp b/benchmark/set/string-box/generator.ipp new file mode 100644 index 000000000000..9adc82e0bdc0 --- /dev/null +++ b/benchmark/set/string-box/generator.ipp @@ -0,0 +1,46 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include <immer/box.hpp> + +#include <random> +#include <vector> +#include <cassert> +#include <functional> +#include <algorithm> + +#define GENERATOR_T generate_unsigned + +namespace { + +struct GENERATOR_T +{ + static constexpr auto char_set = "_-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; + static constexpr auto max_length = 64; + static constexpr auto min_length = 8; + + auto operator() (std::size_t runs) const + { + assert(runs > 0); + auto engine = std::default_random_engine{42}; + auto dist = std::uniform_int_distribution<unsigned>{}; + auto gen = std::bind(dist, engine); + auto r = std::vector<immer::box<std::string>>(runs); + std::generate_n(r.begin(), runs, [&] { + auto len = gen() % (max_length - min_length) + min_length; + auto str = std::string(len, ' '); + std::generate_n(str.begin(), len, [&] { + return char_set[gen() % sizeof(char_set)]; + }); + return str; + }); + return r; + } +}; + +} // namespace diff --git a/benchmark/set/string-box/insert.cpp b/benchmark/set/string-box/insert.cpp new file mode 100644 index 000000000000..c5762498c23c --- /dev/null +++ b/benchmark/set/string-box/insert.cpp @@ -0,0 +1,11 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#define DISABLE_GC_BENCHMARKS +#include "generator.ipp" +#include "../insert.ipp" diff --git a/benchmark/set/string-box/iter.cpp b/benchmark/set/string-box/iter.cpp new file mode 100644 index 000000000000..83e57e7845d3 --- /dev/null +++ b/benchmark/set/string-box/iter.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "generator.ipp" +#include "../iter.ipp" diff --git a/benchmark/set/string-long/access.cpp b/benchmark/set/string-long/access.cpp new file mode 100644 index 000000000000..c3deffbb0636 --- /dev/null +++ b/benchmark/set/string-long/access.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "generator.ipp" +#include "../access.ipp" diff --git a/benchmark/set/string-long/generator.ipp b/benchmark/set/string-long/generator.ipp new file mode 100644 index 000000000000..386364cc96fe --- /dev/null +++ b/benchmark/set/string-long/generator.ipp @@ -0,0 +1,44 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include <random> +#include <vector> +#include <cassert> +#include <functional> +#include <algorithm> + +#define GENERATOR_T generate_unsigned + +namespace { + +struct GENERATOR_T +{ + static constexpr auto char_set = "_-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; + static constexpr auto max_length = 256; + static constexpr auto min_length = 32; + + auto operator() (std::size_t runs) const + { + assert(runs > 0); + auto engine = std::default_random_engine{42}; + auto dist = std::uniform_int_distribution<unsigned>{}; + auto gen = std::bind(dist, engine); + auto r = std::vector<std::string>(runs); + std::generate_n(r.begin(), runs, [&] { + auto len = gen() % (max_length - min_length) + min_length; + auto str = std::string(len, ' '); + std::generate_n(str.begin(), len, [&] { + return char_set[gen() % sizeof(char_set)]; + }); + return str; + }); + return r; + } +}; + +} // namespace diff --git a/benchmark/set/string-long/insert.cpp b/benchmark/set/string-long/insert.cpp new file mode 100644 index 000000000000..c5762498c23c --- /dev/null +++ b/benchmark/set/string-long/insert.cpp @@ -0,0 +1,11 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#define DISABLE_GC_BENCHMARKS +#include "generator.ipp" +#include "../insert.ipp" diff --git a/benchmark/set/string-long/iter.cpp b/benchmark/set/string-long/iter.cpp new file mode 100644 index 000000000000..83e57e7845d3 --- /dev/null +++ b/benchmark/set/string-long/iter.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "generator.ipp" +#include "../iter.ipp" diff --git a/benchmark/set/string-short/access.cpp b/benchmark/set/string-short/access.cpp new file mode 100644 index 000000000000..c3deffbb0636 --- /dev/null +++ b/benchmark/set/string-short/access.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "generator.ipp" +#include "../access.ipp" diff --git a/benchmark/set/string-short/generator.ipp b/benchmark/set/string-short/generator.ipp new file mode 100644 index 000000000000..bd40d2d639a8 --- /dev/null +++ b/benchmark/set/string-short/generator.ipp @@ -0,0 +1,44 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include <random> +#include <vector> +#include <cassert> +#include <functional> +#include <algorithm> + +#define GENERATOR_T generate_unsigned + +namespace { + +struct GENERATOR_T +{ + static constexpr auto char_set = "_-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; + static constexpr auto max_length = 15; + static constexpr auto min_length = 4; + + auto operator() (std::size_t runs) const + { + assert(runs > 0); + auto engine = std::default_random_engine{42}; + auto dist = std::uniform_int_distribution<unsigned>{}; + auto gen = std::bind(dist, engine); + auto r = std::vector<std::string>(runs); + std::generate_n(r.begin(), runs, [&] { + auto len = gen() % (max_length - min_length) + min_length; + auto str = std::string(len, ' '); + std::generate_n(str.begin(), len, [&] { + return char_set[gen() % sizeof(char_set)]; + }); + return str; + }); + return r; + } +}; + +} // namespace diff --git a/benchmark/set/string-short/insert.cpp b/benchmark/set/string-short/insert.cpp new file mode 100644 index 000000000000..26dfbce29204 --- /dev/null +++ b/benchmark/set/string-short/insert.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "generator.ipp" +#include "../insert.ipp" diff --git a/benchmark/set/string-short/iter.cpp b/benchmark/set/string-short/iter.cpp new file mode 100644 index 000000000000..83e57e7845d3 --- /dev/null +++ b/benchmark/set/string-short/iter.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "generator.ipp" +#include "../iter.ipp" diff --git a/benchmark/set/unsigned/access.cpp b/benchmark/set/unsigned/access.cpp new file mode 100644 index 000000000000..c3deffbb0636 --- /dev/null +++ b/benchmark/set/unsigned/access.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "generator.ipp" +#include "../access.ipp" diff --git a/benchmark/set/unsigned/generator.ipp b/benchmark/set/unsigned/generator.ipp new file mode 100644 index 000000000000..2a2a2a0fb627 --- /dev/null +++ b/benchmark/set/unsigned/generator.ipp @@ -0,0 +1,32 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include <random> +#include <vector> +#include <cassert> +#include <functional> +#include <algorithm> + +#define GENERATOR_T generate_unsigned + +namespace { + +struct GENERATOR_T +{ + auto operator() (std::size_t runs) const + { + assert(runs > 0); + auto engine = std::default_random_engine{42}; + auto dist = std::uniform_int_distribution<unsigned>{}; + auto r = std::vector<unsigned>(runs); + std::generate_n(r.begin(), runs, std::bind(dist, engine)); + return r; + } +}; + +} // namespace diff --git a/benchmark/set/unsigned/insert.cpp b/benchmark/set/unsigned/insert.cpp new file mode 100644 index 000000000000..26dfbce29204 --- /dev/null +++ b/benchmark/set/unsigned/insert.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "generator.ipp" +#include "../insert.ipp" diff --git a/benchmark/set/unsigned/iter.cpp b/benchmark/set/unsigned/iter.cpp new file mode 100644 index 000000000000..83e57e7845d3 --- /dev/null +++ b/benchmark/set/unsigned/iter.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "generator.ipp" +#include "../iter.ipp" diff --git a/benchmark/vector/access.hpp b/benchmark/vector/access.hpp new file mode 100644 index 000000000000..4dff7a667f33 --- /dev/null +++ b/benchmark/vector/access.hpp @@ -0,0 +1,261 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include "benchmark/vector/common.hpp" + +#include <immer/algorithm.hpp> + +#if IMMER_BENCHMARK_BOOST_COROUTINE +#include <boost/coroutine2/all.hpp> +#endif + +namespace { + +template <typename Vektor> +auto benchmark_access_reduce_chunkedseq() +{ + return [] (nonius::parameters params) + { + auto n = params.get<N>(); + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v.push_back(i); + return [=] { + auto init = 0u; + v.for_each_segment([&] (auto first, auto last) { + init = std::accumulate(first, last, init); + }); + return init; + }; + }; +} + +template <typename Vektor> +auto benchmark_access_iter_std() +{ + return [] (nonius::parameters params) + { + auto n = params.get<N>(); + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v.push_back(i); + return [=] { + auto volatile x = std::accumulate(v.begin(), v.end(), 0u); + return x; + }; + }; +} + +template <typename Vektor> +auto benchmark_access_idx_std() +{ + return [] (nonius::parameters params) + { + auto n = params.get<N>(); + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v.push_back(i); + return [=] { + auto r = 0u; + for (auto i = 0u; i < n; ++i) + r += v[i]; + volatile auto rr = r; + return rr; + }; + }; +} + +template <typename Vektor> +auto benchmark_access_random_std() +{ + return [] (nonius::parameters params) + { + auto n = params.get<N>(); + auto v = Vektor{}; + auto g = make_generator(n); + for (auto i = 0u; i < n; ++i) + v.push_back(i); + return [=] { + auto r = 0u; + for (auto i = 0u; i < n; ++i) + r += v[g[i]]; + volatile auto rr = r; + return rr; + }; + }; +} + +template <typename Vektor, typename PushFn=push_back_fn> +auto benchmark_access_iter() +{ + return [] (nonius::parameters params) + { + auto n = params.get<N>(); + + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v = PushFn{}(std::move(v), i); + + return [=] { + auto volatile x = std::accumulate(v.begin(), v.end(), 0u); + return x; + }; + }; +} + +#if IMMER_BENCHMARK_BOOST_COROUTINE +template <typename Vektor, typename PushFn=push_back_fn> +auto benchmark_access_coro() +{ + return [] (nonius::parameters params) + { + using coro_t = typename boost::coroutines2::coroutine<int>; + + auto n = params.get<N>(); + + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v = PushFn{}(std::move(v), i); + + return [=] { + auto c = coro_t::pull_type { [&](auto& sink) { + v.for_each_chunk([&](auto f, auto l) { + for (; f != l; ++f) + sink(*f); + }); + }}; + auto volatile x = std::accumulate(begin(c), end(c), 0u); + return x; + }; + }; +} +#endif + +template <typename Vektor, + typename PushFn=push_back_fn> +auto benchmark_access_idx() +{ + return [] (nonius::parameters params) + { + auto n = params.get<N>(); + + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v = PushFn{}(std::move(v), i); + + return [=] { + auto r = 0u; + for (auto i = 0u; i < n; ++i) + r += v[i]; + volatile auto rr = r; + return rr; + }; + }; +} + +template <typename Vektor, + typename PushFn=push_back_fn> +auto benchmark_access_reduce() +{ + return [] (nonius::parameters params) + { + auto n = params.get<N>(); + + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v = PushFn{}(std::move(v), i); + + return [=] { + auto volatile x = immer::accumulate(v, 0u); + return x; + }; + }; +} + +template <typename Vektor, + typename PushFn=push_back_fn> +auto benchmark_access_reduce_range() +{ + return [] (nonius::parameters params) + { + auto n = params.get<N>(); + + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v = PushFn{}(std::move(v), i); + + return [=] { + auto volatile x = immer::accumulate(v.begin(), v.end(), 0u); + return x; + }; + }; +} + +template <typename Vektor, + typename PushFn=push_back_fn> +auto benchmark_access_random() +{ + return [] (nonius::parameters params) + { + auto n = params.get<N>(); + + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v = PushFn{}(std::move(v), i); + auto g = make_generator(n); + + return [=] { + auto r = 0u; + for (auto i = 0u; i < n; ++i) + r += v[g[i]]; + volatile auto rr = r; + return rr; + }; + }; +} + +template <typename Fn> +auto benchmark_access_librrb(Fn maker) +{ + return + [=] (nonius::parameters params) { + auto n = params.get<N>(); + auto v = maker(n); + return + [=] { + auto r = 0u; + for (auto i = 0u; i < n; ++i) + r += reinterpret_cast<unsigned long>(rrb_nth(v, i)); + volatile auto rr = r; + return rr; + }; + }; +} + +template <typename Fn> +auto benchmark_access_random_librrb(Fn maker) +{ + return + [=] (nonius::parameters params) { + auto n = params.get<N>(); + auto v = maker(n); + auto g = make_generator(n); + return + [=] { + auto r = 0u; + for (auto i = 0u; i < n; ++i) + r += reinterpret_cast<unsigned long>(rrb_nth(v, g[i])); + volatile auto rr = r; + return rr; + }; + }; +} + +} // anonymous namespace diff --git a/benchmark/vector/assoc.hpp b/benchmark/vector/assoc.hpp new file mode 100644 index 000000000000..5619d7ee6936 --- /dev/null +++ b/benchmark/vector/assoc.hpp @@ -0,0 +1,245 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include "benchmark/vector/common.hpp" + +namespace { + +template <typename Vektor> +auto benchmark_assoc_std() +{ + return + [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + auto v = Vektor(n, 0); + std::iota(v.begin(), v.end(), 0u); + auto all = std::vector<Vektor>(meter.runs(), v); + meter.measure([&] (int iter) { + auto& r = all[iter]; + for (auto i = 0u; i < n; ++i) + r[i] = n - i; + return r; + }); + }; +} + +template <typename Vektor> +auto benchmark_assoc_random_std() +{ + return + [](nonius::chronometer meter) + { + auto n = meter.param<N>(); + auto g = make_generator(n); + auto v = Vektor(n, 0); + std::iota(v.begin(), v.end(), 0u); + auto all = std::vector<Vektor>(meter.runs(), v); + meter.measure([&] (int iter) { + auto& r = all[iter]; + for (auto i = 0u; i < n; ++i) + r[g[i]] = n - i; + return r; + }); + }; +} + +template <typename Vektor, + typename PushFn=push_back_fn, + typename SetFn=set_fn> +auto benchmark_assoc() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + if (n > get_limit<Vektor>{}) + nonius::skip(); + + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v = PushFn{}(std::move(v), i); + + measure(meter, [&] { + auto r = v; + for (auto i = 0u; i < n; ++i) + r = SetFn{}(r, i, n - i); + return r; + }); + }; +} + +template <typename Vektor, + typename PushFn=push_back_fn> +auto benchmark_assoc_move() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + if (n > get_limit<Vektor>{}) + nonius::skip(); + + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v = PushFn{}(std::move(v), i); + + measure(meter, [&] { + auto r = v; + for (auto i = 0u; i < n; ++i) + r = std::move(r).set(i, n - i); + return r; + }); + }; +} + +template <typename Vektor, + typename PushFn=push_back_fn, + typename SetFn=set_fn> +auto benchmark_assoc_random() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + if (n > get_limit<Vektor>{}) + nonius::skip(); + + auto g = make_generator(n); + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v = PushFn{}(std::move(v), i); + + measure(meter, [&] { + auto r = v; + for (auto i = 0u; i < n; ++i) + r = SetFn{}(r, g[i], i); + return r; + }); + }; +} + +template <typename Vektor, + typename PushFn=push_back_fn> +auto benchmark_assoc_mut() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + if (n > get_limit<Vektor>{}) + nonius::skip(); + + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v = PushFn{}(std::move(v), i); + + measure(meter, [&] { + auto r = v.transient(); + for (auto i = 0u; i < n; ++i) + r.set(i, n - i); + return r; + }); + }; +} + +template <typename Vektor, + typename PushFn=push_back_fn> +auto benchmark_assoc_mut_random() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + if (n > get_limit<Vektor>{}) + nonius::skip(); + + auto g = make_generator(n); + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v = PushFn{}(std::move(v), i); + + measure(meter, [&] { + auto r = v.transient(); + for (auto i = 0u; i < n; ++i) + r.set(g[i], i); + return r; + }); + }; +} + +template <typename Fn> +auto benchmark_assoc_librrb(Fn maker) +{ + return + [=] (nonius::chronometer meter) { + auto n = meter.param<N>(); + auto v = maker(n); + measure( + meter, [&] { + auto r = v; + for (auto i = 0u; i < n; ++i) + r = rrb_update(r, i, reinterpret_cast<void*>(n - i)); + return r; + }); + }; +} + +template <typename Fn> +auto benchmark_assoc_random_librrb(Fn maker) +{ + return + [=] (nonius::chronometer meter) { + auto n = meter.param<N>(); + auto v = maker(n); + auto g = make_generator(n); + measure( + meter, [&] { + auto r = v; + for (auto i = 0u; i < n; ++i) + r = rrb_update(r, g[i], reinterpret_cast<void*>(i)); + return r; + }); + }; +} + +template <typename Fn> +auto benchmark_assoc_mut_librrb(Fn maker) +{ + return + [=] (nonius::chronometer meter) { + auto n = meter.param<N>(); + auto v = maker(n); + measure( + meter, [&] { + auto r = rrb_to_transient(v); + for (auto i = 0u; i < n; ++i) + r = transient_rrb_update( + r, i, reinterpret_cast<void*>(i)); + return r; + }); + }; +} + +template <typename Fn> +auto benchmark_assoc_mut_random_librrb(Fn maker) +{ + return + [=] (nonius::chronometer meter) { + auto n = meter.param<N>(); + auto v = maker(n); + auto g = make_generator(n); + measure( + meter, [&] { + auto r = rrb_to_transient(v); + for (auto i = 0u; i < n; ++i) + r = transient_rrb_update( + r, g[i], reinterpret_cast<void*>(i)); + return r; + }); + }; +} + +} // anonymous namespace diff --git a/benchmark/vector/branching/access.ipp b/benchmark/vector/branching/access.ipp new file mode 100644 index 000000000000..bd7f985d4df0 --- /dev/null +++ b/benchmark/vector/branching/access.ipp @@ -0,0 +1,20 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "benchmark/vector/access.hpp" +#include <immer/flex_vector.hpp> + +#ifndef MEMORY_T +#error "define the MEMORY_T" +#endif + +NONIUS_BENCHMARK("flex/3", benchmark_access_idx<immer::flex_vector<std::size_t,MEMORY_T,3>>()) +NONIUS_BENCHMARK("flex/4", benchmark_access_idx<immer::flex_vector<std::size_t,MEMORY_T,4>>()) +NONIUS_BENCHMARK("flex/5", benchmark_access_idx<immer::flex_vector<std::size_t,MEMORY_T,5>>()) +NONIUS_BENCHMARK("flex/6", benchmark_access_idx<immer::flex_vector<std::size_t,MEMORY_T,6>>()) +NONIUS_BENCHMARK("flex/7", benchmark_access_idx<immer::flex_vector<std::size_t,MEMORY_T,7>>()) diff --git a/benchmark/vector/branching/assoc.ipp b/benchmark/vector/branching/assoc.ipp new file mode 100644 index 000000000000..4aa9984f9275 --- /dev/null +++ b/benchmark/vector/branching/assoc.ipp @@ -0,0 +1,20 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "benchmark/vector/assoc.hpp" +#include <immer/flex_vector.hpp> + +#ifndef MEMORY_T +#error "define the MEMORY_T" +#endif + +NONIUS_BENCHMARK("flex/3", benchmark_assoc<immer::flex_vector<std::size_t,MEMORY_T,3>>()) +NONIUS_BENCHMARK("flex/4", benchmark_assoc<immer::flex_vector<std::size_t,MEMORY_T,4>>()) +NONIUS_BENCHMARK("flex/5", benchmark_assoc<immer::flex_vector<std::size_t,MEMORY_T,5>>()) +NONIUS_BENCHMARK("flex/6", benchmark_assoc<immer::flex_vector<std::size_t,MEMORY_T,6>>()) +NONIUS_BENCHMARK("flex/7", benchmark_assoc<immer::flex_vector<std::size_t,MEMORY_T,7>>()) diff --git a/benchmark/vector/branching/basic/access.cpp b/benchmark/vector/branching/basic/access.cpp new file mode 100644 index 000000000000..23eb25565da0 --- /dev/null +++ b/benchmark/vector/branching/basic/access.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#define MEMORY_T basic_memory +#include "../access.ipp" diff --git a/benchmark/vector/branching/basic/assoc.cpp b/benchmark/vector/branching/basic/assoc.cpp new file mode 100644 index 000000000000..210a432abab2 --- /dev/null +++ b/benchmark/vector/branching/basic/assoc.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#define MEMORY_T basic_memory +#include "../assoc.ipp" diff --git a/benchmark/vector/branching/basic/concat.cpp b/benchmark/vector/branching/basic/concat.cpp new file mode 100644 index 000000000000..21163bdc0b94 --- /dev/null +++ b/benchmark/vector/branching/basic/concat.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#define MEMORY_T basic_memory +#include "../concat.ipp" diff --git a/benchmark/vector/branching/basic/push.cpp b/benchmark/vector/branching/basic/push.cpp new file mode 100644 index 000000000000..6be28f9219f5 --- /dev/null +++ b/benchmark/vector/branching/basic/push.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#define MEMORY_T basic_memory +#include "../push.ipp" diff --git a/benchmark/vector/branching/concat.ipp b/benchmark/vector/branching/concat.ipp new file mode 100644 index 000000000000..0e21ca0b111f --- /dev/null +++ b/benchmark/vector/branching/concat.ipp @@ -0,0 +1,20 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "benchmark/vector/concat.hpp" +#include <immer/flex_vector.hpp> + +#ifndef MEMORY_T +#error "define the MEMORY_T" +#endif + +NONIUS_BENCHMARK("flex/3", benchmark_concat<immer::flex_vector<std::size_t,MEMORY_T,3>>()) +NONIUS_BENCHMARK("flex/4", benchmark_concat<immer::flex_vector<std::size_t,MEMORY_T,4>>()) +NONIUS_BENCHMARK("flex/5", benchmark_concat<immer::flex_vector<std::size_t,MEMORY_T,5>>()) +NONIUS_BENCHMARK("flex/6", benchmark_concat<immer::flex_vector<std::size_t,MEMORY_T,6>>()) +NONIUS_BENCHMARK("flex/7", benchmark_concat<immer::flex_vector<std::size_t,MEMORY_T,7>>()) diff --git a/benchmark/vector/branching/gc/access.cpp b/benchmark/vector/branching/gc/access.cpp new file mode 100644 index 000000000000..cec060481c73 --- /dev/null +++ b/benchmark/vector/branching/gc/access.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#define MEMORY_T gc_memory +#include "../access.ipp" diff --git a/benchmark/vector/branching/gc/assoc.cpp b/benchmark/vector/branching/gc/assoc.cpp new file mode 100644 index 000000000000..448b2fd2ff79 --- /dev/null +++ b/benchmark/vector/branching/gc/assoc.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#define MEMORY_T gc_memory +#include "../assoc.ipp" diff --git a/benchmark/vector/branching/gc/concat.cpp b/benchmark/vector/branching/gc/concat.cpp new file mode 100644 index 000000000000..6c32ca821c8f --- /dev/null +++ b/benchmark/vector/branching/gc/concat.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#define MEMORY_T gc_memory +#include "../concat.ipp" diff --git a/benchmark/vector/branching/gc/push.cpp b/benchmark/vector/branching/gc/push.cpp new file mode 100644 index 000000000000..f1d1e33b9243 --- /dev/null +++ b/benchmark/vector/branching/gc/push.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#define MEMORY_T gc_memory +#include "../push.ipp" diff --git a/benchmark/vector/branching/push.ipp b/benchmark/vector/branching/push.ipp new file mode 100644 index 000000000000..2f92d6569220 --- /dev/null +++ b/benchmark/vector/branching/push.ipp @@ -0,0 +1,20 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "benchmark/vector/push.hpp" +#include <immer/flex_vector.hpp> + +#ifndef MEMORY_T +#error "define the MEMORY_T" +#endif + +NONIUS_BENCHMARK("flex/3", benchmark_push<immer::flex_vector<std::size_t,MEMORY_T,3>>()) +NONIUS_BENCHMARK("flex/4", benchmark_push<immer::flex_vector<std::size_t,MEMORY_T,4>>()) +NONIUS_BENCHMARK("flex/5", benchmark_push<immer::flex_vector<std::size_t,MEMORY_T,5>>()) +NONIUS_BENCHMARK("flex/6", benchmark_push<immer::flex_vector<std::size_t,MEMORY_T,6>>()) +NONIUS_BENCHMARK("flex/7", benchmark_push<immer::flex_vector<std::size_t,MEMORY_T,7>>()) diff --git a/benchmark/vector/branching/safe/access.cpp b/benchmark/vector/branching/safe/access.cpp new file mode 100644 index 000000000000..027aa1b7619e --- /dev/null +++ b/benchmark/vector/branching/safe/access.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#define MEMORY_T safe_memory +#include "../access.ipp" diff --git a/benchmark/vector/branching/safe/assoc.cpp b/benchmark/vector/branching/safe/assoc.cpp new file mode 100644 index 000000000000..c2f5b0cc2034 --- /dev/null +++ b/benchmark/vector/branching/safe/assoc.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#define MEMORY_T safe_memory +#include "../assoc.ipp" diff --git a/benchmark/vector/branching/safe/concat.cpp b/benchmark/vector/branching/safe/concat.cpp new file mode 100644 index 000000000000..3c5dbb8a70a2 --- /dev/null +++ b/benchmark/vector/branching/safe/concat.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#define MEMORY_T safe_memory +#include "../concat.ipp" diff --git a/benchmark/vector/branching/safe/push.cpp b/benchmark/vector/branching/safe/push.cpp new file mode 100644 index 000000000000..19d5bbd254ea --- /dev/null +++ b/benchmark/vector/branching/safe/push.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#define MEMORY_T safe_memory +#include "../push.ipp" diff --git a/benchmark/vector/branching/unsafe/access.cpp b/benchmark/vector/branching/unsafe/access.cpp new file mode 100644 index 000000000000..156d84e71763 --- /dev/null +++ b/benchmark/vector/branching/unsafe/access.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#define MEMORY_T unsafe_memory +#include "../access.ipp" diff --git a/benchmark/vector/branching/unsafe/assoc.cpp b/benchmark/vector/branching/unsafe/assoc.cpp new file mode 100644 index 000000000000..ff1802c0bc76 --- /dev/null +++ b/benchmark/vector/branching/unsafe/assoc.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#define MEMORY_T unsafe_memory +#include "../assoc.ipp" diff --git a/benchmark/vector/branching/unsafe/concat.cpp b/benchmark/vector/branching/unsafe/concat.cpp new file mode 100644 index 000000000000..d6d401bd483d --- /dev/null +++ b/benchmark/vector/branching/unsafe/concat.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#define MEMORY_T unsafe_memory +#include "../concat.ipp" diff --git a/benchmark/vector/branching/unsafe/push.cpp b/benchmark/vector/branching/unsafe/push.cpp new file mode 100644 index 000000000000..09ba8d7a3759 --- /dev/null +++ b/benchmark/vector/branching/unsafe/push.cpp @@ -0,0 +1,10 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#define MEMORY_T unsafe_memory +#include "../push.ipp" diff --git a/benchmark/vector/common.hpp b/benchmark/vector/common.hpp new file mode 100644 index 000000000000..c96d6d017d9c --- /dev/null +++ b/benchmark/vector/common.hpp @@ -0,0 +1,212 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include <utility> +#include <cstddef> +#include <limits> + +#include "benchmark/config.hpp" + +#if IMMER_BENCHMARK_LIBRRB +extern "C" { +#define restrict __restrict__ +#include <rrb.h> +#undef restrict +} +#include <immer/heap/gc_heap.hpp> +#endif + +namespace immer { +template <typename T, typename MP> class array; +} // namespace immer + +namespace { + +auto make_generator(std::size_t runs) +{ + assert(runs > 0); + auto engine = std::default_random_engine{42}; + auto dist = std::uniform_int_distribution<std::size_t>{0, runs-1}; + auto r = std::vector<std::size_t>(runs); + std::generate_n(r.begin(), runs, std::bind(dist, engine)); + return r; +} + +struct push_back_fn +{ + template <typename T, typename U> + auto operator() (T&& v, U&& x) + { return std::forward<T>(v).push_back(std::forward<U>(x)); } +}; + +struct push_front_fn +{ + template <typename T, typename U> + auto operator() (T&& v, U&& x) + { return std::forward<T>(v).push_front(std::forward<U>(x)); } +}; + +struct set_fn +{ + template <typename T, typename I, typename U> + decltype(auto) operator() (T&& v, I i, U&& x) + { return std::forward<T>(v).set(i, std::forward<U>(x)); } +}; + +struct store_fn +{ + template <typename T, typename I, typename U> + decltype(auto) operator() (T&& v, I i, U&& x) + { return std::forward<T>(v).store(i, std::forward<U>(x)); } +}; + +template <typename T> +struct get_limit : std::integral_constant< + std::size_t, std::numeric_limits<std::size_t>::max()> {}; + +template <typename T, typename MP> +struct get_limit<immer::array<T, MP>> : std::integral_constant< + std::size_t, 10000> {}; + +auto make_librrb_vector(std::size_t n) +{ + auto v = rrb_create(); + for (auto i = 0u; i < n; ++i) { + v = rrb_push(v, reinterpret_cast<void*>(i)); + } + return v; +} + +auto make_librrb_vector_f(std::size_t n) +{ + auto v = rrb_create(); + for (auto i = 0u; i < n; ++i) { + auto f = rrb_push(rrb_create(), + reinterpret_cast<void*>(i)); + v = rrb_concat(f, v); + } + return v; +} + + +// copied from: +// https://github.com/ivmai/bdwgc/blob/master/include/gc_allocator.h + +template <class GC_tp> +struct GC_type_traits +{ + std::false_type GC_is_ptr_free; +}; + +# define GC_DECLARE_PTRFREE(T) \ + template<> struct GC_type_traits<T> { \ + std::true_type GC_is_ptr_free; \ + } + +GC_DECLARE_PTRFREE(char); +GC_DECLARE_PTRFREE(signed char); +GC_DECLARE_PTRFREE(unsigned char); +GC_DECLARE_PTRFREE(signed short); +GC_DECLARE_PTRFREE(unsigned short); +GC_DECLARE_PTRFREE(signed int); +GC_DECLARE_PTRFREE(unsigned int); +GC_DECLARE_PTRFREE(signed long); +GC_DECLARE_PTRFREE(unsigned long); +GC_DECLARE_PTRFREE(float); +GC_DECLARE_PTRFREE(double); +GC_DECLARE_PTRFREE(long double); + +template <class IsPtrFree> +inline void* GC_selective_alloc(size_t n, IsPtrFree, bool ignore_off_page) +{ + return ignore_off_page + ? GC_MALLOC_IGNORE_OFF_PAGE(n) + : GC_MALLOC(n); +} + +template <> +inline void* GC_selective_alloc<std::true_type>(size_t n, + std::true_type, + bool ignore_off_page) +{ + return ignore_off_page + ? GC_MALLOC_ATOMIC_IGNORE_OFF_PAGE(n) + : GC_MALLOC_ATOMIC(n); +} + +template <class T> +class gc_allocator +{ +public: + typedef size_t size_type; + typedef ptrdiff_t difference_type; + typedef T* pointer; + typedef const T* const_pointer; + typedef T& reference; + typedef const T& const_reference; + typedef T value_type; + + template <class T1> struct rebind { + typedef gc_allocator<T1> other; + }; + + gc_allocator() {} + gc_allocator(const gc_allocator&) throw() {} + template <class T1> + explicit gc_allocator(const gc_allocator<T1>&) throw() {} + ~gc_allocator() throw() {} + + pointer address(reference GC_x) const { return &GC_x; } + const_pointer address(const_reference GC_x) const { return &GC_x; } + + // GC_n is permitted to be 0. The C++ standard says nothing about what + // the return value is when GC_n == 0. + T* allocate(size_type GC_n, const void* = 0) + { + GC_type_traits<T> traits; + return static_cast<T *> + (GC_selective_alloc(GC_n * sizeof(T), + traits.GC_is_ptr_free, false)); + } + + // p is not permitted to be a null pointer. + void deallocate(pointer p, size_type /* GC_n */) + { GC_FREE(p); } + + size_type max_size() const throw() + { return size_t(-1) / sizeof(T); } + + void construct(pointer p, const T& __val) { new(p) T(__val); } + void destroy(pointer p) { p->~T(); } +}; + +template<> +class gc_allocator<void> +{ + typedef size_t size_type; + typedef ptrdiff_t difference_type; + typedef void* pointer; + typedef const void* const_pointer; + typedef void value_type; + + template <class T1> struct rebind { + typedef gc_allocator<T1> other; + }; +}; + +template <class T1, class T2> +inline bool operator==(const gc_allocator<T1>&, const gc_allocator<T2>&) +{ return true; } + +template <class T1, class T2> +inline bool operator!=(const gc_allocator<T1>&, const gc_allocator<T2>&) +{ return false; } + +} // anonymous namespace diff --git a/benchmark/vector/concat.hpp b/benchmark/vector/concat.hpp new file mode 100644 index 000000000000..8656587d5dbd --- /dev/null +++ b/benchmark/vector/concat.hpp @@ -0,0 +1,166 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include "benchmark/vector/common.hpp" + +namespace { + +constexpr auto concat_steps = 10u; + +template <typename Vektor, + typename PushFn=push_back_fn> +auto benchmark_concat() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v = PushFn{}(std::move(v), i); + + measure(meter, [&] { + return v + v; + }); + }; +} + +template <typename Fn> +auto benchmark_concat_librrb(Fn maker) +{ + return + [=] (nonius::chronometer meter) { + auto n = meter.param<N>(); + auto v = maker(n); + measure(meter, [&] { + return rrb_concat(v, v); + }); + }; +} + +template <typename Vektor, + typename PushFn=push_back_fn> +auto benchmark_concat_incr() +{ + return + [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + + auto v = Vektor{}; + for (auto i = 0u; i < n / concat_steps; ++i) + v = PushFn{}(std::move(v), i); + + measure(meter, [&] { + auto r = Vektor{}; + for (auto i = 0u; i < concat_steps; ++i) + r = r + v; + return r; + }); + }; +} + +template <typename Vektor> +auto benchmark_concat_incr_mut() +{ + return + [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + + auto v = Vektor{}.transient(); + for (auto i = 0u; i < n / concat_steps; ++i) + v.push_back(i); + + measure(meter, [&] (int run) { + auto r = Vektor{}.transient(); + for (auto i = 0u; i < concat_steps; ++i) + r.append(v); + return r; + }); + }; +} + +template <typename Vektor> +auto benchmark_concat_incr_mut2() +{ + return + [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + + using transient_t = typename Vektor::transient_type; + using steps_t = std::vector<transient_t, gc_allocator<transient_t>>; + auto vs = std::vector<steps_t, gc_allocator<steps_t>>(meter.runs()); + for (auto k = 0u; k < vs.size(); ++k) { + vs[k].reserve(concat_steps); + for (auto j = 0u; j < concat_steps; ++j) { + auto vv = Vektor{}.transient(); + for (auto i = 0u; i < n / concat_steps; ++i) + vv.push_back(i); + vs[k].push_back(std::move(vv)); + } + } + measure(meter, [&] (int run) { + auto& vr = vs[run]; + auto r = Vektor{}.transient(); + assert(vr.size() == concat_steps); + for (auto i = 0u; i < concat_steps; ++i) + r.append(std::move(vr[i])); + return r; + }); + }; +} + +template <typename Vektor> +auto benchmark_concat_incr_chunkedseq() +{ + return + [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + + using steps_t = std::vector<Vektor>; + auto vs = std::vector<steps_t>(meter.runs()); + for (auto k = 0u; k < vs.size(); ++k) { + for (auto j = 0u; j < concat_steps; ++j) { + auto vv = Vektor{}; + for (auto i = 0u; i < n / concat_steps; ++i) + vv.push_back(i); + vs[k].push_back(std::move(vv)); + } + } + measure(meter, [&] (int run) { + auto& vr = vs[run]; + auto r = Vektor{}; + for (auto i = 0u; i < concat_steps; ++i) + r.concat(vr[i]); + return r; + }); + }; +} + +template <typename Fn> +auto benchmark_concat_incr_librrb(Fn maker) +{ + return + [=] (nonius::chronometer meter) { + auto n = meter.param<N>(); + auto v = maker(n / concat_steps); + measure(meter, [&] { + auto r = rrb_create(); + for (auto i = 0ul; i < concat_steps; ++i) + r = rrb_concat(r, v); + return r; + }); + }; +} + +} // anonymous namespace diff --git a/benchmark/vector/drop.hpp b/benchmark/vector/drop.hpp new file mode 100644 index 000000000000..0a525f67a50a --- /dev/null +++ b/benchmark/vector/drop.hpp @@ -0,0 +1,142 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include "benchmark/vector/common.hpp" + +namespace { + +template <typename Vektor, + typename PushFn=push_back_fn> +auto benchmark_drop() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v = PushFn{}(std::move(v), i); + + measure(meter, [&] { + for (auto i = 0u; i < n; ++i) + (void) v.drop(i); + }); + }; +} + +template <typename Vektor, + typename PushFn=push_back_fn> +auto benchmark_drop_lin() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v = PushFn{}(std::move(v), i); + + measure(meter, [&] { + auto r = v; + for (auto i = 0u; i < n; ++i) + r = r.drop(1); + return r; + }); + }; +} + +template <typename Vektor, + typename PushFn=push_back_fn> +auto benchmark_drop_move() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v = PushFn{}(std::move(v), i); + + measure(meter, [&] { + auto r = v; + for (auto i = 0u; i < n; ++i) + r = std::move(r).drop(1); + return r; + }); + }; +} + +template <typename Vektor, + typename PushFn=push_back_fn> +auto benchmark_drop_mut() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + + auto vv = Vektor{}; + for (auto i = 0u; i < n; ++i) + vv = PushFn{}(std::move(vv), i); + + measure(meter, [&] { + auto v = vv.transient(); + for (auto i = 0u; i < n; ++i) + (void) v.drop(1); + }); + }; +} + +template <typename Fn> +auto benchmark_drop_librrb(Fn make) +{ + return [=] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + auto v = make(n); + measure(meter, [&] { + for (auto i = 0u; i < n; ++i) + rrb_slice(v, i, n); + }); + }; +} + +template <typename Fn> +auto benchmark_drop_lin_librrb(Fn make) +{ + return [=] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + auto v = make(n); + measure(meter, [&] { + auto r = v; + for (auto i = 0u; i < n; ++i) + r = rrb_slice(r, 1, n); + return r; + }); + }; +} + +template <typename Fn> +auto benchmark_drop_mut_librrb(Fn make) +{ + return [=] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + auto v = make(n); + measure(meter, [&] { + auto r = rrb_to_transient(v); + for (auto i = 0u; i < n; ++i) + r = transient_rrb_slice(r, 1, n); + return r; + }); + }; +} + +} // anonymous namespace diff --git a/benchmark/vector/misc/access.cpp b/benchmark/vector/misc/access.cpp new file mode 100644 index 000000000000..9a00266a87d8 --- /dev/null +++ b/benchmark/vector/misc/access.cpp @@ -0,0 +1,94 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "benchmark/vector/access.hpp" + +#include <immer/algorithm.hpp> +#include <immer/array.hpp> +#include <immer/flex_vector.hpp> +#include <immer/vector.hpp> + +#if IMMER_BENCHMARK_EXPERIMENTAL +#include <immer/experimental/dvektor.hpp> +#endif + +#if IMMER_BENCHMARK_STEADY +#define QUARK_ASSERT_ON 0 +#include <steady/steady_vector.h> +#endif + +#include <vector> +#include <list> +#include <numeric> + +NONIUS_BENCHMARK("std::vector", benchmark_access_iter_std<std::vector<unsigned>>()) +NONIUS_BENCHMARK("std::vector/idx", benchmark_access_idx_std<std::vector<unsigned>>()) +NONIUS_BENCHMARK("std::vector/random", benchmark_access_random_std<std::vector<unsigned>>()) +NONIUS_BENCHMARK("std::list", benchmark_access_iter_std<std::list<unsigned>>()) + +#if IMMER_BENCHMARK_LIBRRB +NONIUS_BENCHMARK("librrb", benchmark_access_librrb(make_librrb_vector)) +NONIUS_BENCHMARK("librrb/F", benchmark_access_librrb(make_librrb_vector_f)) +NONIUS_BENCHMARK("librrb/random", benchmark_access_random_librrb(make_librrb_vector)) +NONIUS_BENCHMARK("librrb/F/random", benchmark_access_random_librrb(make_librrb_vector_f)) +#endif + +NONIUS_BENCHMARK("flex/5B", benchmark_access_iter<immer::flex_vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("flex/F/5B", benchmark_access_iter<immer::flex_vector<unsigned,def_memory,5>,push_front_fn>()) +NONIUS_BENCHMARK("vector/4B", benchmark_access_iter<immer::vector<unsigned,def_memory,4>>()) +NONIUS_BENCHMARK("vector/5B", benchmark_access_iter<immer::vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("vector/6B", benchmark_access_iter<immer::vector<unsigned,def_memory,6>>()) + +#if IMMER_BENCHMARK_EXPERIMENTAL +NONIUS_BENCHMARK("dvektor/4B", benchmark_access_iter<immer::dvektor<unsigned,def_memory,4>>()) +NONIUS_BENCHMARK("dvektor/5B", benchmark_access_iter<immer::dvektor<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("dvektor/6B", benchmark_access_iter<immer::dvektor<unsigned,def_memory,6>>()) +#endif + +#if IMMER_BENCHMARK_STEADY +NONIUS_BENCHMARK("steady/idx", benchmark_access_idx<steady::vector<unsigned>>()) +#endif + +NONIUS_BENCHMARK("flex/5B/idx", benchmark_access_idx<immer::flex_vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("flex/F/5B/idx", benchmark_access_idx<immer::flex_vector<unsigned,def_memory,5>,push_front_fn>()) +NONIUS_BENCHMARK("vector/4B/idx", benchmark_access_idx<immer::vector<unsigned,def_memory,4>>()) +NONIUS_BENCHMARK("vector/5B/idx", benchmark_access_idx<immer::vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("vector/6B/idx", benchmark_access_idx<immer::vector<unsigned,def_memory,6>>()) +#if IMMER_BENCHMARK_EXPERIMENTAL +NONIUS_BENCHMARK("dvektor/4B/idx", benchmark_access_idx<immer::dvektor<unsigned,def_memory,4>>()) +NONIUS_BENCHMARK("dvektor/5B/idx", benchmark_access_idx<immer::dvektor<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("dvektor/6B/idx", benchmark_access_idx<immer::dvektor<unsigned,def_memory,6>>()) +#endif + +NONIUS_BENCHMARK("flex/5B/reduce_i", benchmark_access_reduce_range<immer::flex_vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("vector/5B/reduce_i", benchmark_access_reduce_range<immer::vector<unsigned,def_memory,5>>()) + +NONIUS_BENCHMARK("flex/5B/reduce", benchmark_access_reduce<immer::flex_vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("flex/F/5B/reduce", benchmark_access_reduce<immer::flex_vector<unsigned,def_memory,5>,push_front_fn>()) +NONIUS_BENCHMARK("vector/4B/reduce", benchmark_access_reduce<immer::vector<unsigned,def_memory,4>>()) +NONIUS_BENCHMARK("vector/5B/reduce", benchmark_access_reduce<immer::vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("vector/6B/reduce", benchmark_access_reduce<immer::vector<unsigned,def_memory,6>>()) + +#if IMMER_BENCHMARK_STEADY +NONIUS_BENCHMARK("steady/random", benchmark_access_random<steady::vector<unsigned>>()) +#endif + +NONIUS_BENCHMARK("flex/5B/random", benchmark_access_random<immer::flex_vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("flex/F/5B/random", benchmark_access_random<immer::flex_vector<unsigned,def_memory,5>, push_front_fn>()) +NONIUS_BENCHMARK("vector/4B/random", benchmark_access_random<immer::vector<unsigned,def_memory,4>>()) +NONIUS_BENCHMARK("vector/5B/random", benchmark_access_random<immer::vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("vector/6B/random", benchmark_access_random<immer::vector<unsigned,def_memory,6>>()) +#if IMMER_BENCHMARK_EXPERIMENTAL +NONIUS_BENCHMARK("dvektor/4B/random", benchmark_access_random<immer::dvektor<unsigned,def_memory,4>>()) +NONIUS_BENCHMARK("dvektor/5B/random", benchmark_access_random<immer::dvektor<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("dvektor/6B/random", benchmark_access_random<immer::dvektor<unsigned,def_memory,6>>()) +#endif + +#if IMMER_BENCHMARK_BOOST_COROUTINE +NONIUS_BENCHMARK("vector/5B/coro", benchmark_access_coro<immer::vector<unsigned,def_memory,5>>()) +#endif diff --git a/benchmark/vector/misc/assoc.cpp b/benchmark/vector/misc/assoc.cpp new file mode 100644 index 000000000000..2b3d6d76b985 --- /dev/null +++ b/benchmark/vector/misc/assoc.cpp @@ -0,0 +1,119 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "benchmark/vector/assoc.hpp" + +#include <immer/array.hpp> +#include <immer/flex_vector.hpp> +#include <immer/flex_vector_transient.hpp> +#include <immer/vector.hpp> +#include <immer/vector_transient.hpp> + +#if IMMER_BENCHMARK_EXPERIMENTAL +#include <immer/experimental/dvektor.hpp> +#endif + +#include <immer/heap/gc_heap.hpp> +#include <immer/refcount/no_refcount_policy.hpp> +#include <immer/refcount/unsafe_refcount_policy.hpp> + +#include <vector> +#include <list> + +#if IMMER_BENCHMARK_STEADY +#define QUARK_ASSERT_ON 0 +#include <steady/steady_vector.h> +#endif + +#if IMMER_BENCHMARK_LIBRRB +extern "C" { +#define restrict __restrict__ +#include <rrb.h> +#undef restrict +} +#endif + +NONIUS_BENCHMARK("std::vector", benchmark_assoc_std<std::vector<unsigned>>()) +NONIUS_BENCHMARK("std::vector/random", benchmark_assoc_random_std<std::vector<unsigned>>()) + +#if IMMER_BENCHMARK_LIBRRB +NONIUS_BENCHMARK("librrb", benchmark_assoc_librrb(make_librrb_vector)) +NONIUS_BENCHMARK("librrb/F", benchmark_assoc_librrb(make_librrb_vector_f)) +NONIUS_BENCHMARK("librrb/random", benchmark_assoc_random_librrb(make_librrb_vector)) +NONIUS_BENCHMARK("t/librrb", benchmark_assoc_mut_librrb(make_librrb_vector)) +NONIUS_BENCHMARK("t/librrb/F", benchmark_assoc_mut_librrb(make_librrb_vector_f)) +NONIUS_BENCHMARK("t/librrb/random", benchmark_assoc_mut_random_librrb(make_librrb_vector)) +#endif + +#if IMMER_BENCHMARK_STEADY +NONIUS_BENCHMARK("steady", benchmark_assoc<steady::vector<unsigned>, push_back_fn, store_fn>()) +#endif + +NONIUS_BENCHMARK("flex/5B", benchmark_assoc<immer::flex_vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("flex/F/5B", benchmark_assoc<immer::flex_vector<unsigned,def_memory,5>,push_front_fn>()) + +NONIUS_BENCHMARK("flex/GC", benchmark_assoc<immer::flex_vector<unsigned,gc_memory,5>>()) +NONIUS_BENCHMARK("flex/F/GC", benchmark_assoc<immer::flex_vector<unsigned,gc_memory,5>,push_front_fn>()) +NONIUS_BENCHMARK("flex/F/GCF", benchmark_assoc<immer::flex_vector<unsigned,gcf_memory,5>,push_front_fn>()) + +NONIUS_BENCHMARK("flex_s/GC", benchmark_assoc<immer::flex_vector<std::size_t,gc_memory,5>>()) +NONIUS_BENCHMARK("flex_s/F/GC",benchmark_assoc<immer::flex_vector<std::size_t,gc_memory,5>,push_front_fn>()) +NONIUS_BENCHMARK("flex_s/F/GCF",benchmark_assoc<immer::flex_vector<std::size_t,gcf_memory,5>,push_front_fn>()) + +NONIUS_BENCHMARK("vector/4B", benchmark_assoc<immer::vector<unsigned,def_memory,4>>()) +NONIUS_BENCHMARK("vector/5B", benchmark_assoc<immer::vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("vector/6B", benchmark_assoc<immer::vector<unsigned,def_memory,6>>()) + +NONIUS_BENCHMARK("vector/GC", benchmark_assoc<immer::vector<unsigned,gc_memory,5>>()) +NONIUS_BENCHMARK("vector/NO", benchmark_assoc<immer::vector<unsigned,basic_memory,5>>()) +NONIUS_BENCHMARK("vector/UN", benchmark_assoc<immer::vector<unsigned,unsafe_memory,5>>()) + +#if IMMER_BENCHMARK_EXPERIMENTAL +NONIUS_BENCHMARK("dvektor/4B", benchmark_assoc<immer::dvektor<unsigned,def_memory,4>>()) +NONIUS_BENCHMARK("dvektor/5B", benchmark_assoc<immer::dvektor<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("dvektor/6B", benchmark_assoc<immer::dvektor<unsigned,def_memory,6>>()) + +NONIUS_BENCHMARK("dvektor/GC", benchmark_assoc<immer::dvektor<unsigned,gc_memory,5>>()) +NONIUS_BENCHMARK("dvektor/NO", benchmark_assoc<immer::dvektor<unsigned,basic_memory,5>>()) +NONIUS_BENCHMARK("dvektor/UN", benchmark_assoc<immer::dvektor<unsigned,unsafe_memory,5>>()) +#endif + +NONIUS_BENCHMARK("array", benchmark_assoc<immer::array<unsigned>>()) + +#if IMMER_BENCHMARK_STEADY +NONIUS_BENCHMARK("steady/random", benchmark_assoc_random<steady::vector<unsigned>, push_back_fn, store_fn>()) +#endif + +NONIUS_BENCHMARK("flex/5B/random", benchmark_assoc_random<immer::flex_vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("vector/4B/random", benchmark_assoc_random<immer::vector<unsigned,def_memory,4>>()) +NONIUS_BENCHMARK("vector/5B/random", benchmark_assoc_random<immer::vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("vector/6B/random", benchmark_assoc_random<immer::vector<unsigned,def_memory,6>>()) +#if IMMER_BENCHMARK_EXPERIMENTAL +NONIUS_BENCHMARK("dvektor/4B/random", benchmark_assoc_random<immer::dvektor<unsigned,def_memory,4>>()) +NONIUS_BENCHMARK("dvektor/5B/random", benchmark_assoc_random<immer::dvektor<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("dvektor/6B/random", benchmark_assoc_random<immer::dvektor<unsigned,def_memory,6>>()) +#endif +NONIUS_BENCHMARK("array/random", benchmark_assoc_random<immer::array<unsigned>>()) + +NONIUS_BENCHMARK("t/vector/5B", benchmark_assoc_mut<immer::vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("t/vector/GC", benchmark_assoc_mut<immer::vector<unsigned,gc_memory,5>>()) +NONIUS_BENCHMARK("t/vector/NO", benchmark_assoc_mut<immer::vector<unsigned,basic_memory,5>>()) +NONIUS_BENCHMARK("t/vector/UN", benchmark_assoc_mut<immer::vector<unsigned,unsafe_memory,5>>()) +NONIUS_BENCHMARK("t/flex/F/5B", benchmark_assoc_mut<immer::flex_vector<unsigned,def_memory,5>,push_front_fn>()) + +NONIUS_BENCHMARK("m/vector/5B", benchmark_assoc_move<immer::vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("m/vector/GC", benchmark_assoc_move<immer::vector<unsigned,gc_memory,5>>()) +NONIUS_BENCHMARK("m/vector/NO", benchmark_assoc_move<immer::vector<unsigned,basic_memory,5>>()) +NONIUS_BENCHMARK("m/vector/UN", benchmark_assoc_move<immer::vector<unsigned,unsafe_memory,5>>()) +NONIUS_BENCHMARK("m/flex/F/5B", benchmark_assoc_move<immer::flex_vector<unsigned,def_memory,5>,push_front_fn>()) + +NONIUS_BENCHMARK("t/vector/5B/random", benchmark_assoc_mut_random<immer::vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("t/vector/GC/random", benchmark_assoc_mut_random<immer::vector<unsigned,gc_memory,5>>()) +NONIUS_BENCHMARK("t/vector/NO/random", benchmark_assoc_mut_random<immer::vector<unsigned,basic_memory,5>>()) +NONIUS_BENCHMARK("t/vector/UN/random", benchmark_assoc_mut_random<immer::vector<unsigned,unsafe_memory,5>>()) +NONIUS_BENCHMARK("t/flex/F/5B/random", benchmark_assoc_mut_random<immer::flex_vector<unsigned,def_memory,5>,push_front_fn>()) diff --git a/benchmark/vector/misc/concat.cpp b/benchmark/vector/misc/concat.cpp new file mode 100644 index 000000000000..9bc10c5c2309 --- /dev/null +++ b/benchmark/vector/misc/concat.cpp @@ -0,0 +1,49 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "benchmark/vector/concat.hpp" + +#include <immer/flex_vector.hpp> +#include <immer/flex_vector_transient.hpp> +#include <immer/heap/gc_heap.hpp> +#include <immer/refcount/no_refcount_policy.hpp> +#include <immer/refcount/unsafe_refcount_policy.hpp> + +#if IMMER_BENCHMARK_LIBRRB +extern "C" { +#define restrict __restrict__ +#include <rrb.h> +#undef restrict +} +#endif + +#if IMMER_BENCHMARK_LIBRRB +NONIUS_BENCHMARK("librrb", benchmark_concat_librrb(make_librrb_vector)) +NONIUS_BENCHMARK("librrb/F", benchmark_concat_librrb(make_librrb_vector_f)) +NONIUS_BENCHMARK("i/librrb", benchmark_concat_incr_librrb(make_librrb_vector)) +#endif + +NONIUS_BENCHMARK("flex/4B", benchmark_concat<immer::flex_vector<unsigned,def_memory,4>>()) +NONIUS_BENCHMARK("flex/5B", benchmark_concat<immer::flex_vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("flex/6B", benchmark_concat<immer::flex_vector<unsigned,def_memory,6>>()) +NONIUS_BENCHMARK("flex/GC", benchmark_concat<immer::flex_vector<unsigned,gc_memory,5>>()) +NONIUS_BENCHMARK("flex_s/GC", benchmark_concat<immer::flex_vector<std::size_t,gc_memory,5>>()) +NONIUS_BENCHMARK("flex/NO", benchmark_concat<immer::flex_vector<unsigned,basic_memory,5>>()) +NONIUS_BENCHMARK("flex/UN", benchmark_concat<immer::flex_vector<unsigned,unsafe_memory,5>>()) + +NONIUS_BENCHMARK("flex/F/5B", benchmark_concat<immer::flex_vector<unsigned,def_memory,5>,push_front_fn>()) +NONIUS_BENCHMARK("flex/F/GC", benchmark_concat<immer::flex_vector<unsigned,gc_memory,5>,push_front_fn>()) +NONIUS_BENCHMARK("flex_s/F/GC", benchmark_concat<immer::flex_vector<std::size_t,gc_memory,5>,push_front_fn>()) + +NONIUS_BENCHMARK("i/flex/GC", benchmark_concat_incr<immer::flex_vector<unsigned,gc_memory,5>>()) +NONIUS_BENCHMARK("i/flex_s/GC", benchmark_concat_incr<immer::flex_vector<std::size_t,gc_memory,5>>()) +NONIUS_BENCHMARK("i/flex/5B", benchmark_concat_incr<immer::flex_vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("i/flex/UN", benchmark_concat_incr<immer::flex_vector<unsigned,unsafe_memory,5>>()) + +NONIUS_BENCHMARK("m/flex/GC", benchmark_concat_incr_mut<immer::flex_vector<unsigned,gc_memory,5>>()) +NONIUS_BENCHMARK("m/flex_s/GC", benchmark_concat_incr_mut<immer::flex_vector<std::size_t,gc_memory,5>>()) diff --git a/benchmark/vector/misc/drop.cpp b/benchmark/vector/misc/drop.cpp new file mode 100644 index 000000000000..c2ca48390b13 --- /dev/null +++ b/benchmark/vector/misc/drop.cpp @@ -0,0 +1,63 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "benchmark/vector/drop.hpp" + +#include <immer/flex_vector.hpp> +#include <immer/flex_vector_transient.hpp> +#include <immer/heap/gc_heap.hpp> +#include <immer/refcount/no_refcount_policy.hpp> +#include <immer/refcount/unsafe_refcount_policy.hpp> + +#if IMMER_BENCHMARK_LIBRRB +extern "C" { +#define restrict __restrict__ +#include <rrb.h> +#undef restrict +} +#endif + +#if IMMER_BENCHMARK_LIBRRB +NONIUS_BENCHMARK("librrb", benchmark_drop_librrb(make_librrb_vector)) +NONIUS_BENCHMARK("librrb/F", benchmark_drop_librrb(make_librrb_vector_f)) +NONIUS_BENCHMARK("l/librrb", benchmark_drop_lin_librrb(make_librrb_vector)) +NONIUS_BENCHMARK("l/librrb/F", benchmark_drop_lin_librrb(make_librrb_vector_f)) +NONIUS_BENCHMARK("t/librrb", benchmark_drop_mut_librrb(make_librrb_vector)) +NONIUS_BENCHMARK("t/librrb/F", benchmark_drop_mut_librrb(make_librrb_vector_f)) +#endif + +NONIUS_BENCHMARK("flex/4B", benchmark_drop<immer::flex_vector<unsigned,def_memory,4>>()) +NONIUS_BENCHMARK("flex/5B", benchmark_drop<immer::flex_vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("flex/6B", benchmark_drop<immer::flex_vector<unsigned,def_memory,6>>()) +NONIUS_BENCHMARK("flex/GC", benchmark_drop<immer::flex_vector<unsigned,gc_memory,5>>()) +NONIUS_BENCHMARK("flex/NO", benchmark_drop<immer::flex_vector<unsigned,basic_memory,5>>()) +NONIUS_BENCHMARK("flex/UN", benchmark_drop<immer::flex_vector<unsigned,unsafe_memory,5>>()) +NONIUS_BENCHMARK("flex_s/GC", benchmark_drop<immer::flex_vector<std::size_t,gc_memory,5>>()) + +NONIUS_BENCHMARK("flex/F/5B", benchmark_drop<immer::flex_vector<unsigned,def_memory,5>, push_front_fn>()) +NONIUS_BENCHMARK("flex/F/GC", benchmark_drop<immer::flex_vector<unsigned,gc_memory,5>, push_front_fn>()) +NONIUS_BENCHMARK("flex/F/GCF", benchmark_drop<immer::flex_vector<unsigned,gcf_memory,5>, push_front_fn>()) +NONIUS_BENCHMARK("flex_s/F/GC", benchmark_drop<immer::flex_vector<std::size_t,gc_memory,5>, push_front_fn>()) + +NONIUS_BENCHMARK("l/flex/5B", benchmark_drop_lin<immer::flex_vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("l/flex/GC", benchmark_drop_lin<immer::flex_vector<unsigned,gc_memory,5>>()) +NONIUS_BENCHMARK("l/flex/NO", benchmark_drop_lin<immer::flex_vector<unsigned,basic_memory,5>>()) +NONIUS_BENCHMARK("l/flex/UN", benchmark_drop_lin<immer::flex_vector<unsigned,unsafe_memory,5>>()) +NONIUS_BENCHMARK("l/flex/F/5B", benchmark_drop_lin<immer::flex_vector<unsigned,def_memory,5>, push_front_fn>()) + +NONIUS_BENCHMARK("m/flex/5B", benchmark_drop_move<immer::flex_vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("m/flex/GC", benchmark_drop_move<immer::flex_vector<unsigned,gc_memory,5>>()) +NONIUS_BENCHMARK("m/flex/NO", benchmark_drop_move<immer::flex_vector<unsigned,basic_memory,5>>()) +NONIUS_BENCHMARK("m/flex/UN", benchmark_drop_move<immer::flex_vector<unsigned,unsafe_memory,5>>()) +NONIUS_BENCHMARK("m/flex/F/5B", benchmark_drop_move<immer::flex_vector<unsigned,def_memory,5>, push_front_fn>()) + +NONIUS_BENCHMARK("t/flex/5B", benchmark_drop_mut<immer::flex_vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("t/flex/GC", benchmark_drop_mut<immer::flex_vector<unsigned,gc_memory,5>>()) +NONIUS_BENCHMARK("t/flex/NO", benchmark_drop_mut<immer::flex_vector<unsigned,basic_memory,5>>()) +NONIUS_BENCHMARK("t/flex/UN", benchmark_drop_mut<immer::flex_vector<unsigned,unsafe_memory,5>>()) +NONIUS_BENCHMARK("t/flex/F/5B", benchmark_drop_mut<immer::flex_vector<unsigned,def_memory,5>, push_front_fn>()) diff --git a/benchmark/vector/misc/push-front.cpp b/benchmark/vector/misc/push-front.cpp new file mode 100644 index 000000000000..48b98c8ee9b1 --- /dev/null +++ b/benchmark/vector/misc/push-front.cpp @@ -0,0 +1,30 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "benchmark/vector/push_front.hpp" + +#include <immer/flex_vector.hpp> + +#if IMMER_BENCHMARK_LIBRRB +extern "C" { +#define restrict __restrict__ +#include <rrb.h> +#undef restrict +} +#endif + +#if IMMER_BENCHMARK_LIBRRB +NONIUS_BENCHMARK("librrb", benchmark_push_front_librrb) +#endif +NONIUS_BENCHMARK("flex/4B", bechmark_push_front<immer::flex_vector<unsigned,def_memory,4>>()) +NONIUS_BENCHMARK("flex/5B", bechmark_push_front<immer::flex_vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("flex/6B", bechmark_push_front<immer::flex_vector<unsigned,def_memory,6>>()) +NONIUS_BENCHMARK("flex/GC", bechmark_push_front<immer::flex_vector<unsigned,gc_memory,5>>()) +NONIUS_BENCHMARK("flex_s/GC", bechmark_push_front<immer::flex_vector<std::size_t,gc_memory,5>>()) +NONIUS_BENCHMARK("flex/NO", bechmark_push_front<immer::flex_vector<unsigned,basic_memory,5>>()) +NONIUS_BENCHMARK("flex/UN", bechmark_push_front<immer::flex_vector<unsigned,unsafe_memory,5>>()) diff --git a/benchmark/vector/misc/push.cpp b/benchmark/vector/misc/push.cpp new file mode 100644 index 000000000000..98f57600bd78 --- /dev/null +++ b/benchmark/vector/misc/push.cpp @@ -0,0 +1,83 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "benchmark/vector/push.hpp" + +#include <immer/array.hpp> +#include <immer/flex_vector.hpp> +#include <immer/vector_transient.hpp> +#include <immer/vector.hpp> + +#if IMMER_BENCHMARK_EXPERIMENTAL +#include <immer/experimental/dvektor.hpp> +#endif + +#include <immer/heap/gc_heap.hpp> +#include <immer/refcount/no_refcount_policy.hpp> +#include <immer/refcount/unsafe_refcount_policy.hpp> + +#include <vector> +#include <list> +#include <numeric> + +#if IMMER_BENCHMARK_STEADY +#define QUARK_ASSERT_ON 0 +#include <steady/steady_vector.h> +#endif + +#if IMMER_BENCHMARK_LIBRRB +extern "C" { +#define restrict __restrict__ +#include <rrb.h> +#undef restrict +} +#endif + +#if IMMER_BENCHMARK_LIBRRB +NONIUS_BENCHMARK("librrb", benchmark_push_librrb) +NONIUS_BENCHMARK("t/librrb", benchmark_push_mut_librrb) +#endif + +NONIUS_BENCHMARK("std::vector", benchmark_push_mut_std<std::vector<unsigned>>()) +NONIUS_BENCHMARK("std::list", benchmark_push_mut_std<std::list<unsigned>>()) + +NONIUS_BENCHMARK("m/vector/5B", benchmark_push_move<immer::vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("m/vector/GC", benchmark_push_move<immer::vector<unsigned,gc_memory,5>>()) +NONIUS_BENCHMARK("m/vector/NO", benchmark_push_move<immer::vector<unsigned,basic_memory,5>>()) + +NONIUS_BENCHMARK("t/vector/5B", benchmark_push_mut<immer::vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("t/vector/GC", benchmark_push_mut<immer::vector<unsigned,gc_memory,5>>()) +NONIUS_BENCHMARK("t/vector/NO", benchmark_push_mut<immer::vector<unsigned,basic_memory,5>>()) +NONIUS_BENCHMARK("t/vector/UN", benchmark_push_mut<immer::vector<unsigned,unsafe_memory,5>>()) + +NONIUS_BENCHMARK("flex/5B", benchmark_push<immer::flex_vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("flex_s/GC", benchmark_push<immer::flex_vector<std::size_t,gc_memory,5>>()) + +NONIUS_BENCHMARK("vector/4B", benchmark_push<immer::vector<unsigned,def_memory,4>>()) +NONIUS_BENCHMARK("vector/5B", benchmark_push<immer::vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("vector/6B", benchmark_push<immer::vector<unsigned,def_memory,6>>()) + +NONIUS_BENCHMARK("vector/GC", benchmark_push<immer::vector<unsigned,gc_memory,5>>()) +NONIUS_BENCHMARK("vector/NO", benchmark_push<immer::vector<unsigned,basic_memory,5>>()) +NONIUS_BENCHMARK("vector/UN", benchmark_push<immer::vector<unsigned,unsafe_memory,5>>()) + +#if IMMER_BENCHMARK_EXPERIMENTAL +NONIUS_BENCHMARK("dvektor/4B", benchmark_push<immer::dvektor<unsigned,def_memory,4>>()) +NONIUS_BENCHMARK("dvektor/5B", benchmark_push<immer::dvektor<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("dvektor/6B", benchmark_push<immer::dvektor<unsigned,def_memory,6>>()) + +NONIUS_BENCHMARK("dvektor/GC", benchmark_push<immer::dvektor<unsigned,gc_memory,5>>()) +NONIUS_BENCHMARK("dvektor/NO", benchmark_push<immer::dvektor<unsigned,basic_memory,5>>()) +NONIUS_BENCHMARK("dvektor/UN", benchmark_push<immer::dvektor<unsigned,unsafe_memory,5>>()) +#endif + +NONIUS_BENCHMARK("array", benchmark_push<immer::array<unsigned>>()) + +#if IMMER_BENCHMARK_STEADY +NONIUS_BENCHMARK("steady", benchmark_push<steady::vector<unsigned>>()) +#endif diff --git a/benchmark/vector/misc/take.cpp b/benchmark/vector/misc/take.cpp new file mode 100644 index 000000000000..78f0e958db4c --- /dev/null +++ b/benchmark/vector/misc/take.cpp @@ -0,0 +1,65 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "benchmark/vector/take.hpp" + +#include <immer/vector.hpp> +#include <immer/flex_vector.hpp> +#include <immer/vector_transient.hpp> +#include <immer/flex_vector_transient.hpp> +#include <immer/heap/gc_heap.hpp> +#include <immer/refcount/no_refcount_policy.hpp> +#include <immer/refcount/unsafe_refcount_policy.hpp> + +#if IMMER_BENCHMARK_LIBRRB +extern "C" { +#define restrict __restrict__ +#include <rrb.h> +#undef restrict +} +#endif + +#if IMMER_BENCHMARK_LIBRRB +NONIUS_BENCHMARK("librrb", benchmark_take_librrb(make_librrb_vector)) +NONIUS_BENCHMARK("librrb/F", benchmark_take_librrb(make_librrb_vector_f)) +NONIUS_BENCHMARK("l/librrb", benchmark_take_lin_librrb(make_librrb_vector)) +NONIUS_BENCHMARK("l/librrb/F", benchmark_take_lin_librrb(make_librrb_vector_f)) +NONIUS_BENCHMARK("t/librrb", benchmark_take_mut_librrb(make_librrb_vector)) +NONIUS_BENCHMARK("t/librrb/F", benchmark_take_mut_librrb(make_librrb_vector_f)) +#endif + +NONIUS_BENCHMARK("vector/4B", benchmark_take<immer::vector<unsigned,def_memory,4>>()) +NONIUS_BENCHMARK("vector/5B", benchmark_take<immer::vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("vector/6B", benchmark_take<immer::vector<unsigned,def_memory,6>>()) +NONIUS_BENCHMARK("vector/GC", benchmark_take<immer::vector<unsigned,gc_memory,5>>()) +NONIUS_BENCHMARK("vector/NO", benchmark_take<immer::vector<unsigned,basic_memory,5>>()) +NONIUS_BENCHMARK("vector/UN", benchmark_take<immer::vector<unsigned,unsafe_memory,5>>()) +NONIUS_BENCHMARK("vector_s/GC", benchmark_take<immer::vector<std::size_t,gc_memory,5>>()) + +NONIUS_BENCHMARK("flex/F/5B", benchmark_take<immer::flex_vector<unsigned,def_memory,5>, push_front_fn>()) +NONIUS_BENCHMARK("flex/F/GC", benchmark_take<immer::flex_vector<unsigned,gc_memory,5>, push_front_fn>()) +NONIUS_BENCHMARK("flex/F/GCF", benchmark_take<immer::flex_vector<unsigned,gcf_memory,5>, push_front_fn>()) +NONIUS_BENCHMARK("flex_s/F/GC", benchmark_take<immer::flex_vector<std::size_t,gc_memory,5>, push_front_fn>()) + +NONIUS_BENCHMARK("l/vector/5B", benchmark_take_lin<immer::vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("l/vector/GC", benchmark_take_lin<immer::vector<unsigned,gc_memory,5>>()) +NONIUS_BENCHMARK("l/vector/NO", benchmark_take_lin<immer::vector<unsigned,basic_memory,5>>()) +NONIUS_BENCHMARK("l/vector/UN", benchmark_take_lin<immer::vector<unsigned,unsafe_memory,5>>()) +NONIUS_BENCHMARK("l/flex/F/5B", benchmark_take_lin<immer::flex_vector<unsigned,def_memory,5>, push_front_fn>()) + +NONIUS_BENCHMARK("m/vector/5B", benchmark_take_move<immer::vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("m/vector/GC", benchmark_take_move<immer::vector<unsigned,gc_memory,5>>()) +NONIUS_BENCHMARK("m/vector/NO", benchmark_take_move<immer::vector<unsigned,basic_memory,5>>()) +NONIUS_BENCHMARK("m/vector/UN", benchmark_take_move<immer::vector<unsigned,unsafe_memory,5>>()) +NONIUS_BENCHMARK("m/flex/F/5B", benchmark_take_move<immer::flex_vector<unsigned,def_memory,5>, push_front_fn>()) + +NONIUS_BENCHMARK("t/vector/5B", benchmark_take_mut<immer::vector<unsigned,def_memory,5>>()) +NONIUS_BENCHMARK("t/vector/GC", benchmark_take_mut<immer::vector<unsigned,gc_memory,5>>()) +NONIUS_BENCHMARK("t/vector/NO", benchmark_take_mut<immer::vector<unsigned,basic_memory,5>>()) +NONIUS_BENCHMARK("t/vector/UN", benchmark_take_mut<immer::vector<unsigned,unsafe_memory,5>>()) +NONIUS_BENCHMARK("t/flex/F/5B", benchmark_take_mut<immer::flex_vector<unsigned,def_memory,5>, push_front_fn>()) diff --git a/benchmark/vector/paper/access.cpp b/benchmark/vector/paper/access.cpp new file mode 100644 index 000000000000..db677a1adb80 --- /dev/null +++ b/benchmark/vector/paper/access.cpp @@ -0,0 +1,31 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "benchmark/vector/access.hpp" +#include <immer/flex_vector.hpp> +#include <chunkedseq/chunkedseq.hpp> + +NONIUS_BENCHMARK("idx owrs", benchmark_access_idx<immer::flex_vector<unsigned,def_memory>>()) +NONIUS_BENCHMARK("idx librrb", benchmark_access_librrb(make_librrb_vector)) +NONIUS_BENCHMARK("idx relaxed owrs", benchmark_access_idx<immer::flex_vector<unsigned,def_memory>,push_front_fn>()) +NONIUS_BENCHMARK("idx relaxed librrb", benchmark_access_librrb(make_librrb_vector_f)) +NONIUS_BENCHMARK("idx std::vector", benchmark_access_idx_std<std::vector<unsigned>>()) +NONIUS_BENCHMARK("idx chunkedseq32", benchmark_access_idx_std<pasl::data::chunkedseq::bootstrapped::deque<unsigned, 32>>()) +NONIUS_BENCHMARK("idx chunkedseq", benchmark_access_idx_std<pasl::data::chunkedseq::bootstrapped::deque<unsigned>>()) + +NONIUS_BENCHMARK("iter orws", benchmark_access_iter<immer::flex_vector<unsigned,def_memory>>()) +NONIUS_BENCHMARK("iter relaxed orws", benchmark_access_iter<immer::flex_vector<unsigned,def_memory>,push_front_fn>()) +NONIUS_BENCHMARK("iter chunkedseq32", benchmark_access_iter_std<pasl::data::chunkedseq::bootstrapped::deque<unsigned, 32>>()) +NONIUS_BENCHMARK("iter chunkedseq", benchmark_access_iter_std<pasl::data::chunkedseq::bootstrapped::deque<unsigned>>()) + +NONIUS_BENCHMARK("reduce owrs", benchmark_access_reduce<immer::flex_vector<unsigned,def_memory>>()) +NONIUS_BENCHMARK("reduce relaxed owrs", benchmark_access_reduce<immer::flex_vector<unsigned,def_memory>,push_front_fn>()) +NONIUS_BENCHMARK("reduce chunkedseq32", benchmark_access_reduce_chunkedseq<pasl::data::chunkedseq::bootstrapped::deque<unsigned, 32>>()) +NONIUS_BENCHMARK("reduce chunkedseq", benchmark_access_reduce_chunkedseq<pasl::data::chunkedseq::bootstrapped::deque<unsigned>>()) +NONIUS_BENCHMARK("reduce std::vector", benchmark_access_iter_std<std::vector<unsigned>>()) +NONIUS_BENCHMARK("reduce std::list", benchmark_access_iter_std<std::list<unsigned>>()) diff --git a/benchmark/vector/paper/assoc-random.cpp b/benchmark/vector/paper/assoc-random.cpp new file mode 100644 index 000000000000..becd4dc0c5b4 --- /dev/null +++ b/benchmark/vector/paper/assoc-random.cpp @@ -0,0 +1,40 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "benchmark/vector/assoc.hpp" +#include <immer/flex_vector.hpp> +#include <immer/flex_vector_transient.hpp> +#include <chunkedseq/chunkedseq.hpp> + +NONIUS_BENCHMARK("ours/basic", benchmark_assoc_random<immer::flex_vector<unsigned,basic_memory>>()) +NONIUS_BENCHMARK("ours/safe", benchmark_assoc_random<immer::flex_vector<unsigned,def_memory>>()) +NONIUS_BENCHMARK("ours/unsafe", benchmark_assoc_random<immer::flex_vector<unsigned,unsafe_memory>>()) +NONIUS_BENCHMARK("ours/gc", benchmark_assoc_random<immer::flex_vector<unsigned,gc_memory>>()) +NONIUS_BENCHMARK("librrb", benchmark_assoc_random_librrb(make_librrb_vector)) + +NONIUS_BENCHMARK("relaxed ours/basic", benchmark_assoc_random<immer::flex_vector<unsigned,basic_memory>,push_front_fn>()) +NONIUS_BENCHMARK("relaxed ours/safe", benchmark_assoc_random<immer::flex_vector<unsigned,def_memory>,push_front_fn>()) +NONIUS_BENCHMARK("relaxed ours/unsafe", benchmark_assoc_random<immer::flex_vector<unsigned,unsafe_memory>,push_front_fn>()) +NONIUS_BENCHMARK("relaxed ours/gc", benchmark_assoc_random<immer::flex_vector<unsigned,gc_memory>,push_front_fn>()) +NONIUS_BENCHMARK("relaxed librrb", benchmark_assoc_random_librrb(make_librrb_vector_f)) + +NONIUS_BENCHMARK("transient ours/basic", benchmark_assoc_mut_random<immer::flex_vector<unsigned,basic_memory>>()) +NONIUS_BENCHMARK("transient ours/safe", benchmark_assoc_mut_random<immer::flex_vector<unsigned,def_memory>>()) +NONIUS_BENCHMARK("transient ours/unsafe", benchmark_assoc_mut_random<immer::flex_vector<unsigned,unsafe_memory>>()) +NONIUS_BENCHMARK("transient ours/gc", benchmark_assoc_mut_random<immer::flex_vector<unsigned,gc_memory>>()) +NONIUS_BENCHMARK("transient librrb", benchmark_assoc_mut_random_librrb(make_librrb_vector)) + +NONIUS_BENCHMARK("transient relaxed ours/basic", benchmark_assoc_mut_random<immer::flex_vector<unsigned,basic_memory>,push_back_fn>()) +NONIUS_BENCHMARK("transient relaxed ours/safe", benchmark_assoc_mut_random<immer::flex_vector<unsigned,def_memory>,push_back_fn>()) +NONIUS_BENCHMARK("transient relaxed ours/unsafe", benchmark_assoc_mut_random<immer::flex_vector<unsigned,unsafe_memory>,push_back_fn>()) +NONIUS_BENCHMARK("transient relaxed ours/gc", benchmark_assoc_mut_random<immer::flex_vector<unsigned,gc_memory>,push_back_fn>()) +NONIUS_BENCHMARK("transient relaxed librrb", benchmark_assoc_mut_random_librrb(make_librrb_vector_f)) + +NONIUS_BENCHMARK("transient std::vector", benchmark_assoc_random_std<std::vector<unsigned>>()) +NONIUS_BENCHMARK("transient chunkedseq32", benchmark_assoc_random_std<pasl::data::chunkedseq::bootstrapped::deque<unsigned>>()) +NONIUS_BENCHMARK("transient chunkedseq", benchmark_assoc_random_std<pasl::data::chunkedseq::bootstrapped::deque<unsigned, 32>>()) diff --git a/benchmark/vector/paper/assoc.cpp b/benchmark/vector/paper/assoc.cpp new file mode 100644 index 000000000000..fe682ce74934 --- /dev/null +++ b/benchmark/vector/paper/assoc.cpp @@ -0,0 +1,40 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "benchmark/vector/assoc.hpp" +#include <immer/flex_vector.hpp> +#include <immer/flex_vector_transient.hpp> +#include <chunkedseq/chunkedseq.hpp> + +NONIUS_BENCHMARK("ours/basic", benchmark_assoc<immer::flex_vector<unsigned,basic_memory>>()) +NONIUS_BENCHMARK("ours/safe", benchmark_assoc<immer::flex_vector<unsigned,def_memory>>()) +NONIUS_BENCHMARK("ours/unsafe", benchmark_assoc<immer::flex_vector<unsigned,unsafe_memory>>()) +NONIUS_BENCHMARK("ours/gc", benchmark_assoc<immer::flex_vector<unsigned,gc_memory>>()) +NONIUS_BENCHMARK("librrb", benchmark_assoc_librrb(make_librrb_vector)) + +NONIUS_BENCHMARK("relaxed ours/basic", benchmark_assoc<immer::flex_vector<unsigned,basic_memory>,push_front_fn>()) +NONIUS_BENCHMARK("relaxed ours/safe", benchmark_assoc<immer::flex_vector<unsigned,def_memory>,push_front_fn>()) +NONIUS_BENCHMARK("relaxed ours/unsafe", benchmark_assoc<immer::flex_vector<unsigned,unsafe_memory>,push_front_fn>()) +NONIUS_BENCHMARK("relaxed ours/gc", benchmark_assoc<immer::flex_vector<unsigned,gc_memory>,push_front_fn>()) +NONIUS_BENCHMARK("relaxed librrb", benchmark_assoc_librrb(make_librrb_vector_f)) + +NONIUS_BENCHMARK("transient ours/basic", benchmark_assoc_mut<immer::flex_vector<unsigned,basic_memory>>()) +NONIUS_BENCHMARK("transient ours/safe", benchmark_assoc_mut<immer::flex_vector<unsigned,def_memory>>()) +NONIUS_BENCHMARK("transient ours/unsafe", benchmark_assoc_mut<immer::flex_vector<unsigned,unsafe_memory>>()) +NONIUS_BENCHMARK("transient ours/gc", benchmark_assoc_mut<immer::flex_vector<unsigned,gc_memory>>()) +NONIUS_BENCHMARK("transient librrb", benchmark_assoc_mut_librrb(make_librrb_vector)) + +NONIUS_BENCHMARK("transient relaxed ours/basic", benchmark_assoc_mut<immer::flex_vector<unsigned,basic_memory>,push_back_fn>()) +NONIUS_BENCHMARK("transient relaxed ours/safe", benchmark_assoc_mut<immer::flex_vector<unsigned,def_memory>,push_back_fn>()) +NONIUS_BENCHMARK("transient relaxed ours/unsafe", benchmark_assoc_mut<immer::flex_vector<unsigned,unsafe_memory>,push_back_fn>()) +NONIUS_BENCHMARK("transient relaxed ours/gc", benchmark_assoc_mut<immer::flex_vector<unsigned,gc_memory>,push_back_fn>()) +NONIUS_BENCHMARK("transient relaxed librrb", benchmark_assoc_mut_librrb(make_librrb_vector_f)) + +NONIUS_BENCHMARK("transient std::vector", benchmark_assoc_std<std::vector<unsigned>>()) +NONIUS_BENCHMARK("transient chunkedseq32", benchmark_assoc_std<pasl::data::chunkedseq::bootstrapped::deque<unsigned, 32>>()) +NONIUS_BENCHMARK("transient chunkedseq", benchmark_assoc_std<pasl::data::chunkedseq::bootstrapped::deque<unsigned>>()) diff --git a/benchmark/vector/paper/concat.cpp b/benchmark/vector/paper/concat.cpp new file mode 100644 index 000000000000..af9b3d20eda5 --- /dev/null +++ b/benchmark/vector/paper/concat.cpp @@ -0,0 +1,22 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "benchmark/vector/concat.hpp" +#include <immer/flex_vector.hpp> +#include <immer/flex_vector_transient.hpp> +#include <chunkedseq/chunkedseq.hpp> + +NONIUS_BENCHMARK("ours/basic", benchmark_concat_incr<immer::flex_vector<unsigned,basic_memory>>()) +NONIUS_BENCHMARK("ours/safe", benchmark_concat_incr<immer::flex_vector<unsigned,def_memory>>()) +NONIUS_BENCHMARK("ours/unsafe", benchmark_concat_incr<immer::flex_vector<unsigned,unsafe_memory>>()) +NONIUS_BENCHMARK("ours/gc", benchmark_concat_incr<immer::flex_vector<unsigned,gc_memory>>()) +NONIUS_BENCHMARK("librrb", benchmark_concat_incr_librrb(make_librrb_vector)) + +NONIUS_BENCHMARK("transient ours/gc", benchmark_concat_incr_mut<immer::flex_vector<unsigned,gc_memory>>()) +NONIUS_BENCHMARK("transient chunkedseq32", benchmark_concat_incr_chunkedseq<pasl::data::chunkedseq::bootstrapped::deque<unsigned, 32>>()) +NONIUS_BENCHMARK("transient chunkedseq", benchmark_concat_incr_chunkedseq<pasl::data::chunkedseq::bootstrapped::deque<unsigned>>()) diff --git a/benchmark/vector/paper/push.cpp b/benchmark/vector/paper/push.cpp new file mode 100644 index 000000000000..7c467985bb3b --- /dev/null +++ b/benchmark/vector/paper/push.cpp @@ -0,0 +1,28 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#include "benchmark/vector/push.hpp" +#include <immer/flex_vector.hpp> +#include <immer/flex_vector_transient.hpp> +#include <chunkedseq/chunkedseq.hpp> + +NONIUS_BENCHMARK("ours/basic", benchmark_push<immer::flex_vector<unsigned,basic_memory>>()) +NONIUS_BENCHMARK("ours/safe", benchmark_push<immer::flex_vector<unsigned,def_memory>>()) +NONIUS_BENCHMARK("ours/unsafe", benchmark_push<immer::flex_vector<unsigned,unsafe_memory>>()) +NONIUS_BENCHMARK("ours/gc", benchmark_push<immer::flex_vector<unsigned,gc_memory>>()) +NONIUS_BENCHMARK("librrb", benchmark_push_librrb) + +NONIUS_BENCHMARK("transient ours/basic", benchmark_push_mut<immer::flex_vector<unsigned,basic_memory>>()) +NONIUS_BENCHMARK("transient ours/safe", benchmark_push_mut<immer::flex_vector<unsigned,def_memory>>()) +NONIUS_BENCHMARK("transient ours/unsafe", benchmark_push_mut<immer::flex_vector<unsigned,unsafe_memory>>()) +NONIUS_BENCHMARK("transient ours/gc", benchmark_push_mut<immer::flex_vector<unsigned,gc_memory>>()) +NONIUS_BENCHMARK("transient librrb", benchmark_push_mut_librrb) +NONIUS_BENCHMARK("transient std::vector", benchmark_push_mut_std<std::vector<unsigned>>()) +NONIUS_BENCHMARK("transient std::list", benchmark_push_mut_std<std::list<unsigned>>()) +NONIUS_BENCHMARK("transient chunkedseq32", benchmark_push_mut_std<pasl::data::chunkedseq::bootstrapped::deque<unsigned, 32>>()) +NONIUS_BENCHMARK("transient chunkedseq", benchmark_push_mut_std<pasl::data::chunkedseq::bootstrapped::deque<unsigned>>()) diff --git a/benchmark/vector/push.hpp b/benchmark/vector/push.hpp new file mode 100644 index 000000000000..83f128c8fcc6 --- /dev/null +++ b/benchmark/vector/push.hpp @@ -0,0 +1,111 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include "benchmark/vector/common.hpp" + +namespace { + +template <typename Vektor> +auto benchmark_push_mut_std() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + if (n > get_limit<Vektor>{}) + nonius::skip(); + + measure(meter, [&] { + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v.push_back(i); + return v; + }); + }; +} + +template <typename Vektor> +auto benchmark_push_mut() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + if (n > get_limit<Vektor>{}) + nonius::skip(); + + measure(meter, [&] { + auto v = Vektor{}.transient(); + for (auto i = 0u; i < n; ++i) + v.push_back(i); + return v; + }); + }; +} + +template <typename Vektor> +auto benchmark_push_move() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + if (n > get_limit<Vektor>{}) + nonius::skip(); + + measure(meter, [&] { + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v = std::move(v).push_back(i); + return v; + }); + }; +} + +template <typename Vektor> +auto benchmark_push() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + if (n > get_limit<Vektor>{}) + nonius::skip(); + + measure(meter, [&] { + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v = v.push_back(i); + return v; + }); + }; +} + +auto benchmark_push_librrb(nonius::chronometer meter) +{ + auto n = meter.param<N>(); + + measure(meter, [&] { + auto v = rrb_create(); + for (auto i = 0u; i < n; ++i) + v = rrb_push(v, reinterpret_cast<void*>(i)); + return v; + }); +} + +auto benchmark_push_mut_librrb(nonius::chronometer meter) +{ + auto n = meter.param<N>(); + + measure(meter, [&] { + auto v = rrb_to_transient(rrb_create()); + for (auto i = 0u; i < n; ++i) + v = transient_rrb_push(v, reinterpret_cast<void*>(i)); + return v; + }); +} + +} // anonymous namespace diff --git a/benchmark/vector/push_front.hpp b/benchmark/vector/push_front.hpp new file mode 100644 index 000000000000..25ccbab0f9a6 --- /dev/null +++ b/benchmark/vector/push_front.hpp @@ -0,0 +1,46 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include "benchmark/vector/common.hpp" + +namespace { + +template <typename Vektor> +auto bechmark_push_front() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + + measure(meter, [&] { + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v = v.push_front(i); + return v; + }); + }; +} + +auto benchmark_push_front_librrb(nonius::chronometer meter) +{ + auto n = meter.param<N>(); + + measure(meter, [&] { + auto v = rrb_create(); + for (auto i = 0u; i < n; ++i) { + auto f = rrb_push(rrb_create(), + reinterpret_cast<void*>(i)); + v = rrb_concat(f, v); + } + return v; + }); +} + +} // anonymous namespace diff --git a/benchmark/vector/take.hpp b/benchmark/vector/take.hpp new file mode 100644 index 000000000000..bce5aceb0072 --- /dev/null +++ b/benchmark/vector/take.hpp @@ -0,0 +1,144 @@ +// +// immer: immutable data structures for C++ +// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente +// +// This software is distributed under the Boost Software License, Version 1.0. +// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt +// + +#pragma once + +#include "benchmark/vector/common.hpp" + +namespace { + +template <typename Vektor, + typename PushFn=push_back_fn> +auto benchmark_take() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v = PushFn{}(std::move(v), i); + + measure(meter, [&] { + for (auto i = 0u; i < n; ++i) + (void) v.take(i); + }); + }; +} + +template <typename Vektor, + typename PushFn=push_back_fn> +auto benchmark_take_lin() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v = PushFn{}(std::move(v), i); + + measure(meter, [&] { + auto r = v; + for (auto i = n; i > 0; --i) + r = r.take(i); + return r; + }); + }; +} + +template <typename Vektor, + typename PushFn=push_back_fn> +auto benchmark_take_move() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + + auto v = Vektor{}; + for (auto i = 0u; i < n; ++i) + v = PushFn{}(std::move(v), i); + + measure(meter, [&] { + auto r = v; + for (auto i = n; i > 0; --i) + r = std::move(r).take(i); + return r; + }); + }; +} + +template <typename Vektor, + typename PushFn=push_back_fn> +auto benchmark_take_mut() +{ + return [] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + + auto vv = Vektor{}; + for (auto i = 0u; i < n; ++i) + vv = PushFn{}(std::move(vv), i); + + measure(meter, [&] { + auto v = vv.transient(); + for (auto i = n; i > 0; --i) + (void) v.take(i); + }); + }; +} + +template <typename Fn> +auto benchmark_take_librrb(Fn make) +{ + return [=] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + auto v = make(n); + measure(meter, [&] { + for (auto i = 0u; i < n; ++i) + rrb_slice(v, 0, i); + }); + }; +} + +template <typename Fn> +auto benchmark_take_lin_librrb(Fn make) +{ + return [=] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + auto v = make(n); + measure( + meter, [&] { + auto r = v; + for (auto i = n; i > 0; --i) + r = rrb_slice(r, 0, i); + return r; + }); + }; +} + +template <typename Fn> +auto benchmark_take_mut_librrb(Fn make) +{ + return [=] (nonius::chronometer meter) + { + auto n = meter.param<N>(); + auto v = make(n); + measure( + meter, [&] { + auto r = rrb_to_transient(v); + for (auto i = n; i > 0; --i) + r = transient_rrb_slice(r, 0, i); + return r; + }); + }; +} + +} // anonymous namespace |