HashMap should support selecting a random entry
authorggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 25 Oct 2018 17:41:35 +0000 (17:41 +0000)
committerggaren@apple.com <ggaren@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 25 Oct 2018 17:41:35 +0000 (17:41 +0000)
https://bugs.webkit.org/show_bug.cgi?id=190814

Reviewed by Antti Koivisto.

Source/WTF:

In some cases, remove(begin()) is not quite good enough as a random
eviction strategy. (See https://bugs.webkit.org/show_bug.cgi?id=190792.)
So, let's support real random eviction.

(And by "real" I mean "pseudo".)

* wtf/HashCountedSet.h:
* wtf/HashMap.h:
* wtf/HashSet.h:
* wtf/ListHashSet.h:
(WTF::ListHashSet::random):
(WTF::ListHashSet::random const):
* wtf/LoggingHashMap.h:
* wtf/LoggingHashSet.h: Plumb through the random() iterator.

* wtf/HashTable.h:
(WTF::HashTable::random):
(WTF::HashTable::random const): Implement the random() iterator.
makeIterator() already supports starting from any bucket, so this is
pretty easy.

In the subtle case where we select end(), we choose to wrap around and
return begin(). We expect that clients don't really think of the end()
bucket as being in the domain of the random search. Also, we don't want
to annoy clients who know their tables are non-empty with needless
checks for end().

* wtf/RandomNumber.cpp:
(WTF::weakRandomUint32):
* wtf/RandomNumber.h: Added a free function for weak random numbers so
that clients that want cheap random numbers aren't required to allocate
storage for a WeakRandom generator.

Tools:

Unit testing is fun and easy!

* TestWebKitAPI/Tests/WTF/HashMap.cpp:
(TestWebKitAPI::ZeroHash::hash):
(TestWebKitAPI::TEST):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@237419 268f45cc-cd09-0410-ab3c-d52691b4dbfc

12 files changed:
Source/WTF/ChangeLog
Source/WTF/wtf/HashCountedSet.h
Source/WTF/wtf/HashMap.h
Source/WTF/wtf/HashSet.h
Source/WTF/wtf/HashTable.h
Source/WTF/wtf/ListHashSet.h
Source/WTF/wtf/LoggingHashMap.h
Source/WTF/wtf/LoggingHashSet.h
Source/WTF/wtf/RandomNumber.cpp
Source/WTF/wtf/RandomNumber.h
Tools/ChangeLog
Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp

index 05bd665..1530431 100644 (file)
@@ -1,3 +1,43 @@
+2018-10-25  Geoffrey Garen  <ggaren@apple.com>
+
+        HashMap should support selecting a random entry
+        https://bugs.webkit.org/show_bug.cgi?id=190814
+
+        Reviewed by Antti Koivisto.
+
+        In some cases, remove(begin()) is not quite good enough as a random
+        eviction strategy. (See https://bugs.webkit.org/show_bug.cgi?id=190792.)
+        So, let's support real random eviction.
+
+        (And by "real" I mean "pseudo".)
+
+        * wtf/HashCountedSet.h:
+        * wtf/HashMap.h:
+        * wtf/HashSet.h:
+        * wtf/ListHashSet.h:
+        (WTF::ListHashSet::random):
+        (WTF::ListHashSet::random const):
+        * wtf/LoggingHashMap.h:
+        * wtf/LoggingHashSet.h: Plumb through the random() iterator.
+
+        * wtf/HashTable.h:
+        (WTF::HashTable::random):
+        (WTF::HashTable::random const): Implement the random() iterator.
+        makeIterator() already supports starting from any bucket, so this is
+        pretty easy.
+
+        In the subtle case where we select end(), we choose to wrap around and
+        return begin(). We expect that clients don't really think of the end()
+        bucket as being in the domain of the random search. Also, we don't want
+        to annoy clients who know their tables are non-empty with needless
+        checks for end().
+
+        * wtf/RandomNumber.cpp:
+        (WTF::weakRandomUint32):
+        * wtf/RandomNumber.h: Added a free function for weak random numbers so
+        that clients that want cheap random numbers aren't required to allocate
+        storage for a WeakRandom generator.
+
 2018-10-24  Megan Gardner  <megan_gardner@apple.com>
 
         Turn on Conic Gradients
index bf7b825..5569be8 100644 (file)
@@ -69,6 +69,9 @@ public:
     const_iterator begin() const;
     const_iterator end() const;
 
+    iterator random() { return m_impl.random(); }
+    const_iterator random() const { return m_impl.random(); }
+
     ValuesIteratorRange values();
     const ValuesConstIteratorRange values() const;
 
index 0059e8b..3406f54 100644 (file)
@@ -98,6 +98,9 @@ public:
     const_iterator begin() const;
     const_iterator end() const;
     
+    iterator random() { return m_impl.random(); }
+    const_iterator random() const { return m_impl.random(); }
+
     KeysIteratorRange keys() { return makeSizedIteratorRange(*this, begin().keys(), end().keys()); }
     const KeysConstIteratorRange keys() const { return makeSizedIteratorRange(*this, begin().keys(), end().keys()); }
 
index 8ecd685..70f8820 100644 (file)
@@ -68,6 +68,9 @@ public:
     iterator begin() const;
     iterator end() const;
 
+    iterator random() { return m_impl.random(); }
+    const_iterator random() const { return m_impl.random(); }
+
     iterator find(const ValueType&) const;
     bool contains(const ValueType&) const;
 
index 809adbf..fab69ab 100644 (file)
@@ -32,6 +32,7 @@
 #include <wtf/HashTraits.h>
 #include <wtf/Lock.h>
 #include <wtf/MathExtras.h>
+#include <wtf/RandomNumber.h>
 #include <wtf/StdLibExtras.h>
 #include <wtf/ValueCheck.h>
 
@@ -379,6 +380,18 @@ namespace WTF {
         const_iterator begin() const { return isEmpty() ? end() : makeConstIterator(m_table); }
         const_iterator end() const { return makeKnownGoodConstIterator(m_table + m_tableSize); }
 
+        iterator random()
+        {
+            if (isEmpty())
+                return end();
+            auto it = makeIterator(m_table + (weakRandomUint32() & m_tableSizeMask));
+            if (it == end())
+                return begin();
+            return it;
+        }
+
+        const_iterator random() const { return const_cast<HashTable*>(this)->random().const_iterator(); }
+
         unsigned size() const { return m_keyCount; }
         unsigned capacity() const { return m_tableSize; }
         bool isEmpty() const { return !m_keyCount; }
index 3fd7f64..9c41dd6 100644 (file)
@@ -87,6 +87,9 @@ public:
     const_iterator begin() const { return makeConstIterator(m_head); }
     const_iterator end() const { return makeConstIterator(nullptr); }
 
+    iterator random() { return makeIterator(m_impl.random()); }
+    const_iterator random() const { return makeIterator(m_impl.random()); }
+
     reverse_iterator rbegin() { return reverse_iterator(end()); }
     reverse_iterator rend() { return reverse_iterator(begin()); }
     const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
index 5b6e621..9779b51 100644 (file)
@@ -100,6 +100,9 @@ public:
     iterator end() { return m_map.end(); }
     const_iterator begin() const { return m_map.begin(); }
     const_iterator end() const { return m_map.end(); }
+
+    iterator random() { return m_map.random(); }
+    const_iterator random() const { return m_map.random(); }
     
     auto keys() { return m_map.keys(); }
     const auto keys() const { return m_map.keys(); }
index eb8e631..c903668 100644 (file)
@@ -100,6 +100,9 @@ public:
     iterator begin() const { return m_set.begin(); }
     iterator end() const { return m_set.end(); }
     
+    iterator random() { return m_set.random(); }
+    const_iterator random() const { return m_set.random(); }
+
     iterator find(const ValueType& value) const
     {
         StringPrintStream string;
index 791d0dd..d11eb44 100644 (file)
@@ -34,6 +34,7 @@
 #include <stdlib.h>
 #include <wtf/CryptographicallyRandomNumber.h>
 #include <wtf/RandomNumberSeed.h>
+#include <wtf/WeakRandom.h>
 
 namespace WTF {
 
@@ -43,4 +44,12 @@ double randomNumber()
     return static_cast<double>(bits) / (static_cast<double>(std::numeric_limits<uint32_t>::max()) + 1.0);
 }
 
+unsigned weakRandomUint32()
+{
+    // We don't care about thread safety. WeakRandom just uses POD types,
+    // and racy access just increases randomness.
+    static WeakRandom s_weakRandom;
+    return s_weakRandom.getUint32();
+}
+
 }
index 238ccc2..2b309c7 100644 (file)
 
 namespace WTF {
 
-// Returns a pseudo-random number in the range [0, 1), attempts to be
-// cryptographically secure if possible on the target platform
+// Returns a cryptographically secure pseudo-random number in the range [0, 1).
 WTF_EXPORT_PRIVATE double randomNumber();
 
+// Returns a cheap pseudo-random number in the range (0, UINT_MAX].
+WTF_EXPORT_PRIVATE unsigned weakRandomUint32();
+
 }
 
 using WTF::randomNumber;
+using WTF::weakRandomUint32;
index dd3ba6e..31a47ce 100644 (file)
@@ -1,3 +1,16 @@
+2018-10-25  Geoffrey Garen  <ggaren@apple.com>
+
+        HashMap should support selecting a random entry
+        https://bugs.webkit.org/show_bug.cgi?id=190814
+
+        Reviewed by Antti Koivisto.
+
+        Unit testing is fun and easy!
+
+        * TestWebKitAPI/Tests/WTF/HashMap.cpp:
+        (TestWebKitAPI::ZeroHash::hash):
+        (TestWebKitAPI::TEST):
+
 2018-10-24  Tim Horton  <timothy_horton@apple.com>
 
         REGRESSION (r237331): DismissingActionSheetShouldNotDismissPresentingViewController times out
index 4399da8..2e4e76c 100644 (file)
@@ -69,6 +69,14 @@ static int bucketForKey(double key)
     return DefaultHash<double>::Hash::hash(key) & (TestDoubleHashTraits::minimumTableSize - 1);
 }
 
+template<typename T> struct BigTableHashTraits : public HashTraits<T> {
+    static const int minimumTableSize = WTF::HashTableCapacityForSize<4096>::value;
+};
+
+template<typename T> struct ZeroHash : public IntHash<T> {
+    static unsigned hash(const T&) { return 0; }
+};
+
 TEST(WTF_HashMap, DoubleHashCollisions)
 {
     // The "clobber" key here is one that ends up stealing the bucket that the -0 key
@@ -988,4 +996,45 @@ TEST(WTF_HashMap, RefMappedToNonZeroEmptyValue)
         ASSERT_TRUE(map.remove(pair.first));
 }
 
+TEST(WTF_HashMap, Random_Empty)
+{
+    HashMap<unsigned, unsigned> map;
+
+    auto result = map.random();
+    ASSERT_EQ(result, map.end());
+}
+
+TEST(WTF_HashMap, Random_WrapAround)
+{
+    HashMap<unsigned, unsigned, ZeroHash<unsigned>, BigTableHashTraits<unsigned>> map;
+    map.add(1, 1);
+
+    auto result = map.random();
+    ASSERT_EQ(result, map.begin());
+}
+
+TEST(WTF_HashMap, Random_IsRandom)
+{
+    HashMap<unsigned, unsigned> map;
+    map.add(1, 1);
+    map.add(2, 2);
+
+    unsigned ones = 0;
+    unsigned twos = 0;
+
+    for (unsigned i = 0; i < 100; ++i) {
+        auto it = map.random();
+        if (it->value == 1)
+            ++ones;
+        else {
+            ASSERT_EQ(it->value, 2u);
+            ++twos;
+        }
+    }
+
+    ASSERT_EQ(ones + twos, 100u);
+    ASSERT_LE(ones, 99u);
+    ASSERT_LE(twos, 99u);
+}
+
 } // namespace TestWebKitAPI