AtomicUnorderedMapTest.cpp File Reference

#include <folly/AtomicUnorderedMap.h>
#include <memory>
#include <thread>
#include <unordered_map>
#include <folly/Benchmark.h>
#include <folly/portability/GFlags.h>
#include <folly/portability/GTest.h>
#include <folly/portability/Semaphore.h>
#include <folly/test/DeterministicSchedule.h>

Go to the source code of this file.

Classes
struct	non_atomic< T >
struct	PairHash

Typedefs
template<typename Key , typename Value , typename IndexType , template< typename > class Atom = std::atomic, typename Allocator = std::allocator<char>>
using	UIM = AtomicUnorderedInsertMap< Key, Value, std::hash< Key >, std::equal_to< Key >,(boost::has_trivial_destructor< Key >::value &&boost::has_trivial_destructor< Value >::value), Atom, IndexType, Allocator >
using	IndexTypesToTest = ::testing::Types< uint16_t, uint32_t, uint64_t >

Functions
	TYPED_TEST_CASE (AtomicUnorderedInsertMapTest, IndexTypesToTest)
	TYPED_TEST (AtomicUnorderedInsertMapTest, basic)
	TEST (AtomicUnorderedInsertMap, load_factor)
	TEST (AtomicUnorderedInsertMap, capacity_exceeded)
	TYPED_TEST (AtomicUnorderedInsertMapTest, value_mutation)
	TEST (UnorderedInsertMap, value_mutation)
	TEST (AtomicUnorderedInsertMap, DISABLED_mega_map)
	BENCHMARK (lookup_int_int_hit, iters)
void	contendedRW (size_t itersPerThread, size_t capacity, size_t numThreads, size_t readsPerWrite)
	BENCHMARK_DRAW_LINE ()
	BENCHMARK (std_map)
	BENCHMARK (atomic_fast_map)
	BENCHMARK (fast_map)
	BENCHMARK (atomic_fast_map_64)
	BENCHMARK (fast_map_64)
int	main (int argc, char **argv)

Typedef Documentation

using IndexTypesToTest = ::testing::Types<uint16_t, uint32_t, uint64_t>

Definition at line 125 of file AtomicUnorderedMapTest.cpp.

template<typename Key , typename Value , typename IndexType , template< typename > class Atom = std::atomic, typename Allocator = std::allocator<char>>

using UIM = AtomicUnorderedInsertMap< Key, Value, std::hash<Key>, std::equal_to<Key>, (boost::has_trivial_destructor<Key>::value && boost::has_trivial_destructor<Value>::value), Atom, IndexType, Allocator>

Definition at line 116 of file AtomicUnorderedMapTest.cpp.

Function Documentation

BENCHMARK	(	lookup_int_int_hit	,
		iters
	)

Definition at line 217 of file AtomicUnorderedMapTest.cpp.

References BENCHMARK_SUSPEND, EXPECT_EQ, EXPECT_TRUE, i, k, and ptr.

                                     {
  std::unique_ptr<AtomicUnorderedInsertMap<int, size_t>> ptr = {};

  size_t capacity = 100000;

  BENCHMARK_SUSPEND {
    ptr = std::make_unique<AtomicUnorderedInsertMap<int, size_t>>(capacity);
    for (size_t i = 0; i < capacity; ++i) {
      auto k = 3 * ((5641 * i) % capacity);
      ptr->emplace(k, k + 1);
      EXPECT_EQ(ptr->find(k)->second, k + 1);
    }
  }

  for (size_t i = 0; i < iters; ++i) {
    size_t k = 3 * (((i * 7919) ^ (i * 4001)) % capacity);
    auto iter = ptr->find(k);
    if (iter == ptr->cend() || iter->second != k + 1) {
      auto jter = ptr->find(k);
      EXPECT_TRUE(iter == jter);
    }
    EXPECT_EQ(iter->second, k + 1);
  }

  BENCHMARK_SUSPEND {
    ptr.reset(nullptr);
  }
}

BENCHMARK

(

std_map

)

Definition at line 353 of file AtomicUnorderedMapTest.cpp.

References a, folly::doNotOptimizeAway(), i, and m.

                   {
  std::unordered_map<long, long> m;
  m.reserve(10000);
  for (int i = 0; i < 10000; ++i) {
    m.emplace(i, i);
  }

  for (int i = 0; i < 10000; ++i) {
    auto a = m.find(i);
    folly::doNotOptimizeAway(&*a);
  }
}

