Diff
Modified: trunk/Source/WTF/ChangeLog (128649 => 128650)
--- trunk/Source/WTF/ChangeLog 2012-09-14 20:51:13 UTC (rev 128649)
+++ trunk/Source/WTF/ChangeLog 2012-09-14 21:00:20 UTC (rev 128650)
@@ -1,3 +1,38 @@
+2012-09-14 Dana Jansens <[email protected]>
+
+ Minimize collisions when hashing pairs
+ https://bugs.webkit.org/show_bug.cgi?id=96022
+
+ Reviewed by Adrienne Walker.
+
+ 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):
+
2012-09-14 Tor Arne Vestbø <[email protected]>
[Qt] Make force_static_libs_as_shared work on Mac OS
Modified: trunk/Source/WTF/wtf/HashFunctions.h (128649 => 128650)
--- trunk/Source/WTF/wtf/HashFunctions.h 2012-09-14 20:51:13 UTC (rev 128649)
+++ trunk/Source/WTF/wtf/HashFunctions.h 2012-09-14 21:00:20 UTC (rev 128650)
@@ -86,6 +86,18 @@
return static_cast<unsigned>(key);
}
+ // Compound integer hash method: http://opendatastructures.org/versions/edition-0.1d/ods-java/node33.html#SECTION00832000000000000000
+ inline unsigned pairIntHash(unsigned key1, unsigned key2)
+ {
+ unsigned shortRandom1 = 277951225; // A random 32-bit value.
+ unsigned shortRandom2 = 95187966; // A random 32-bit value.
+ uint64_t longRandom = 19248658165952622LL; // A random 64-bit value.
+
+ uint64_t product = longRandom * (shortRandom1 * key1 + shortRandom2 * key2);
+ unsigned highBits = product >> (sizeof(uint64_t) - sizeof(unsigned));
+ return highBits;
+ }
+
template<typename T> struct IntHash {
static unsigned hash(T key) { return intHash(static_cast<typename IntTypes<sizeof(T)>::UnsignedType>(key)); }
static bool equal(T a, T b) { return a == b; }
@@ -139,7 +151,7 @@
template<typename T, typename U> struct PairHash {
static unsigned hash(const std::pair<T, U>& p)
{
- return intHash((static_cast<uint64_t>(DefaultHash<T>::Hash::hash(p.first)) << 32 | DefaultHash<U>::Hash::hash(p.second)));
+ return pairIntHash(DefaultHash<T>::Hash::hash(p.first), DefaultHash<U>::Hash::hash(p.second));
}
static bool equal(const std::pair<T, U>& a, const std::pair<T, U>& b)
{
@@ -149,6 +161,12 @@
&& DefaultHash<U>::Hash::safeToCompareToEmptyOrDeleted;
};
+ template<typename T, typename U> struct IntPairHash {
+ static unsigned hash(const std::pair<T, U>& p) { return pairIntHash(p.first, p.second); }
+ static bool equal(const std::pair<T, U>& a, const std::pair<T, U>& b) { return PairHash<T, T>::equal(a, b); }
+ static const bool safeToCompareToEmptyOrDeleted = PairHash<T, U>::safeToCompareToEmptyOrDeleted;
+ };
+
// make IntHash the default hash function for many integer types
template<> struct DefaultHash<short> { typedef IntHash<unsigned> Hash; };
@@ -172,6 +190,27 @@
template<typename P> struct DefaultHash<P*> { typedef PtrHash<P*> Hash; };
template<typename P> struct DefaultHash<RefPtr<P> > { typedef PtrHash<RefPtr<P> > Hash; };
+ // make IntPairHash the default hash function for pairs of (at most) 32-bit integers.
+
+ template<> struct DefaultHash<std::pair<short, short> > { typedef IntPairHash<short, short> Hash; };
+ template<> struct DefaultHash<std::pair<short, unsigned short> > { typedef IntPairHash<short, unsigned short> Hash; };
+ template<> struct DefaultHash<std::pair<short, int> > { typedef IntPairHash<short, int> Hash; };
+ template<> struct DefaultHash<std::pair<short, unsigned> > { typedef IntPairHash<short, unsigned> Hash; };
+ template<> struct DefaultHash<std::pair<unsigned short, short> > { typedef IntPairHash<unsigned short, short> Hash; };
+ template<> struct DefaultHash<std::pair<unsigned short, unsigned short> > { typedef IntPairHash<unsigned short, unsigned short> Hash; };
+ template<> struct DefaultHash<std::pair<unsigned short, int> > { typedef IntPairHash<unsigned short, int> Hash; };
+ template<> struct DefaultHash<std::pair<unsigned short, unsigned> > { typedef IntPairHash<unsigned short, unsigned> Hash; };
+ template<> struct DefaultHash<std::pair<int, short> > { typedef IntPairHash<int, short> Hash; };
+ template<> struct DefaultHash<std::pair<int, unsigned short> > { typedef IntPairHash<int, unsigned short> Hash; };
+ template<> struct DefaultHash<std::pair<int, int> > { typedef IntPairHash<int, int> Hash; };
+ template<> struct DefaultHash<std::pair<int, unsigned> > { typedef IntPairHash<unsigned, unsigned> Hash; };
+ template<> struct DefaultHash<std::pair<unsigned, short> > { typedef IntPairHash<unsigned, short> Hash; };
+ template<> struct DefaultHash<std::pair<unsigned, unsigned short> > { typedef IntPairHash<unsigned, unsigned short> Hash; };
+ template<> struct DefaultHash<std::pair<unsigned, int> > { typedef IntPairHash<unsigned, int> Hash; };
+ template<> struct DefaultHash<std::pair<unsigned, unsigned> > { typedef IntPairHash<unsigned, unsigned> Hash; };
+
+ // make PairHash the default hash function for pairs of arbitrary values.
+
template<typename T, typename U> struct DefaultHash<std::pair<T, U> > { typedef PairHash<T, U> Hash; };
} // namespace WTF
Modified: trunk/Source/WebCore/ChangeLog (128649 => 128650)
--- trunk/Source/WebCore/ChangeLog 2012-09-14 20:51:13 UTC (rev 128649)
+++ trunk/Source/WebCore/ChangeLog 2012-09-14 21:00:20 UTC (rev 128650)
@@ -1,3 +1,26 @@
+2012-09-14 Dana Jansens <[email protected]>
+
+ Minimize collisions when hashing pairs
+ https://bugs.webkit.org/show_bug.cgi?id=96022
+
+ Reviewed by Adrienne Walker.
+
+ 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):
+
2012-09-14 Rob Buis <[email protected]>
[BlackBerry] Use StringBuilder more in BlackBerry RSS classes
Modified: trunk/Source/WebCore/dom/Document.cpp (128649 => 128650)
--- trunk/Source/WebCore/dom/Document.cpp 2012-09-14 20:51:13 UTC (rev 128649)
+++ trunk/Source/WebCore/dom/Document.cpp 2012-09-14 21:00:20 UTC (rev 128650)
@@ -6322,7 +6322,7 @@
unsigned hash() const
{
unsigned attributeHash = StringHasher::hashMemory(m_attributes, m_attributeCount * sizeof(Attribute));
- return WTF::intHash((static_cast<uint64_t>(m_localName->existingHash()) << 32 | attributeHash));
+ return WTF::pairIntHash(m_localName->existingHash(), attributeHash);
}
private:
Modified: trunk/Source/WebCore/dom/StyledElement.cpp (128649 => 128650)
--- trunk/Source/WebCore/dom/StyledElement.cpp 2012-09-14 20:51:13 UTC (rev 128649)
+++ trunk/Source/WebCore/dom/StyledElement.cpp 2012-09-14 21:00:20 UTC (rev 128650)
@@ -266,7 +266,7 @@
return 0;
ASSERT(key.attributesAndValues.size());
unsigned attributeHash = StringHasher::hashMemory(key.attributesAndValues.data(), key.attributesAndValues.size() * sizeof(key.attributesAndValues[0]));
- return WTF::intHash((static_cast<uint64_t>(key.tagName->existingHash()) << 32 | attributeHash));
+ return WTF::pairIntHash(key.tagName->existingHash(), attributeHash);
}
void StyledElement::updateAttributeStyle()
Modified: trunk/Source/WebCore/platform/graphics/Gradient.cpp (128649 => 128650)
--- trunk/Source/WebCore/platform/graphics/Gradient.cpp 2012-09-14 20:51:13 UTC (rev 128649)
+++ trunk/Source/WebCore/platform/graphics/Gradient.cpp 2012-09-14 21:00:20 UTC (rev 128650)
@@ -33,7 +33,7 @@
#include <wtf/StringHasher.h>
#include <wtf/UnusedParam.h>
-using WTF::intHash;
+using WTF::pairIntHash;
namespace WebCore {
@@ -283,7 +283,7 @@
unsigned parametersHash = StringHasher::hashMemory(¶meters, sizeof(parameters));
unsigned stopHash = StringHasher::hashMemory(m_stops.data(), m_stops.size() * sizeof(ColorStop));
- m_cachedHash = intHash((static_cast<uint64_t>(parametersHash) << 32) | stopHash);
+ m_cachedHash = pairIntHash(parametersHash, stopHash);
return m_cachedHash;
}
Modified: trunk/Source/WebCore/platform/graphics/IntPointHash.h (128649 => 128650)
--- trunk/Source/WebCore/platform/graphics/IntPointHash.h 2012-09-14 20:51:13 UTC (rev 128649)
+++ trunk/Source/WebCore/platform/graphics/IntPointHash.h 2012-09-14 21:00:20 UTC (rev 128650)
@@ -28,7 +28,7 @@
// The empty value is (0, INT_MIN), the deleted value is (INT_MIN, 0)
struct IntPointHash {
- static unsigned hash(const WebCore::IntPoint& p) { return WTF::intHash(static_cast<uint64_t>(p.x()) << 32 | p.y()); }
+ static unsigned hash(const WebCore::IntPoint& p) { return pairIntHash(p.x(), p.y()); }
static bool equal(const WebCore::IntPoint& a, const WebCore::IntPoint& b) { return a == b; }
static const bool safeToCompareToEmptyOrDeleted = true;
};
Modified: trunk/Source/WebCore/platform/graphics/IntRectHash.h (128649 => 128650)
--- trunk/Source/WebCore/platform/graphics/IntRectHash.h 2012-09-14 20:51:13 UTC (rev 128649)
+++ trunk/Source/WebCore/platform/graphics/IntRectHash.h 2012-09-14 21:00:20 UTC (rev 128650)
@@ -37,7 +37,7 @@
template<> struct IntHash<WebCore::IntRect> {
static unsigned hash(const WebCore::IntRect& key)
{
- return intHash(static_cast<uint64_t>(DefaultHash<WebCore::IntPoint>::Hash::hash(key.location())) << 32 | DefaultHash<WebCore::IntSize>::Hash::hash(key.size()));
+ return pairIntHash(DefaultHash<WebCore::IntPoint>::Hash::hash(key.location()), DefaultHash<WebCore::IntSize>::Hash::hash(key.size()));
}
static bool equal(const WebCore::IntRect& a, const WebCore::IntRect& b)
{
Modified: trunk/Source/WebCore/platform/graphics/IntSizeHash.h (128649 => 128650)
--- trunk/Source/WebCore/platform/graphics/IntSizeHash.h 2012-09-14 20:51:13 UTC (rev 128649)
+++ trunk/Source/WebCore/platform/graphics/IntSizeHash.h 2012-09-14 21:00:20 UTC (rev 128650)
@@ -27,7 +27,7 @@
namespace WTF {
template<> struct IntHash<WebCore::IntSize> {
- static unsigned hash(const WebCore::IntSize& key) { return intHash((static_cast<uint64_t>(key.width()) << 32 | key.height())); }
+ static unsigned hash(const WebCore::IntSize& key) { return pairIntHash(key.width(), key.height()); }
static bool equal(const WebCore::IntSize& a, const WebCore::IntSize& b) { return a == b; }
static const bool safeToCompareToEmptyOrDeleted = true;
};
Modified: trunk/Source/WebCore/platform/graphics/blackberry/LayerTileIndex.h (128649 => 128650)
--- trunk/Source/WebCore/platform/graphics/blackberry/LayerTileIndex.h 2012-09-14 20:51:13 UTC (rev 128649)
+++ trunk/Source/WebCore/platform/graphics/blackberry/LayerTileIndex.h 2012-09-14 21:00:20 UTC (rev 128650)
@@ -66,7 +66,7 @@
namespace WTF {
template<> struct IntHash<WebCore::TileIndex> {
- static unsigned hash(const WebCore::TileIndex& key) { return intHash((static_cast<uint64_t>(key.i()) << 32 | key.j())); }
+ static unsigned hash(const WebCore::TileIndex& key) { return pairIntHash(key.i(), key.j()); }
static bool equal(const WebCore::TileIndex& a, const WebCore::TileIndex& b) { return a == b; }
static const bool safeToCompareToEmptyOrDeleted = true;
};
Modified: trunk/Source/WebCore/platform/graphics/cg/GraphicsContextCG.cpp (128649 => 128650)
--- trunk/Source/WebCore/platform/graphics/cg/GraphicsContextCG.cpp 2012-09-14 20:51:13 UTC (rev 128649)
+++ trunk/Source/WebCore/platform/graphics/cg/GraphicsContextCG.cpp 2012-09-14 21:00:20 UTC (rev 128650)
@@ -74,7 +74,7 @@
using namespace std;
// FIXME: The following using declaration should be in <wtf/HashFunctions.h>.
-using WTF::intHash;
+using WTF::pairIntHash;
// FIXME: The following using declaration should be in <wtf/HashTraits.h>.
using WTF::GenericHashTraits;
@@ -116,8 +116,8 @@
struct SubimageCacheHash {
static unsigned hash(CGImageRef image, const FloatRect& rect)
{
- return intHash((static_cast<uint64_t>(PtrHash<CGImageRef>::hash(image)) << 32)
- | (static_cast<unsigned>(rect.x()) << 16) | static_cast<unsigned>(rect.y()));
+ return pairIntHash(PtrHash<CGImageRef>::hash(image),
+ (static_cast<unsigned>(rect.x()) << 16) | static_cast<unsigned>(rect.y()));
}
static unsigned hash(const SubimageCacheEntry& key)
{
Modified: trunk/Source/WebKit/blackberry/ChangeLog (128649 => 128650)
--- trunk/Source/WebKit/blackberry/ChangeLog 2012-09-14 20:51:13 UTC (rev 128649)
+++ trunk/Source/WebKit/blackberry/ChangeLog 2012-09-14 21:00:20 UTC (rev 128650)
@@ -1,3 +1,14 @@
+2012-09-14 Dana Jansens <[email protected]>
+
+ Minimize collisions when hashing pairs
+ https://bugs.webkit.org/show_bug.cgi?id=96022
+
+ Reviewed by Adrienne Walker.
+
+ Use WTF::pairIntHash() to hash a pair of integers.
+
+ * WebKitSupport/TileIndexHash.h:
+
2012-09-14 Genevieve Mak <[email protected]>
Always send mouse events on pages that don't scroll even if there
Modified: trunk/Source/WebKit/blackberry/WebKitSupport/TileIndexHash.h (128649 => 128650)
--- trunk/Source/WebKit/blackberry/WebKitSupport/TileIndexHash.h 2012-09-14 20:51:13 UTC (rev 128649)
+++ trunk/Source/WebKit/blackberry/WebKitSupport/TileIndexHash.h 2012-09-14 21:00:20 UTC (rev 128650)
@@ -28,7 +28,7 @@
namespace WTF {
template<> struct IntHash<TileIndex> {
- static unsigned hash(const TileIndex& key) { return intHash((static_cast<uint64_t>(key.i()) << 32 | key.j())); }
+ static unsigned hash(const TileIndex& key) { return pairIntHash(key.i(), key.j()); }
static bool equal(const TileIndex& a, const TileIndex& b) { return a == b; }
static const bool safeToCompareToEmptyOrDeleted = true;
};
