2 * Copyright 2016 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>
26 #include <system_error>
28 #include <glog/logging.h>
29 #include <gtest/gtest.h>
31 #include <folly/Arena.h>
32 #include <folly/Foreach.h>
33 #include <folly/Memory.h>
34 #include <folly/String.h>
35 #include <folly/portability/GFlags.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)) sum += *it;
120 VLOG(20) << "sum = " << sum;
123 bool verifyEqual(SkipListAccessor skipList,
124 const SetType &verifier) {
125 EXPECT_EQ(verifier.size(), skipList.size());
126 FOR_EACH(it, verifier) {
127 CHECK(skipList.contains(*it)) << *it;
128 SkipListType::const_iterator iter = skipList.find(*it);
129 CHECK(iter != skipList.end());
130 EXPECT_EQ(*iter, *it);
132 EXPECT_TRUE(std::equal(verifier.begin(), verifier.end(), skipList.begin()));
136 TEST(ConcurrentSkipList, SequentialAccess) {
138 LOG(INFO) << "nodetype size=" << sizeof(SkipListNodeType);
140 auto skipList(SkipListType::create(kHeadHeight));
141 EXPECT_TRUE(skipList.first() == nullptr);
142 EXPECT_TRUE(skipList.last() == nullptr);
145 EXPECT_TRUE(skipList.contains(3));
146 EXPECT_FALSE(skipList.contains(2));
147 EXPECT_EQ(3, *skipList.first());
148 EXPECT_EQ(3, *skipList.last());
150 EXPECT_EQ(3, *skipList.find(3));
151 EXPECT_FALSE(skipList.find(3) == skipList.end());
152 EXPECT_TRUE(skipList.find(2) == skipList.end());
155 SkipListAccessor::Skipper skipper(skipList);
157 CHECK_EQ(3, *skipper);
161 EXPECT_EQ(2, *skipList.first());
162 EXPECT_EQ(3, *skipList.last());
164 EXPECT_EQ(5, *skipList.last());
166 EXPECT_EQ(5, *skipList.last());
167 auto ret = skipList.insert(9);
168 EXPECT_EQ(9, *ret.first);
169 EXPECT_TRUE(ret.second);
171 ret = skipList.insert(5);
172 EXPECT_EQ(5, *ret.first);
173 EXPECT_FALSE(ret.second);
175 EXPECT_EQ(2, *skipList.first());
176 EXPECT_EQ(9, *skipList.last());
177 EXPECT_TRUE(skipList.pop_back());
178 EXPECT_EQ(5, *skipList.last());
179 EXPECT_TRUE(skipList.pop_back());
180 EXPECT_EQ(3, *skipList.last());
185 CHECK(skipList.contains(2));
186 CHECK(skipList.contains(3));
187 CHECK(skipList.contains(5));
188 CHECK(skipList.contains(9));
189 CHECK(!skipList.contains(4));
192 auto it = skipList.lower_bound(5);
194 it = skipList.lower_bound(4);
196 it = skipList.lower_bound(9);
198 it = skipList.lower_bound(12);
199 EXPECT_FALSE(it.good());
201 it = skipList.begin();
205 SkipListAccessor::Skipper skipper(skipList);
207 EXPECT_EQ(3, skipper.data());
209 EXPECT_EQ(5, skipper.data());
210 CHECK(!skipper.to(7));
214 CHECK(skipper.to(9));
215 EXPECT_EQ(9, skipper.data());
217 CHECK(!skipList.contains(3));
219 CHECK(skipList.contains(3));
221 FOR_EACH(it, skipList) {
222 LOG(INFO) << "pos= " << pos++ << " value= " << *it;
227 auto skipList(SkipListType::create(kHeadHeight));
230 randomAdding(10000, skipList, &verifier);
231 verifyEqual(skipList, verifier);
234 SkipListAccessor::Skipper skipper(skipList);
235 int num_skips = 1000;
236 for (int i = 0; i < num_skips; ++i) {
237 int n = i * kMaxValue / num_skips;
238 bool found = skipper.to(n);
239 EXPECT_EQ(found, (verifier.find(n) != verifier.end()));
245 static std::string makeRandomeString(int len) {
247 for (int j = 0; j < len; j++) {
248 s.push_back((rand() % 26) + 'A');
253 TEST(ConcurrentSkipList, TestStringType) {
254 typedef folly::ConcurrentSkipList<std::string> SkipListT;
255 std::shared_ptr<SkipListT> skip = SkipListT::createInstance();
256 SkipListT::Accessor accessor(skip);
258 for (int i = 0; i < 100000; i++) {
259 std::string s = makeRandomeString(7);
263 EXPECT_TRUE(std::is_sorted(accessor.begin(), accessor.end()));
266 struct UniquePtrComp {
268 const std::unique_ptr<int> &x, const std::unique_ptr<int> &y) const {
269 if (!x) return false;
275 TEST(ConcurrentSkipList, TestMovableData) {
276 typedef folly::ConcurrentSkipList<std::unique_ptr<int>, UniquePtrComp>
278 auto sl = SkipListT::createInstance() ;
279 SkipListT::Accessor accessor(sl);
281 static const int N = 10;
282 for (int i = 0; i < N; ++i) {
283 accessor.insert(std::unique_ptr<int>(new int(i)));
286 for (int i = 0; i < N; ++i) {
287 EXPECT_TRUE(accessor.find(std::unique_ptr<int>(new int(i))) !=
290 EXPECT_TRUE(accessor.find(std::unique_ptr<int>(new int(N))) ==
294 void testConcurrentAdd(int numThreads) {
295 auto skipList(SkipListType::create(kHeadHeight));
297 vector<std::thread> threads;
298 vector<SetType> verifiers(numThreads);
300 for (int i = 0; i < numThreads; ++i) {
301 threads.push_back(std::thread(
302 &randomAdding, 100, skipList, &verifiers[i], kMaxValue));
304 } catch (const std::system_error& e) {
306 << "Caught " << exceptionStr(e)
307 << ": could only create " << threads.size() << " threads out of "
310 for (size_t i = 0; i < threads.size(); ++i) {
315 FOR_EACH(s, verifiers) {
316 all.insert(s->begin(), s->end());
318 verifyEqual(skipList, all);
321 TEST(ConcurrentSkipList, ConcurrentAdd) {
322 // test it many times
323 for (int numThreads = 10; numThreads < 10000; numThreads += 1000) {
324 testConcurrentAdd(numThreads);
328 void testConcurrentRemoval(int numThreads, int maxValue) {
329 auto skipList = SkipListType::create(kHeadHeight);
330 for (int i = 0; i < maxValue; ++i) {
334 vector<std::thread> threads;
335 vector<SetType > verifiers(numThreads);
337 for (int i = 0; i < numThreads; ++i) {
338 threads.push_back(std::thread(
339 &randomRemoval, 100, skipList, &verifiers[i], maxValue));
341 } catch (const std::system_error& e) {
343 << "Caught " << exceptionStr(e)
344 << ": could only create " << threads.size() << " threads out of "
347 FOR_EACH(t, threads) {
352 FOR_EACH(s, verifiers) {
353 all.insert(s->begin(), s->end());
356 CHECK_EQ(maxValue, all.size() + skipList.size());
357 for (int i = 0; i < maxValue; ++i) {
358 if (all.find(i) != all.end()) {
359 CHECK(!skipList.contains(i)) << i;
361 CHECK(skipList.contains(i)) << i;
366 TEST(ConcurrentSkipList, ConcurrentRemove) {
367 for (int numThreads = 10; numThreads < 1000; numThreads += 100) {
368 testConcurrentRemoval(numThreads, 100 * numThreads);
372 static void testConcurrentAccess(
373 int numInsertions, int numDeletions, int maxValue) {
374 auto skipList = SkipListType::create(kHeadHeight);
376 vector<SetType> verifiers(FLAGS_num_threads);
377 vector<int64_t> sums(FLAGS_num_threads);
378 vector<vector<ValueType> > skipValues(FLAGS_num_threads);
380 for (int i = 0; i < FLAGS_num_threads; ++i) {
381 for (int j = 0; j < numInsertions; ++j) {
382 skipValues[i].push_back(rand() % (maxValue + 1));
384 std::sort(skipValues[i].begin(), skipValues[i].end());
387 vector<std::thread> threads;
388 for (int i = 0; i < FLAGS_num_threads; ++i) {
392 threads.push_back(std::thread(
393 randomAdding, numInsertions, skipList, &verifiers[i], maxValue));
396 threads.push_back(std::thread(
397 randomRemoval, numDeletions, skipList, &verifiers[i], maxValue));
400 threads.push_back(std::thread(
401 concurrentSkip, &skipValues[i], skipList));
404 threads.push_back(std::thread(sumAllValues, skipList, &sums[i]));
409 FOR_EACH(t, threads) {
412 // just run through it, no need to verify the correctness.
415 TEST(ConcurrentSkipList, ConcurrentAccess) {
416 testConcurrentAccess(10000, 100, kMaxValue);
417 testConcurrentAccess(100000, 10000, kMaxValue * 10);
418 testConcurrentAccess(1000000, 100000, kMaxValue);
421 struct NonTrivialValue {
422 static std::atomic<int> InstanceCounter;
423 static const int kBadPayLoad;
425 NonTrivialValue() : payload_(kBadPayLoad) { ++InstanceCounter; }
427 explicit NonTrivialValue(int payload) : payload_(payload) {
431 NonTrivialValue(const NonTrivialValue& rhs) : payload_(rhs.payload_) {
435 NonTrivialValue& operator=(const NonTrivialValue& rhs) {
436 payload_ = rhs.payload_;
440 ~NonTrivialValue() { --InstanceCounter; }
442 bool operator<(const NonTrivialValue& rhs) const {
443 EXPECT_NE(kBadPayLoad, payload_);
444 EXPECT_NE(kBadPayLoad, rhs.payload_);
445 return payload_ < rhs.payload_;
452 std::atomic<int> NonTrivialValue::InstanceCounter(0);
453 const int NonTrivialValue::kBadPayLoad = 0xDEADBEEF;
455 template <typename SkipListPtrType>
456 void TestNonTrivialDeallocation(SkipListPtrType& list) {
458 auto accessor = typename SkipListPtrType::element_type::Accessor(list);
459 static const size_t N = 10000;
460 for (size_t i = 0; i < N; ++i) {
461 accessor.add(NonTrivialValue(i));
465 EXPECT_EQ(0, NonTrivialValue::InstanceCounter);
468 template <typename ParentAlloc>
469 void NonTrivialDeallocationWithParanoid() {
470 using Alloc = ParanoidArenaAlloc<ParentAlloc>;
472 ConcurrentSkipList<NonTrivialValue, std::less<NonTrivialValue>, Alloc>;
473 ParentAlloc parentAlloc;
474 Alloc paranoidAlloc(&parentAlloc);
475 auto list = SkipListType::createInstance(10, paranoidAlloc);
476 TestNonTrivialDeallocation(list);
477 EXPECT_TRUE(paranoidAlloc.isEmpty());
480 TEST(ConcurrentSkipList, NonTrivialDeallocationWithParanoidSysAlloc) {
481 NonTrivialDeallocationWithParanoid<SysAlloc>();
484 TEST(ConcurrentSkipList, NonTrivialDeallocationWithParanoidSysArena) {
485 NonTrivialDeallocationWithParanoid<SysArena>();
488 TEST(ConcurrentSkipList, NonTrivialDeallocationWithSysArena) {
490 ConcurrentSkipList<NonTrivialValue, std::less<NonTrivialValue>, SysArena>;
491 auto list = SkipListType::createInstance(10);
492 TestNonTrivialDeallocation(list);
497 int main(int argc, char* argv[]) {
498 testing::InitGoogleTest(&argc, argv);
499 google::InitGoogleLogging(argv[0]);
500 gflags::ParseCommandLineFlags(&argc, &argv, true);
502 return RUN_ALL_TESTS();