BENCHMARK

(

atomic_fast_map

)

Definition at line 366 of file AtomicUnorderedMapTest.cpp.

References a, folly::doNotOptimizeAway(), folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::emplace(), folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::find(), i, and m.

                           {
  UIM<long, long, uint32_t, std::atomic> m(10000);
  for (int i = 0; i < 10000; ++i) {
    m.emplace(i, i);
  }

  for (int i = 0; i < 10000; ++i) {
    auto a = m.find(i);
    folly::doNotOptimizeAway(&*a);
  }
}

BENCHMARK

(

fast_map

)

Definition at line 378 of file AtomicUnorderedMapTest.cpp.

References a, folly::doNotOptimizeAway(), folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::emplace(), folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::find(), i, and m.

                    {
  UIM<long, long, uint32_t, non_atomic> m(10000);
  for (int i = 0; i < 10000; ++i) {
    m.emplace(i, i);
  }

  for (int i = 0; i < 10000; ++i) {
    auto a = m.find(i);
    folly::doNotOptimizeAway(&*a);
  }
}

BENCHMARK

(

atomic_fast_map_64

)

Definition at line 390 of file AtomicUnorderedMapTest.cpp.

References a, folly::doNotOptimizeAway(), folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::emplace(), folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::find(), i, and m.

                              {
  UIM<long, long, uint64_t, std::atomic> m(10000);
  for (int i = 0; i < 10000; ++i) {
    m.emplace(i, i);
  }

  for (int i = 0; i < 10000; ++i) {
    auto a = m.find(i);
    folly::doNotOptimizeAway(&*a);
  }
}

BENCHMARK

(

fast_map_64

)

Definition at line 402 of file AtomicUnorderedMapTest.cpp.

References a, folly::doNotOptimizeAway(), folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::emplace(), folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::find(), i, and m.

                       {
  UIM<long, long, uint64_t, non_atomic> m(10000);
  for (int i = 0; i < 10000; ++i) {
    m.emplace(i, i);
  }

  for (int i = 0; i < 10000; ++i) {
    auto a = m.find(i);
    folly::doNotOptimizeAway(&*a);
  }
}

BENCHMARK_DRAW_LINE

(

)

void contendedRW	(	size_t	itersPerThread,
		size_t	capacity,
		size_t	numThreads,
		size_t	readsPerWrite
	)

Definition at line 252 of file AtomicUnorderedMapTest.cpp.

References folly::BENCHMARK_DRAW_LINE(), BENCHMARK_NAMED_PARAM, BENCHMARK_SUSPEND, EXPECT_TRUE, folly::INFO, testing::Key(), ptr, folly::Random::rand32(), threads, and folly::fibers::yield().

                          {
  typedef std::pair<uint64_t, uint64_t> Key;
  typedef AtomicUnorderedInsertMap<Key, MutableAtom<uint32_t>, PairHash> Map;

  std::unique_ptr<Map> ptr = {};
  std::atomic<bool> go{false};
  std::vector<std::thread> threads;

  BENCHMARK_SUSPEND {
    ptr = std::make_unique<Map>(capacity);
    while (threads.size() < numThreads) {
      threads.emplace_back([&]() {
        while (!go) {
          std::this_thread::yield();
        }

        size_t reads = 0;
        size_t writes = 0;
        while (reads + writes < itersPerThread) {
          auto r = Random::rand32();
          Key key(reads + writes, r);
          if (reads < writes * readsPerWrite ||
              writes >= capacity / numThreads) {
            // read needed
            ++reads;
            auto iter = ptr->find(key);
            EXPECT_TRUE(
                iter == ptr->cend() ||
                iter->second.data.load(std::memory_order_acquire) >= key.first);
          } else {
            ++writes;
            try {
              auto pr = ptr->emplace(key, key.first);
              if (!pr.second) {
                pr.first->second.data++;
              }
            } catch (std::bad_alloc&) {
              LOG(INFO) << "bad alloc";
            }
          }
        }
      });
    }
  }

  go = true;

  for (auto& thr : threads) {
    thr.join();
  }

  BENCHMARK_SUSPEND {
    ptr.reset(nullptr);
  }
}

int main	(	int	argc,
		char **	argv
	)

Definition at line 414 of file AtomicUnorderedMapTest.cpp.

