Diff
Modified: trunk/Source/WTF/ChangeLog (123581 => 123582)
--- trunk/Source/WTF/ChangeLog 2012-07-25 06:52:43 UTC (rev 123581)
+++ trunk/Source/WTF/ChangeLog 2012-07-25 07:22:48 UTC (rev 123582)
@@ -1,3 +1,18 @@
+2012-07-24 Benjamin Poulain <[email protected]> && Joseph Pecoraro <[email protected]>
+
+ QualifiedName's HashSet should be big enough to hold at least all the static names
+ https://bugs.webkit.org/show_bug.cgi?id=91891
+
+ Reviewed by Darin Adler.
+
+ Add a static struct to compute the HashTable capacity for any given size at compile time.
+ This allow us to create HashTraits giving the minimumSize without hardcoding the values.
+
+ * wtf/HashTable.h:
+ (OneifyLowBits):
+ (UpperPowerOfTwoBound):
+ (HashTableCapacityForSize): Compute the HashTable capacity at compile time.
+
2012-07-24 Michael Saboff <[email protected]>
Convert HTML parser to handle 8-bit resources without converting to UChar*
Modified: trunk/Source/WTF/wtf/HashTable.h (123581 => 123582)
--- trunk/Source/WTF/wtf/HashTable.h 2012-07-25 06:52:43 UTC (rev 123581)
+++ trunk/Source/WTF/wtf/HashTable.h 2012-07-25 07:22:48 UTC (rev 123582)
@@ -505,6 +505,44 @@
#endif
};
+ // Set all the bits to one after the most significant bit: 00110101010 -> 00111111111.
+ template<unsigned size> struct OneifyLowBits;
+ template<>
+ struct OneifyLowBits<0> {
+ static const unsigned value = 0;
+ };
+ template<unsigned number>
+ struct OneifyLowBits {
+ static const unsigned value = number | OneifyLowBits<(number >> 1)>::value;
+ };
+ // Compute the first power of two integer that is an upper bound of the parameter 'number'.
+ template<unsigned number>
+ struct UpperPowerOfTwoBound {
+ static const unsigned value = (OneifyLowBits<number - 1>::value + 1) * 2;
+ };
+
+ // Because power of two numbers are the limit of maxLoad, their capacity is twice the
+ // UpperPowerOfTwoBound, or 4 times their values.
+ template<unsigned size, bool isPowerOfTwo> struct HashTableCapacityForSizeSplitter;
+ template<unsigned size>
+ struct HashTableCapacityForSizeSplitter<size, true> {
+ static const unsigned value = size * 4;
+ };
+ template<unsigned size>
+ struct HashTableCapacityForSizeSplitter<size, false> {
+ static const unsigned value = UpperPowerOfTwoBound<size>::value;
+ };
+
+ // HashTableCapacityForSize computes the upper power of two capacity to hold the size parameter.
+ // This is done at compile time to initialize the HashTraits.
+ template<unsigned size>
+ struct HashTableCapacityForSize {
+ static const unsigned value = HashTableCapacityForSizeSplitter<size, !(size & (size - 1))>::value;
+ COMPILE_ASSERT(size > 0, HashTableNonZeroMinimumCapacity);
+ COMPILE_ASSERT(!static_cast<int>(value >> 31), HashTableNoCapacityOverflow);
+ COMPILE_ASSERT(value > (2 * size), HashTableCapacityHoldsContentSize);
+ };
+
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
inline HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::HashTable()
: m_table(0)
Modified: trunk/Source/WebCore/ChangeLog (123581 => 123582)
--- trunk/Source/WebCore/ChangeLog 2012-07-25 06:52:43 UTC (rev 123581)
+++ trunk/Source/WebCore/ChangeLog 2012-07-25 07:22:48 UTC (rev 123582)
@@ -1,3 +1,23 @@
+2012-07-24 Benjamin Poulain <[email protected]> && Joseph Pecoraro <[email protected]>
+
+ QualifiedName's HashSet should be big enough to hold at least all the static names
+ https://bugs.webkit.org/show_bug.cgi?id=91891
+
+ Reviewed by Darin Adler.
+
+ QualifiedName's table has a standard size of 64 buckets. When initializing WebKit,
+ we create 850 static QualifiedName for the standard names (HTMLNames, SVGNames etc).
+
+ The small base size forces us to grow and rehash the table several time on startup.
+
+ This patch solves the issue by defining the initial table size to the minimum size that
+ can hold all the static QualifiedName.
+
+ * dom/QualifiedName.cpp:
+ (QualifiedNameHashTraits):
+ * dom/make_names.pl:
+ (printNamesHeaderFile):
+
2012-07-24 Kwang Yul Seo <[email protected]>
Remove anonymous namespace and make functions static.
Modified: trunk/Source/WebCore/dom/QualifiedName.cpp (123581 => 123582)
--- trunk/Source/WebCore/dom/QualifiedName.cpp 2012-07-25 06:52:43 UTC (rev 123581)
+++ trunk/Source/WebCore/dom/QualifiedName.cpp 2012-07-25 07:22:48 UTC (rev 123582)
@@ -26,14 +26,41 @@
#endif
#include "QualifiedName.h"
+#include "HTMLNames.h"
+#include "XLinkNames.h"
+#include "XMLNSNames.h"
+#include "XMLNames.h"
#include <wtf/Assertions.h>
#include <wtf/HashSet.h>
#include <wtf/StaticConstructors.h>
+#if ENABLE(MATHML)
+#include "MathMLNames.h"
+#endif
+
+#if ENABLE(SVG)
+#include "SVGNames.h"
+#endif
+
namespace WebCore {
-typedef HashSet<QualifiedName::QualifiedNameImpl*, QualifiedNameHash> QNameSet;
+static const int staticQualifiedNamesCount = HTMLNames::HTMLTagsCount + HTMLNames::HTMLAttrsCount
+#if ENABLE(MATHML)
+ + MathMLNames::MathMLTagsCount + MathMLNames::MathMLAttrsCount
+#endif
+#if ENABLE(SVG)
+ + SVGNames::SVGTagsCount + SVGNames::SVGAttrsCount
+#endif
+ + XLinkNames::XLinkAttrsCount
+ + XMLNSNames::XMLNSAttrsCount
+ + XMLNames::XMLAttrsCount;
+struct QualifiedNameHashTraits : public HashTraits<QualifiedName::QualifiedNameImpl*> {
+ static const int minimumTableSize = WTF::HashTableCapacityForSize<staticQualifiedNamesCount>::value;
+};
+
+typedef HashSet<QualifiedName::QualifiedNameImpl*, QualifiedNameHash, QualifiedNameHashTraits> QNameSet;
+
struct QNameComponentsTranslator {
static unsigned hash(const QualifiedNameComponents& components)
{
Modified: trunk/Source/WebCore/dom/make_names.pl (123581 => 123582)
--- trunk/Source/WebCore/dom/make_names.pl 2012-07-25 06:52:43 UTC (rev 123581)
+++ trunk/Source/WebCore/dom/make_names.pl 2012-07-25 07:22:48 UTC (rev 123582)
@@ -600,10 +600,12 @@
print F "#endif\n\n";
if (keys %allTags) {
+ print F "const unsigned $parameters{namespace}TagsCount = ", scalar(keys %allTags), ";\n";
print F "WebCore::QualifiedName** get$parameters{namespace}Tags(size_t* size);\n";
}
if (keys %allAttrs) {
+ print F "const unsigned $parameters{namespace}AttrsCount = ", scalar(keys %allAttrs), ";\n";
print F "WebCore::QualifiedName** get$parameters{namespace}Attrs(size_t* size);\n";
}
Modified: trunk/Tools/ChangeLog (123581 => 123582)
--- trunk/Tools/ChangeLog 2012-07-25 06:52:43 UTC (rev 123581)
+++ trunk/Tools/ChangeLog 2012-07-25 07:22:48 UTC (rev 123582)
@@ -1,3 +1,19 @@
+2012-07-24 Benjamin Poulain <[email protected]> && Joseph Pecoraro <[email protected]>
+
+ QualifiedName's HashSet should be big enough to hold at least all the static names
+ https://bugs.webkit.org/show_bug.cgi?id=91891
+
+ Reviewed by Darin Adler.
+
+ Add a test for WTF::hashTableCapacityForSize.
+
+ * TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
+ * TestWebKitAPI/Tests/WTF/HashSet.cpp: Added.
+ (InitialCapacityTestHashTraits):
+ (TestWebKitAPI::testInitialCapacity):
+ (TestWebKitAPI::generateTestCapacityUpToSize):
+ (TestWebKitAPI::TEST):
+
2012-07-24 Adam Barth <[email protected]>
The EWS bots get flaky when we hit the failure limit
Modified: trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj (123581 => 123582)
--- trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj 2012-07-25 06:52:43 UTC (rev 123581)
+++ trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj 2012-07-25 07:22:48 UTC (rev 123582)
@@ -21,6 +21,7 @@
1ADBEFE3130C6AA100D61D19 /* simple-accelerated-compositing.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 1ADBEFBC130C6A0100D61D19 /* simple-accelerated-compositing.html */; };
1AEDE22613E5E7E700E62FE8 /* InjectedBundleControllerMac.mm in Sources */ = {isa = PBXBuildFile; fileRef = 1AEDE22413E5E7A000E62FE8 /* InjectedBundleControllerMac.mm */; };
261516D615B0E60500A2C201 /* SetAndUpdateCacheModel.mm in Sources */ = {isa = PBXBuildFile; fileRef = 261516D515B0E60500A2C201 /* SetAndUpdateCacheModel.mm */; };
+ 26B2DFF915BDE599004F691D /* HashSet.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26B2DFF815BDE599004F691D /* HashSet.cpp */; };
26DF5A5E15A29BAA003689C2 /* CancelLoadFromResourceLoadDelegate.mm in Sources */ = {isa = PBXBuildFile; fileRef = 26DF5A5D15A29BAA003689C2 /* CancelLoadFromResourceLoadDelegate.mm */; };
26DF5A6315A2A27E003689C2 /* CancelLoadFromResourceLoadDelegate.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 26DF5A6115A2A22B003689C2 /* CancelLoadFromResourceLoadDelegate.html */; };
333B9CE21277F23100FEFCE3 /* PreventEmptyUserAgent.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 333B9CE11277F23100FEFCE3 /* PreventEmptyUserAgent.cpp */; };
@@ -245,6 +246,7 @@
1ADBEFBC130C6A0100D61D19 /* simple-accelerated-compositing.html */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = "simple-accelerated-compositing.html"; sourceTree = "<group>"; };
1AEDE22413E5E7A000E62FE8 /* InjectedBundleControllerMac.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = InjectedBundleControllerMac.mm; sourceTree = "<group>"; };
261516D515B0E60500A2C201 /* SetAndUpdateCacheModel.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = SetAndUpdateCacheModel.mm; sourceTree = "<group>"; };
+ 26B2DFF815BDE599004F691D /* HashSet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = HashSet.cpp; path = WTF/HashSet.cpp; sourceTree = "<group>"; };
26DF5A5D15A29BAA003689C2 /* CancelLoadFromResourceLoadDelegate.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = CancelLoadFromResourceLoadDelegate.mm; sourceTree = "<group>"; };
26DF5A6115A2A22B003689C2 /* CancelLoadFromResourceLoadDelegate.html */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = CancelLoadFromResourceLoadDelegate.html; sourceTree = "<group>"; };
333B9CE11277F23100FEFCE3 /* PreventEmptyUserAgent.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = PreventEmptyUserAgent.cpp; sourceTree = "<group>"; };
@@ -620,6 +622,7 @@
A7A966DA140ECCC8005EF9B4 /* CheckedArithmeticOperations.cpp */,
1AA9E55714980A9900001A8A /* Functional.cpp */,
0BCD833414857CE400EA2003 /* HashMap.cpp */,
+ 26B2DFF815BDE599004F691D /* HashSet.cpp */,
81B50192140F232300D9EB58 /* StringBuilder.cpp */,
C01363C713C3997300EF3964 /* StringOperators.cpp */,
0BCD85691485C98B00EA2003 /* TemporaryChange.cpp */,
@@ -945,6 +948,7 @@
0F17BBD615AF6C4D007AB753 /* WebCoreStatisticsWithNoWebProcess.cpp in Sources */,
261516D615B0E60500A2C201 /* SetAndUpdateCacheModel.mm in Sources */,
A5E2027315B2181900C13E14 /* WindowlessWebViewWithMedia.mm in Sources */,
+ 26B2DFF915BDE599004F691D /* HashSet.cpp in Sources */,
);
runOnlyForDeploymentPostprocessing = 0;
};
Added: trunk/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp (0 => 123582)
--- trunk/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp (rev 0)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/HashSet.cpp 2012-07-25 07:22:48 UTC (rev 123582)
@@ -0,0 +1,79 @@
+/*
+ * Copyright (C) 2012 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+
+#include <wtf/HashSet.h>
+
+namespace TestWebKitAPI {
+
+template<int initialCapacity>
+ struct InitialCapacityTestHashTraits : public WTF::UnsignedWithZeroKeyHashTraits<int> {
+ static const int minimumTableSize = initialCapacity;
+};
+
+template<unsigned size>
+void testInitialCapacity()
+{
+ const unsigned initialCapacity = WTF::HashTableCapacityForSize<size>::value;
+ HashSet<int, DefaultHash<int>::Hash, InitialCapacityTestHashTraits<initialCapacity> > testSet;
+
+ // Initial capacity is null.
+ ASSERT_EQ(0, testSet.capacity());
+
+ // Adding items up to size should never change the capacity.
+ for (size_t i = 0; i < size; ++i) {
+ testSet.add(i);
+ ASSERT_EQ(initialCapacity, static_cast<unsigned>(testSet.capacity()));
+ }
+
+ // Adding items up to less than half the capacity should not change the capacity.
+ unsigned capacityLimit = initialCapacity / 2 - 1;
+ for (size_t i = size; i < capacityLimit; ++i) {
+ testSet.add(i);
+ ASSERT_EQ(initialCapacity, static_cast<unsigned>(testSet.capacity()));
+ }
+
+ // Adding one more item increase the capacity.
+ testSet.add(initialCapacity);
+ EXPECT_GT(static_cast<unsigned>(testSet.capacity()), initialCapacity);
+}
+
+template<unsigned size> void generateTestCapacityUpToSize();
+template<> void generateTestCapacityUpToSize<0>()
+{
+}
+template<unsigned size> void generateTestCapacityUpToSize()
+{
+ generateTestCapacityUpToSize<size - 1>();
+ testInitialCapacity<size>();
+}
+
+TEST(WTF, HashSetInitialCapacity)
+{
+ generateTestCapacityUpToSize<128>();
+}
+
+} // namespace TestWebKitAPI
