AtomicHashMapTest.cpp File Reference

#include <folly/AtomicHashMap.h>
#include <atomic>
#include <memory>
#include <thread>
#include <glog/logging.h>
#include <folly/Benchmark.h>
#include <folly/Conv.h>
#include <folly/portability/GTest.h>
#include <folly/portability/SysTime.h>

Go to the source code of this file.

Classes
struct	EqTraits
struct	HashTraits
class	Counters
class	Integer

Typedefs
typedef int32_t	KeyT
typedef int32_t	ValueT
typedef AtomicHashMap< KeyT, ValueT >	AHMapT
typedef AHMapT::value_type	RecordT
typedef AtomicHashArray< KeyT, ValueT >	AHArrayT
typedef folly::QuadraticProbingAtomicHashMap< KeyT, ValueT >	QPAHMapT
typedef AtomicHashMap< const char *, int64_t, HashTraits, EqTraits >	AHMCstrInt
typedef AtomicHashArray< int32_t, int32_t >	AHA

Functions
	DEFINE_double (targetLoadFactor, 0.75,"Target memory utilization fraction.")
	DEFINE_double (maxLoadFactor, 0.80,"Max before growth.")
	DEFINE_int32 (numThreads, 8,"Threads to use for concurrency tests.")
	DEFINE_int64 (numBMElements, 12 *1000 *1000,"Size of maps for benchmarks.")
static int64_t	nowInUsec ()
	TEST (Ahm, BasicStrings)
	TEST (Ahm, BasicNoncopyable)
static AHArrayT::SmartPtr	globalAHA (nullptr)
static int	genVal (int key)
static bool	legalKey (const char *a)
	TEST (Ahm, BasicLookup)
	TEST (Ahm, grow)
	TEST (Ahm, iterator)
	TEST (Ahm, counter)
	TEST (Ahm, map_exception_safety)
	TEST (Ahm, basicErase)
	TEST (Ahm, collision_test)
	TEST (Ahm, race_insert_iterate_thread_test)
	TEST (Ahm, thread_erase_insert_race)
void *	atomicHashArrayInsertRaceThread (void *)
	TEST (Ahm, atomic_hash_array_insert_race)
	TEST (Ahm, erase_find_race)
	TEST (Ahm, erase_after_insert_race)
	TEST (Ahm, iterator_skips_empty_submaps)
	BENCHMARK (st_aha_find, iters)
	BENCHMARK (st_ahm_find, iters)
	BENCHMARK (st_qpahm_find, iters)
	BENCHMARK_DRAW_LINE ()
	BENCHMARK (mt_ahm_miss, iters)
	BENCHMARK (mt_qpahm_miss, iters)
	BENCHMARK (st_ahm_miss, iters)
	BENCHMARK (st_qpahm_miss, iters)
	BENCHMARK (mt_ahm_find_insert_mix, iters)
	BENCHMARK (mt_qpahm_find_insert_mix, iters)
	BENCHMARK (mt_aha_find, iters)
	BENCHMARK (mt_ahm_find, iters)
	BENCHMARK (mt_qpahm_find, iters)
	BENCHMARK (st_baseline_modulus_and_random, iters)
	BENCHMARK (mt_ahm_insert, iters)
	BENCHMARK (mt_qpahm_insert, iters)
	BENCHMARK (st_ahm_insert, iters)
	BENCHMARK (st_qpahm_insert, iters)
void	benchmarkSetup ()
int	main (int argc, char **argv)

Variables
const double	LF = FLAGS_maxLoadFactor / FLAGS_targetLoadFactor
const int	maxBMElements = int(FLAGS_numBMElements * LF)
AHArrayT::Config	config
QPAHMapT::Config	qpConfig
static std::unique_ptr< AHMapT >	globalAHM
static std::unique_ptr< QPAHMapT >	globalQPAHM
AHMCstrInt::Config	cstrIntCfg
AHA::Config	configRace
auto	atomicHashArrayInsertRaceArray = AHA::create(2, configRace)
KeyT	k

Typedef Documentation

typedef AtomicHashArray<int32_t, int32_t> AHA

Definition at line 675 of file AtomicHashMapTest.cpp.

typedef AtomicHashArray<KeyT, ValueT> AHArrayT

Definition at line 105 of file AtomicHashMapTest.cpp.

typedef AtomicHashMap<KeyT, ValueT> AHMapT

Definition at line 103 of file AtomicHashMapTest.cpp.

typedef AtomicHashMap<const char*, int64_t, HashTraits, EqTraits> AHMCstrInt

Definition at line 153 of file AtomicHashMapTest.cpp.

typedef int32_t KeyT

Definition at line 100 of file AtomicHashMapTest.cpp.

typedef folly::QuadraticProbingAtomicHashMap<KeyT, ValueT> QPAHMapT

Definition at line 107 of file AtomicHashMapTest.cpp.

typedef AHMapT::value_type RecordT

Definition at line 104 of file AtomicHashMapTest.cpp.

typedef int32_t ValueT

Definition at line 101 of file AtomicHashMapTest.cpp.

Function Documentation

void* atomicHashArrayInsertRaceThread

(

void *

)

Definition at line 678 of file AtomicHashMapTest.cpp.

References atomicHashArrayInsertRaceArray, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::end(), i, and folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insert().

Referenced by TEST().

                                               {
  AHA* arr = atomicHashArrayInsertRaceArray.get();
  uintptr_t numInserted = 0;
  while (!runThreadsCreatedAllThreads.load()) {
    ;
  }
  for (int i = 0; i < 2; i++) {
    if (arr->insert(RecordT(randomizeKey(i), 0)).first != arr->end()) {
      numInserted++;
    }
  }
  return (void*)numInserted;
}

