Skip to content
  • danakj@chromium.org's avatar
    Minimize collisions when hashing pairs · a9d74b51
    danakj@chromium.org authored
    https://bugs.webkit.org/show_bug.cgi?id=96022
    
    Reviewed by Adrienne Walker.
    
    Source/WebCore:
    
    Use WTF::pairIntHash() to hash pairs of integers.
    
    * dom/Document.cpp:
    (WebCore::ImmutableAttributeDataCacheKey::hash):
    * dom/StyledElement.cpp:
    (WebCore::computePresentationAttributeCacheHash):
    * platform/graphics/Gradient.cpp:
    (WebCore::Gradient::hash):
    * platform/graphics/IntPointHash.h:
    (WTF::IntPointHash::hash):
    * platform/graphics/IntRectHash.h:
    * platform/graphics/IntSizeHash.h:
    * platform/graphics/blackberry/LayerTileIndex.h:
    * platform/graphics/cg/GraphicsContextCG.cpp:
    (WebCore::SubimageCacheHash::hash):
    
    Source/WebKit/blackberry:
    
    Use WTF::pairIntHash() to hash a pair of integers.
    
    * WebKitSupport/TileIndexHash.h:
    
    Source/WTF:
    
    The current hash function for pairs has poor performance as it does a
    nice hash function on 64 bits, but then just drops the top 32 bits. The
    hash method for pairs tries to use Thomas Wang's 64 bit Mix Function,
    but this requires not dropping any bits in order to retain the
    characteristics mentioned by Thomas.
    
    A better method of hashing sets of 32-bit integers is to use
    multiplication in 64 bits with random integers. This method is a
    provably almost-universal hash function. Testing shows that this
    method decreases the time required, when compared with the current
    method, by more than 20% due to better hashing characteristics.
    
    * wtf/HashFunctions.h:
    (WTF):
    (WTF::pairIntHash):
    Implments the hashing method for a pair of unsigned integers.
    
    (WTF::PairHash::hash):
    Use pairIntHash() on the hash results of each object in the pair.
    
    (WTF::IntPairHash::hash):
    Implement an integer-specific PairHash class that does not need to
    hash each object in the pair. It uses pairIntHash on the two
    integers in the pair directly.
    
    (WTF::IntPairHash::equal):
    (IntPairHash):
    
    
    git-svn-id: http://svn.webkit.org/repository/webkit/trunk@128650 268f45cc-cd09-0410-ab3c-d52691b4dbfc
    a9d74b51