junction/SingleMap_Leapfrog.h

   1 /*------------------------------------------------------------------------
   2   Junction: Concurrent data structures in C++
   3   Copyright (c) 2016 Jeff Preshing
   4
   5   Distributed under the Simplified BSD License.
   6   Original location: https://github.com/preshing/junction
   7
   8   This software is distributed WITHOUT ANY WARRANTY; without even the
   9   implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  10   See the LICENSE file for more information.
  11 ------------------------------------------------------------------------*/
  12
  13 #ifndef JUNCTION_SINGLEMAP_LEAPFROG_H
  14 #define JUNCTION_SINGLEMAP_LEAPFROG_H
  15
  16 #include <junction/Core.h>
  17 #include <junction/MapTraits.h>
  18 #include <turf/Util.h>
  19 #include <turf/Heap.h>
  20
  21 namespace junction {
  22
  23 template <typename Key, typename Value, class KeyTraits = DefaultKeyTraits<Key>, class ValueTraits = DefaultValueTraits<Value>>
  24 class SingleMap_Leapfrog {
  25 private:
  26     typedef typename KeyTraits::Hash Hash;
  27
  28     static const ureg InitialSize = 8;
  29     static const ureg LinearSearchLimit = 128;
  30     static const ureg CellsInUseSample = LinearSearchLimit;
  31     TURF_STATIC_ASSERT(LinearSearchLimit > 0 && LinearSearchLimit < 256);              // Must fit in CellGroup::links
  32     TURF_STATIC_ASSERT(CellsInUseSample > 0 && CellsInUseSample <= LinearSearchLimit); // Limit sample to failed search chain
  33
  34     struct Cell {
  35         Hash hash;
  36         Value value;
  37         Cell(Hash hash, Value value) : hash(hash), value(value) {
  38         }
  39     };
  40
  41     struct CellGroup {
  42         u8 deltas[8];
  43         Cell cells[4];
  44     };
  45
  46     CellGroup* m_cellGroups;
  47     ureg m_sizeMask;
  48
  49     static CellGroup* createTable(ureg size = InitialSize) {
  50         TURF_ASSERT(size >= 4 && turf::util::isPowerOf2(size));
  51         CellGroup* cellGroups = (CellGroup*) TURF_HEAP.alloc(sizeof(CellGroup) * (size >> 2));
  52         for (ureg i = 0; i < (size >> 2); i++) {
  53             CellGroup* group = cellGroups + i;
  54             ureg j;
  55             for (j = 0; j < 8; j++)
  56                 group->deltas[j] = 0;
  57             for (j = 0; j < 4; j++)
  58                 new (group->cells + j) Cell(KeyTraits::NullHash, Value(ValueTraits::NullValue));
  59         }
  60         return cellGroups;
  61     }
  62
  63     static void destroyTable(CellGroup* cellGroups, ureg size) {
  64         TURF_ASSERT(size >= 4 && turf::util::isPowerOf2(size));
  65         for (ureg i = 0; i < (size >> 2); i++) {
  66             CellGroup* group = cellGroups + i;
  67             for (ureg j = 0; j < 4; j++)
  68                 group->cells[i].~Cell();
  69         }
  70         TURF_HEAP.free(cellGroups);
  71     }
  72
  73     enum InsertResult { InsertResult_AlreadyFound, InsertResult_InsertedNew, InsertResult_Overflow };
  74     InsertResult insertOrFind(Hash hash, Cell*& cell, ureg& overflowIdx) {
  75         TURF_ASSERT(hash != KeyTraits::NullHash);
  76         ureg idx = ureg(hash);
  77         // Check hashed cell first, though it may not even belong to the bucket.
  78         CellGroup* group = m_cellGroups + ((idx & m_sizeMask) >> 2);
  79         cell = group->cells + (idx & 3);
  80         if (cell->hash == hash)
  81             return InsertResult_AlreadyFound; // Key found in table.
  82         else if (cell->hash == KeyTraits::NullHash) {
  83             // Reserve the first cell.
  84             cell->hash = hash;
  85             return InsertResult_InsertedNew;
  86         }
  87         // Follow probe chain for our bucket.
  88         ureg maxIdx = idx + m_sizeMask;
  89         u8* prevLink = group->deltas + (idx & 3);
  90         u8 delta = *prevLink;
  91         while (delta) {
  92             idx += delta;
  93             group = m_cellGroups + ((idx & m_sizeMask) >> 2);
  94             cell = group->cells + (idx & 3);
  95             if (cell->hash == hash)
  96                 return InsertResult_AlreadyFound; // Key found in table
  97             prevLink = group->deltas + (idx & 3) + 4;
  98             delta = *prevLink;
  99         }
 100         // Reached the end of the link chain for this bucket. Key does not exist in table.
 101         // Switch to linear probing to find a free cell.
 102         ureg prevLinkIdx = idx;
 103         TURF_ASSERT(sreg(maxIdx - idx) >= 0); // Nobody would have linked an idx that's out of range.
 104         ureg linearProbesRemaining = turf::util::min(maxIdx - idx, LinearSearchLimit);
 105         while (linearProbesRemaining-- > 0) {
 106             idx++;
 107             group = m_cellGroups + ((idx & m_sizeMask) >> 2);
 108             cell = group->cells + (idx & 3);
 109             if (cell->hash == KeyTraits::NullHash) {
 110                 // It's an empty cell. Reserve it.
 111                 cell->hash = hash;
 112                 // Link it to previous cell in the same bucket.
 113                 *prevLink = idx - prevLinkIdx;
 114                 return InsertResult_InsertedNew;
 115             }
 116             // In a single-threaded map, it's impossible for a matching hash to appear outside the probe chain.
 117             TURF_ASSERT(cell->hash != hash);
 118             // Continue linear search...
 119         }
 120         // Table is too full to insert.
 121         overflowIdx = idx + 1;
 122         return InsertResult_Overflow;
 123     }
 124
 125     bool tryMigrateToNewTableWithSize(ureg desiredSize) {
 126         CellGroup* srcCellGroups = m_cellGroups;
 127         ureg srcSize = m_sizeMask + 1;
 128         m_cellGroups = createTable(desiredSize);
 129         m_sizeMask = desiredSize - 1;
 130         for (ureg srcIdx = 0; srcIdx < srcSize; srcIdx++) {
 131             CellGroup* srcGroup = srcCellGroups + (srcIdx >> 2);
 132             Cell* srcCell = srcGroup->cells + (srcIdx & 3);
 133             if (srcCell->value != Value(ValueTraits::NullValue)) {
 134                 Cell* dstCell;
 135                 ureg overflowIdx;
 136                 InsertResult result = insertOrFind(srcCell->hash, dstCell, overflowIdx);
 137                 TURF_ASSERT(result != InsertResult_AlreadyFound);
 138                 if (result == InsertResult_Overflow) {
 139                     // Migration failed; destination table too small
 140                     destroyTable(m_cellGroups, m_sizeMask + 1);
 141                     m_cellGroups = srcCellGroups;
 142                     m_sizeMask = srcSize - 1;
 143                     return false;
 144                 }
 145                 dstCell->value = srcCell->value;
 146             }
 147         }
 148         destroyTable(srcCellGroups, srcSize);
 149         return true;
 150     }
 151
 152     void migrateToNewTable(ureg overflowIdx) {
 153         // Estimate number of cells in use based on a small sample.
 154         ureg idx = overflowIdx - CellsInUseSample;
 155         ureg inUseCells = 0;
 156         for (ureg linearProbesRemaining = CellsInUseSample; linearProbesRemaining > 0; linearProbesRemaining--) {
 157             CellGroup* group = m_cellGroups + ((idx & m_sizeMask) >> 2);
 158             Cell* cell = group->cells + (idx & 3);
 159             if (cell->value != Value(ValueTraits::NullValue))
 160                 inUseCells++;
 161             idx++;
 162         }
 163         float inUseRatio = float(inUseCells) / CellsInUseSample;
 164         float estimatedInUse = (m_sizeMask + 1) * inUseRatio;
 165 #if JUNCTION_LEAPFROG_FORCE_MIGRATION_OVERFLOWS
 166         // Periodically underestimate the number of cells in use.
 167         // This exercises the code that handles overflow during migration.
 168         static ureg counter = 1;
 169         if ((++counter & 3) == 0) {
 170             estimatedInUse /= 4;
 171         }
 172 #endif
 173         ureg nextTableSize = turf::util::max(InitialSize, turf::util::roundUpPowerOf2(ureg(estimatedInUse * 2)));
 174         for (;;) {
 175             if (tryMigrateToNewTableWithSize(nextTableSize))
 176                 break; // Success
 177             // Failed; try a larger table
 178             nextTableSize *= 2;
 179         }
 180     }
 181
 182 public:
 183     SingleMap_Leapfrog(ureg initialSize = 8) : m_cellGroups(createTable(initialSize)), m_sizeMask(initialSize - 1) {
 184     }
 185
 186     ~SingleMap_Leapfrog() {
 187         destroyTable(m_cellGroups, m_sizeMask + 1);
 188     }
 189
 190     class Mutator {
 191     private:
 192         friend class SingleMap_Leapfrog;
 193         SingleMap_Leapfrog& m_map;
 194         Cell* m_cell;
 195
 196         // Constructor: Find without insert
 197         Mutator(SingleMap_Leapfrog& map, Key key, bool) : m_map(map) {
 198             Hash hash = KeyTraits::hash(key);
 199             TURF_ASSERT(hash != KeyTraits::NullHash);
 200             // Optimistically check hashed cell even though it might belong to another bucket
 201             ureg idx = ureg(hash);
 202             CellGroup* group = map.m_cellGroups + ((idx & map.m_sizeMask) >> 2);
 203             m_cell = group->cells + (idx & 3);
 204             if (m_cell->hash == hash)
 205                 return; // Key found in table.
 206             // Follow probe chain for our bucket.
 207             u8 delta = group->deltas[idx & 3];
 208             while (delta) {
 209                 idx += delta;
 210                 group = map.m_cellGroups + ((idx & map.m_sizeMask) >> 2);
 211                 m_cell = group->cells + (idx & 3);
 212                 if (m_cell->hash == hash)
 213                     return; // Key found in table
 214                 delta = group->deltas[(idx & 3) + 4];
 215             }
 216             // End of probe chain, not found
 217             m_cell = NULL;
 218             return;
 219         }
 220
 221         // Constructor: Find with insert
 222         Mutator(SingleMap_Leapfrog& map, Key key) : m_map(map) {
 223             Hash hash = KeyTraits::hash(key);
 224             for (;;) {
 225                 ureg overflowIdx;
 226                 if (map.insertOrFind(hash, m_cell, overflowIdx) != InsertResult_Overflow)
 227                     return;
 228                 // Insert overflow. Migrate and try again.
 229                 // On the first iteration of this loop, deleted cells will be purged.
 230                 // The second iteration (if any) will always double in size.
 231                 // On the third iteration (if any), the insert will succeed.
 232                 map.migrateToNewTable(overflowIdx);
 233             }
 234         }
 235
 236     public:
 237         bool isValid() const {
 238             return !!m_cell;
 239         }
 240
 241         Value getValue() const {
 242             TURF_ASSERT(m_cell);
 243             return m_cell->value;
 244         }
 245
 246         Value exchangeValue(Value desired) {
 247             TURF_ASSERT(m_cell);
 248             TURF_ASSERT(desired != NULL); // Use eraseValue()
 249             Value oldValue = m_cell->value;
 250             m_cell->value = desired;
 251             return oldValue;
 252         }
 253
 254         Value erase() {
 255             TURF_ASSERT(m_cell);
 256             // Since this map is single-threaded, we could conceivably shuffle existing cells around to safely fill
 257             // gaps, much like SingleMap_Linear currently does.
 258             // Instead, we'll just leave them as deleted entries and let them get purged on the next migration.
 259             Value oldValue = m_cell->value;
 260             m_cell->value = Value(ValueTraits::NullValue);
 261             return oldValue;
 262         }
 263     };
 264
 265     Mutator insertOrFindKey(const Key& key) {
 266         return Mutator(*this, key);
 267     }
 268
 269     Value get(const Key& key) {
 270         Mutator iter(*this, key, false);
 271         return iter.isValid() ? iter.getValue() : NULL;
 272     }
 273
 274     Value set(const Key& key, Value desired) {
 275         Mutator iter(*this, key);
 276         return iter.exchangeValue(desired);
 277     }
 278
 279     Value erase(const Key& key) {
 280         Mutator iter(*this, key, false);
 281         if (iter.isValid())
 282             return iter.erase();
 283         return NULL;
 284     }
 285 };
 286
 287 } // namespace junction
 288
 289 #endif // JUNCTION_SINGLEMAP_LEAPFROG_H