References testing::InitGoogleTest(), RUN_ALL_TESTS(), and folly::runBenchmarksOnFlag().

                                {
  testing::InitGoogleTest(&argc, argv);
  gflags::ParseCommandLineFlags(&argc, &argv, true);
  int rv = RUN_ALL_TESTS();
  folly::runBenchmarksOnFlag();
  return rv;
}

TEST	(	AtomicUnorderedInsertMap	,
		load_factor
	)

Definition at line 156 of file AtomicUnorderedMapTest.cpp.

References folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::emplace(), f, i, and m.

                                            {
  AtomicUnorderedInsertMap<int, bool> m(5000, 0.5f);

  // we should be able to put in much more than 5000 things because of
  // our load factor request
  for (int i = 0; i < 10000; ++i) {
    m.emplace(i, true);
  }
}

TEST	(	AtomicUnorderedInsertMap	,
		capacity_exceeded
	)

Definition at line 166 of file AtomicUnorderedMapTest.cpp.

References folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::emplace(), EXPECT_THROW, f, i, and m.

                                                  {
  AtomicUnorderedInsertMap<int, bool> m(5000, 1.0f);

  EXPECT_THROW(
      {
        for (int i = 0; i < 6000; ++i) {
          m.emplace(i, false);
        }
      },
      std::bad_alloc);
}

TEST	(	UnorderedInsertMap	,
		value_mutation
	)

Definition at line 188 of file AtomicUnorderedMapTest.cpp.

References folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::emplace(), EXPECT_EQ, folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::find(), i, m, and uint32_t.

                                         {
  UIM<int, MutableData<int>, uint32_t, non_atomic> m(100);

  for (int i = 0; i < 50; ++i) {
    m.emplace(i, i);
  }

  m.find(1)->second.data++;
  EXPECT_EQ(m.find(1)->second.data, 2);
}

TEST	(	AtomicUnorderedInsertMap	,
		DISABLED_mega_map
	)

Definition at line 201 of file AtomicUnorderedMapTest.cpp.

References folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::cend(), folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::emplace(), EXPECT_EQ, EXPECT_TRUE, folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::find(), and i.

                                                  {
  size_t capacity = 2000000000;
  AtomicUnorderedInsertMap64<size_t, size_t> big(capacity);
  for (size_t i = 0; i < capacity * 2; i += 2) {
    big.emplace(i, i * 10);
  }
  for (size_t i = 0; i < capacity * 3; i += capacity / 1000 + 1) {
    auto iter = big.find(i);
    if ((i & 1) == 0 && i < capacity * 2) {
      EXPECT_EQ(iter->second, i * 10);
    } else {
      EXPECT_TRUE(iter == big.cend());
    }
  }
}

TYPED_TEST	(	AtomicUnorderedInsertMapTest	,
		basic
	)

Definition at line 128 of file AtomicUnorderedMapTest.cpp.

References a, b, EXPECT_EQ, EXPECT_TRUE, m, and string.

                                                {
  UIM<std::string,
      std::string,
      TypeParam,
      std::atomic,
      folly::detail::MMapAlloc>
      m(100);

  m.emplace("abc", "ABC");
  EXPECT_TRUE(m.find("abc") != m.cend());
  EXPECT_EQ(m.find("abc")->first, "abc");
  EXPECT_EQ(m.find("abc")->second, "ABC");
  EXPECT_TRUE(m.find("def") == m.cend());
  auto iter = m.cbegin();
  EXPECT_TRUE(iter != m.cend());
  EXPECT_TRUE(iter == m.find("abc"));
  auto a = iter;
  EXPECT_TRUE(a == iter);
  auto b = iter;
  ++iter;
  EXPECT_TRUE(iter == m.cend());
  EXPECT_TRUE(a == b);
  EXPECT_TRUE(a != iter);
  a++;
  EXPECT_TRUE(a == iter);
  EXPECT_TRUE(a != b);
}

TYPED_TEST	(	AtomicUnorderedInsertMapTest	,
		value_mutation
	)

Definition at line 178 of file AtomicUnorderedMapTest.cpp.

References folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::emplace(), folly::AtomicUnorderedInsertMap< Key, Value, Hash, KeyEqual, SkipKeyValueDeletion, Atom, IndexType, Allocator >::find(), i, and m.

                                                         {
  UIM<int, MutableAtom<int>, TypeParam> m(100);

  for (int i = 0; i < 50; ++i) {
    m.emplace(i, i);
  }

  m.find(1)->second.data++;
}

TYPED_TEST_CASE	(	AtomicUnorderedInsertMapTest	,
		IndexTypesToTest
	)