2 * Copyright 2011-present Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 // @author: Xin Liu <xliux@fb.com>
19 #include <folly/ConcurrentSkipList.h>
24 #include <system_error>
28 #include <glog/logging.h>
30 #include <folly/Memory.h>
31 #include <folly/String.h>
32 #include <folly/container/Foreach.h>
33 #include <folly/memory/Arena.h>
34 #include <folly/portability/GFlags.h>
35 #include <folly/portability/GTest.h>
37 DEFINE_int32(num_threads, 12, "num concurrent threads to test");
41 template <typename ParentAlloc>
42 struct ParanoidArenaAlloc {
43 explicit ParanoidArenaAlloc(ParentAlloc* arena) : arena_(arena) {}
45 void* allocate(size_t size) {
46 void* result = arena_->allocate(size);
47 allocated_.insert(result);
51 void deallocate(void* ptr) {
52 EXPECT_EQ(1, allocated_.erase(ptr));
53 arena_->deallocate(ptr);
56 bool isEmpty() const { return allocated_.empty(); }
59 std::set<void*> allocated_;
65 struct IsArenaAllocator<ParanoidArenaAlloc<SysArena>> : std::true_type {};
70 using namespace folly;
73 typedef int ValueType;
74 typedef detail::SkipListNode<ValueType> SkipListNodeType;
75 typedef ConcurrentSkipList<ValueType> SkipListType;
76 typedef SkipListType::Accessor SkipListAccessor;
77 typedef vector<ValueType> VectorType;
78 typedef std::set<ValueType> SetType;
80 static const int kHeadHeight = 2;
81 static const int kMaxValue = 5000;
83 static void randomAdding(int size,
84 SkipListAccessor skipList,
86 int maxValue = kMaxValue) {
87 for (int i = 0; i < size; ++i) {
88 int32_t r = rand() % maxValue;
94 static void randomRemoval(int size,
95 SkipListAccessor skipList,
97 int maxValue=kMaxValue) {
98 for (int i = 0; i < size; ++i) {
99 int32_t r = rand() % maxValue;
105 static void sumAllValues(SkipListAccessor skipList, int64_t *sum) {
107 FOR_EACH(it, skipList) {
110 VLOG(20) << "sum = " << sum;
113 static void concurrentSkip(const vector<ValueType> *values,
114 SkipListAccessor skipList) {
116 SkipListAccessor::Skipper skipper(skipList);
117 FOR_EACH(it, *values) {
118 if (skipper.to(*it)) {
122 VLOG(20) << "sum = " << sum;
125 bool verifyEqual(SkipListAccessor skipList,
126 const SetType &verifier) {
127 EXPECT_EQ(verifier.size(), skipList.size());
128 FOR_EACH(it, verifier) {
129 CHECK(skipList.contains(*it)) << *it;
130 SkipListType::const_iterator iter = skipList.find(*it);
131 CHECK(iter != skipList.end());
132 EXPECT_EQ(*iter, *it);
134 EXPECT_TRUE(std::equal(verifier.begin(), verifier.end(), skipList.begin()));
138 TEST(ConcurrentSkipList, SequentialAccess) {
140 LOG(INFO) << "nodetype size=" << sizeof(SkipListNodeType);
142 auto skipList(SkipListType::create(kHeadHeight));
143 EXPECT_TRUE(skipList.first() == nullptr);
144 EXPECT_TRUE(skipList.last() == nullptr);
147 EXPECT_TRUE(skipList.contains(3));
148 EXPECT_FALSE(skipList.contains(2));
149 EXPECT_EQ(3, *skipList.first());
150 EXPECT_EQ(3, *skipList.last());
152 EXPECT_EQ(3, *skipList.find(3));
153 EXPECT_FALSE(skipList.find(3) == skipList.end());
154 EXPECT_TRUE(skipList.find(2) == skipList.end());
157 SkipListAccessor::Skipper skipper(skipList);
159 CHECK_EQ(3, *skipper);
163 EXPECT_EQ(2, *skipList.first());
164 EXPECT_EQ(3, *skipList.last());
166 EXPECT_EQ(5, *skipList.last());
168 EXPECT_EQ(5, *skipList.last());
169 auto ret = skipList.insert(9);
170 EXPECT_EQ(9, *ret.first);
171 EXPECT_TRUE(ret.second);
173 ret = skipList.insert(5);
174 EXPECT_EQ(5, *ret.first);
175 EXPECT_FALSE(ret.second);
177 EXPECT_EQ(2, *skipList.first());
178 EXPECT_EQ(9, *skipList.last());
179 EXPECT_TRUE(skipList.pop_back());
180 EXPECT_EQ(5, *skipList.last());
181 EXPECT_TRUE(skipList.pop_back());
182 EXPECT_EQ(3, *skipList.last());
187 CHECK(skipList.contains(2));
188 CHECK(skipList.contains(3));
189 CHECK(skipList.contains(5));
190 CHECK(skipList.contains(9));
191 CHECK(!skipList.contains(4));
194 auto it = skipList.lower_bound(5);
196 it = skipList.lower_bound(4);
198 it = skipList.lower_bound(9);
200 it = skipList.lower_bound(12);
201 EXPECT_FALSE(it.good());
203 it = skipList.begin();
207 SkipListAccessor::Skipper skipper(skipList);
209 EXPECT_EQ(3, skipper.data());
211 EXPECT_EQ(5, skipper.data());
212 CHECK(!skipper.to(7));
216 CHECK(skipper.to(9));
217 EXPECT_EQ(9, skipper.data());
219 CHECK(!skipList.contains(3));
221 CHECK(skipList.contains(3));
223 for (auto entry : skipList) {
224 LOG(INFO) << "pos= " << pos++ << " value= " << entry;
229 auto skipList(SkipListType::create(kHeadHeight));
232 randomAdding(10000, skipList, &verifier);
233 verifyEqual(skipList, verifier);
236 SkipListAccessor::Skipper skipper(skipList);
237 int num_skips = 1000;
238 for (int i = 0; i < num_skips; ++i) {
239 int n = i * kMaxValue / num_skips;
240 bool found = skipper.to(n);
241 EXPECT_EQ(found, (verifier.find(n) != verifier.end()));
247 static std::string makeRandomeString(int len) {
249 for (int j = 0; j < len; j++) {
250 s.push_back((rand() % 26) + 'A');
255 TEST(ConcurrentSkipList, TestStringType) {
256 typedef folly::ConcurrentSkipList<std::string> SkipListT;
257 std::shared_ptr<SkipListT> skip = SkipListT::createInstance();
258 SkipListT::Accessor accessor(skip);
260 for (int i = 0; i < 100000; i++) {
261 std::string s = makeRandomeString(7);
265 EXPECT_TRUE(std::is_sorted(accessor.begin(), accessor.end()));
268 struct UniquePtrComp {
270 const std::unique_ptr<int> &x, const std::unique_ptr<int> &y) const {
281 TEST(ConcurrentSkipList, TestMovableData) {
282 typedef folly::ConcurrentSkipList<std::unique_ptr<int>, UniquePtrComp>
284 auto sl = SkipListT::createInstance() ;
285 SkipListT::Accessor accessor(sl);
287 static const int N = 10;
288 for (int i = 0; i < N; ++i) {
289 accessor.insert(std::make_unique<int>(i));
292 for (int i = 0; i < N; ++i) {
293 EXPECT_TRUE(accessor.find(std::unique_ptr<int>(new int(i))) !=
296 EXPECT_TRUE(accessor.find(std::unique_ptr<int>(new int(N))) ==
300 void testConcurrentAdd(int numThreads) {
301 auto skipList(SkipListType::create(kHeadHeight));
303 vector<std::thread> threads;
304 vector<SetType> verifiers(numThreads);
306 for (int i = 0; i < numThreads; ++i) {
307 threads.push_back(std::thread(
308 &randomAdding, 100, skipList, &verifiers[i], kMaxValue));
310 } catch (const std::system_error& e) {
312 << "Caught " << exceptionStr(e)
313 << ": could only create " << threads.size() << " threads out of "
316 for (size_t i = 0; i < threads.size(); ++i) {
321 FOR_EACH(s, verifiers) {
322 all.insert(s->begin(), s->end());
324 verifyEqual(skipList, all);
327 TEST(ConcurrentSkipList, ConcurrentAdd) {
328 // test it many times
329 for (int numThreads = 10; numThreads < 10000; numThreads += 1000) {
330 testConcurrentAdd(numThreads);
334 void testConcurrentRemoval(int numThreads, int maxValue) {
335 auto skipList = SkipListType::create(kHeadHeight);
336 for (int i = 0; i < maxValue; ++i) {
340 vector<std::thread> threads;
341 vector<SetType > verifiers(numThreads);
343 for (int i = 0; i < numThreads; ++i) {
344 threads.push_back(std::thread(
345 &randomRemoval, 100, skipList, &verifiers[i], maxValue));
347 } catch (const std::system_error& e) {
349 << "Caught " << exceptionStr(e)
350 << ": could only create " << threads.size() << " threads out of "
353 FOR_EACH(t, threads) {
358 FOR_EACH(s, verifiers) {
359 all.insert(s->begin(), s->end());
362 CHECK_EQ(maxValue, all.size() + skipList.size());
363 for (int i = 0; i < maxValue; ++i) {
364 if (all.find(i) != all.end()) {
365 CHECK(!skipList.contains(i)) << i;
367 CHECK(skipList.contains(i)) << i;
372 TEST(ConcurrentSkipList, ConcurrentRemove) {
373 for (int numThreads = 10; numThreads < 1000; numThreads += 100) {
374 testConcurrentRemoval(numThreads, 100 * numThreads);
378 static void testConcurrentAccess(
379 int numInsertions, int numDeletions, int maxValue) {
380 auto skipList = SkipListType::create(kHeadHeight);
382 vector<SetType> verifiers(FLAGS_num_threads);
383 vector<int64_t> sums(FLAGS_num_threads);
384 vector<vector<ValueType> > skipValues(FLAGS_num_threads);
386 for (int i = 0; i < FLAGS_num_threads; ++i) {
387 for (int j = 0; j < numInsertions; ++j) {
388 skipValues[i].push_back(rand() % (maxValue + 1));
390 std::sort(skipValues[i].begin(), skipValues[i].end());
393 vector<std::thread> threads;
394 for (int i = 0; i < FLAGS_num_threads; ++i) {
398 threads.push_back(std::thread(
399 randomAdding, numInsertions, skipList, &verifiers[i], maxValue));
402 threads.push_back(std::thread(
403 randomRemoval, numDeletions, skipList, &verifiers[i], maxValue));
406 threads.push_back(std::thread(
407 concurrentSkip, &skipValues[i], skipList));
410 threads.push_back(std::thread(sumAllValues, skipList, &sums[i]));
415 FOR_EACH(t, threads) {
418 // just run through it, no need to verify the correctness.
421 TEST(ConcurrentSkipList, ConcurrentAccess) {
422 testConcurrentAccess(10000, 100, kMaxValue);
423 testConcurrentAccess(100000, 10000, kMaxValue * 10);
424 testConcurrentAccess(1000000, 100000, kMaxValue);
427 struct NonTrivialValue {
428 static std::atomic<int> InstanceCounter;
429 static const int kBadPayLoad;
431 NonTrivialValue() : payload_(kBadPayLoad) { ++InstanceCounter; }
433 explicit NonTrivialValue(int payload) : payload_(payload) {
437 NonTrivialValue(const NonTrivialValue& rhs) : payload_(rhs.payload_) {
441 NonTrivialValue& operator=(const NonTrivialValue& rhs) {
442 payload_ = rhs.payload_;
446 ~NonTrivialValue() { --InstanceCounter; }
448 bool operator<(const NonTrivialValue& rhs) const {
449 EXPECT_NE(kBadPayLoad, payload_);
450 EXPECT_NE(kBadPayLoad, rhs.payload_);
451 return payload_ < rhs.payload_;
458 std::atomic<int> NonTrivialValue::InstanceCounter(0);
459 const int NonTrivialValue::kBadPayLoad = 0xDEADBEEF;
461 template <typename SkipListPtrType>
462 void TestNonTrivialDeallocation(SkipListPtrType& list) {
464 auto accessor = typename SkipListPtrType::element_type::Accessor(list);
465 static const size_t N = 10000;
466 for (size_t i = 0; i < N; ++i) {
467 accessor.add(NonTrivialValue(i));
471 EXPECT_EQ(0, NonTrivialValue::InstanceCounter);
474 template <typename ParentAlloc>
475 void NonTrivialDeallocationWithParanoid() {
476 using Alloc = ParanoidArenaAlloc<ParentAlloc>;
477 using ParanoidSkipListType =
478 ConcurrentSkipList<NonTrivialValue, std::less<NonTrivialValue>, Alloc>;
479 ParentAlloc parentAlloc;
480 Alloc paranoidAlloc(&parentAlloc);
481 auto list = ParanoidSkipListType::createInstance(10, paranoidAlloc);
482 TestNonTrivialDeallocation(list);
483 EXPECT_TRUE(paranoidAlloc.isEmpty());
486 TEST(ConcurrentSkipList, NonTrivialDeallocationWithParanoidSysAlloc) {
487 NonTrivialDeallocationWithParanoid<SysAlloc>();
490 TEST(ConcurrentSkipList, NonTrivialDeallocationWithParanoidSysArena) {
491 NonTrivialDeallocationWithParanoid<SysArena>();
494 TEST(ConcurrentSkipList, NonTrivialDeallocationWithSysArena) {
495 using SysArenaSkipListType =
496 ConcurrentSkipList<NonTrivialValue, std::less<NonTrivialValue>, SysArena>;
497 auto list = SysArenaSkipListType::createInstance(10);
498 TestNonTrivialDeallocation(list);
503 int main(int argc, char* argv[]) {
504 testing::InitGoogleTest(&argc, argv);
505 google::InitGoogleLogging(argv[0]);
506 gflags::ParseCommandLineFlags(&argc, &argv, true);
508 return RUN_ALL_TESTS();