From ebd740423cce85a1d1049f637d4e65b7d8465717 Mon Sep 17 00:00:00 2001 From: Jeff Preshing Date: Mon, 29 Feb 2016 08:59:57 -0500 Subject: [PATCH] Rename LeapFrog to Leapfrog --- README.md | 4 +- ...eapFrog.cpp => ConcurrentMap_Leapfrog.cpp} | 6 +- ...ap_LeapFrog.h => ConcurrentMap_Leapfrog.h} | 56 +++++++------- .../details/{LeapFrog.cpp => Leapfrog.cpp} | 6 +- junction/details/{LeapFrog.h => Leapfrog.h} | 76 +++++++++---------- ...apter_LeapFrog.h => MapAdapter_Leapfrog.h} | 6 +- samples/MapMemoryBench/TestAllMaps.py | 2 +- samples/MapPerformanceTests/TestAllMaps.py | 2 +- samples/MapScalabilityTests/TestAllMaps.py | 2 +- 9 files changed, 80 insertions(+), 80 deletions(-) rename junction/{ConcurrentMap_LeapFrog.cpp => ConcurrentMap_Leapfrog.cpp} (91%) rename junction/{ConcurrentMap_LeapFrog.h => ConcurrentMap_Leapfrog.h} (89%) rename junction/details/{LeapFrog.cpp => Leapfrog.cpp} (95%) rename junction/details/{LeapFrog.h => Leapfrog.h} (92%) rename junction/extra/impl/{MapAdapter_LeapFrog.h => MapAdapter_Leapfrog.h} (90%) diff --git a/README.md b/README.md index 96d4dd2..b4361a0 100644 --- a/README.md +++ b/README.md @@ -2,7 +2,7 @@ Junction is a library of concurrent data structures in C++. It contains several junction::ConcurrentMap_Crude junction::ConcurrentMap_Linear - junction::ConcurrentMap_LeapFrog + junction::ConcurrentMap_Leapfrog junction::ConcurrentMap_Grampa [CMake](https://cmake.org/) and [Turf](https://github.com/preshing/turf) are required. See the blog post [New Concurrent Hash Maps for C++](http://preshing.com/20160201/new-concurrent-hash-maps-for-cpp/) for more information. @@ -103,7 +103,7 @@ A Junction map is a lot like a big array of `std::atomic<>` variables, where the * All of a Junction map's member functions, together with its `Mutator` member functions, are atomic with respect to each other, so you can safely call them from any thread without mutual exclusion. * If an `set` [happens before](http://preshing.com/20130702/the-happens-before-relation/) a `get` with the same key, the `get` will return the value set, except if another operation changes the value in between. Any [synchronizing operation](http://preshing.com/20130823/the-synchronizes-with-relation/) will establish this relationship. -* For Linear, LeapFrog and Grampa maps, `set` is a [release](http://preshing.com/20120913/acquire-and-release-semantics/) operation and `get` is a [consume](http://preshing.com/20140709/the-purpose-of-memory_order_consume-in-cpp11/) operation, so you can safely pass non-atomic information between threads using a pointer. For Crude maps, all operations are relaxed. +* For Linear, Leapfrog and Grampa maps, `set` is a [release](http://preshing.com/20120913/acquire-and-release-semantics/) operation and `get` is a [consume](http://preshing.com/20140709/the-purpose-of-memory_order_consume-in-cpp11/) operation, so you can safely pass non-atomic information between threads using a pointer. For Crude maps, all operations are relaxed. * In the current version, you must not set while concurrently using an `Iterator`. ## Feedback diff --git a/junction/ConcurrentMap_LeapFrog.cpp b/junction/ConcurrentMap_Leapfrog.cpp similarity index 91% rename from junction/ConcurrentMap_LeapFrog.cpp rename to junction/ConcurrentMap_Leapfrog.cpp index 67a39ad..e4aa4b7 100644 --- a/junction/ConcurrentMap_LeapFrog.cpp +++ b/junction/ConcurrentMap_Leapfrog.cpp @@ -10,11 +10,11 @@ See the LICENSE file for more information. ------------------------------------------------------------------------*/ -#include +#include namespace junction { -TURF_TRACE_DEFINE_BEGIN(ConcurrentMap_LeapFrog, 17) // autogenerated by TidySource.py +TURF_TRACE_DEFINE_BEGIN(ConcurrentMap_Leapfrog, 17) // autogenerated by TidySource.py TURF_TRACE_DEFINE("[Mutator] find constructor called") TURF_TRACE_DEFINE("[Mutator] find was redirected") TURF_TRACE_DEFINE("[Mutator] insertOrFind constructor called") @@ -32,6 +32,6 @@ TURF_TRACE_DEFINE("[Mutator::eraseValue] was redirected") TURF_TRACE_DEFINE("[Mutator::eraseValue] was re-redirected") TURF_TRACE_DEFINE("[get] called") TURF_TRACE_DEFINE("[get] was redirected") -TURF_TRACE_DEFINE_END(ConcurrentMap_LeapFrog, 17) +TURF_TRACE_DEFINE_END(ConcurrentMap_Leapfrog, 17) } // namespace junction diff --git a/junction/ConcurrentMap_LeapFrog.h b/junction/ConcurrentMap_Leapfrog.h similarity index 89% rename from junction/ConcurrentMap_LeapFrog.h rename to junction/ConcurrentMap_Leapfrog.h index 2d0c0e2..89ba120 100644 --- a/junction/ConcurrentMap_LeapFrog.h +++ b/junction/ConcurrentMap_Leapfrog.h @@ -14,33 +14,33 @@ #define JUNCTION_CONCURRENTMAP_LEAPFROG_H #include -#include +#include #include #include #include namespace junction { -TURF_TRACE_DECLARE(ConcurrentMap_LeapFrog, 17) +TURF_TRACE_DECLARE(ConcurrentMap_Leapfrog, 17) template , class VT = DefaultValueTraits > -class ConcurrentMap_LeapFrog { +class ConcurrentMap_Leapfrog { public: typedef K Key; typedef V Value; typedef KT KeyTraits; typedef VT ValueTraits; typedef typename turf::util::BestFit::Unsigned Hash; - typedef details::LeapFrog Details; + typedef details::Leapfrog Details; private: turf::Atomic m_root; public: - ConcurrentMap_LeapFrog(ureg capacity = Details::InitialSize) : m_root(Details::Table::create(capacity)) { + ConcurrentMap_Leapfrog(ureg capacity = Details::InitialSize) : m_root(Details::Table::create(capacity)) { } - ~ConcurrentMap_LeapFrog() { + ~ConcurrentMap_Leapfrog() { typename Details::Table* table = m_root.loadNonatomic(); table->destroy(); } @@ -65,16 +65,16 @@ public: // or if another thread deletes the key between the two steps. class Mutator { private: - friend class ConcurrentMap_LeapFrog; + friend class ConcurrentMap_Leapfrog; - ConcurrentMap_LeapFrog& m_map; + ConcurrentMap_Leapfrog& m_map; typename Details::Table* m_table; typename Details::Cell* m_cell; Value m_value; // Constructor: Find existing cell - Mutator(ConcurrentMap_LeapFrog& map, Key key, bool) : m_map(map), m_value(Value(ValueTraits::NullValue)) { - TURF_TRACE(ConcurrentMap_LeapFrog, 0, "[Mutator] find constructor called", uptr(0), uptr(key)); + Mutator(ConcurrentMap_Leapfrog& map, Key key, bool) : m_map(map), m_value(Value(ValueTraits::NullValue)) { + TURF_TRACE(ConcurrentMap_Leapfrog, 0, "[Mutator] find constructor called", uptr(0), uptr(key)); Hash hash = KeyTraits::hash(key); for (;;) { m_table = m_map.m_root.load(turf::Consume); @@ -85,15 +85,15 @@ public: if (m_value != Value(ValueTraits::Redirect)) return; // Found an existing value // We've encountered a Redirect value. Help finish the migration. - TURF_TRACE(ConcurrentMap_LeapFrog, 1, "[Mutator] find was redirected", uptr(m_table), 0); + TURF_TRACE(ConcurrentMap_Leapfrog, 1, "[Mutator] find was redirected", uptr(m_table), 0); m_table->jobCoordinator.participate(); // Try again using the latest root. } } // Constructor: Insert or find cell - Mutator(ConcurrentMap_LeapFrog& map, Key key) : m_map(map), m_value(Value(ValueTraits::NullValue)) { - TURF_TRACE(ConcurrentMap_LeapFrog, 2, "[Mutator] insertOrFind constructor called", uptr(0), uptr(key)); + Mutator(ConcurrentMap_Leapfrog& map, Key key) : m_map(map), m_value(Value(ValueTraits::NullValue)) { + TURF_TRACE(ConcurrentMap_Leapfrog, 2, "[Mutator] insertOrFind constructor called", uptr(0), uptr(key)); Hash hash = KeyTraits::hash(key); for (;;) { m_table = m_map.m_root.load(turf::Consume); @@ -108,7 +108,7 @@ public: m_value = m_cell->value.load(turf::Consume); if (m_value == Value(ValueTraits::Redirect)) { // We've encountered a Redirect value. - TURF_TRACE(ConcurrentMap_LeapFrog, 3, "[Mutator] insertOrFind was redirected", uptr(m_table), uptr(m_value)); + TURF_TRACE(ConcurrentMap_Leapfrog, 3, "[Mutator] insertOrFind was redirected", uptr(m_table), uptr(m_value)); break; // Help finish the migration. } return; // Found an existing value @@ -134,12 +134,12 @@ public: TURF_ASSERT(desired != Value(ValueTraits::NullValue)); TURF_ASSERT(desired != Value(ValueTraits::Redirect)); TURF_ASSERT(m_cell); // Cell must have been found or inserted - TURF_TRACE(ConcurrentMap_LeapFrog, 4, "[Mutator::exchangeValue] called", uptr(m_table), uptr(m_value)); + TURF_TRACE(ConcurrentMap_Leapfrog, 4, "[Mutator::exchangeValue] called", uptr(m_table), uptr(m_value)); for (;;) { Value oldValue = m_value; if (m_cell->value.compareExchangeStrong(m_value, desired, turf::ConsumeRelease)) { // Exchange was successful. Return previous value. - TURF_TRACE(ConcurrentMap_LeapFrog, 5, "[Mutator::exchangeValue] exchanged Value", uptr(m_value), + TURF_TRACE(ConcurrentMap_Leapfrog, 5, "[Mutator::exchangeValue] exchanged Value", uptr(m_value), uptr(desired)); Value result = m_value; m_value = desired; // Leave the mutator in a valid state @@ -147,10 +147,10 @@ public: } // The CAS failed and m_value has been updated with the latest value. if (m_value != Value(ValueTraits::Redirect)) { - TURF_TRACE(ConcurrentMap_LeapFrog, 6, "[Mutator::exchangeValue] detected race to write value", uptr(m_table), + TURF_TRACE(ConcurrentMap_Leapfrog, 6, "[Mutator::exchangeValue] detected race to write value", uptr(m_table), uptr(m_value)); if (oldValue == Value(ValueTraits::NullValue) && m_value != Value(ValueTraits::NullValue)) { - TURF_TRACE(ConcurrentMap_LeapFrog, 7, "[Mutator::exchangeValue] racing write inserted new value", + TURF_TRACE(ConcurrentMap_Leapfrog, 7, "[Mutator::exchangeValue] racing write inserted new value", uptr(m_table), uptr(m_value)); } // There was a racing write (or erase) to this cell. @@ -158,7 +158,7 @@ public: return desired; } // We've encountered a Redirect value. Help finish the migration. - TURF_TRACE(ConcurrentMap_LeapFrog, 8, "[Mutator::exchangeValue] was redirected", uptr(m_table), uptr(m_value)); + TURF_TRACE(ConcurrentMap_Leapfrog, 8, "[Mutator::exchangeValue] was redirected", uptr(m_table), uptr(m_value)); Hash hash = m_cell->hash.load(turf::Relaxed); for (;;) { // Help complete the migration. @@ -171,7 +171,7 @@ public: case Details::InsertResult_AlreadyFound: m_value = m_cell->value.load(turf::Consume); if (m_value == Value(ValueTraits::Redirect)) { - TURF_TRACE(ConcurrentMap_LeapFrog, 9, "[Mutator::exchangeValue] was re-redirected", uptr(m_table), + TURF_TRACE(ConcurrentMap_Leapfrog, 9, "[Mutator::exchangeValue] was re-redirected", uptr(m_table), uptr(m_value)); break; } @@ -179,7 +179,7 @@ public: case Details::InsertResult_InsertedNew: goto breakOuter; case Details::InsertResult_Overflow: - TURF_TRACE(ConcurrentMap_LeapFrog, 10, "[Mutator::exchangeValue] overflow after redirect", uptr(m_table), + TURF_TRACE(ConcurrentMap_Leapfrog, 10, "[Mutator::exchangeValue] overflow after redirect", uptr(m_table), overflowIdx); Details::beginTableMigration(m_map, m_table, overflowIdx); break; @@ -197,7 +197,7 @@ public: Value eraseValue() { TURF_ASSERT(m_cell); // Cell must have been found or inserted - TURF_TRACE(ConcurrentMap_LeapFrog, 11, "[Mutator::eraseValue] called", uptr(m_table), uptr(m_cell)); + TURF_TRACE(ConcurrentMap_Leapfrog, 11, "[Mutator::eraseValue] called", uptr(m_table), uptr(m_cell)); for (;;) { if (m_value == Value(ValueTraits::NullValue)) return Value(m_value); @@ -210,7 +210,7 @@ public: return result; } // The CAS failed and m_value has been updated with the latest value. - TURF_TRACE(ConcurrentMap_LeapFrog, 12, "[Mutator::eraseValue] detected race to write value", uptr(m_table), + TURF_TRACE(ConcurrentMap_Leapfrog, 12, "[Mutator::eraseValue] detected race to write value", uptr(m_table), uptr(m_cell)); if (m_value != Value(ValueTraits::Redirect)) { // There was a racing write (or erase) to this cell. @@ -218,7 +218,7 @@ public: return Value(ValueTraits::NullValue); } // We've been redirected to a new table. - TURF_TRACE(ConcurrentMap_LeapFrog, 13, "[Mutator::eraseValue] was redirected", uptr(m_table), uptr(m_cell)); + TURF_TRACE(ConcurrentMap_Leapfrog, 13, "[Mutator::eraseValue] was redirected", uptr(m_table), uptr(m_cell)); Hash hash = m_cell->hash.load(turf::Relaxed); // Re-fetch hash for (;;) { // Help complete the migration. @@ -233,7 +233,7 @@ public: m_value = m_cell->value.load(turf::Relaxed); if (m_value != Value(ValueTraits::Redirect)) break; - TURF_TRACE(ConcurrentMap_LeapFrog, 14, "[Mutator::eraseValue] was re-redirected", uptr(m_table), + TURF_TRACE(ConcurrentMap_Leapfrog, 14, "[Mutator::eraseValue] was re-redirected", uptr(m_table), uptr(m_cell)); } } @@ -251,7 +251,7 @@ public: // Lookup without creating a temporary Mutator. Value get(Key key) { Hash hash = KeyTraits::hash(key); - TURF_TRACE(ConcurrentMap_LeapFrog, 15, "[get] called", uptr(this), uptr(hash)); + TURF_TRACE(ConcurrentMap_Leapfrog, 15, "[get] called", uptr(this), uptr(hash)); for (;;) { typename Details::Table* table = m_root.load(turf::Consume); typename Details::Cell* cell = Details::find(hash, table); @@ -261,7 +261,7 @@ public: if (value != Value(ValueTraits::Redirect)) return value; // Found an existing value // We've been redirected to a new table. Help with the migration. - TURF_TRACE(ConcurrentMap_LeapFrog, 16, "[get] was redirected", uptr(table), uptr(hash)); + TURF_TRACE(ConcurrentMap_Leapfrog, 16, "[get] was redirected", uptr(table), uptr(hash)); table->jobCoordinator.participate(); // Try again in the new table. } @@ -293,7 +293,7 @@ public: Value m_value; public: - Iterator(ConcurrentMap_LeapFrog& map) { + Iterator(ConcurrentMap_Leapfrog& map) { // Since we've forbidden concurrent inserts (for now), nonatomic would suffice here, but let's plan ahead: m_table = map.m_root.load(turf::Consume); m_idx = -1; diff --git a/junction/details/LeapFrog.cpp b/junction/details/Leapfrog.cpp similarity index 95% rename from junction/details/LeapFrog.cpp rename to junction/details/Leapfrog.cpp index 7cb9452..367cd3d 100644 --- a/junction/details/LeapFrog.cpp +++ b/junction/details/Leapfrog.cpp @@ -11,13 +11,13 @@ ------------------------------------------------------------------------*/ #include -#include +#include #include namespace junction { namespace details { -TURF_TRACE_DEFINE_BEGIN(LeapFrog, 33) // autogenerated by TidySource.py +TURF_TRACE_DEFINE_BEGIN(Leapfrog, 33) // autogenerated by TidySource.py TURF_TRACE_DEFINE("[find] called") TURF_TRACE_DEFINE("[find] found existing cell optimistically") TURF_TRACE_DEFINE("[find] found existing cell") @@ -51,7 +51,7 @@ TURF_TRACE_DEFINE("[TableMigration::run] race to set m_overflowed") TURF_TRACE_DEFINE("[TableMigration::run] out of migration units") TURF_TRACE_DEFINE("[TableMigration::run] not the last worker") TURF_TRACE_DEFINE("[TableMigration::run] a new TableMigration was already started") -TURF_TRACE_DEFINE_END(LeapFrog, 33) +TURF_TRACE_DEFINE_END(Leapfrog, 33) } // namespace details } // namespace junction diff --git a/junction/details/LeapFrog.h b/junction/details/Leapfrog.h similarity index 92% rename from junction/details/LeapFrog.h rename to junction/details/Leapfrog.h index bc184f9..33fd5be 100644 --- a/junction/details/LeapFrog.h +++ b/junction/details/Leapfrog.h @@ -30,10 +30,10 @@ namespace junction { namespace details { -TURF_TRACE_DECLARE(LeapFrog, 33) +TURF_TRACE_DECLARE(Leapfrog, 33) template -struct LeapFrog { +struct Leapfrog { typedef typename Map::Hash Hash; typedef typename Map::Value Value; typedef typename Map::KeyTraits KeyTraits; @@ -153,7 +153,7 @@ struct LeapFrog { }; static Cell* find(Hash hash, Table* table) { - TURF_TRACE(LeapFrog, 0, "[find] called", uptr(table), hash); + TURF_TRACE(Leapfrog, 0, "[find] called", uptr(table), hash); TURF_ASSERT(table); TURF_ASSERT(hash != KeyTraits::NullHash); ureg sizeMask = table->sizeMask; @@ -163,7 +163,7 @@ struct LeapFrog { Cell* cell = group->cells + (idx & 3); Hash probeHash = cell->hash.load(turf::Relaxed); if (probeHash == hash) { - TURF_TRACE(LeapFrog, 1, "[find] found existing cell optimistically", uptr(table), idx); + TURF_TRACE(Leapfrog, 1, "[find] found existing cell optimistically", uptr(table), idx); return cell; } else if (probeHash == KeyTraits::NullHash) { return cell = NULL; @@ -178,7 +178,7 @@ struct LeapFrog { // Note: probeHash might actually be NULL due to memory reordering of a concurrent insert, // but we don't check for it. We just follow the probe chain. if (probeHash == hash) { - TURF_TRACE(LeapFrog, 2, "[find] found existing cell", uptr(table), idx); + TURF_TRACE(Leapfrog, 2, "[find] found existing cell", uptr(table), idx); return cell; } delta = group->deltas[(idx & 3) + 4].load(turf::Relaxed); @@ -190,7 +190,7 @@ struct LeapFrog { // FIXME: Possible optimization: Dedicated insert for migration? It wouldn't check for InsertResult_AlreadyFound. enum InsertResult { InsertResult_AlreadyFound, InsertResult_InsertedNew, InsertResult_Overflow }; static InsertResult insertOrFind(Hash hash, Table* table, Cell*& cell, ureg& overflowIdx) { - TURF_TRACE(LeapFrog, 3, "[insertOrFind] called", uptr(table), hash); + TURF_TRACE(Leapfrog, 3, "[insertOrFind] called", uptr(table), hash); TURF_ASSERT(table); TURF_ASSERT(hash != KeyTraits::NullHash); ureg sizeMask = table->sizeMask; @@ -202,16 +202,16 @@ struct LeapFrog { Hash probeHash = cell->hash.load(turf::Relaxed); if (probeHash == KeyTraits::NullHash) { if (cell->hash.compareExchangeStrong(probeHash, hash, turf::Relaxed)) { - TURF_TRACE(LeapFrog, 4, "[insertOrFind] reserved first cell", uptr(table), idx); + TURF_TRACE(Leapfrog, 4, "[insertOrFind] reserved first cell", uptr(table), idx); // There are no links to set. We're done. return InsertResult_InsertedNew; } else { - TURF_TRACE(LeapFrog, 5, "[insertOrFind] race to reserve first cell", uptr(table), idx); + TURF_TRACE(Leapfrog, 5, "[insertOrFind] race to reserve first cell", uptr(table), idx); // Fall through to check if it was the same hash... } } if (probeHash == hash) { - TURF_TRACE(LeapFrog, 6, "[insertOrFind] found in first cell", uptr(table), idx); + TURF_TRACE(Leapfrog, 6, "[insertOrFind] found in first cell", uptr(table), idx); return InsertResult_AlreadyFound; } @@ -234,14 +234,14 @@ struct LeapFrog { // Cell was linked, but hash is not visible yet. // We could avoid this case (and guarantee it's visible) using acquire & release, but instead, // just poll until it becomes visible. - TURF_TRACE(LeapFrog, 7, "[insertOrFind] race to read hash", uptr(table), idx); + TURF_TRACE(Leapfrog, 7, "[insertOrFind] race to read hash", uptr(table), idx); do { probeHash = cell->hash.load(turf::Acquire); } while (probeHash == KeyTraits::NullHash); } TURF_ASSERT(((probeHash ^ hash) & sizeMask) == 0); // Only hashes in same bucket can be linked if (probeHash == hash) { - TURF_TRACE(LeapFrog, 8, "[insertOrFind] found in probe chain", uptr(table), idx); + TURF_TRACE(Leapfrog, 8, "[insertOrFind] found in probe chain", uptr(table), idx); return InsertResult_AlreadyFound; } } else { @@ -259,7 +259,7 @@ struct LeapFrog { // It's an empty cell. Try to reserve it. if (cell->hash.compareExchangeStrong(probeHash, hash, turf::Relaxed)) { // Success. We've reserved the cell. Link it to previous cell in same bucket. - TURF_TRACE(LeapFrog, 9, "[insertOrFind] reserved cell", uptr(table), idx); + TURF_TRACE(Leapfrog, 9, "[insertOrFind] reserved cell", uptr(table), idx); TURF_ASSERT(probeDelta == 0); u8 desiredDelta = idx - prevLinkIdx; #if TURF_WITH_ASSERTS @@ -270,19 +270,19 @@ struct LeapFrog { #endif return InsertResult_InsertedNew; } else { - TURF_TRACE(LeapFrog, 10, "[insertOrFind] race to reserve cell", uptr(table), idx); + TURF_TRACE(Leapfrog, 10, "[insertOrFind] race to reserve cell", uptr(table), idx); // Fall through to check if it's the same hash... } } Hash x = (probeHash ^ hash); // Check for same hash. if (!x) { - TURF_TRACE(LeapFrog, 11, "[insertOrFind] found outside probe chain", uptr(table), idx); + TURF_TRACE(Leapfrog, 11, "[insertOrFind] found outside probe chain", uptr(table), idx); return InsertResult_AlreadyFound; } // Check for same bucket. if ((x & sizeMask) == 0) { - TURF_TRACE(LeapFrog, 12, "[insertOrFind] found late-arriving cell in same bucket", uptr(table), idx); + TURF_TRACE(Leapfrog, 12, "[insertOrFind] found late-arriving cell in same bucket", uptr(table), idx); // Attempt to set the link on behalf of the late-arriving cell. // This is usually redundant, but if we don't attempt to set the late-arriving cell's link here, // there's no guarantee that our own link chain will be well-formed by the time this function returns. @@ -292,7 +292,7 @@ struct LeapFrog { probeDelta = prevLink->exchange(desiredDelta, turf::Relaxed); TURF_ASSERT(probeDelta == 0 || probeDelta == desiredDelta); if (probeDelta == 0) - TURF_TRACE(LeapFrog, 13, "[insertOrFind] set link on behalf of late-arriving cell", uptr(table), idx); + TURF_TRACE(Leapfrog, 13, "[insertOrFind] set link on behalf of late-arriving cell", uptr(table), idx); #else prevLink->store(desiredDelta, turf::Relaxed); #endif @@ -302,7 +302,7 @@ struct LeapFrog { } // Table is too full to insert. overflowIdx = idx + 1; - TURF_TRACE(LeapFrog, 14, "[insertOrFind] overflow", uptr(table), overflowIdx); + TURF_TRACE(Leapfrog, 14, "[insertOrFind] overflow", uptr(table), overflowIdx); return InsertResult_Overflow; } } @@ -310,15 +310,15 @@ struct LeapFrog { static void beginTableMigrationToSize(Map& map, Table* table, ureg nextTableSize) { // Create new migration by DCLI. - TURF_TRACE(LeapFrog, 15, "[beginTableMigrationToSize] called", 0, 0); + TURF_TRACE(Leapfrog, 15, "[beginTableMigrationToSize] called", 0, 0); SimpleJobCoordinator::Job* job = table->jobCoordinator.loadConsume(); if (job) { - TURF_TRACE(LeapFrog, 16, "[beginTableMigrationToSize] new migration already exists", 0, 0); + TURF_TRACE(Leapfrog, 16, "[beginTableMigrationToSize] new migration already exists", 0, 0); } else { turf::LockGuard guard(table->mutex); job = table->jobCoordinator.loadConsume(); // Non-atomic would be sufficient, but that's OK. if (job) { - TURF_TRACE(LeapFrog, 17, "[beginTableMigrationToSize] new migration already exists (double-checked)", 0, 0); + TURF_TRACE(Leapfrog, 17, "[beginTableMigrationToSize] new migration already exists (double-checked)", 0, 0); } else { // Create new migration. TableMigration* migration = TableMigration::create(map, 1); @@ -343,7 +343,7 @@ struct LeapFrog { Value value = cell->value.load(turf::Relaxed); if (value == Value(ValueTraits::Redirect)) { // Another thread kicked off the jobCoordinator. The caller will participate upon return. - TURF_TRACE(LeapFrog, 18, "[beginTableMigration] redirected while determining table size", 0, 0); + TURF_TRACE(Leapfrog, 18, "[beginTableMigration] redirected while determining table size", 0, 0); return; } if (value != Value(ValueTraits::NullValue)) @@ -363,10 +363,10 @@ struct LeapFrog { ureg nextTableSize = turf::util::max(InitialSize, turf::util::roundUpPowerOf2(ureg(estimatedInUse * 2))); beginTableMigrationToSize(map, table, nextTableSize); } -}; // LeapFrog +}; // Leapfrog template -bool LeapFrog::TableMigration::migrateRange(Table* srcTable, ureg startIdx) { +bool Leapfrog::TableMigration::migrateRange(Table* srcTable, ureg startIdx) { ureg srcSizeMask = srcTable->sizeMask; ureg endIdx = turf::util::min(startIdx + TableMigrationUnitSize, srcSizeMask + 1); // Iterate over source range. @@ -384,12 +384,12 @@ bool LeapFrog::TableMigration::migrateRange(Table* srcTable, ureg startIdx) srcCell->value.compareExchange(Value(ValueTraits::NullValue), Value(ValueTraits::Redirect), turf::Relaxed); if (srcValue == Value(ValueTraits::Redirect)) { // srcValue is already marked Redirect due to previous incomplete migration. - TURF_TRACE(LeapFrog, 19, "[migrateRange] empty cell already redirected", uptr(srcTable), srcIdx); + TURF_TRACE(Leapfrog, 19, "[migrateRange] empty cell already redirected", uptr(srcTable), srcIdx); break; } if (srcValue == Value(ValueTraits::NullValue)) break; // Redirect has been placed. Break inner loop, continue outer loop. - TURF_TRACE(LeapFrog, 20, "[migrateRange] race to insert key", uptr(srcTable), srcIdx); + TURF_TRACE(Leapfrog, 20, "[migrateRange] race to insert key", uptr(srcTable), srcIdx); // Otherwise, somebody just claimed the cell. Read srcHash again... } else { // Check for deleted/uninitialized value. @@ -398,15 +398,15 @@ bool LeapFrog::TableMigration::migrateRange(Table* srcTable, ureg startIdx) // Try to put a Redirect marker. if (srcCell->value.compareExchangeStrong(srcValue, Value(ValueTraits::Redirect), turf::Relaxed)) break; // Redirect has been placed. Break inner loop, continue outer loop. - TURF_TRACE(LeapFrog, 21, "[migrateRange] race to insert value", uptr(srcTable), srcIdx); + TURF_TRACE(Leapfrog, 21, "[migrateRange] race to insert value", uptr(srcTable), srcIdx); if (srcValue == Value(ValueTraits::Redirect)) { // FIXME: I don't think this will happen. Investigate & change to assert - TURF_TRACE(LeapFrog, 22, "[migrateRange] race inserted Redirect", uptr(srcTable), srcIdx); + TURF_TRACE(Leapfrog, 22, "[migrateRange] race inserted Redirect", uptr(srcTable), srcIdx); break; } } else if (srcValue == Value(ValueTraits::Redirect)) { // srcValue is already marked Redirect due to previous incomplete migration. - TURF_TRACE(LeapFrog, 23, "[migrateRange] in-use cell already redirected", uptr(srcTable), srcIdx); + TURF_TRACE(Leapfrog, 23, "[migrateRange] in-use cell already redirected", uptr(srcTable), srcIdx); break; } @@ -445,11 +445,11 @@ bool LeapFrog::TableMigration::migrateRange(Table* srcTable, ureg startIdx) // srcValue was non-NULL when we decided to migrate it, but it may have changed to NULL // by a late-arriving erase. if (srcValue == Value(ValueTraits::NullValue)) - TURF_TRACE(LeapFrog, 24, "[migrateRange] racing update was erase", uptr(srcTable), srcIdx); + TURF_TRACE(Leapfrog, 24, "[migrateRange] racing update was erase", uptr(srcTable), srcIdx); break; } // There was a late-arriving write (or erase) to the src. Migrate the new value and try again. - TURF_TRACE(LeapFrog, 25, "[migrateRange] race to update migrated value", uptr(srcTable), srcIdx); + TURF_TRACE(Leapfrog, 25, "[migrateRange] race to update migrated value", uptr(srcTable), srcIdx); srcValue = doubleCheckedSrcValue; } // Cell successfully migrated. Proceed to next source cell. @@ -462,13 +462,13 @@ bool LeapFrog::TableMigration::migrateRange(Table* srcTable, ureg startIdx) } template -void LeapFrog::TableMigration::run() { +void Leapfrog::TableMigration::run() { // Conditionally increment the shared # of workers. ureg probeStatus = m_workerStatus.load(turf::Relaxed); do { if (probeStatus & 1) { // End flag is already set, so do nothing. - TURF_TRACE(LeapFrog, 26, "[TableMigration::run] already ended", uptr(this), 0); + TURF_TRACE(Leapfrog, 26, "[TableMigration::run] already ended", uptr(this), 0); return; } } while (!m_workerStatus.compareExchangeWeak(probeStatus, probeStatus + 2, turf::Relaxed, turf::Relaxed)); @@ -481,7 +481,7 @@ void LeapFrog::TableMigration::run() { // Loop over all migration units in this source table. for (;;) { if (m_workerStatus.load(turf::Relaxed) & 1) { - TURF_TRACE(LeapFrog, 27, "[TableMigration::run] detected end flag set", uptr(this), 0); + TURF_TRACE(Leapfrog, 27, "[TableMigration::run] detected end flag set", uptr(this), 0); goto endMigration; } ureg startIdx = source.sourceIndex.fetchAdd(TableMigrationUnitSize, turf::Relaxed); @@ -494,14 +494,14 @@ void LeapFrog::TableMigration::run() { // No other thread can declare the migration successful at this point, because *this* unit will never complete, // hence m_unitsRemaining won't reach zero. // However, multiple threads can independently detect a failed migration at the same time. - TURF_TRACE(LeapFrog, 28, "[TableMigration::run] destination overflow", uptr(source.table), uptr(startIdx)); + TURF_TRACE(Leapfrog, 28, "[TableMigration::run] destination overflow", uptr(source.table), uptr(startIdx)); // The reason we store overflowed in a shared variable is because we can must flush all the worker threads before // we can safely deal with the overflow. Therefore, the thread that detects the failure is often different from // the thread // that deals with it. bool oldOverflowed = m_overflowed.exchange(overflowed, turf::Relaxed); if (oldOverflowed) - TURF_TRACE(LeapFrog, 29, "[TableMigration::run] race to set m_overflowed", uptr(overflowed), + TURF_TRACE(Leapfrog, 29, "[TableMigration::run] race to set m_overflowed", uptr(overflowed), uptr(oldOverflowed)); m_workerStatus.fetchOr(1, turf::Relaxed); goto endMigration; @@ -516,7 +516,7 @@ void LeapFrog::TableMigration::run() { } } } - TURF_TRACE(LeapFrog, 30, "[TableMigration::run] out of migration units", uptr(this), 0); + TURF_TRACE(Leapfrog, 30, "[TableMigration::run] out of migration units", uptr(this), 0); endMigration: // Decrement the shared # of workers. @@ -524,7 +524,7 @@ endMigration: 2, turf::AcquireRelease); // AcquireRelease makes all previous writes visible to the last worker thread. if (probeStatus >= 4) { // There are other workers remaining. Return here so that only the very last worker will proceed. - TURF_TRACE(LeapFrog, 31, "[TableMigration::run] not the last worker", uptr(this), uptr(probeStatus)); + TURF_TRACE(Leapfrog, 31, "[TableMigration::run] not the last worker", uptr(this), uptr(probeStatus)); return; } @@ -543,7 +543,7 @@ endMigration: turf::LockGuard guard(origTable->mutex); SimpleJobCoordinator::Job* checkedJob = origTable->jobCoordinator.loadConsume(); if (checkedJob != this) { - TURF_TRACE(LeapFrog, 32, "[TableMigration::run] a new TableMigration was already started", uptr(origTable), + TURF_TRACE(Leapfrog, 32, "[TableMigration::run] a new TableMigration was already started", uptr(origTable), uptr(checkedJob)); } else { TableMigration* migration = TableMigration::create(m_map, m_numSources + 1); diff --git a/junction/extra/impl/MapAdapter_LeapFrog.h b/junction/extra/impl/MapAdapter_Leapfrog.h similarity index 90% rename from junction/extra/impl/MapAdapter_LeapFrog.h rename to junction/extra/impl/MapAdapter_Leapfrog.h index c277044..7661725 100644 --- a/junction/extra/impl/MapAdapter_LeapFrog.h +++ b/junction/extra/impl/MapAdapter_Leapfrog.h @@ -15,7 +15,7 @@ #include #include -#include +#include #include namespace junction { @@ -23,7 +23,7 @@ namespace extra { class MapAdapter { public: - static TURF_CONSTEXPR const char* MapName = "Junction LeapFrog map"; + static TURF_CONSTEXPR const char* MapName = "Junction Leapfrog map"; MapAdapter(ureg) { } @@ -49,7 +49,7 @@ public: } }; - typedef ConcurrentMap_LeapFrog Map; + typedef ConcurrentMap_Leapfrog Map; static ureg getInitialCapacity(ureg maxPopulation) { return turf::util::roundUpPowerOf2(maxPopulation / 4); diff --git a/samples/MapMemoryBench/TestAllMaps.py b/samples/MapMemoryBench/TestAllMaps.py index 1dfc5fa..f84ef12 100644 --- a/samples/MapMemoryBench/TestAllMaps.py +++ b/samples/MapMemoryBench/TestAllMaps.py @@ -10,7 +10,7 @@ CMAKE = os.getenv('CMAKE', 'cmake') ALL_MAPS = [ ('michael', 'junction/extra/impl/MapAdapter_CDS_Michael.h', ['-DJUNCTION_WITH_CDS=1', '-DTURF_WITH_EXCEPTIONS=1']), ('linear', 'junction/extra/impl/MapAdapter_Linear.h', []), - ('leapfrog', 'junction/extra/impl/MapAdapter_LeapFrog.h', []), + ('leapfrog', 'junction/extra/impl/MapAdapter_Leapfrog.h', []), ('grampa', 'junction/extra/impl/MapAdapter_Grampa.h', []), ('stdmap', 'junction/extra/impl/MapAdapter_StdMap.h', []), ('folly', 'junction/extra/impl/MapAdapter_Folly.h', ['-DJUNCTION_WITH_FOLLY=1', '-DTURF_WITH_EXCEPTIONS=1']), diff --git a/samples/MapPerformanceTests/TestAllMaps.py b/samples/MapPerformanceTests/TestAllMaps.py index 1e76984..792e196 100644 --- a/samples/MapPerformanceTests/TestAllMaps.py +++ b/samples/MapPerformanceTests/TestAllMaps.py @@ -11,7 +11,7 @@ ALL_MAPS = [ ('null', 'junction/extra/impl/MapAdapter_Null.h', [], ['-i256', '-c10']), ('michael', 'junction/extra/impl/MapAdapter_CDS_Michael.h', ['-DJUNCTION_WITH_CDS=1', '-DTURF_WITH_EXCEPTIONS=1'], ['-i256', '-c10']), ('linear', 'junction/extra/impl/MapAdapter_Linear.h', [], ['-i256', '-c10']), - ('leapfrog', 'junction/extra/impl/MapAdapter_LeapFrog.h', [], ['-i256', '-c10']), + ('leapfrog', 'junction/extra/impl/MapAdapter_Leapfrog.h', [], ['-i256', '-c10']), ('grampa', 'junction/extra/impl/MapAdapter_Grampa.h', [], ['-i256', '-c10']), ('stdmap', 'junction/extra/impl/MapAdapter_StdMap.h', [], ['-i256', '-c10']), ('folly', 'junction/extra/impl/MapAdapter_Folly.h', ['-DJUNCTION_WITH_FOLLY=1', '-DTURF_WITH_EXCEPTIONS=1'], ['-i256', '-c1']), diff --git a/samples/MapScalabilityTests/TestAllMaps.py b/samples/MapScalabilityTests/TestAllMaps.py index bc9cbd5..83359b6 100644 --- a/samples/MapScalabilityTests/TestAllMaps.py +++ b/samples/MapScalabilityTests/TestAllMaps.py @@ -10,7 +10,7 @@ CMAKE = os.getenv('CMAKE', 'cmake') ALL_MAPS = [ ('michael', 'junction/extra/impl/MapAdapter_CDS_Michael.h', ['-DJUNCTION_WITH_CDS=1', '-DTURF_WITH_EXCEPTIONS=1'], ['-i10000', '-c200']), ('linear', 'junction/extra/impl/MapAdapter_Linear.h', [], ['-i10000', '-c200']), - ('leapfrog', 'junction/extra/impl/MapAdapter_LeapFrog.h', [], ['-i10000', '-c200']), + ('leapfrog', 'junction/extra/impl/MapAdapter_Leapfrog.h', [], ['-i10000', '-c200']), ('grampa', 'junction/extra/impl/MapAdapter_Grampa.h', [], ['-i10000', '-c200']), ('stdmap', 'junction/extra/impl/MapAdapter_StdMap.h', [], ['-i10000', '-c10']), ('folly', 'junction/extra/impl/MapAdapter_Folly.h', ['-DJUNCTION_WITH_FOLLY=1', '-DTURF_WITH_EXCEPTIONS=1'], ['-i2000', '-c1']), -- 2.34.1