From: Jeff Preshing Date: Mon, 29 Feb 2016 18:40:25 +0000 (-0500) Subject: Add SingleMap_Leapfrog X-Git-Url: http://plrg.eecs.uci.edu/git/?p=junction.git;a=commitdiff_plain;h=67553e4e9f491e31e92a0ccd2967eb34b0c6f206 Add SingleMap_Leapfrog --- diff --git a/junction/ConcurrentMap_Leapfrog.h b/junction/ConcurrentMap_Leapfrog.h index 89ba120..3a8493e 100644 --- a/junction/ConcurrentMap_Leapfrog.h +++ b/junction/ConcurrentMap_Leapfrog.h @@ -114,6 +114,12 @@ public: return; // Found an existing value } case Details::InsertResult_Overflow: { + // Unlike ConcurrentMap_Linear, we don't need to keep track of & pass a "mustDouble" flag. + // Passing overflowIdx is sufficient to prevent an infinite loop here. + // It defines the start of the range of cells to check while estimating total cells in use. + // After the first migration, deleted keys are purged, so if we hit this line during the + // second loop iteration, every cell in the range will be in use, thus the estimate will be 100%. + // (Concurrent deletes could result in further iterations, but it will eventually settle.) Details::beginTableMigration(m_map, m_table, overflowIdx); break; } diff --git a/junction/Core.h b/junction/Core.h index e670b5d..d2ec778 100644 --- a/junction/Core.h +++ b/junction/Core.h @@ -30,4 +30,7 @@ namespace junction { using namespace turf::intTypes; } +// Enable this to force migration overflows (for test purposes): +#define JUNCTION_LEAPFROG_FORCE_MIGRATION_OVERFLOWS 0 + #endif // JUNCTION_CORE_H diff --git a/junction/SingleMap_Leapfrog.h b/junction/SingleMap_Leapfrog.h new file mode 100644 index 0000000..b83d095 --- /dev/null +++ b/junction/SingleMap_Leapfrog.h @@ -0,0 +1,289 @@ +/*------------------------------------------------------------------------ + Junction: Concurrent data structures in C++ + Copyright (c) 2016 Jeff Preshing + + Distributed under the Simplified BSD License. + Original location: https://github.com/preshing/junction + + This software is distributed WITHOUT ANY WARRANTY; without even the + implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + See the LICENSE file for more information. +------------------------------------------------------------------------*/ + +#ifndef JUNCTION_SINGLEMAP_LEAPFROG_H +#define JUNCTION_SINGLEMAP_LEAPFROG_H + +#include +#include +#include +#include + +namespace junction { + +template , class ValueTraits = DefaultValueTraits> +class SingleMap_Leapfrog { +private: + typedef typename KeyTraits::Hash Hash; + + static const ureg InitialSize = 8; + static const ureg LinearSearchLimit = 128; + static const ureg CellsInUseSample = LinearSearchLimit; + TURF_STATIC_ASSERT(LinearSearchLimit > 0 && LinearSearchLimit < 256); // Must fit in CellGroup::links + TURF_STATIC_ASSERT(CellsInUseSample > 0 && CellsInUseSample <= LinearSearchLimit); // Limit sample to failed search chain + + struct Cell { + Hash hash; + Value value; + Cell(Hash hash, Value value) : hash(hash), value(value) { + } + }; + + struct CellGroup { + u8 deltas[8]; + Cell cells[4]; + }; + + CellGroup* m_cellGroups; + ureg m_sizeMask; + + static CellGroup* createTable(ureg size = InitialSize) { + TURF_ASSERT(size >= 4 && turf::util::isPowerOf2(size)); + CellGroup* cellGroups = (CellGroup*) TURF_HEAP.alloc(sizeof(CellGroup) * (size >> 2)); + for (ureg i = 0; i < (size >> 2); i++) { + CellGroup* group = cellGroups + i; + ureg j; + for (j = 0; j < 8; j++) + group->deltas[j] = 0; + for (j = 0; j < 4; j++) + new (group->cells + j) Cell(KeyTraits::NullHash, Value(ValueTraits::NullValue)); + } + return cellGroups; + } + + static void destroyTable(CellGroup* cellGroups, ureg size) { + TURF_ASSERT(size >= 4 && turf::util::isPowerOf2(size)); + for (ureg i = 0; i < (size >> 2); i++) { + CellGroup* group = cellGroups + i; + for (ureg j = 0; j < 4; j++) + group->cells[i].~Cell(); + } + TURF_HEAP.free(cellGroups); + } + + enum InsertResult { InsertResult_AlreadyFound, InsertResult_InsertedNew, InsertResult_Overflow }; + InsertResult insertOrFind(Hash hash, Cell*& cell, ureg& overflowIdx) { + TURF_ASSERT(hash != KeyTraits::NullHash); + ureg idx = ureg(hash); + // Check hashed cell first, though it may not even belong to the bucket. + CellGroup* group = m_cellGroups + ((idx & m_sizeMask) >> 2); + cell = group->cells + (idx & 3); + if (cell->hash == hash) + return InsertResult_AlreadyFound; // Key found in table. + else if (cell->hash == KeyTraits::NullHash) { + // Reserve the first cell. + cell->hash = hash; + return InsertResult_InsertedNew; + } + // Follow probe chain for our bucket. + ureg maxIdx = idx + m_sizeMask; + u8* prevLink = group->deltas + (idx & 3); + u8 delta = *prevLink; + while (delta) { + idx += delta; + group = m_cellGroups + ((idx & m_sizeMask) >> 2); + cell = group->cells + (idx & 3); + if (cell->hash == hash) + return InsertResult_AlreadyFound; // Key found in table + prevLink = group->deltas + (idx & 3) + 4; + delta = *prevLink; + } + // Reached the end of the link chain for this bucket. Key does not exist in table. + // Switch to linear probing to find a free cell. + ureg prevLinkIdx = idx; + TURF_ASSERT(sreg(maxIdx - idx) >= 0); // Nobody would have linked an idx that's out of range. + ureg linearProbesRemaining = turf::util::min(maxIdx - idx, LinearSearchLimit); + while (linearProbesRemaining-- > 0) { + idx++; + group = m_cellGroups + ((idx & m_sizeMask) >> 2); + cell = group->cells + (idx & 3); + if (cell->hash == KeyTraits::NullHash) { + // It's an empty cell. Reserve it. + cell->hash = hash; + // Link it to previous cell in the same bucket. + *prevLink = idx - prevLinkIdx; + return InsertResult_InsertedNew; + } + // In a single-threaded map, it's impossible for a matching hash to appear outside the probe chain. + TURF_ASSERT(cell->hash != hash); + // Continue linear search... + } + // Table is too full to insert. + overflowIdx = idx + 1; + return InsertResult_Overflow; + } + + bool tryMigrateToNewTableWithSize(ureg desiredSize) { + CellGroup* srcCellGroups = m_cellGroups; + ureg srcSize = m_sizeMask + 1; + m_cellGroups = createTable(desiredSize); + m_sizeMask = desiredSize - 1; + for (ureg srcIdx = 0; srcIdx < srcSize; srcIdx++) { + CellGroup* srcGroup = srcCellGroups + (srcIdx >> 2); + Cell* srcCell = srcGroup->cells + (srcIdx & 3); + if (srcCell->value != Value(ValueTraits::NullValue)) { + Cell* dstCell; + ureg overflowIdx; + InsertResult result = insertOrFind(srcCell->hash, dstCell, overflowIdx); + TURF_ASSERT(result != InsertResult_AlreadyFound); + if (result == InsertResult_Overflow) { + // Migration failed; destination table too small + destroyTable(m_cellGroups, m_sizeMask + 1); + m_cellGroups = srcCellGroups; + m_sizeMask = srcSize - 1; + return false; + } + dstCell->value = srcCell->value; + } + } + destroyTable(srcCellGroups, srcSize); + return true; + } + + void migrateToNewTable(ureg overflowIdx) { + // Estimate number of cells in use based on a small sample. + ureg idx = overflowIdx - CellsInUseSample; + ureg inUseCells = 0; + for (ureg linearProbesRemaining = CellsInUseSample; linearProbesRemaining > 0; linearProbesRemaining--) { + CellGroup* group = m_cellGroups + ((idx & m_sizeMask) >> 2); + Cell* cell = group->cells + (idx & 3); + if (cell->value != Value(ValueTraits::NullValue)) + inUseCells++; + idx++; + } + float inUseRatio = float(inUseCells) / CellsInUseSample; + float estimatedInUse = (m_sizeMask + 1) * inUseRatio; +#if JUNCTION_LEAPFROG_FORCE_MIGRATION_OVERFLOWS + // Periodically underestimate the number of cells in use. + // This exercises the code that handles overflow during migration. + static ureg counter = 1; + if ((++counter & 3) == 0) { + estimatedInUse /= 4; + } +#endif + ureg nextTableSize = turf::util::max(InitialSize, turf::util::roundUpPowerOf2(ureg(estimatedInUse * 2))); + for (;;) { + if (tryMigrateToNewTableWithSize(nextTableSize)) + break; // Success + // Failed; try a larger table + nextTableSize *= 2; + } + } + +public: + SingleMap_Leapfrog(ureg initialSize = 8) : m_cellGroups(createTable(initialSize)), m_sizeMask(initialSize - 1) { + } + + ~SingleMap_Leapfrog() { + destroyTable(m_cellGroups, m_sizeMask + 1); + } + + class Mutator { + private: + friend class SingleMap_Leapfrog; + SingleMap_Leapfrog& m_map; + Cell* m_cell; + + // Constructor: Find without insert + Mutator(SingleMap_Leapfrog& map, Key key, bool) : m_map(map) { + Hash hash = KeyTraits::hash(key); + TURF_ASSERT(hash != KeyTraits::NullHash); + // Optimistically check hashed cell even though it might belong to another bucket + ureg idx = ureg(hash); + CellGroup* group = map.m_cellGroups + ((idx & map.m_sizeMask) >> 2); + m_cell = group->cells + (idx & 3); + if (m_cell->hash == hash) + return; // Key found in table. + // Follow probe chain for our bucket. + u8 delta = group->deltas[idx & 3]; + while (delta) { + idx += delta; + group = map.m_cellGroups + ((idx & map.m_sizeMask) >> 2); + m_cell = group->cells + (idx & 3); + if (m_cell->hash == hash) + return; // Key found in table + delta = group->deltas[(idx & 3) + 4]; + } + // End of probe chain, not found + m_cell = NULL; + return; + } + + // Constructor: Find with insert + Mutator(SingleMap_Leapfrog& map, Key key) : m_map(map) { + Hash hash = KeyTraits::hash(key); + for (;;) { + ureg overflowIdx; + if (map.insertOrFind(hash, m_cell, overflowIdx) != InsertResult_Overflow) + return; + // Insert overflow. Migrate and try again. + // On the first iteration of this loop, deleted cells will be purged. + // The second iteration (if any) will always double in size. + // On the third iteration (if any), the insert will succeed. + map.migrateToNewTable(overflowIdx); + } + } + + public: + bool isValid() const { + return !!m_cell; + } + + Value getValue() const { + TURF_ASSERT(m_cell); + return m_cell->value; + } + + Value exchangeValue(Value desired) { + TURF_ASSERT(m_cell); + TURF_ASSERT(desired != NULL); // Use eraseValue() + Value oldValue = m_cell->value; + m_cell->value = desired; + return oldValue; + } + + Value erase() { + TURF_ASSERT(m_cell); + // Since this map is single-threaded, we could conceivably shuffle existing cells around to safely fill + // gaps, much like SingleMap_Linear currently does. + // Instead, we'll just leave them as deleted entries and let them get purged on the next migration. + Value oldValue = m_cell->value; + m_cell->value = Value(ValueTraits::NullValue); + return oldValue; + } + }; + + Mutator insertOrFindKey(const Key& key) { + return Mutator(*this, key); + } + + Value get(const Key& key) { + Mutator iter(*this, key, false); + return iter.isValid() ? iter.getValue() : NULL; + } + + Value set(const Key& key, Value desired) { + Mutator iter(*this, key); + return iter.exchangeValue(desired); + } + + Value erase(const Key& key) { + Mutator iter(*this, key, false); + if (iter.isValid()) + return iter.erase(); + return NULL; + } +}; + +} // namespace junction + +#endif // JUNCTION_SINGLEMAP_LEAPFROG_H diff --git a/junction/SingleMap_Linear.h b/junction/SingleMap_Linear.h index f68ec10..ff1fd52 100644 --- a/junction/SingleMap_Linear.h +++ b/junction/SingleMap_Linear.h @@ -33,10 +33,11 @@ private: }; Cell* m_cells; - u32 m_sizeMask; - u32 m_population; + ureg m_sizeMask; + ureg m_population; static Cell* createTable(ureg size) { + TURF_ASSERT(turf::util::isPowerOf2(size)); Cell* cells = (Cell*) TURF_HEAP.alloc(sizeof(Cell) * size); for (ureg i = 0; i < size; i++) new (cells + i) Cell(KeyTraits::NullHash, Value(ValueTraits::NullValue)); @@ -44,6 +45,7 @@ private: } static void destroyTable(Cell* cells, ureg size) { + TURF_ASSERT(turf::util::isPowerOf2(size)); for (ureg i = 0; i < size; i++) cells[i].~Cell(); TURF_HEAP.free(cells); @@ -53,8 +55,7 @@ private: return (population * 4) >= (sizeMask * 3); } - void migrateToNewTable(size_t desiredSize) { - TURF_ASSERT(turf::util::isPowerOf2(desiredSize)); + void migrateToNewTable(ureg desiredSize) { Cell* srcCells = m_cells; ureg srcSize = m_sizeMask + 1; m_cells = createTable(desiredSize); @@ -75,22 +76,21 @@ private: } public: - SingleMap_Linear(size_t initialSize = 8) : m_cells(createTable(initialSize)), m_sizeMask(initialSize - 1), m_population(0) { - TURF_ASSERT(turf::util::isPowerOf2(initialSize)); + SingleMap_Linear(ureg initialSize = 8) : m_cells(createTable(initialSize)), m_sizeMask(initialSize - 1), m_population(0) { } ~SingleMap_Linear() { destroyTable(m_cells, m_sizeMask + 1); } - class Iterator { + class Mutator { private: friend class SingleMap_Linear; SingleMap_Linear& m_map; Cell* m_cell; // Constructor: Find without insert - Iterator(SingleMap_Linear& map, Key key, bool) : m_map(map) { + Mutator(SingleMap_Linear& map, Key key, bool) : m_map(map) { Hash hash = KeyTraits::hash(key); TURF_ASSERT(hash != KeyTraits::NullHash); for (ureg idx = hash;; idx++) { @@ -106,7 +106,7 @@ public: } // Constructor: Find with insert - Iterator(SingleMap_Linear& map, Key key) : m_map(map) { + Mutator(SingleMap_Linear& map, Key key) : m_map(map) { Hash hash = KeyTraits::hash(key); TURF_ASSERT(hash != KeyTraits::NullHash); for (;;) { @@ -124,14 +124,14 @@ public: } map.m_population++; m_cell->hash = hash; - TURF_ASSERT(m_cell->value == NULL); + TURF_ASSERT(m_cell->value == Value(ValueTraits::NullValue)); return; } } } - ~Iterator() { - TURF_ASSERT(!m_cell || m_cell->value != NULL); // Forbid leaving a cell half-inserted. + ~Mutator() { + TURF_ASSERT(!m_cell || m_cell->value != NULL); // In SingleMap_Linear, there are no deleted cells. } public: @@ -154,7 +154,7 @@ public: Value erase() { TURF_ASSERT(m_cell); - TURF_ASSERT(m_cell->value != NULL); // Forbid erasing a cell that's not actually used. + TURF_ASSERT(m_cell->value != Value(ValueTraits::NullValue)); // SingleMap_Linear never contains "deleted" cells. Value oldValue = m_cell->value; // Remove this cell by shuffling neighboring cells so there are no gaps in anyone's probe chain ureg cellIdx = m_cell - m_map.m_cells; @@ -164,7 +164,7 @@ public: if (neighbor->hash == KeyTraits::NullHash) { // Go ahead and clear this cell. It won't break anyone else's probe chain. m_cell->hash = KeyTraits::NullHash; - m_cell->value = NULL; + m_cell->value = Value(ValueTraits::NullValue); m_cell = NULL; m_map.m_population--; return oldValue; @@ -180,22 +180,22 @@ public: } }; - Iterator insertOrFindKey(const Key& key) { - return Iterator(*this, key); + Mutator insertOrFindKey(const Key& key) { + return Mutator(*this, key); } Value get(const Key& key) { - Iterator iter(*this, key, false); + Mutator iter(*this, key, false); return iter.isValid() ? iter.getValue() : NULL; } Value set(const Key& key, Value desired) { - Iterator iter(*this, key); + Mutator iter(*this, key); return iter.exchangeValue(desired); } Value erase(const Key& key) { - Iterator iter(*this, key, false); + Mutator iter(*this, key, false); if (iter.isValid()) return iter.erase(); return NULL; diff --git a/junction/details/Leapfrog.h b/junction/details/Leapfrog.h index 33fd5be..8b511c5 100644 --- a/junction/details/Leapfrog.h +++ b/junction/details/Leapfrog.h @@ -24,9 +24,6 @@ #include #include -// Enable this to force migration overflows (for test purposes): -#define JUNCTION_LEAPFROG_FORCE_MIGRATION_OVERFLOWS 0 - namespace junction { namespace details { diff --git a/junction/extra/impl/MapAdapter_Leapfrog_RWLock.h b/junction/extra/impl/MapAdapter_Leapfrog_RWLock.h new file mode 100644 index 0000000..547cee3 --- /dev/null +++ b/junction/extra/impl/MapAdapter_Leapfrog_RWLock.h @@ -0,0 +1,79 @@ +/*------------------------------------------------------------------------ + Junction: Concurrent data structures in C++ + Copyright (c) 2016 Jeff Preshing + + Distributed under the Simplified BSD License. + Original location: https://github.com/preshing/junction + + This software is distributed WITHOUT ANY WARRANTY; without even the + implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + See the LICENSE file for more information. +------------------------------------------------------------------------*/ + +#ifndef JUNCTION_EXTRA_IMPL_MAPADAPTER_LEAPFROG_RWLOCK_H +#define JUNCTION_EXTRA_IMPL_MAPADAPTER_LEAPFROG_RWLOCK_H + +#include +#include +#include +#include + +namespace junction { +namespace extra { + +class MapAdapter { +public: + static TURF_CONSTEXPR const char* MapName = "Single + RWLock"; + + MapAdapter(ureg) { + } + + class ThreadContext { + public: + ThreadContext(MapAdapter&, ureg) { + } + + void registerThread() { + } + + void unregisterThread() { + } + + void update() { + } + }; + + class Map { + private: + turf::RWLock m_rwLock; + SingleMap_Leapfrog m_map; + + public: + Map(ureg capacity) : m_map(capacity) { + } + + void set(u32 key, void* value) { + turf::ExclusiveLockGuard guard(m_rwLock); + m_map.set(key, value); + } + + void* get(u32 key) { + turf::SharedLockGuard guard(m_rwLock); + return m_map.get(key); + } + + void erase(u32 key) { + turf::ExclusiveLockGuard guard(m_rwLock); + m_map.erase(key); + } + }; + + static ureg getInitialCapacity(ureg maxPopulation) { + return turf::util::roundUpPowerOf2(maxPopulation / 4); + } +}; + +} // namespace extra +} // namespace junction + +#endif // JUNCTION_EXTRA_IMPL_MAPADAPTER_LEAPFROG_RWLOCK_H