merge(3p/immer): Subtree merge at 'ad3e3556d' as 'third_party/immer' r/1299

Change-Id: I9636a41ad44b4218293833fd3e9456d9b07c731b

5 files changed, 161 insertions, 0 deletions

diff --git a/third_party/immer/benchmark/vector/paper/access.cpp b/third_party/immer/benchmark/vector/paper/access.cpp
new file mode 100644
index 000000000000..db677a1adb80
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/vector/paper/assoc-random.cpp b/third_party/immer/benchmark/vector/paper/assoc-random.cpp
new file mode 100644
index 000000000000..becd4dc0c5b4
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/vector/paper/assoc.cpp b/third_party/immer/benchmark/vector/paper/assoc.cpp
new file mode 100644
index 000000000000..fe682ce74934
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/vector/paper/concat.cpp b/third_party/immer/benchmark/vector/paper/concat.cpp
new file mode 100644
index 000000000000..af9b3d20eda5
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/vector/paper/push.cpp b/third_party/immer/benchmark/vector/paper/push.cpp
new file mode 100644
index 000000000000..7c467985bb3b
--- /dev/null
+++ b/third_party/immer/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>>())