Add SingleMap_Leapfrog
authorJeff Preshing <filter-github@preshing.com>
Mon, 29 Feb 2016 18:40:25 +0000 (13:40 -0500)
committerJeff Preshing <filter-github@preshing.com>
Mon, 29 Feb 2016 18:40:25 +0000 (13:40 -0500)
junction/ConcurrentMap_Leapfrog.h
junction/Core.h
junction/SingleMap_Leapfrog.h [new file with mode: 0644]
junction/SingleMap_Linear.h
junction/details/Leapfrog.h
junction/extra/impl/MapAdapter_Leapfrog_RWLock.h [new file with mode: 0644]

index 89ba120..3a8493e 100644 (file)
@@ -114,6 +114,12 @@ public:
                     return; // Found an existing value
                 }
                 case Details::InsertResult_Overflow: {
                     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;
                 }
                     Details::beginTableMigration(m_map, m_table, overflowIdx);
                     break;
                 }
index e670b5d..d2ec778 100644 (file)
@@ -30,4 +30,7 @@ namespace junction {
 using namespace turf::intTypes;
 }
 
 using namespace turf::intTypes;
 }
 
+// Enable this to force migration overflows (for test purposes):
+#define JUNCTION_LEAPFROG_FORCE_MIGRATION_OVERFLOWS 0
+
 #endif // JUNCTION_CORE_H
 #endif // JUNCTION_CORE_H
diff --git a/junction/SingleMap_Leapfrog.h b/junction/SingleMap_Leapfrog.h
new file mode 100644 (file)
index 0000000..b83d095
--- /dev/null
@@ -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 <junction/Core.h>
+#include <junction/MapTraits.h>
+#include <turf/Util.h>
+#include <turf/Heap.h>
+
+namespace junction {
+
+template <typename Key, typename Value, class KeyTraits = DefaultKeyTraits<Key>, class ValueTraits = DefaultValueTraits<Value>>
+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
index f68ec10..ff1fd52 100644 (file)
@@ -33,10 +33,11 @@ private:
     };
 
     Cell* m_cells;
     };
 
     Cell* m_cells;
-    u32 m_sizeMask;
-    u32 m_population;
+    ureg m_sizeMask;
+    ureg m_population;
 
     static Cell* createTable(ureg size) {
 
     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));
         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) {
     }
 
     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);
         for (ureg i = 0; i < size; i++)
             cells[i].~Cell();
         TURF_HEAP.free(cells);
@@ -53,8 +55,7 @@ private:
         return (population * 4) >= (sizeMask * 3);
     }
 
         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);
         Cell* srcCells = m_cells;
         ureg srcSize = m_sizeMask + 1;
         m_cells = createTable(desiredSize);
@@ -75,22 +76,21 @@ private:
     }
 
 public:
     }
 
 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);
     }
 
     }
 
     ~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
     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++) {
             Hash hash = KeyTraits::hash(key);
             TURF_ASSERT(hash != KeyTraits::NullHash);
             for (ureg idx = hash;; idx++) {
@@ -106,7 +106,7 @@ public:
         }
 
         // Constructor: Find with insert
         }
 
         // 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 (;;) {
             Hash hash = KeyTraits::hash(key);
             TURF_ASSERT(hash != KeyTraits::NullHash);
             for (;;) {
@@ -124,14 +124,14 @@ public:
                     }
                     map.m_population++;
                     m_cell->hash = hash;
                     }
                     map.m_population++;
                     m_cell->hash = hash;
-                    TURF_ASSERT(m_cell->value == NULL);
+                    TURF_ASSERT(m_cell->value == Value(ValueTraits::NullValue));
                     return;
                 }
             }
         }
 
                     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:
         }
 
     public:
@@ -154,7 +154,7 @@ public:
 
         Value erase() {
             TURF_ASSERT(m_cell);
 
         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;
             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;
                 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;
                     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) {
     }
 
     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) {
         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) {
         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;
         if (iter.isValid())
             return iter.erase();
         return NULL;
index 33fd5be..8b511c5 100644 (file)
@@ -24,9 +24,6 @@
 #include <junction/SimpleJobCoordinator.h>
 #include <junction/QSBR.h>
 
 #include <junction/SimpleJobCoordinator.h>
 #include <junction/QSBR.h>
 
-// Enable this to force migration overflows (for test purposes):
-#define JUNCTION_LEAPFROG_FORCE_MIGRATION_OVERFLOWS 0
-
 namespace junction {
 namespace details {
 
 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 (file)
index 0000000..547cee3
--- /dev/null
@@ -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 <junction/Core.h>
+#include <junction/SingleMap_Leapfrog.h>
+#include <turf/RWLock.h>
+#include <turf/Util.h>
+
+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<u32, void*> m_map;
+
+    public:
+        Map(ureg capacity) : m_map(capacity) {
+        }
+
+        void set(u32 key, void* value) {
+            turf::ExclusiveLockGuard<turf::RWLock> guard(m_rwLock);
+            m_map.set(key, value);
+        }
+
+        void* get(u32 key) {
+            turf::SharedLockGuard<turf::RWLock> guard(m_rwLock);
+            return m_map.get(key);
+        }
+
+        void erase(u32 key) {
+            turf::ExclusiveLockGuard<turf::RWLock> 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