- Revision
- 237419
- Author
- [email protected]
- Date
- 2018-10-25 10:41:35 -0700 (Thu, 25 Oct 2018)
Log Message
HashMap should support selecting a random entry
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):
Modified Paths
Diff
Modified: trunk/Source/WTF/ChangeLog (237418 => 237419)
--- trunk/Source/WTF/ChangeLog 2018-10-25 17:09:23 UTC (rev 237418)
+++ trunk/Source/WTF/ChangeLog 2018-10-25 17:41:35 UTC (rev 237419)
@@ -1,3 +1,43 @@
+2018-10-25 Geoffrey Garen <[email protected]>
+
+ 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 <[email protected]>
Turn on Conic Gradients
Modified: trunk/Source/WTF/wtf/HashCountedSet.h (237418 => 237419)
--- trunk/Source/WTF/wtf/HashCountedSet.h 2018-10-25 17:09:23 UTC (rev 237418)
+++ trunk/Source/WTF/wtf/HashCountedSet.h 2018-10-25 17:41:35 UTC (rev 237419)
@@ -69,6 +69,9 @@
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;
Modified: trunk/Source/WTF/wtf/HashMap.h (237418 => 237419)
--- trunk/Source/WTF/wtf/HashMap.h 2018-10-25 17:09:23 UTC (rev 237418)
+++ trunk/Source/WTF/wtf/HashMap.h 2018-10-25 17:41:35 UTC (rev 237419)
@@ -98,6 +98,9 @@
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()); }
Modified: trunk/Source/WTF/wtf/HashSet.h (237418 => 237419)
--- trunk/Source/WTF/wtf/HashSet.h 2018-10-25 17:09:23 UTC (rev 237418)
+++ trunk/Source/WTF/wtf/HashSet.h 2018-10-25 17:41:35 UTC (rev 237419)
@@ -68,6 +68,9 @@
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;
Modified: trunk/Source/WTF/wtf/HashTable.h (237418 => 237419)
--- trunk/Source/WTF/wtf/HashTable.h 2018-10-25 17:09:23 UTC (rev 237418)
+++ trunk/Source/WTF/wtf/HashTable.h 2018-10-25 17:41:35 UTC (rev 237419)
@@ -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 @@
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; }
Modified: trunk/Source/WTF/wtf/ListHashSet.h (237418 => 237419)
--- trunk/Source/WTF/wtf/ListHashSet.h 2018-10-25 17:09:23 UTC (rev 237418)
+++ trunk/Source/WTF/wtf/ListHashSet.h 2018-10-25 17:41:35 UTC (rev 237419)
@@ -87,6 +87,9 @@
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()); }
Modified: trunk/Source/WTF/wtf/LoggingHashMap.h (237418 => 237419)
--- trunk/Source/WTF/wtf/LoggingHashMap.h 2018-10-25 17:09:23 UTC (rev 237418)
+++ trunk/Source/WTF/wtf/LoggingHashMap.h 2018-10-25 17:41:35 UTC (rev 237419)
@@ -100,6 +100,9 @@
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(); }
Modified: trunk/Source/WTF/wtf/LoggingHashSet.h (237418 => 237419)
--- trunk/Source/WTF/wtf/LoggingHashSet.h 2018-10-25 17:09:23 UTC (rev 237418)
+++ trunk/Source/WTF/wtf/LoggingHashSet.h 2018-10-25 17:41:35 UTC (rev 237419)
@@ -100,6 +100,9 @@
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;
Modified: trunk/Source/WTF/wtf/RandomNumber.cpp (237418 => 237419)
--- trunk/Source/WTF/wtf/RandomNumber.cpp 2018-10-25 17:09:23 UTC (rev 237418)
+++ trunk/Source/WTF/wtf/RandomNumber.cpp 2018-10-25 17:41:35 UTC (rev 237419)
@@ -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 @@
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();
}
+
+}
Modified: trunk/Source/WTF/wtf/RandomNumber.h (237418 => 237419)
--- trunk/Source/WTF/wtf/RandomNumber.h 2018-10-25 17:09:23 UTC (rev 237418)
+++ trunk/Source/WTF/wtf/RandomNumber.h 2018-10-25 17:41:35 UTC (rev 237419)
@@ -27,10 +27,13 @@
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;
Modified: trunk/Tools/ChangeLog (237418 => 237419)
--- trunk/Tools/ChangeLog 2018-10-25 17:09:23 UTC (rev 237418)
+++ trunk/Tools/ChangeLog 2018-10-25 17:41:35 UTC (rev 237419)
@@ -1,3 +1,16 @@
+2018-10-25 Geoffrey Garen <[email protected]>
+
+ 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 <[email protected]>
REGRESSION (r237331): DismissingActionSheetShouldNotDismissPresentingViewController times out
Modified: trunk/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp (237418 => 237419)
--- trunk/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp 2018-10-25 17:09:23 UTC (rev 237418)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp 2018-10-25 17:41:35 UTC (rev 237419)
@@ -69,6 +69,14 @@
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 @@
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
