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

Change-Id: I9636a41ad44b4218293833fd3e9456d9b07c731b

22 files changed, 712 insertions, 0 deletions

diff --git a/third_party/immer/benchmark/set/access.hpp b/third_party/immer/benchmark/set/access.hpp
new file mode 100644
index 000000000000..8605c0ff453c
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/set/access.ipp b/third_party/immer/benchmark/set/access.ipp
new file mode 100644
index 000000000000..f026d9cfa736
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/set/insert.hpp b/third_party/immer/benchmark/set/insert.hpp
new file mode 100644
index 000000000000..be679b4de342
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/set/insert.ipp b/third_party/immer/benchmark/set/insert.ipp
new file mode 100644
index 000000000000..6717ccd57ea7
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/set/iter.hpp b/third_party/immer/benchmark/set/iter.hpp
new file mode 100644
index 000000000000..91dd48644367
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/set/iter.ipp b/third_party/immer/benchmark/set/iter.ipp
new file mode 100644
index 000000000000..f8c3cb9695cd
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/set/string-box/access.cpp b/third_party/immer/benchmark/set/string-box/access.cpp
new file mode 100644
index 000000000000..c3deffbb0636
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/set/string-box/generator.ipp b/third_party/immer/benchmark/set/string-box/generator.ipp
new file mode 100644
index 000000000000..9adc82e0bdc0
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/set/string-box/insert.cpp b/third_party/immer/benchmark/set/string-box/insert.cpp
new file mode 100644
index 000000000000..c5762498c23c
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/set/string-box/iter.cpp b/third_party/immer/benchmark/set/string-box/iter.cpp
new file mode 100644
index 000000000000..83e57e7845d3
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/set/string-long/access.cpp b/third_party/immer/benchmark/set/string-long/access.cpp
new file mode 100644
index 000000000000..c3deffbb0636
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/set/string-long/generator.ipp b/third_party/immer/benchmark/set/string-long/generator.ipp
new file mode 100644
index 000000000000..386364cc96fe
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/set/string-long/insert.cpp b/third_party/immer/benchmark/set/string-long/insert.cpp
new file mode 100644
index 000000000000..c5762498c23c
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/set/string-long/iter.cpp b/third_party/immer/benchmark/set/string-long/iter.cpp
new file mode 100644
index 000000000000..83e57e7845d3
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/set/string-short/access.cpp b/third_party/immer/benchmark/set/string-short/access.cpp
new file mode 100644
index 000000000000..c3deffbb0636
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/set/string-short/generator.ipp b/third_party/immer/benchmark/set/string-short/generator.ipp
new file mode 100644
index 000000000000..bd40d2d639a8
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/set/string-short/insert.cpp b/third_party/immer/benchmark/set/string-short/insert.cpp
new file mode 100644
index 000000000000..26dfbce29204
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/set/string-short/iter.cpp b/third_party/immer/benchmark/set/string-short/iter.cpp
new file mode 100644
index 000000000000..83e57e7845d3
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/set/unsigned/access.cpp b/third_party/immer/benchmark/set/unsigned/access.cpp
new file mode 100644
index 000000000000..c3deffbb0636
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/set/unsigned/generator.ipp b/third_party/immer/benchmark/set/unsigned/generator.ipp
new file mode 100644
index 000000000000..2a2a2a0fb627
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/set/unsigned/insert.cpp b/third_party/immer/benchmark/set/unsigned/insert.cpp
new file mode 100644
index 000000000000..26dfbce29204
--- /dev/null
+++ b/third_party/immer/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/third_party/immer/benchmark/set/unsigned/iter.cpp b/third_party/immer/benchmark/set/unsigned/iter.cpp
new file mode 100644
index 000000000000..83e57e7845d3
--- /dev/null
+++ b/third_party/immer/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"