wbtiger
/
foundationdb
mirror of https://github.com/apple/foundationdb.git
1
0
Fork 0
Code Issues Packages Projects Releases Wiki Activity
foundationdb/flow/IndexedSet.cpp

584 lines
17 KiB
C++
Raw Permalink Blame History

/*
* IndexedSet.cpp
*
* This source file is part of the FoundationDB open source project
*
* Copyright 2013-2022 Apple Inc. and the FoundationDB project authors
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
// At the moment, this file just contains tests. IndexedSet<> is a template
// and so all the important implementation is in the header file
#include "fmt/format.h"
#include "flow/IndexedSet.h"
#include "flow/IRandom.h"
#include "flow/ThreadPrimitives.h"
#include <cinttypes>
#include <algorithm>
#include <set>
#include <string>
#include <cstring>
#include <deque>
#include <random>
#include <type_traits>
#include "flow/TreeBenchmark.h"
#include "flow/UnitTest.h"
template <class Node>
int ISGetHeight(Node* n) {
if (!n)
return 0;
int lh = ISGetHeight(n->child[0]);
int rh = ISGetHeight(n->child[1]);
return std::max(lh, rh) + 1;
}
void indent(int depth) {
for (int i = 0; i < depth; i++)
printf(" ");
}
template <class T, class Metric>
std::pair<int, int> IndexedSet<T, Metric>::testonly_assertBalanced(typename IndexedSet<T, Metric>::Node* n,
int depth,
bool checkAVL) {
/* An IndexedSet (sub)tree n has the following invariants:
(1) BST invariant: Every descendant x of n->child[0] has x->data < n->data, and every descendant x of
n->child[1] has x->data > n->data (2) Balance invariant: n->balance is the difference between the height (greatest
distance to a descendant) of n->child[1] and the height of n->child[0] (3) AVL invariant: n->balance is -1, 0 or 1
(4) Metric invariant: n->total is the sum of the metric value with which n and each of its descendants was
inserted (5) Parent invariant: Every child x of n has x->parent==n
This function checks all of these for all descendants of n. It assumes that every node was inserted with a metric
of 3 in order to check the metric invariant. If checkAVL==false, it does not check the AVL invariant (since this is
often temporarily broken and then restored during operations, this permits checking invariants e.g. before a
rebalancing operation)
*/
if (!n && depth == 0)
n = root;
if (!n) {
return std::make_pair(0, 0);
}
bool ok = true;
for (int i = 0; i < 2; i++) {
if (n->child[i] && n->child[i]->parent != n) {
indent(depth);
printf("Parent check failed\n");
ok = false;
}
}
if (n->child[0] && !(n->child[0]->data < n->data)) {
indent(depth);
printf("Not a binary search tree\n");
ok = false;
}
if (n->child[1] && !(n->data < n->child[1]->data)) {
indent(depth);
printf("Not a binary search tree\n");
ok = false;
}
auto lp = testonly_assertBalanced(n->child[0], depth + 1, checkAVL);
auto rp = testonly_assertBalanced(n->child[1], depth + 1, checkAVL);
int lh = lp.first;
int rh = rp.first;
if (n->balance != rh - lh) {
indent(depth);
printf("Balance is incorrect %d %d %d (@%d)\n", n->balance, rh, lh, n->data);
ok = false;
}
if (checkAVL && (n->balance < -1 || n->balance > 1)) {
indent(depth);
printf("AVL invariant broken %d %d %d\n", n->balance, rh, lh);
ok = false;
}
if (n->total != lp.second + rp.second + 3) {
indent(depth);
printf("Metric totals are wrong %d != %d + %d + 3\n", n->total, lp.second, rp.second);
ok = false;
}
ASSERT(ok);
return std::make_pair(std::max(lh, rh) + 1, n->total);
}
bool operator<(std::string const& l, const char* r) {
return strcmp(l.c_str(), r) < 0;
}
bool operator<(const char* l, std::string const& r) {
return strcmp(l, r.c_str()) < 0;
}
/*IndexedSet<int,int> concat_unbalanced( IndexedSet<int,int> &&a, int v, IndexedSet<int,int> && b ) {
IndexedSet<int,int>::Node* n = new IndexedSet<int,int>::Node( std::move(v), 1, nullptr );
n->child[0] = a.root; a.root = nullptr;
n->child[1] = b.root; b.root = nullptr;
if (n->child[0]) n->child[0]->parent = n;
if (n->child[1]) n->child[1]->parent = n;
n->balance = ISGetHeight( n->child[1] ) - ISGetHeight( n->child[0] );
if (n->child[0]) n->total += n->child[0]->total;
if (n->child[1]) n->total += n->child[1]->total;
IndexedSet<int,int> s;
s.root = n;
return std::move(s);
}*/
TEST_CASE("/flow/IndexedSet/erase 400k of 1M") {
IndexedSet<int, int> is;
for (int n = 0; n < 1000000; n++)
is.insert(n, 3);
is.erase(is.lower_bound(300000), is.lower_bound(700001));
is.testonly_assertBalanced();
int count = 0;
for (auto iter = is.begin(); iter != is.end(); ++iter)
++count;
ASSERT(count * 3 == is.sumTo(is.end()));
return Void();
}
TEST_CASE("/flow/IndexedSet/random ops") {
for (int t = 0; t < 100; t++) {
IndexedSet<int, int> is;
int rr = deterministicRandom()->randomInt(0, 600) * deterministicRandom()->randomInt(0, 600);
for (int n = 0; n < rr; n++) {
if (deterministicRandom()->random01() < (double)is.sumTo(is.end()) / rr * 2)
is.erase(is.lower_bound(deterministicRandom()->randomInt(0, 10000000)));
else
is.insert(deterministicRandom()->randomInt(0, 10000000), 3);
}
int b = deterministicRandom()->randomInt(0, 10000000);
// int e = b + deterministicRandom()->randomInt(0, 10);
int e = deterministicRandom()->randomInt(0, 10000000);
if (e < b)
std::swap(b, e);
auto ib = is.lower_bound(b);
auto ie = is.lower_bound(e);
int original_count = is.sumTo(is.end()) / 3;
int original_incount = is.sumRange(ib, ie) / 3;
// printf("\n#%d Erasing %d of %d items\n", t, original_incount, original_count);
is.erase(ib, ie);
is.testonly_assertBalanced();
int count = 0, incount = 0;
for (auto i : is) {
++count;
if (i >= b && i < e) {
// printf("Remaining item: %d (%d - %d)\n", i, b, e);
incount++;
}
}
// printf("%d items remain, totalling %d\n", count, is.sumTo(is.end()));
// printf("%d items remain in erased range\n", incount);
ASSERT(incount == 0);
ASSERT(count == original_count - original_incount);
ASSERT(is.sumTo(is.end()) == count * 3);
}
return Void();
}
TEST_CASE("/flow/IndexedSet/strings") {
Map<std::string, int> myMap;
std::map<std::string, int> aMap;
myMap["Hello"] = 1;
myMap["Planet"] = 5;
for (auto i = myMap.begin(); i != myMap.end(); ++i)
aMap[i->key] = i->value;
ASSERT(myMap.find(std::string("Hello"))->value == 1);
ASSERT(myMap.find(std::string("World")) == myMap.end());
ASSERT(myMap["Hello"] == 1);
auto a = myMap.upper_bound("A")->key;
auto x = myMap.lower_bound("M")->key;
ASSERT((a + x) == (std::string) "HelloPlanet");
return Void();
}
template <typename K>
struct IndexedSetHarness {
using map = IndexedSet<K, int>;
using const_result = typename map::const_iterator;
using result = typename map::iterator;
using key_type = K;
map s;
void insert(K const& k) { s.insert(K(k), 1); }
const_result find(K const& k) const { return s.find(k); }
result find(K const& k) { return s.find(k); }
const_result not_found() const { return s.end(); }
result not_found() { return s.end(); }
const_result begin() const { return s.begin(); }
result begin() { return s.begin(); }
const_result end() const { return s.end(); }
result end() { return s.end(); }
const_result lower_bound(K const& k) const { return s.lower_bound(k); }
result lower_bound(K const& k) { return s.lower_bound(k); }
const_result upper_bound(K const& k) const { return s.upper_bound(k); }
result upper_bound(K const& k) { return s.upper_bound(k); }
void erase(K const& k) { s.erase(k); }
};
TEST_CASE("performance/map/StringRef/IndexedSet") {
Arena arena;
IndexedSetHarness<StringRef> is;
treeBenchmark(is, [&arena]() { return randomStr(arena); });
return Void();
}
TEST_CASE("performance/map/StringRef/StdMap") {
Arena arena;
MapHarness<StringRef> is;
treeBenchmark(is, [&arena]() { return randomStr(arena); });
return Void();
}
TEST_CASE("performance/map/int/IndexedSet") {
IndexedSetHarness<int> is;
treeBenchmark(is, &randomInt);
return Void();
}
TEST_CASE("performance/map/int/StdMap") {
MapHarness<int> is;
treeBenchmark(is, &randomInt);
return Void();
}
TEST_CASE("performance/flow/IndexedSet/integers") {
std::mt19937_64 urng(deterministicRandom()->randomUInt32());
std::vector<int> x;
x.reserve(1000000);
for (int i = 0; i < 1000000; i++)
x.push_back(deterministicRandom()->randomInt(0, 10000000));
IndexedSet<int, int> is;
double start = timer();
for (int i = 0; i < x.size(); i++) {
int t = x[i];
is.insert(std::move(t), 3);
}
double end = timer();
double kps = x.size() / 1000.0 / (end - start);
printf("%0.1f Kinsert/sec\n", kps);
start = timer();
for (int i = 0; i < x.size(); i++)
ASSERT(is.find(x[i]) != is.end());
end = timer();
kps = x.size() / 1000.0 / (end - start);
printf("%0.1f Kfind/sec\n", kps);
{
// std::set<int> ss;
IndexedSet<int, NoMetric> ss;
double start = timer();
for (int i = 0; i < x.size(); i++) {
int t = x[i];
ss.insert(t, NoMetric());
}
double end = timer();
printf("%0.1f Kinsert/sec (set)\n", x.size() / 1000.0 / (end - start));
start = timer();
for (int i = 0; i < x.size(); i++)
ASSERT(ss.find(x[i]) != ss.end());
end = timer();
printf("%0.1f Kfind/sec\n", x.size() / 1000.0 / (end - start));
}
for (int i = 0; i < x.size(); i++)
ASSERT(is.find(x[i]) != is.end());
ASSERT(is.find(-6) == is.end());
std::sort(x.begin(), x.end());
x.resize(std::unique(x.begin(), x.end()) - x.begin());
int i = 0;
for (auto it = is.begin(); it != is.end(); ++it, ++i)
ASSERT(*it == x[i]);
ASSERT(i == x.size());
is.testonly_assertBalanced();
std::shuffle(x.begin(), x.end(), urng);
start = timer();
for (int i = 0; i < x.size(); i++) {
is.erase(x[i]);
}
end = timer();
is.testonly_assertBalanced();
printf("%0.1f Kerase/sec\n", x.size() / 1000.0 / (end - start));
is.testonly_assertBalanced();
for (int i = 0; i < x.size() / 2; i++) {
ASSERT(is.find(x[i]) == is.end());
}
return Void();
}
TEST_CASE("performance/flow/IndexedSet/strings") {
constexpr size_t count = 1000000;
Map<std::string, int> myMap;
std::map<std::string, int> aMap;
double start, end;
int tt = 0;
std::string const hello{ "Hello" };
myMap[hello] = 1;
aMap["Hello"] = 1;
start = timer();
for (size_t i = 0; i < count; i++) {
tt += myMap.find(hello)->value;
}
end = timer();
ASSERT(tt == count);
printf("%0.1f Map.KfindStr/sec\n", count / 1000.0 / (end - start));
start = timer();
for (size_t i = 0; i < count; i++) {
aMap.find(hello);
}
end = timer();
printf("%0.1f std::map.KfindStr/sec\n", count / 1000.0 / (end - start));
return Void();
}
TEST_CASE("/flow/IndexedSets/ints") {
IndexedSet<int, int> is;
ASSERT(is.find(10) == is.end());
is.insert(10, 3);
is.testonly_assertBalanced();
ASSERT(is.find(10) != is.end());
ASSERT(is.find(20) == is.end());
is.insert(20, 3);
is.testonly_assertBalanced();
ASSERT(is.find(10) != is.end());
ASSERT(is.find(20) != is.end());
for (int i = 20; i < 200; i += 10) {
is.insert(std::move(i), 3);
is.testonly_assertBalanced();
ASSERT(is.find(i) != is.end());
}
for (int i = 10; i < 200; i += 10)
ASSERT(is.find(i) != is.end());
for (int i = 1; i < 200; i += 10)
ASSERT(is.find(i) == is.end());
for (int i = 20; i < 200; i += 10) {
is.erase(i);
is.testonly_assertBalanced();
}
ASSERT(is.find(10) != is.end());
ASSERT(is.find(20) == is.end());
// test( std::distance( is.begin(), is.end() ) == 1 );
// Only a single `10` should remain
auto i = is.begin();
ASSERT(i != is.end());
ASSERT(*i == 10);
++i;
ASSERT(i == is.end());
return Void();
}
TEST_CASE("/flow/IndexedSet/data constructor and destructor calls match") {
static int count;
count = 0;
struct Counter {
int value;
Counter(int value) : value(value) { count++; }
~Counter() { count--; }
Counter(const Counter& r) : value(r.value) { count++; }
void operator=(const Counter& r) { value = r.value; }
int compare(const Counter& r) const { return ::compare(value, r.value); }
bool operator<(const Counter& r) const { return value < r.value; }
};
IndexedSet<Counter, NoMetric> mySet;
for (int i = 0; i < 1000000; i++) {
mySet.insert(Counter(deterministicRandom()->randomInt(0, 1000000)), NoMetric());
mySet.erase(Counter(deterministicRandom()->randomInt(0, 1000000)));
}
int count2 = 0;
for (int i = 0; i < 1000000; i++)
count2 += mySet.count(Counter(i));
ASSERT(count == count2);
mySet.clear();
ASSERT(count == 0);
return Void();
}
TEST_CASE("/flow/IndexedSet/comparison to std::set") {
IndexedSet<int, int> is;
std::set<int> ss;
for (int i = 0; i < 1000000; i++) {
int p = deterministicRandom()->randomInt(0, 2000000);
is.insert(std::move(p), 1);
ss.insert(p);
}
for (int i = 0; i < 2000000; i++) {
int p = i; // deterministicRandom()->randomInt(0, 2000000);
auto sit = ss.upper_bound(p);
int snext = sit != ss.end() ? *sit : 2000000;
auto iit = is.upper_bound(p);
int inext = iit != is.end() ? *iit : 2000000;
ASSERT(snext == inext);
// if (snext != inext)
// printf("Fail %d %d %d\n", p, snext, inext);
// else
// printf("OK %d %d %d\n", p, snext, inext);
}
return Void();
}
TEST_CASE("/flow/IndexedSet/all numbers") {
IndexedSet<int, int64_t> is;
std::mt19937_64 urng(deterministicRandom()->randomUInt32());
std::vector<int> allNumbers;
allNumbers.reserve(1000000);
for (int i = 0; i < 1000000; i++)
allNumbers.push_back(i);
std::shuffle(allNumbers.begin(), allNumbers.end(), urng);
for (int i = 0; i < allNumbers.size(); i++)
is.insert(allNumbers[i], allNumbers[i]);
ASSERT(is.sumTo(is.end()) == allNumbers.size() * (allNumbers.size() - 1) / 2);
for (int i = 0; i < 100000; i++) {
int b = deterministicRandom()->randomInt(1, (int)allNumbers.size());
int64_t ntotal = int64_t(b) * (b - 1) / 2;
int64_t n = ntotal;
auto ii = is.index(n);
int ib = ii != is.end() ? *ii : 1000000;
ASSERT(ib == b);
if (ib != b) {
fmt::print("{0} {1} {2} {3} {4}\n", ib == b ? "OK" : "ERROR", n, b, ib, is.sumTo(ii));
}
}
for (int i = 0; i < 100000; i++) {
int a = deterministicRandom()->randomInt(0, (int)allNumbers.size());
int b = deterministicRandom()->randomInt(0, (int)allNumbers.size());
if (a > b)
std::swap(a, b);
int64_t itotal = is.sumRange(a, b);
// int ntotal = int64_t(b)*(b-1)/2 - int64_t(a)*(a-1)/2;
int64_t ntotal = int64_t(b - a) * (a + b - 1) / 2;
ASSERT(itotal == ntotal);
if (itotal != ntotal) {
fmt::print("{0} {1} {2}\n", itotal == ntotal ? "OK" : "ERROR", ntotal, itotal);
}
}
// double a = timer();
is.erase(is.begin(), is.end());
// a = timer() - a;
return Void();
}
template <class T>
static constexpr bool is_const_ref_v = std::is_const_v<typename std::remove_reference_t<T>>;
TEST_CASE("/flow/IndexedSet/const_iterator") {
struct Key {
int key;
explicit Key(int key) : key(key) {}
};
struct Metric {
int metric;
explicit Metric(int metric) : metric(metric) {}
};
IndexedSet<int, int64_t> is;
for (int i = 0; i < 10; ++i)
is.insert(i, 1);
IndexedSet<int, int64_t>& ncis = is;
static_assert(!is_const_ref_v<decltype(ncis)>);
static_assert(!is_const_ref_v<decltype(*ncis.begin())>);
static_assert(is_const_ref_v<decltype(*ncis.cbegin())>);
static_assert(!is_const_ref_v<decltype(*ncis.previous(ncis.end()))>);
static_assert(is_const_ref_v<decltype(*ncis.previous(ncis.cend()))>);
static_assert(!is_const_ref_v<decltype(*ncis.index(Metric{ 5 }))>);
static_assert(!is_const_ref_v<decltype(*ncis.find(Key{ 5 }))>);
static_assert(!is_const_ref_v<decltype(*ncis.upper_bound(Key{ 5 }))>);
static_assert(!is_const_ref_v<decltype(*ncis.lower_bound(Key{ 5 }))>);
static_assert(!is_const_ref_v<decltype(*ncis.lastLessOrEqual(Key{ 5 }))>);
static_assert(!is_const_ref_v<decltype(*ncis.lastItem())>);
const IndexedSet<int, int64_t>& cis = is;
static_assert(is_const_ref_v<decltype(cis)>);
static_assert(is_const_ref_v<decltype(*cis.begin())>);
static_assert(is_const_ref_v<decltype(*cis.cbegin())>);
static_assert(is_const_ref_v<decltype(*cis.previous(cis.end()))>);
static_assert(is_const_ref_v<decltype(*cis.previous(cis.cend()))>);
static_assert(is_const_ref_v<decltype(*cis.previous(ncis.end()))>);
static_assert(is_const_ref_v<decltype(*cis.previous(ncis.cend()))>);
static_assert(is_const_ref_v<decltype(*cis.index(Metric{ 5 }))>);
static_assert(is_const_ref_v<decltype(*cis.find(Key{ 5 }))>);
static_assert(is_const_ref_v<decltype(*cis.upper_bound(Key{ 5 }))>);
static_assert(is_const_ref_v<decltype(*cis.lower_bound(Key{ 5 }))>);
static_assert(is_const_ref_v<decltype(*cis.lastLessOrEqual(Key{ 5 }))>);
static_assert(is_const_ref_v<decltype(*cis.lastItem())>);
for (auto& val : ncis) {
static_assert(!is_const_ref_v<decltype(val)>);
}
for (const auto& val : ncis) {
static_assert(is_const_ref_v<decltype(val)>);
}
for (auto& val : cis) {
static_assert(is_const_ref_v<decltype(val)>);
}
return Void();
}
void forceLinkIndexedSetTests() {}
Reference in New Issue View Git Blame Copy Permalink