Changeset 123582 in webkit


Ignore:
Timestamp:
Jul 25, 2012 12:22:48 AM (12 years ago)
Author:
benjamin@webkit.org
Message:

QualifiedName's HashSet should be big enough to hold at least all the static names
​https://bugs.webkit.org/show_bug.cgi?id=91891

Patch by Benjamin Poulain <​bpoulain@apple.com> && Joseph Pecoraro <Joseph Pecoraro> on 2012-07-24
Reviewed by Darin Adler.

Source/WebCore:

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):

Source/WTF:

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.

Tools:

Add a test for WTF::hashTableCapacityForSize.

  • TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
  • TestWebKitAPI/Tests/WTF/HashSet.cpp: Added.

(InitialCapacityTestHashTraits):
(TestWebKitAPI::testInitialCapacity):
(TestWebKitAPI::generateTestCapacityUpToSize):
(TestWebKitAPI::TEST):

Location:
trunk
Files:
1 added
7 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WTF/ChangeLog

    r123560 r123582  
     12012-07-24  Benjamin Poulain  <bpoulain@apple.com> && Joseph Pecoraro  <pecoraro@apple.com>
     2
     3        QualifiedName's HashSet should be big enough to hold at least all the static names
     4        https://bugs.webkit.org/show_bug.cgi?id=91891
     5
     6        Reviewed by Darin Adler.
     7
     8        Add a static struct to compute the HashTable capacity for any given size at compile time.
     9        This allow us to create HashTraits giving the minimumSize without hardcoding the values.
     10
     11        * wtf/HashTable.h:
     12        (OneifyLowBits):
     13        (UpperPowerOfTwoBound):
     14        (HashTableCapacityForSize): Compute the HashTable capacity at compile time.
     15
    1162012-07-24  Michael Saboff  <msaboff@apple.com>
    217

  • trunk/Source/WTF/wtf/HashTable.h

    r123559 r123582  
    504504        mutable OwnPtr<Stats> m_stats;
    505505#endif
     506    };
     507
     508    // Set all the bits to one after the most significant bit: 00110101010 -> 00111111111.
     509    template<unsigned size> struct OneifyLowBits;
     510    template<>
     511    struct OneifyLowBits<0> {
     512        static const unsigned value = 0;
     513    };
     514    template<unsigned number>
     515    struct OneifyLowBits {
     516        static const unsigned value = number | OneifyLowBits<(number >> 1)>::value;
     517    };
     518    // Compute the first power of two integer that is an upper bound of the parameter 'number'.
     519    template<unsigned number>
     520    struct UpperPowerOfTwoBound {
     521        static const unsigned value = (OneifyLowBits<number - 1>::value + 1) * 2;
     522    };
     523
     524    // Because power of two numbers are the limit of maxLoad, their capacity is twice the
     525    // UpperPowerOfTwoBound, or 4 times their values.
     526    template<unsigned size, bool isPowerOfTwo> struct HashTableCapacityForSizeSplitter;
     527    template<unsigned size>
     528    struct HashTableCapacityForSizeSplitter<size, true> {
     529        static const unsigned value = size * 4;
     530    };
     531    template<unsigned size>
     532    struct HashTableCapacityForSizeSplitter<size, false> {
     533        static const unsigned value = UpperPowerOfTwoBound<size>::value;
     534    };
     535
     536    // HashTableCapacityForSize computes the upper power of two capacity to hold the size parameter.
     537    // This is done at compile time to initialize the HashTraits.
     538    template<unsigned size>
     539    struct HashTableCapacityForSize {
     540        static const unsigned value = HashTableCapacityForSizeSplitter<size, !(size & (size - 1))>::value;
     541        COMPILE_ASSERT(size > 0, HashTableNonZeroMinimumCapacity);
     542        COMPILE_ASSERT(!static_cast<int>(value >> 31), HashTableNoCapacityOverflow);
     543        COMPILE_ASSERT(value > (2 * size), HashTableCapacityHoldsContentSize);
    506544    };
    507545

  • trunk/Source/WebCore/ChangeLog

    r123581 r123582  
     12012-07-24  Benjamin Poulain  <bpoulain@apple.com> && Joseph Pecoraro  <pecoraro@apple.com>
     2
     3        QualifiedName's HashSet should be big enough to hold at least all the static names
     4        https://bugs.webkit.org/show_bug.cgi?id=91891
     5
     6        Reviewed by Darin Adler.
     7
     8        QualifiedName's table has a standard size of 64 buckets. When initializing WebKit,
     9        we create 850 static QualifiedName for the standard names (HTMLNames, SVGNames etc).
     10
     11        The small base size forces us to grow and rehash the table several time on startup.
     12
     13        This patch solves the issue by defining the initial table size to the minimum size that
     14        can hold all the static QualifiedName.
     15
     16        * dom/QualifiedName.cpp:
     17        (QualifiedNameHashTraits):
     18        * dom/make_names.pl:
     19        (printNamesHeaderFile):
     20
    1212012-07-24  Kwang Yul Seo  <skyul@company100.net>
    222

  • trunk/Source/WebCore/dom/QualifiedName.cpp

    r112555 r123582  
    2727
    2828#include "QualifiedName.h"
     29#include "HTMLNames.h"
     30#include "XLinkNames.h"
     31#include "XMLNSNames.h"
     32#include "XMLNames.h"
    2933#include <wtf/Assertions.h>
    3034#include <wtf/HashSet.h>
    3135#include <wtf/StaticConstructors.h>
    3236
     37#if ENABLE(MATHML)
     38#include "MathMLNames.h"
     39#endif
     40
     41#if ENABLE(SVG)
     42#include "SVGNames.h"
     43#endif
     44
    3345namespace WebCore {
    3446
    35 typedef HashSet<QualifiedName::QualifiedNameImpl*, QualifiedNameHash> QNameSet;
     47static const int staticQualifiedNamesCount = HTMLNames::HTMLTagsCount + HTMLNames::HTMLAttrsCount
     48#if ENABLE(MATHML)
     49    + MathMLNames::MathMLTagsCount + MathMLNames::MathMLAttrsCount
     50#endif
     51#if ENABLE(SVG)
     52    + SVGNames::SVGTagsCount + SVGNames::SVGAttrsCount
     53#endif
     54    + XLinkNames::XLinkAttrsCount
     55    + XMLNSNames::XMLNSAttrsCount
     56    + XMLNames::XMLAttrsCount;
     57
     58struct QualifiedNameHashTraits : public HashTraits<QualifiedName::QualifiedNameImpl*> {
     59    static const int minimumTableSize = WTF::HashTableCapacityForSize<staticQualifiedNamesCount>::value;
     60};
     61
     62typedef HashSet<QualifiedName::QualifiedNameImpl*, QualifiedNameHash, QualifiedNameHashTraits> QNameSet;
    3663
    3764struct QNameComponentsTranslator {

  • trunk/Source/WebCore/dom/make_names.pl

    r120168 r123582  
    601601
    602602    if (keys %allTags) {
     603        print F "const unsigned $parameters{namespace}TagsCount = ", scalar(keys %allTags), ";\n";
    603604        print F "WebCore::QualifiedName** get$parameters{namespace}Tags(size_t* size);\n";
    604605    }
    605606
    606607    if (keys %allAttrs) {
     608        print F "const unsigned $parameters{namespace}AttrsCount = ", scalar(keys %allAttrs), ";\n";
    607609        print F "WebCore::QualifiedName** get$parameters{namespace}Attrs(size_t* size);\n";
    608610    }

  • trunk/Tools/ChangeLog

    r123580 r123582  
     12012-07-24  Benjamin Poulain  <bpoulain@apple.com> && Joseph Pecoraro  <pecoraro@apple.com>
     2
     3        QualifiedName's HashSet should be big enough to hold at least all the static names
     4        https://bugs.webkit.org/show_bug.cgi?id=91891
     5
     6        Reviewed by Darin Adler.
     7
     8        Add a test for WTF::hashTableCapacityForSize.
     9
     10        * TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
     11        * TestWebKitAPI/Tests/WTF/HashSet.cpp: Added.
     12        (InitialCapacityTestHashTraits):
     13        (TestWebKitAPI::testInitialCapacity):
     14        (TestWebKitAPI::generateTestCapacityUpToSize):
     15        (TestWebKitAPI::TEST):
     16
    1172012-07-24  Adam Barth  <abarth@webkit.org>
    218

  • trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj

    r122683 r123582  
    2222                1AEDE22613E5E7E700E62FE8 /* InjectedBundleControllerMac.mm in Sources */ = {isa = PBXBuildFile; fileRef = 1AEDE22413E5E7A000E62FE8 /* InjectedBundleControllerMac.mm */; };
    2323                261516D615B0E60500A2C201 /* SetAndUpdateCacheModel.mm in Sources */ = {isa = PBXBuildFile; fileRef = 261516D515B0E60500A2C201 /* SetAndUpdateCacheModel.mm */; };
     24                26B2DFF915BDE599004F691D /* HashSet.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 26B2DFF815BDE599004F691D /* HashSet.cpp */; };
    2425                26DF5A5E15A29BAA003689C2 /* CancelLoadFromResourceLoadDelegate.mm in Sources */ = {isa = PBXBuildFile; fileRef = 26DF5A5D15A29BAA003689C2 /* CancelLoadFromResourceLoadDelegate.mm */; };
    2526                26DF5A6315A2A27E003689C2 /* CancelLoadFromResourceLoadDelegate.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 26DF5A6115A2A22B003689C2 /* CancelLoadFromResourceLoadDelegate.html */; };
    … …  
    246247                1AEDE22413E5E7A000E62FE8 /* InjectedBundleControllerMac.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = InjectedBundleControllerMac.mm; sourceTree = "<group>"; };
    247248                261516D515B0E60500A2C201 /* SetAndUpdateCacheModel.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = SetAndUpdateCacheModel.mm; sourceTree = "<group>"; };
     249                26B2DFF815BDE599004F691D /* HashSet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = HashSet.cpp; path = WTF/HashSet.cpp; sourceTree = "<group>"; };
    248250                26DF5A5D15A29BAA003689C2 /* CancelLoadFromResourceLoadDelegate.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = CancelLoadFromResourceLoadDelegate.mm; sourceTree = "<group>"; };
    249251                26DF5A6115A2A22B003689C2 /* CancelLoadFromResourceLoadDelegate.html */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.html; path = CancelLoadFromResourceLoadDelegate.html; sourceTree = "<group>"; };
    … …  
    621623                                1AA9E55714980A9900001A8A /* Functional.cpp */,
    622624                                0BCD833414857CE400EA2003 /* HashMap.cpp */,
     625                                26B2DFF815BDE599004F691D /* HashSet.cpp */,
    623626                                81B50192140F232300D9EB58 /* StringBuilder.cpp */,
    624627                                C01363C713C3997300EF3964 /* StringOperators.cpp */,
    … …  
    946949                                261516D615B0E60500A2C201 /* SetAndUpdateCacheModel.mm in Sources */,
    947950                                A5E2027315B2181900C13E14 /* WindowlessWebViewWithMedia.mm in Sources */,
     951                                26B2DFF915BDE599004F691D /* HashSet.cpp in Sources */,
    948952                        );
    949953                        runOnlyForDeploymentPostprocessing = 0;
Note: See TracChangeset for help on using the changeset viewer.