Changeset 237419 in webkit


Ignore:
Timestamp:
Oct 25, 2018 10:41:35 AM (5 years ago)
Author:
ggaren@apple.com
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):

Location:
trunk
Files:
12 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/WTF/ChangeLog

    r237402 r237419  
     12018-10-25  Geoffrey Garen  <ggaren@apple.com>
     2
     3        HashMap should support selecting a random entry
     4        https://bugs.webkit.org/show_bug.cgi?id=190814
     5
     6        Reviewed by Antti Koivisto.
     7
     8        In some cases, remove(begin()) is not quite good enough as a random
     9        eviction strategy. (See https://bugs.webkit.org/show_bug.cgi?id=190792.)
     10        So, let's support real random eviction.
     11
     12        (And by "real" I mean "pseudo".)
     13
     14        * wtf/HashCountedSet.h:
     15        * wtf/HashMap.h:
     16        * wtf/HashSet.h:
     17        * wtf/ListHashSet.h:
     18        (WTF::ListHashSet::random):
     19        (WTF::ListHashSet::random const):
     20        * wtf/LoggingHashMap.h:
     21        * wtf/LoggingHashSet.h: Plumb through the random() iterator.
     22
     23        * wtf/HashTable.h:
     24        (WTF::HashTable::random):
     25        (WTF::HashTable::random const): Implement the random() iterator.
     26        makeIterator() already supports starting from any bucket, so this is
     27        pretty easy.
     28
     29        In the subtle case where we select end(), we choose to wrap around and
     30        return begin(). We expect that clients don't really think of the end()
     31        bucket as being in the domain of the random search. Also, we don't want
     32        to annoy clients who know their tables are non-empty with needless
     33        checks for end().
     34
     35        * wtf/RandomNumber.cpp:
     36        (WTF::weakRandomUint32):
     37        * wtf/RandomNumber.h: Added a free function for weak random numbers so
     38        that clients that want cheap random numbers aren't required to allocate
     39        storage for a WeakRandom generator.
     40
    1412018-10-24  Megan Gardner  <megan_gardner@apple.com>
    242
  • trunk/Source/WTF/wtf/HashCountedSet.h

    r223617 r237419  
    7070    const_iterator end() const;
    7171
     72    iterator random() { return m_impl.random(); }
     73    const_iterator random() const { return m_impl.random(); }
     74
    7275    ValuesIteratorRange values();
    7376    const ValuesConstIteratorRange values() const;
  • trunk/Source/WTF/wtf/HashMap.h

    r237099 r237419  
    9999    const_iterator end() const;
    100100   
     101    iterator random() { return m_impl.random(); }
     102    const_iterator random() const { return m_impl.random(); }
     103
    101104    KeysIteratorRange keys() { return makeSizedIteratorRange(*this, begin().keys(), end().keys()); }
    102105    const KeysConstIteratorRange keys() const { return makeSizedIteratorRange(*this, begin().keys(), end().keys()); }
  • trunk/Source/WTF/wtf/HashSet.h

    r237099 r237419  
    6969    iterator end() const;
    7070
     71    iterator random() { return m_impl.random(); }
     72    const_iterator random() const { return m_impl.random(); }
     73
    7174    iterator find(const ValueType&) const;
    7275    bool contains(const ValueType&) const;
  • trunk/Source/WTF/wtf/HashTable.h

    r234879 r237419  
    3333#include <wtf/Lock.h>
    3434#include <wtf/MathExtras.h>
     35#include <wtf/RandomNumber.h>
    3536#include <wtf/StdLibExtras.h>
    3637#include <wtf/ValueCheck.h>
     
    379380        const_iterator begin() const { return isEmpty() ? end() : makeConstIterator(m_table); }
    380381        const_iterator end() const { return makeKnownGoodConstIterator(m_table + m_tableSize); }
     382
     383        iterator random()
     384        {
     385            if (isEmpty())
     386                return end();
     387            auto it = makeIterator(m_table + (weakRandomUint32() & m_tableSizeMask));
     388            if (it == end())
     389                return begin();
     390            return it;
     391        }
     392
     393        const_iterator random() const { return const_cast<HashTable*>(this)->random().const_iterator(); }
    381394
    382395        unsigned size() const { return m_keyCount; }
  • trunk/Source/WTF/wtf/ListHashSet.h

    r223617 r237419  
    8888    const_iterator end() const { return makeConstIterator(nullptr); }
    8989
     90    iterator random() { return makeIterator(m_impl.random()); }
     91    const_iterator random() const { return makeIterator(m_impl.random()); }
     92
    9093    reverse_iterator rbegin() { return reverse_iterator(end()); }
    9194    reverse_iterator rend() { return reverse_iterator(begin()); }
  • trunk/Source/WTF/wtf/LoggingHashMap.h

    r235841 r237419  
    101101    const_iterator begin() const { return m_map.begin(); }
    102102    const_iterator end() const { return m_map.end(); }
     103
     104    iterator random() { return m_map.random(); }
     105    const_iterator random() const { return m_map.random(); }
    103106   
    104107    auto keys() { return m_map.keys(); }
  • trunk/Source/WTF/wtf/LoggingHashSet.h

    r213939 r237419  
    101101    iterator end() const { return m_set.end(); }
    102102   
     103    iterator random() { return m_set.random(); }
     104    const_iterator random() const { return m_set.random(); }
     105
    103106    iterator find(const ValueType& value) const
    104107    {
  • trunk/Source/WTF/wtf/RandomNumber.cpp

    r237099 r237419  
    3535#include <wtf/CryptographicallyRandomNumber.h>
    3636#include <wtf/RandomNumberSeed.h>
     37#include <wtf/WeakRandom.h>
    3738
    3839namespace WTF {
     
    4445}
    4546
     47unsigned weakRandomUint32()
     48{
     49    // We don't care about thread safety. WeakRandom just uses POD types,
     50    // and racy access just increases randomness.
     51    static WeakRandom s_weakRandom;
     52    return s_weakRandom.getUint32();
    4653}
     54
     55}
  • trunk/Source/WTF/wtf/RandomNumber.h

    r237099 r237419  
    2828namespace WTF {
    2929
    30 // Returns a pseudo-random number in the range [0, 1), attempts to be
    31 // cryptographically secure if possible on the target platform
     30// Returns a cryptographically secure pseudo-random number in the range [0, 1).
    3231WTF_EXPORT_PRIVATE double randomNumber();
     32
     33// Returns a cheap pseudo-random number in the range (0, UINT_MAX].
     34WTF_EXPORT_PRIVATE unsigned weakRandomUint32();
    3335
    3436}
    3537
    3638using WTF::randomNumber;
     39using WTF::weakRandomUint32;
  • trunk/Tools/ChangeLog

    r237407 r237419  
     12018-10-25  Geoffrey Garen  <ggaren@apple.com>
     2
     3        HashMap should support selecting a random entry
     4        https://bugs.webkit.org/show_bug.cgi?id=190814
     5
     6        Reviewed by Antti Koivisto.
     7
     8        Unit testing is fun and easy!
     9
     10        * TestWebKitAPI/Tests/WTF/HashMap.cpp:
     11        (TestWebKitAPI::ZeroHash::hash):
     12        (TestWebKitAPI::TEST):
     13
    1142018-10-24  Tim Horton  <timothy_horton@apple.com>
    215
  • trunk/Tools/TestWebKitAPI/Tests/WTF/HashMap.cpp

    r234879 r237419  
    7070}
    7171
     72template<typename T> struct BigTableHashTraits : public HashTraits<T> {
     73    static const int minimumTableSize = WTF::HashTableCapacityForSize<4096>::value;
     74};
     75
     76template<typename T> struct ZeroHash : public IntHash<T> {
     77    static unsigned hash(const T&) { return 0; }
     78};
     79
    7280TEST(WTF_HashMap, DoubleHashCollisions)
    7381{
     
    989997}
    990998
     999TEST(WTF_HashMap, Random_Empty)
     1000{
     1001    HashMap<unsigned, unsigned> map;
     1002
     1003    auto result = map.random();
     1004    ASSERT_EQ(result, map.end());
     1005}
     1006
     1007TEST(WTF_HashMap, Random_WrapAround)
     1008{
     1009    HashMap<unsigned, unsigned, ZeroHash<unsigned>, BigTableHashTraits<unsigned>> map;
     1010    map.add(1, 1);
     1011
     1012    auto result = map.random();
     1013    ASSERT_EQ(result, map.begin());
     1014}
     1015
     1016TEST(WTF_HashMap, Random_IsRandom)
     1017{
     1018    HashMap<unsigned, unsigned> map;
     1019    map.add(1, 1);
     1020    map.add(2, 2);
     1021
     1022    unsigned ones = 0;
     1023    unsigned twos = 0;
     1024
     1025    for (unsigned i = 0; i < 100; ++i) {
     1026        auto it = map.random();
     1027        if (it->value == 1)
     1028            ++ones;
     1029        else {
     1030            ASSERT_EQ(it->value, 2u);
     1031            ++twos;
     1032        }
     1033    }
     1034
     1035    ASSERT_EQ(ones + twos, 100u);
     1036    ASSERT_LE(ones, 99u);
     1037    ASSERT_LE(twos, 99u);
     1038}
     1039
    9911040} // namespace TestWebKitAPI
Note: See TracChangeset for help on using the changeset viewer.