in src/benchmarks/doubly_linked_list_benchmark.cc [213:381]
void Main(size_t thread_index) {
DllStats *local_stats = new DllStats;
*stats.MyObject() = local_stats;
if(dll->GetSyncMethod() == IDList::kSyncMwCAS) {
MwCASMetrics::ThreadInitialize();
}
// WARNING: do not change the way these four variables are added
// unless you know what you are doing.
uint32_t insert_pct = FLAGS_insert_pct;
uint32_t delete_pct = insert_pct + FLAGS_delete_pct;
uint32_t search_pct = delete_pct + FLAGS_search_pct;
uint64_t payload_base = (uint64_t)thread_index << 32;
RandomNumberGenerator rng{};
const uint64_t kEpochThreshold = 1000;
const uint64_t kPreallocNodes = 600000000 / FLAGS_threads;
#ifdef WIN32
DListNode* nodes = (DListNode*)_aligned_malloc(
(sizeof(DListNode) + sizeof(uint64_t)) * kPreallocNodes, kCacheLineSize);
#else
DListNode* nodes = nullptr;
int n = posix_memalign((void**)&nodes, kCacheLineSize,
(sizeof(DListNode) + sizeof(uint64_t)) * kPreallocNodes);
#endif
RAW_CHECK(nodes, "out of memory");
uint64_t next_node = 0;
WaitForStart();
auto* node = dll->GetHead();
bool mwcas = dll->GetSyncMethod() == IDList::kSyncMwCAS;
DListCursor cursor((IDList*)dll);
uint64_t epochs = 0;
if(FLAGS_read_heavy) {
while(!IsShutdown()) {
cursor.Reset();
if(mwcas && ++epochs == kEpochThreshold) {
((MwCASDList*)dll)->GetEpoch()->Unprotect();
((MwCASDList*)dll)->GetEpoch()->Protect();
epochs = 0;
}
uint32_t op = rng.Generate(100);
uint64_t range = FLAGS_read_heavy_modify_range;
if(FLAGS_read_heavy_modify_range == 0) {
// Find a random position
// (est. total_insert = local_insert * number of threads)
range = FLAGS_initial_size +
(local_stats->n_insert - local_stats->n_delete) * FLAGS_threads;
range = std::max(range, (uint64_t)0);
}
int32_t pos = rng.Generate(range);
if(op < insert_pct) {
while(pos-- > 0) {
node = cursor.Next();
if(node == dll->GetTail()) {
cursor.Reset();
}
}
RAW_CHECK(node, "invalid node pointer");
uint64_t val = (initial_local_insert + local_stats->n_insert) |
payload_base;
auto* new_node = &nodes[next_node++];
RAW_CHECK(next_node < kPreallocNodes, "No more nodes");
new(new_node) DListNode(nullptr, nullptr, sizeof(uint64_t));
memcpy(new_node->GetPayload(), (char *)&val, sizeof(uint64_t));
Status s;
if (rng.Generate(2) == 0) {
s = dll->InsertAfter(node, new_node, true);
} else {
s = dll->InsertBefore(node, new_node, true);
}
if(s.ok()) { ++local_stats->n_effective_insert; }
++local_stats->n_insert;
} else {
if(FLAGS_read_heavy_modify_range == 0) {
uint32_t thread_index = rng.Generate(FLAGS_threads);
uint32_t local_index = rng.Generate(
initial_local_insert + local_stats->n_insert + 1);
uint64_t expected_value = ((uint64_t)thread_index << 32) |
local_index;
auto* node = dll->GetNext(dll->GetHead());
bool found = false;
while(!found && node != dll->GetTail()) {
if(expected_value == *(uint64_t*)node->GetPayload()) {
found = true;
} else {
node = cursor.Next();
}
}
if(op < delete_pct) {
auto s = dll->Delete(node, true);
++local_stats->n_delete;
if(s.ok()) { ++local_stats->n_effective_delete; }
} else {
++local_stats->n_search;
if(found) { ++local_stats->n_effective_search; }
}
} else {
while(pos-- > 0) {
node = cursor.Next();
if(node == dll->GetTail()) {
cursor.Reset();
}
}
// Must be delete, search is not supported here
RAW_CHECK(op < delete_pct,
"search is not supported for the current setting");
auto s = dll->Delete(node, true);
++local_stats->n_delete;
if(s.ok()) { ++local_stats->n_effective_delete; }
}
}
}
} else {
// This one resembles the original DLL paper's experiment
while(!IsShutdown()) {
if(mwcas && ++epochs == kEpochThreshold) {
((MwCASDList*)dll)->GetEpoch()->Unprotect();
((MwCASDList*)dll)->GetEpoch()->Protect();
epochs = 0;
}
uint32_t op = rng.Generate(100);
bool forward = true;
if (op < insert_pct) {
uint64_t val = (initial_local_insert + local_stats->n_insert) |
payload_base;
auto* new_node = &nodes[next_node++];
RAW_CHECK(next_node < kPreallocNodes, "no more nodes");
new(new_node) DListNode(nullptr, nullptr, sizeof(uint64_t));
memcpy(new_node->GetPayload(), (char *)&val, sizeof(uint64_t));
Status s;
if (rng.Generate(2) == 0) {
s = dll->InsertAfter(node, new_node, true);
} else {
s = dll->InsertBefore(node, new_node, true);
}
if(s.ok()) { ++local_stats->n_effective_insert; }
++local_stats->n_insert;
} else if(op < delete_pct) {
auto s = dll->Delete(node, true);
++local_stats->n_delete;
if(s.ok()) { ++local_stats->n_effective_delete; }
} else {
// Search
if(node == dll->GetTail()) {
forward = false;
} else if (node == dll->GetHead()) {
forward = true;
} else {
uint64_t payload = *(uint64_t*)node->GetPayload();
}
if(forward) {
node = cursor.Next();
} else {
node = cursor.Prev();
}
++local_stats->n_search;
++local_stats->n_effective_search;
}
}
}
}