BENCHMARK	(	st_aha_find	,
		iters
	)

Definition at line 846 of file AtomicHashMapTest.cpp.

References folly::doNotOptimizeAway(), globalAHA(), and i.

                              {
  CHECK_LE(iters, FLAGS_numBMElements);
  for (size_t i = 0; i < iters; i++) {
    KeyT key = randomizeKey(i);
    folly::doNotOptimizeAway(globalAHA->find(key)->second);
  }
}

BENCHMARK	(	st_ahm_find	,
		iters
	)

Definition at line 854 of file AtomicHashMapTest.cpp.

References folly::doNotOptimizeAway(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::find(), and i.

                              {
  CHECK_LE(iters, FLAGS_numBMElements);
  for (size_t i = 0; i < iters; i++) {
    KeyT key = randomizeKey(i);
    folly::doNotOptimizeAway(globalAHM->find(key)->second);
  }
}

BENCHMARK	(	st_qpahm_find	,
		iters
	)

Definition at line 862 of file AtomicHashMapTest.cpp.

References BENCHMARK_DRAW_LINE(), folly::doNotOptimizeAway(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::find(), and i.

                                {
  CHECK_LE(iters, FLAGS_numBMElements);
  for (size_t i = 0; i < iters; i++) {
    KeyT key = randomizeKey(i);
    folly::doNotOptimizeAway(globalQPAHM->find(key)->second);
  }
}

BENCHMARK	(	mt_ahm_miss	,
		iters
	)

Definition at line 872 of file AtomicHashMapTest.cpp.

References folly::doNotOptimizeAway(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::end(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::find(), i, and int64_t.

                              {
  CHECK_LE(iters, FLAGS_numBMElements);
  numOpsPerThread = iters / FLAGS_numThreads;
  runThreads([](void* jj) -> void* {
    int64_t j = (int64_t)jj;
    while (!runThreadsCreatedAllThreads.load()) {
      ;
    }
    for (int i = 0; i < numOpsPerThread; ++i) {
      KeyT key = i + j * numOpsPerThread * 100;
      folly::doNotOptimizeAway(globalAHM->find(key) == globalAHM->end());
    }
    return nullptr;
  });
}

BENCHMARK	(	mt_qpahm_miss	,
		iters
	)

Definition at line 888 of file AtomicHashMapTest.cpp.

References folly::doNotOptimizeAway(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::end(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::find(), i, and int64_t.

                                {
  CHECK_LE(iters, FLAGS_numBMElements);
  numOpsPerThread = iters / FLAGS_numThreads;
  runThreads([](void* jj) -> void* {
    int64_t j = (int64_t)jj;
    while (!runThreadsCreatedAllThreads.load()) {
      ;
    }
    for (int i = 0; i < numOpsPerThread; ++i) {
      KeyT key = i + j * numOpsPerThread * 100;
      folly::doNotOptimizeAway(globalQPAHM->find(key) == globalQPAHM->end());
    }
    return nullptr;
  });
}

BENCHMARK	(	st_ahm_miss	,
		iters
	)

Definition at line 904 of file AtomicHashMapTest.cpp.

References folly::doNotOptimizeAway(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::end(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::find(), and i.

                              {
  CHECK_LE(iters, FLAGS_numBMElements);
  for (size_t i = 0; i < iters; i++) {
    KeyT key = randomizeKey(i + iters * 100);
    folly::doNotOptimizeAway(globalAHM->find(key) == globalAHM->end());
  }
}

BENCHMARK	(	st_qpahm_miss	,
		iters
	)

Definition at line 912 of file AtomicHashMapTest.cpp.

References folly::doNotOptimizeAway(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::end(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::find(), and i.

                                {
  CHECK_LE(iters, FLAGS_numBMElements);
  for (size_t i = 0; i < iters; i++) {
    KeyT key = randomizeKey(i + iters * 100);
    folly::doNotOptimizeAway(globalQPAHM->find(key) == globalQPAHM->end());
  }
}

BENCHMARK	(	mt_ahm_find_insert_mix	,
		iters
	)

Definition at line 920 of file AtomicHashMapTest.cpp.

References folly::doNotOptimizeAway(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::find(), genVal(), i, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insert(), and int64_t.

                                         {
  CHECK_LE(iters, FLAGS_numBMElements);
  numOpsPerThread = iters / FLAGS_numThreads;
  runThreads([](void* jj) -> void* {
    int64_t j = (int64_t)jj;
    while (!runThreadsCreatedAllThreads.load()) {
      ;
    }
    for (int i = 0; i < numOpsPerThread; ++i) {
      if (i % 128) { // ~1% insert mix
        KeyT key = randomizeKey(i + j * numOpsPerThread);
        folly::doNotOptimizeAway(globalAHM->find(key)->second);
      } else {
        KeyT key = randomizeKey(i + j * numOpsPerThread * 100);
        globalAHM->insert(key, genVal(key));
      }
    }
    return nullptr;
  });
}

BENCHMARK	(	mt_qpahm_find_insert_mix	,
		iters
	)

Definition at line 941 of file AtomicHashMapTest.cpp.

References folly::doNotOptimizeAway(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::find(), genVal(), i, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insert(), and int64_t.

                                           {
  CHECK_LE(iters, FLAGS_numBMElements);
  numOpsPerThread = iters / FLAGS_numThreads;
  runThreads([](void* jj) -> void* {
    int64_t j = (int64_t)jj;
    while (!runThreadsCreatedAllThreads.load()) {
      ;
    }
    for (int i = 0; i < numOpsPerThread; ++i) {
      if (i % 128) { // ~1% insert mix
        KeyT key = randomizeKey(i + j * numOpsPerThread);
        folly::doNotOptimizeAway(globalQPAHM->find(key)->second);
      } else {
        KeyT key = randomizeKey(i + j * numOpsPerThread * 100);
        globalQPAHM->insert(key, genVal(key));
      }
    }
    return nullptr;
  });
}

BENCHMARK	(	mt_aha_find	,
		iters
	)

Definition at line 962 of file AtomicHashMapTest.cpp.

References folly::doNotOptimizeAway(), globalAHA(), i, and int64_t.

                              {
  CHECK_LE(iters, FLAGS_numBMElements);
  numOpsPerThread = iters / FLAGS_numThreads;
  runThreads([](void* jj) -> void* {
    int64_t j = (int64_t)jj;
    while (!runThreadsCreatedAllThreads.load()) {
      ;
    }
    for (int i = 0; i < numOpsPerThread; ++i) {
      KeyT key = randomizeKey(i + j * numOpsPerThread);
      folly::doNotOptimizeAway(globalAHA->find(key)->second);
    }
    return nullptr;
  });
}

BENCHMARK	(	mt_ahm_find	,
		iters
	)

Definition at line 978 of file AtomicHashMapTest.cpp.

References folly::doNotOptimizeAway(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::find(), i, and int64_t.

                              {
  CHECK_LE(iters, FLAGS_numBMElements);
  numOpsPerThread = iters / FLAGS_numThreads;
  runThreads([](void* jj) -> void* {
    int64_t j = (int64_t)jj;
    while (!runThreadsCreatedAllThreads.load()) {
      ;
    }
    for (int i = 0; i < numOpsPerThread; ++i) {
      KeyT key = randomizeKey(i + j * numOpsPerThread);
      folly::doNotOptimizeAway(globalAHM->find(key)->second);
    }
    return nullptr;
  });
}

BENCHMARK	(	mt_qpahm_find	,
		iters
	)

Definition at line 994 of file AtomicHashMapTest.cpp.

References folly::doNotOptimizeAway(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::find(), i, and int64_t.

                                {
  CHECK_LE(iters, FLAGS_numBMElements);
  numOpsPerThread = iters / FLAGS_numThreads;
  runThreads([](void* jj) -> void* {
    int64_t j = (int64_t)jj;
    while (!runThreadsCreatedAllThreads.load()) {
      ;
    }
    for (int i = 0; i < numOpsPerThread; ++i) {
      KeyT key = randomizeKey(i + j * numOpsPerThread);
      folly::doNotOptimizeAway(globalQPAHM->find(key)->second);
    }
    return nullptr;
  });
}

BENCHMARK	(	st_baseline_modulus_and_random	,
		iters
	)

Definition at line 1011 of file AtomicHashMapTest.cpp.

References i, and k.

                                                 {
  for (size_t i = 0; i < iters; ++i) {
    k = randomizeKey(i) % iters;
  }
}

BENCHMARK	(	mt_ahm_insert	,
		iters
	)

Definition at line 1019 of file AtomicHashMapTest.cpp.

References BENCHMARK_SUSPEND, config, and LF.

                                {
  BENCHMARK_SUSPEND {
    globalAHM = std::make_unique<AHMapT>(int(iters * LF), config);
    numOpsPerThread = iters / FLAGS_numThreads;
  }
  runThreads(insertThread);
}

BENCHMARK	(	mt_qpahm_insert	,
		iters
	)

Definition at line 1027 of file AtomicHashMapTest.cpp.

References BENCHMARK_SUSPEND, LF, and qpConfig.

                                  {
  BENCHMARK_SUSPEND {
    globalQPAHM = std::make_unique<QPAHMapT>(int(iters * LF), qpConfig);
    numOpsPerThread = iters / FLAGS_numThreads;
  }
  runThreads(qpInsertThread);
}

BENCHMARK	(	st_ahm_insert	,
		iters
	)

Definition at line 1035 of file AtomicHashMapTest.cpp.

References folly::BenchmarkSuspender::dismiss(), genVal(), i, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insert(), and LF.

                                {
  folly::BenchmarkSuspender susp;
  std::unique_ptr<AHMapT> ahm(new AHMapT(int(iters * LF), config));
  susp.dismiss();

  for (size_t i = 0; i < iters; i++) {
    KeyT key = randomizeKey(i);
    ahm->insert(key, genVal(key));
  }
}

BENCHMARK	(	st_qpahm_insert	,
		iters
	)

Definition at line 1046 of file AtomicHashMapTest.cpp.

References folly::BenchmarkSuspender::dismiss(), genVal(), i, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insert(), and LF.

                                  {
  folly::BenchmarkSuspender susp;
  std::unique_ptr<QPAHMapT> ahm(new QPAHMapT(int(iters * LF), qpConfig));
  susp.dismiss();

  for (size_t i = 0; i < iters; i++) {
    KeyT key = randomizeKey(i);
    ahm->insert(key, genVal(key));
  }
}

BENCHMARK_DRAW_LINE

(

)

Referenced by BENCHMARK().

void benchmarkSetup

(

)

Definition at line 1057 of file AtomicHashMapTest.cpp.

References folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::Config::maxLoadFactor, and min.

Referenced by main().

                      {
  config.maxLoadFactor = FLAGS_maxLoadFactor;
  qpConfig.maxLoadFactor = FLAGS_maxLoadFactor;
  configRace.maxLoadFactor = 0.5;
  int numCores = sysconf(_SC_NPROCESSORS_ONLN);
  loadGlobalAha();
  loadGlobalAhm();
  loadGlobalQPAhm();
  string numIters =
      folly::to<string>(std::min(1000000, int(FLAGS_numBMElements)));

  gflags::SetCommandLineOptionWithMode(
      "bm_max_iters", numIters.c_str(), gflags::SET_FLAG_IF_DEFAULT);
  gflags::SetCommandLineOptionWithMode(
      "bm_min_iters", numIters.c_str(), gflags::SET_FLAG_IF_DEFAULT);
  string numCoresStr = folly::to<string>(numCores);
  gflags::SetCommandLineOptionWithMode(
      "numThreads", numCoresStr.c_str(), gflags::SET_FLAG_IF_DEFAULT);

  std::cout << "\nRunning AHM benchmarks on machine with " << numCores
            << " logical cores.\n"
               "  num elements per map: "
            << FLAGS_numBMElements << "\n"
            << "  num threads for mt tests: " << FLAGS_numThreads << "\n"
            << "  AHM load factor: " << FLAGS_targetLoadFactor << "\n\n";
}

DEFINE_double	(	targetLoadFactor	,
		0.	75,
		"Target memory utilization fraction."
	)

DEFINE_double	(	maxLoadFactor	,
		0.	80,
		"Max before growth."
	)

DEFINE_int32	(	numThreads	,
		8	,
		"Threads to use for concurrency tests."
	)

DEFINE_int64	(	numBMElements	,
		12 *1000 *	1000,
		"Size of maps for benchmarks."
	)

static int genVal ( int  key )

static

Definition at line 114 of file AtomicHashMapTest.cpp.

References a, and legalKey().

Referenced by BENCHMARK(), and TEST().

                           {
  return key / 3;
}

static AHArrayT::SmartPtr globalAHA ( nullptr  )

static

Referenced by BENCHMARK(), and TEST().

static bool legalKey ( const char *  a )

static

Definition at line 156 of file AtomicHashMapTest.cpp.

References folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::Config::emptyKey, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::Config::erasedKey, and folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::Config::lockedKey.

Referenced by genVal(), and EqTraits::operator()().

                                    {
  return a != cstrIntCfg.emptyKey && a != cstrIntCfg.lockedKey &&
      a != cstrIntCfg.erasedKey;
}

int main	(	int	argc,
		char **	argv
	)

Definition at line 1084 of file AtomicHashMapTest.cpp.

References benchmarkSetup(), testing::InitGoogleTest(), RUN_ALL_TESTS(), and folly::runBenchmarks().

                                {
  testing::InitGoogleTest(&argc, argv);
  gflags::ParseCommandLineFlags(&argc, &argv, true);
  auto ret = RUN_ALL_TESTS();
  if (!ret && FLAGS_benchmark) {
    benchmarkSetup();
    folly::runBenchmarks();
  }
  return ret;
}

static int64_t nowInUsec ( )

static

Definition at line 45 of file AtomicHashMapTest.cpp.

References int64_t.

Referenced by TEST().

                           {
  timeval tv;
  gettimeofday(&tv, nullptr);
  return int64_t(tv.tv_sec) * 1000 * 1000 + tv.tv_usec;
}

TEST	(	Ahm	,
		BasicStrings
	)

Definition at line 51 of file AtomicHashMapTest.cpp.

References EXPECT_EQ, EXPECT_TRUE, and i.

                        {
  typedef AtomicHashMap<int64_t, string> AHM;
  AHM myMap(1024);
  EXPECT_TRUE(myMap.begin() == myMap.end());

  for (int i = 0; i < 100; ++i) {
    myMap.insert(make_pair(i, folly::to<string>(i)));
  }
  for (int i = 0; i < 100; ++i) {
    EXPECT_EQ(myMap.find(i)->second, folly::to<string>(i));
  }

  myMap.insert(std::make_pair(999, "A"));
  myMap.insert(std::make_pair(999, "B"));
  EXPECT_EQ(myMap.find(999)->second, "A"); // shouldn't have overwritten
  myMap.find(999)->second = "B";
  myMap.find(999)->second = "C";
  EXPECT_EQ(myMap.find(999)->second, "C");
  EXPECT_EQ(myMap.find(999)->first, 999);
}

TEST	(	Ahm	,
		BasicNoncopyable
	)

Definition at line 72 of file AtomicHashMapTest.cpp.

References EXPECT_EQ, EXPECT_TRUE, and i.

                            {
  typedef AtomicHashMap<int64_t, std::unique_ptr<int>> AHM;
  AHM myMap(1024);
  EXPECT_TRUE(myMap.begin() == myMap.end());

  for (int i = 0; i < 50; ++i) {
    myMap.insert(make_pair(i, std::make_unique<int>(i)));
  }
  for (int i = 50; i < 100; ++i) {
    myMap.insert(i, std::make_unique<int>(i));
  }
  for (int i = 100; i < 150; ++i) {
    myMap.emplace(i, new int(i));
  }
  for (int i = 150; i < 200; ++i) {
    myMap.emplace(i, new int(i), std::default_delete<int>());
  }
  for (int i = 0; i < 200; ++i) {
    EXPECT_EQ(*(myMap.find(i)->second), i);
  }
  for (int i = 0; i < 200; i += 4) {
    myMap.erase(i);
  }
  for (int i = 0; i < 200; i += 4) {
    EXPECT_EQ(myMap.find(i), myMap.end());
  }
}

TEST	(	Ahm	,
		BasicLookup
	)

Definition at line 161 of file AtomicHashMapTest.cpp.

References folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::begin(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::end(), EXPECT_EQ, EXPECT_TRUE, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::find(), and folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insert().

                       {
  AHMCstrInt myMap(1024, cstrIntCfg);
  EXPECT_TRUE(myMap.begin() == myMap.end());
  myMap.insert(std::make_pair("f", 42));
  EXPECT_EQ(42, myMap.find("f")->second);
  {
    // Look up a single char, successfully.
    auto it = myMap.find<char>('f');
    EXPECT_EQ(42, it->second);
  }
  {
    // Look up a single char, unsuccessfully.
    auto it = myMap.find<char>('g');
    EXPECT_TRUE(it == myMap.end());
  }
  {
    // Look up a string piece, successfully.
    const StringPiece piece("f");
    auto it = myMap.find(piece);
    EXPECT_EQ(42, it->second);
  }
}

TEST	(	Ahm	,
		grow
	)

Definition at line 184 of file AtomicHashMapTest.cpp.

References folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::clear(), EXPECT_EQ, EXPECT_GT, EXPECT_TRUE, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::find(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::findAt(), genVal(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::ahm_iterator< ContT, IterVal, SubIt >::getIndex(), i, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insert(), int32_t, m, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numSubMaps(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::size(), and uint64_t.

                {
  VLOG(1) << "Overhead: " << sizeof(AHArrayT) << " (array) "
          << sizeof(AHMapT) + sizeof(AHArrayT) << " (map/set) Bytes.";
  uint64_t numEntries = 10000;
  float sizeFactor = 0.46f;

  std::unique_ptr<AHMapT> m(new AHMapT(int(numEntries * sizeFactor), config));

  // load map - make sure we succeed and the index is accurate
  bool success = true;
  for (uint64_t i = 0; i < numEntries; i++) {
    auto ret = m->insert(RecordT(i, genVal(i)));
    success &= ret.second;
    success &= (m->findAt(ret.first.getIndex())->second == genVal(i));
  }
  // Overwrite vals to make sure there are no dups
  // Every insert should fail because the keys are already in the map.
  success = true;
  for (uint64_t i = 0; i < numEntries; i++) {
    auto ret = m->insert(RecordT(i, genVal(i * 2)));
    success &= (ret.second == false); // fail on collision
    success &= (ret.first->second == genVal(i)); // return the previous value
    success &= (m->findAt(ret.first.getIndex())->second == genVal(i));
  }
  EXPECT_TRUE(success);

  // check correctness
  EXPECT_GT(m->numSubMaps(), 1); // make sure we grew
  success = true;
  EXPECT_EQ(m->size(), numEntries);
  for (size_t i = 0; i < numEntries; i++) {
    success &= (m->find(i)->second == genVal(i));
  }
  EXPECT_TRUE(success);

  // Check findAt
  success = true;
  AHMapT::const_iterator retIt;
  for (int32_t i = 0; i < int32_t(numEntries); i++) {
    retIt = m->find(i);
    retIt = m->findAt(retIt.getIndex());
    success &= (retIt->second == genVal(i));
    // We use a uint32_t index so that this comparison is between two
    // variables of the same type.
    success &= (retIt->first == i);
  }
  EXPECT_TRUE(success);

  // Try modifying value
  m->find(8)->second = 5309;
  EXPECT_EQ(m->find(8)->second, 5309);

  // check clear()
  m->clear();
  success = true;
  for (uint64_t i = 0; i < numEntries / 2; i++) {
    success &= m->insert(RecordT(i, genVal(i))).second;
  }
  EXPECT_TRUE(success);
  EXPECT_EQ(m->size(), numEntries / 2);
}

TEST	(	Ahm	,
		iterator
	)

Definition at line 246 of file AtomicHashMapTest.cpp.

References count, EXPECT_EQ, EXPECT_TRUE, FOR_EACH, genVal(), i, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insert(), and m.

                    {
  int numEntries = 10000;
  float sizeFactor = .46f;
  std::unique_ptr<AHMapT> m(new AHMapT(int(numEntries * sizeFactor), config));

  // load map - make sure we succeed and the index is accurate
  for (int i = 0; i < numEntries; i++) {
    m->insert(RecordT(i, genVal(i)));
  }

  bool success = true;
  int count = 0;
  FOR_EACH (it, *m) {
    success &= (it->second == genVal(it->first));
    ++count;
  }
  EXPECT_TRUE(success);
  EXPECT_EQ(count, numEntries);
}

TEST	(	Ahm	,
		counter
	)

Definition at line 303 of file AtomicHashMapTest.cpp.

References c, EXPECT_EQ, EXPECT_NE, FOR_EACH_RANGE, Counters::getValue(), i, Counters::increment(), folly::pushmi::detail::t, threads, Counters::toString(), and val.

                   {
  const int numKeys = 10;
  const int mult = 10;
  Counters c(numKeys);
  vector<int64_t> keys;
  FOR_EACH_RANGE (i, 1, numKeys) { keys.push_back(i); }
  vector<std::thread> threads;
  for (auto key : keys) {
    FOR_EACH_RANGE (i, 0, key * mult) {
      threads.push_back(std::thread([&, key] { c.increment(key); }));
    }
  }
  for (auto& t : threads) {
    t.join();
  }
  string str = c.toString();
  for (auto key : keys) {
    int val = key * mult;
    EXPECT_EQ(val, c.getValue(key));
    EXPECT_NE(
        string::npos, str.find(folly::to<string>("[", key, ":", val, "]")));
  }
}

TEST	(	Ahm	,
		map_exception_safety
	)

Definition at line 349 of file AtomicHashMapTest.cpp.

References count, EXPECT_EQ, EXPECT_TRUE, genVal(), i, and m.

                                {
  typedef AtomicHashMap<KeyT, Integer> MyMapT;

  int numEntries = 10000;
  float sizeFactor = 0.46f;
  std::unique_ptr<MyMapT> m(new MyMapT(int(numEntries * sizeFactor)));

  bool success = true;
  int count = 0;
  for (int i = 0; i < numEntries; i++) {
    try {
      m->insert(i, Integer(genVal(i)));
      success &= (m->find(i)->second == Integer(genVal(i)));
      ++count;
    } catch (...) {
      success &= !m->count(i);
    }
  }
  EXPECT_EQ(count, m->size());
  EXPECT_TRUE(success);
}

TEST	(	Ahm	,
		basicErase
	)

Definition at line 371 of file AtomicHashMapTest.cpp.

References folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::count(), folly::BenchmarkSuspender::dismiss(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::erase(), EXPECT_EQ, EXPECT_TRUE, genVal(), globalAHA(), i, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insert(), int64_t, folly::hash::jenkins_rev_mix32(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numSubMaps(), s, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::size(), and threads.

                      {
  size_t numEntries = 3000;

  std::unique_ptr<AHMapT> s(new AHMapT(numEntries, config));
  // Iterate filling up the map and deleting all keys a few times
  // to test more than one subMap.
  for (int iterations = 0; iterations < 4; ++iterations) {
    // Testing insertion of keys
    bool success = true;
    for (size_t i = 0; i < numEntries; ++i) {
      success &= !(s->count(i));
      auto ret = s->insert(RecordT(i, i));
      success &= s->count(i);
      success &= ret.second;
    }
    EXPECT_TRUE(success);
    EXPECT_EQ(s->size(), numEntries);

    // Delete every key in the map and verify that the key is gone and the the
    // size is correct.
    success = true;
    for (size_t i = 0; i < numEntries; ++i) {
      success &= s->erase(i);
      success &= (s->size() == numEntries - 1 - i);
      success &= !(s->count(i));
      success &= !(s->erase(i));
    }
    EXPECT_TRUE(success);
  }
  VLOG(1) << "Final number of subMaps = " << s->numSubMaps();
}

TEST	(	Ahm	,
		collision_test
	)

Definition at line 470 of file AtomicHashMapTest.cpp.

References folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::begin(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::capacity(), config, count, folly::test::end(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::end(), EXPECT_EQ, EXPECT_FALSE, EXPECT_TRUE, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::find(), genVal(), i, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insert(), nowInUsec(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numSubMaps(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::size(), and start.

                          {
  const int numInserts = 1000000 / 4;

  // Doing the same number on each thread so we collide.
  numOpsPerThread = numInserts;

  float sizeFactor = 0.46f;
  int entrySize = sizeof(KeyT) + sizeof(ValueT);
  VLOG(1) << "Testing " << numInserts << " unique " << entrySize
          << " Byte entries replicated in " << FLAGS_numThreads
          << " threads with " << FLAGS_maxLoadFactor * 100.0
          << "% max load factor.";

  globalAHM = std::make_unique<AHMapT>(int(numInserts * sizeFactor), config);

  size_t sizeInit = globalAHM->capacity();
  VLOG(1) << "  Initial capacity: " << sizeInit;

  double start = nowInUsec();
  runThreads([](void*) -> void* { // collisionInsertThread
    for (int i = 0; i < numOpsPerThread; ++i) {
      KeyT key = randomizeKey(i);
      globalAHM->insert(key, genVal(key));
    }
    return nullptr;
  });
  double elapsed = nowInUsec() - start;

  size_t finalCap = globalAHM->capacity();
  size_t sizeAHM = globalAHM->size();
  VLOG(1) << elapsed / sizeAHM << " usec per " << FLAGS_numThreads
          << " duplicate inserts (atomic).";
  VLOG(1) << "  Final capacity: " << finalCap << " in "
          << globalAHM->numSubMaps() << " sub maps ("
          << sizeAHM * 100 / finalCap << "% load factor, "
          << (finalCap - sizeInit) * 100 / sizeInit << "% growth).";

  // check correctness
  EXPECT_EQ(sizeAHM, numInserts);
  bool success = true;
  for (int i = 0; i < numInserts; ++i) {
    KeyT key = randomizeKey(i);
    success &= (globalAHM->find(key)->second == genVal(key));
  }
  EXPECT_TRUE(success);

  // check colliding finds
  start = nowInUsec();
  runThreads([](void*) -> void* { // collisionFindThread
    KeyT key(0);
    for (int i = 0; i < numOpsPerThread; ++i) {
      globalAHM->find(key);
    }
    return nullptr;
  });

  elapsed = nowInUsec() - start;

  VLOG(1) << elapsed / sizeAHM << " usec per " << FLAGS_numThreads
          << " duplicate finds (atomic).";
}

TEST	(	Ahm	,
		race_insert_iterate_thread_test
	)

Definition at line 564 of file AtomicHashMapTest.cpp.

References config, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::count(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::erase(), genVal(), i, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insert(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numSubMaps(), and folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::size().

                                           {
  const int kInsertThreads = 20;
  const int kIterateThreads = 20;
  raceFinalSizeEstimate = kInsertThreads * kInsertPerThread;

  VLOG(1) << "Testing iteration and insertion with " << kInsertThreads
          << " threads inserting and " << kIterateThreads
          << " threads iterating.";

  globalAHM = std::make_unique<AHMapT>(raceFinalSizeEstimate / 9, config);

  vector<pthread_t> threadIds;
  for (int j = 0; j < kInsertThreads + kIterateThreads; j++) {
    pthread_t tid;
    void* (*thread)(void*) =
        (j < kInsertThreads ? raceInsertRandomThread : raceIterateThread);
    if (pthread_create(&tid, nullptr, thread, nullptr) != 0) {
      LOG(ERROR) << "Could not start thread";
    } else {
      threadIds.push_back(tid);
    }
  }
  for (size_t i = 0; i < threadIds.size(); ++i) {
    pthread_join(threadIds[i], nullptr);
  }
  VLOG(1) << "Ended up with " << globalAHM->numSubMaps() << " submaps";
  VLOG(1) << "Final size of map " << globalAHM->size();
}

TEST	(	Ahm	,
		thread_erase_insert_race
	)

Definition at line 644 of file AtomicHashMapTest.cpp.

References config, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::empty(), EXPECT_EQ, EXPECT_TRUE, i, int64_t, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::numSubMaps(), and folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::size().

                                    {
  const int kInsertThreads = 1;
  const int kEraseThreads = 10;

  VLOG(1) << "Testing insertion and erase with " << kInsertThreads
          << " thread inserting and " << kEraseThreads << " threads erasing.";

  globalAHM = std::make_unique<AHMapT>(kTestEraseInsertions / 4, config);

  vector<pthread_t> threadIds;
  for (int64_t j = 0; j < kInsertThreads + kEraseThreads; j++) {
    pthread_t tid;
    void* (*thread)(void*) =
        (j < kInsertThreads ? testEraseInsertThread : testEraseEraseThread);
    if (pthread_create(&tid, nullptr, thread, (void*)j) != 0) {
      LOG(ERROR) << "Could not start thread";
    } else {
      threadIds.push_back(tid);
    }
  }
  for (size_t i = 0; i < threadIds.size(); i++) {
    pthread_join(threadIds[i], nullptr);
  }

  EXPECT_TRUE(globalAHM->empty());
  EXPECT_EQ(globalAHM->size(), 0);

  VLOG(1) << "Ended up with " << globalAHM->numSubMaps() << " submaps";
}

TEST	(	Ahm	,
		atomic_hash_array_insert_race
	)

Definition at line 691 of file AtomicHashMapTest.cpp.

References atomicHashArrayInsertRaceArray, atomicHashArrayInsertRaceThread(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::clear(), EXPECT_EQ, EXPECT_GE, i, and folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::size().

                                         {
  AHA* arr = atomicHashArrayInsertRaceArray.get();
  int numIterations = 5000;
  constexpr int numThreads = 4;
  void* statuses[numThreads];
  for (int i = 0; i < numIterations; i++) {
    arr->clear();
    runThreads(atomicHashArrayInsertRaceThread, numThreads, statuses);
    EXPECT_GE(arr->size(), 1);
    for (int j = 0; j < numThreads; j++) {
      EXPECT_EQ(arr->size(), uintptr_t(statuses[j]));
    }
  }
}

TEST	(	Ahm	,
		erase_find_race
	)

Definition at line 707 of file AtomicHashMapTest.cpp.

References ASSERT_EQ, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::end(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::erase(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::find(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insert(), k, map(), and uint64_t.

                           {
  const uint64_t limit = 10000;
  AtomicHashMap<uint64_t, uint64_t> map(limit + 10);
  std::atomic<uint64_t> key{1};

  // Invariant: all values are equal to their keys.
  // At any moment there is one or two consecutive keys in the map.

  std::thread write_thread([&]() {
    while (true) {
      uint64_t k = ++key;
      if (k > limit) {
        break;
      }
      map.insert(k + 1, k + 1);
      map.erase(k);
    }
  });

  std::thread read_thread([&]() {
    while (true) {
      uint64_t k = key.load();
      if (k > limit) {
        break;
      }

      auto it = map.find(k);
      if (it != map.end()) {
        ASSERT_EQ(k, it->second);
      }
    }
  });

  read_thread.join();
  write_thread.join();
}

TEST	(	Ahm	,
		erase_after_insert_race
	)

Definition at line 745 of file AtomicHashMapTest.cpp.

References folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::erase(), i, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insert(), map(), folly::pushmi::detail::t, and uint64_t.

                                   {
  const uint64_t limit = 10000;
  const size_t num_threads = 100;
  const size_t num_iters = 500;
  AtomicHashMap<uint64_t, uint64_t> map(limit + 10);

  std::atomic<bool> go{false};
  std::vector<std::thread> ts;
  for (size_t i = 0; i < num_threads; ++i) {
    ts.emplace_back([&]() {
      while (!go) {
        continue;
      }
      for (size_t n = 0; n < num_iters; ++n) {
        map.erase(1);
        map.insert(1, 1);
      }
    });
  }

  go = true;

  for (auto& t : ts) {
    t.join();
  }
}

TEST	(	Ahm	,
		iterator_skips_empty_submaps
	)

Definition at line 773 of file AtomicHashMapTest.cpp.

References ASSERT_EQ, ASSERT_NE, config, folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::create(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::end(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::erase(), EXPECT_EQ, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::find(), globalAHA(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insert(), map(), maxBMElements, nowInUsec(), qpConfig, folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::size(), start, and uint64_t.

                                        {
  AtomicHashMap<uint64_t, uint64_t>::Config conf;
  conf.growthFactor = 1;

  AtomicHashMap<uint64_t, uint64_t> map(1, conf);

  map.insert(1, 1);
  map.insert(2, 2);
  map.insert(3, 3);

  map.erase(2);

  auto it = map.find(1);

  ASSERT_NE(map.end(), it);
  ASSERT_EQ(1, it->first);
  ASSERT_EQ(1, it->second);

  ++it;

  ASSERT_NE(map.end(), it);
  ASSERT_EQ(3, it->first);
  ASSERT_EQ(3, it->second);

  ++it;
  ASSERT_EQ(map.end(), it);
}

Variable Documentation

auto atomicHashArrayInsertRaceArray = AHA::create(2, configRace)

Definition at line 677 of file AtomicHashMapTest.cpp.

Referenced by atomicHashArrayInsertRaceThread(), and TEST().

AHArrayT::Config config

Definition at line 106 of file AtomicHashMapTest.cpp.

Referenced by BENCHMARK(), cmake_minimum_required(), folly::initializeLoggerDB(), folly::initLogging(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::insertInternal(), folly::StandardLogHandler::StandardLogHandler(), and TEST().

AHA::Config configRace

Definition at line 676 of file AtomicHashMapTest.cpp.

AHMCstrInt::Config cstrIntCfg

Definition at line 154 of file AtomicHashMapTest.cpp.

std::unique_ptr<AHMapT> globalAHM

static

Definition at line 110 of file AtomicHashMapTest.cpp.

std::unique_ptr<QPAHMapT> globalQPAHM

static

Definition at line 111 of file AtomicHashMapTest.cpp.

KeyT k

Definition at line 1010 of file AtomicHashMapTest.cpp.

Referenced by testing::gmock_generated_actions_test::ACTION_P3(), testing::gmock_generated_actions_test::ACTION_TEMPLATE(), folly::compression::EliasFanoEncoderV2< Value, SkipValue, kSkipQuantum, kForwardQuantum >::add(), detail::addHashBenchmark(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::addOrGetData(), folly::detail::FingerprintPolynomial< BITS-1 >::addXk(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::assign(), folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::assign(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::assign_if_equal(), folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::assign_if_equal(), folly::dynamic::at(), BENCHMARK(), benchmarkSet(), detail::bmHasher(), check_select64_default(), check_select64_haswell(), checkMaybeCoercedKeys(), codeSize_bracket_F14Node(), codeSize_bracket_F14Value(), codeSize_bracket_F14Vector(), codeSize_bracket_Std(), std::tr1::gtest_internal::Get< 9 >::ConstField(), folly::DynamicConverter< Token >::convert(), std::tr1::tuple< T0, T1, T2, T3, T4, T5, T6, T7, T8, T9 >::CopyFrom(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::emplace(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::emplace(), std::tr1::gtest_internal::SameSizeTuplePrefixComparator< k, k >::Eq(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::find(), folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::find(), folly::AtomicHashMap< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::findInternal(), std::tr1::get(), folly::dynamic::get_ptr(), folly::dynamic::getDefault(), testing::gmock_generated_actions_test::GiantTemplate< T1, T2, T3, k4, k5, k6, T7, T8, T9 >::GiantTemplate(), testing::GTEST_CONCAT_TOKEN_(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert(), folly::AtomicHashMap< int64_t, int64_t >::insert(), folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::insert(), folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::insert_internal(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::insert_or_assign(), folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::insert_or_assign(), testing::InvokeArgument(), testing::internal::invoke_argument::InvokeArgumentAdl(), folly::AtomicHashArray< KeyT, ValueT, HashFcn, EqualFcn, Allocator, ProbeFcn, KeyConvertFcn >::keyToAnchorIdx(), main(), testing::gmock_generated_function_mockers_test::MockFoo::MockFoo(), folly::detail::FingerprintPolynomial< BITS-1 >::mulXkmod(), folly::AsciiCaseInsensitive::operator()(), folly::F14VectorSet< Key, Hasher, KeyEqual, Alloc >::operator=(), folly::dynamic::operator[](), folly::DynamicParser::ParserStack::ParserStack(), testing::internal::InvokeMethodAction< Class, MethodPtr >::Perform(), testing::gmock_generated_actions_test::SubstractAction::Perform(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::pickSegment(), folly::DynamicParser::ParserStack::push(), folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::rehash(), folly::ConcurrentSkipList< T, Comp, NodeAlloc, MAX_HEIGHT >::remove(), folly::futures::detail::retrying(), Random::Rot64(), folly::hash::SpookyHashV1::Rot64(), folly::hash::SpookyHashV2::Rot64(), runInThreadsAndWait(), runSingleInsert(), folly::select64< compression::instructions::Haswell >(), folly::dynamic::setDefault(), testing::gmock_generated_actions_test::TenArgConstructorClass::TenArgConstructorClass(), folly::test::TEST(), TEST(), folly::detail::TEST_F(), TEST_F(), TestAlignment(), TestDeltas(), folly::ConcurrentHashMap< KeyType, ValueType, HashFn, KeyEqual, Allocator, ShardBits, Atom, Mutex >::try_emplace(), folly::detail::ConcurrentHashMapSegment< KeyType, ValueType, ShardBits, HashFn, KeyEqual, Allocator, Atom, Mutex >::try_emplace(), folly::detail::concurrenthashmap::ValueHolder< KeyType, ValueType, Allocator, std::enable_if_t< !std::is_nothrow_copy_constructible< ValueType >::value||!std::is_nothrow_copy_constructible< KeyType >::value > >::ValueHolder(), and testing::gmock_generated_function_mockers_test::FooInterface::~FooInterface().

const double LF = FLAGS_maxLoadFactor / FLAGS_targetLoadFactor

Definition at line 42 of file AtomicHashMapTest.cpp.

Referenced by BENCHMARK().

const int maxBMElements = int(FLAGS_numBMElements * LF)

Definition at line 43 of file AtomicHashMapTest.cpp.

Referenced by TEST().

QPAHMapT::Config qpConfig

Definition at line 108 of file AtomicHashMapTest.cpp.

Referenced by BENCHMARK(), and TEST().