⚠ Archived content — this site is no longer maintained.   Current WebKit documentation is at docs.webkit.org.

Changeset 282142 in webkit


Ignore:
Timestamp:
Sep 8, 2021, 7:01:50 AM (5 years ago)
Author:
Wenson Hsieh
Message:

Add a fast path for atomizing strings when parsing HTML
​https://bugs.webkit.org/show_bug.cgi?id=229907
rdar://82854612

Reviewed by Yusuke Suzuki and Darin Adler.

On various subtests in Speedometer 2, a nontrivial amount of time is spent mapping raw UChar data vectors into
AtomStrings while parsing HTML tag names, attribute names and attribute values. Most of this happens underneath
the AtomHTMLToken constructor, which computes a hash for each string in the process of adding it to the atom
string table; the time it takes to compute this string hash increases linearly with the length of the string.

However, over the course of the benchmark, the vast majority of AtomStrings created out of tag names, attribute
names and attribute values are both:

(1) Strings that we've already recently atomized, and
(2) Usually distinguishable from other atom strings based solely on their first character, last character, and

overall string length.

As such, it's possible to slightly improve string atomization performance in this particular case (i.e. parsing
HTML) by maintaining a smaller cache of recently atomized AtomStrings that we index using a simple, constant-
time hash function that considers only the first character, last character, and length of the string. In terms
of the cache hit rate in this AtomString cache, the default string hashing algorithm only barely outperforms
this simple hash function on Speedometer (i.e., a cache hit rate of 99.24% using the default hash algorithm vs.
99.15% using the "first/last character and length" hash).

Using this technique, we can get a significant performance improvement on Speedometer by introducing two small,
fixed-size (512 capacity) AtomString tables: one to hold tag names and attribute names, and another to hold
attribute values (which seems to contain a much larger set of unique strings); we additionally use the cheap "2-
char & length" hash algorithm described above to index into these fixed-size tables.

This allows us to more efficiently atomize not only known tag and attribute names, but also custom element tag
names and attribute names and values that tend to appear frequently in markup (e.g. due to using certain
JavaScript frameworks that get and set HTML attributes).

  • Sources.txt:
  • WebCore.xcodeproj/project.pbxproj:
  • html/parser/AtomHTMLToken.h:

(WebCore::AtomHTMLToken::initializeAttributes):
(WebCore::AtomHTMLToken::AtomHTMLToken):

  • html/parser/HTMLAtomStringCache.cpp: Added.

(WebCore::HTMLAtomStringCache::cache):

  • html/parser/HTMLAtomStringCache.h: Added.

Add a helper class that exposes three static inline helper methods: makeTagOrAttributeName and
makeAttributeValue, which return AtomStrings for the given Vector<UChar> (consulting the corresponding
cache if possible); and clear, which empties all cached atom strings.

(WebCore::HTMLAtomStringCache::makeTagOrAttributeName):
(WebCore::HTMLAtomStringCache::makeAttributeValue):
(WebCore::HTMLAtomStringCache::clear):
(WebCore::HTMLAtomStringCache::make):

Additionally add an upper length limit for characters that we include in this cache; in practice, longer strings
tend to be repeatedly atomized less frequently than shorter strings. The 36-character limit also allows for
frequently-parsed (and atomized) UUIDs to be cached.

(WebCore::HTMLAtomStringCache::cacheSlot):

This hashing algorithm was inspired by calculateWithTwoCharacters, but with constants specifically chosen to
minimize collisions between common HTML tag and attribute names.

  • page/MemoryRelease.cpp:

(WebCore::releaseNoncriticalMemory):

  • page/cocoa/MemoryReleaseCocoa.mm:

(WebCore::jettisonExpensiveObjectsOnTopLevelNavigation):

Add logic to clear the HTML atom string cache upon receiving a low memory warning, and upon top-level
navigation.

Location:
trunk/Source/WebCore
Files:
2 added
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r282141 r282142  
     12021-09-08  Wenson Hsieh  <wenson_hsieh@apple.com>
     2
     3        Add a fast path for atomizing strings when parsing HTML
     4        https://bugs.webkit.org/show_bug.cgi?id=229907
     5        rdar://82854612
     6
     7        Reviewed by Yusuke Suzuki and Darin Adler.
     8
     9        On various subtests in Speedometer 2, a nontrivial amount of time is spent mapping raw UChar data vectors into
     10        AtomStrings while parsing HTML tag names, attribute names and attribute values. Most of this happens underneath
     11        the AtomHTMLToken constructor, which computes a hash for each string in the process of adding it to the atom
     12        string table; the time it takes to compute this string hash increases linearly with the length of the string.
     13
     14        However, over the course of the benchmark, the vast majority of AtomStrings created out of tag names, attribute
     15        names and attribute values are both:
     16
     17        (1) Strings that we've already recently atomized, and
     18        (2) Usually distinguishable from other atom strings based solely on their first character, last character, and
     19            overall string length.
     20
     21        As such, it's possible to slightly improve string atomization performance in this particular case (i.e. parsing
     22        HTML) by maintaining a smaller cache of recently atomized AtomStrings that we index using a simple, constant-
     23        time hash function that considers only the first character, last character, and length of the string. In terms
     24        of the cache hit rate in this AtomString cache, the default string hashing algorithm only barely outperforms
     25        this simple hash function on Speedometer (i.e., a cache hit rate of 99.24% using the default hash algorithm vs.
     26        99.15% using the "first/last character and length" hash).
     27
     28        Using this technique, we can get a significant performance improvement on Speedometer by introducing two small,
     29        fixed-size (512 capacity) AtomString tables: one to hold tag names and attribute names, and another to hold
     30        attribute values (which seems to contain a much larger set of unique strings); we additionally use the cheap "2-
     31        char & length" hash algorithm described above to index into these fixed-size tables.
     32
     33        This allows us to more efficiently atomize not only known tag and attribute names, but also custom element tag
     34        names and attribute names and values that tend to appear frequently in markup (e.g. due to using certain
     35        JavaScript frameworks that get and set HTML attributes).
     36
     37        * Sources.txt:
     38        * WebCore.xcodeproj/project.pbxproj:
     39        * html/parser/AtomHTMLToken.h:
     40        (WebCore::AtomHTMLToken::initializeAttributes):
     41        (WebCore::AtomHTMLToken::AtomHTMLToken):
     42        * html/parser/HTMLAtomStringCache.cpp: Added.
     43        (WebCore::HTMLAtomStringCache::cache):
     44        * html/parser/HTMLAtomStringCache.h: Added.
     45
     46        Add a helper class that exposes three static inline helper methods: `makeTagOrAttributeName` and
     47        `makeAttributeValue`, which return AtomStrings for the given `Vector<UChar>` (consulting the corresponding
     48        cache if possible); and `clear`, which empties all cached atom strings.
     49
     50        (WebCore::HTMLAtomStringCache::makeTagOrAttributeName):
     51        (WebCore::HTMLAtomStringCache::makeAttributeValue):
     52        (WebCore::HTMLAtomStringCache::clear):
     53        (WebCore::HTMLAtomStringCache::make):
     54
     55        Additionally add an upper length limit for characters that we include in this cache; in practice, longer strings
     56        tend to be repeatedly atomized less frequently than shorter strings. The 36-character limit also allows for
     57        frequently-parsed (and atomized) UUIDs to be cached.
     58
     59        (WebCore::HTMLAtomStringCache::cacheSlot):
     60
     61        This hashing algorithm was inspired by `calculateWithTwoCharacters`, but with constants specifically chosen to
     62        minimize collisions between common HTML tag and attribute names.
     63
     64        * page/MemoryRelease.cpp:
     65        (WebCore::releaseNoncriticalMemory):
     66        * page/cocoa/MemoryReleaseCocoa.mm:
     67        (WebCore::jettisonExpensiveObjectsOnTopLevelNavigation):
     68
     69        Add logic to clear the HTML atom string cache upon receiving a low memory warning, and upon top-level
     70        navigation.
     71
    1722021-09-08  Alan Bujtas  <zalan@apple.com>
    273

  • trunk/Source/WebCore/Sources.txt

    r282130 r282142  
    13131313html/forms/FileIconLoader.cpp
    13141314html/parser/CSSPreloadScanner.cpp
     1315html/parser/HTMLAtomStringCache.cpp
    13151316html/parser/HTMLConstructionSite.cpp
    13161317html/parser/HTMLDocumentParser.cpp

  • trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj

    r282130 r282142  
    54105410                F48D2AA52159740D00C6752B /* ColorCocoa.h in Headers */ = {isa = PBXBuildFile; fileRef = F48D2AA32159740D00C6752B /* ColorCocoa.h */; settings = {ATTRIBUTES = (Private, ); }; };
    54115411                F49786881FF45FA500E060AB /* PasteboardItemInfo.h in Headers */ = {isa = PBXBuildFile; fileRef = F49786871FF45FA500E060AB /* PasteboardItemInfo.h */; settings = {ATTRIBUTES = (Private, ); }; };
     5412                F4B0018926E7F21F006EAABE /* HTMLAtomStringCache.h in Headers */ = {isa = PBXBuildFile; fileRef = F4B0018726E7F21F006EAABE /* HTMLAtomStringCache.h */; };
    54125413                F4B2A909265030BA009E7286 /* DataDetectorHighlight.h in Headers */ = {isa = PBXBuildFile; fileRef = F4B2A90626502BA0009E7286 /* DataDetectorHighlight.h */; };
    54135414                F4B422C4220C0568009E1E7D /* DOMPasteAccess.h in Headers */ = {isa = PBXBuildFile; fileRef = F4B422C2220C0000009E1E7D /* DOMPasteAccess.h */; settings = {ATTRIBUTES = (Private, ); }; };
    … …  
    1664116642                F49786871FF45FA500E060AB /* PasteboardItemInfo.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = PasteboardItemInfo.h; sourceTree = "<group>"; };
    1664216643                F49E98E421DEE6C1009AE55E /* EditAction.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = EditAction.cpp; sourceTree = "<group>"; };
     16644                F4B0018726E7F21F006EAABE /* HTMLAtomStringCache.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = HTMLAtomStringCache.h; sourceTree = "<group>"; };
     16645                F4B0018826E7F21F006EAABE /* HTMLAtomStringCache.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = HTMLAtomStringCache.cpp; sourceTree = "<group>"; };
    1664316646                F4B2A90626502BA0009E7286 /* DataDetectorHighlight.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = DataDetectorHighlight.h; sourceTree = "<group>"; };
    1664416647                F4B2A90826502BC0009E7286 /* DataDetectorHighlight.mm */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.objcpp; path = DataDetectorHighlight.mm; sourceTree = "<group>"; };
    … …  
    2419324196                                977B3849122883E900B81FF8 /* CSSPreloadScanner.cpp */,
    2419424197                                977B384A122883E900B81FF8 /* CSSPreloadScanner.h */,
     24198                                F4B0018826E7F21F006EAABE /* HTMLAtomStringCache.cpp */,
     24199                                F4B0018726E7F21F006EAABE /* HTMLAtomStringCache.h */,
    2419524200                                977B384B122883E900B81FF8 /* HTMLConstructionSite.cpp */,
    2419624201                                977B384C122883E900B81FF8 /* HTMLConstructionSite.h */,
    … …  
    3230732312                                A8CFF7AB0A156978000A4234 /* HTMLAnchorElement.h in Headers */,
    3230832313                                A8EA7D2E0A19385500A8EF5F /* HTMLAreaElement.h in Headers */,
     32314                                F4B0018926E7F21F006EAABE /* HTMLAtomStringCache.h in Headers */,
    3230932315                                7C5F28FC1A827D8400C0F31F /* HTMLAttachmentElement.h in Headers */,
    3231032316                                E44613A20CD6331000FADA75 /* HTMLAudioElement.h in Headers */,

  • trunk/Source/WebCore/html/parser/AtomHTMLToken.h

    r280199 r282142  
    2727#pragma once
    2828
     29#include "HTMLAtomStringCache.h"
    2930#include "HTMLToken.h"
    3031
    … …  
    203204            continue;
    204205
    205         AtomString localName(attribute.name);
     206        auto localName = HTMLAtomStringCache::makeTagOrAttributeName(attribute.name);
    206207
    207208        // FIXME: This is N^2 for the number of attributes.
    208209        if (!hasAttribute(m_attributes, localName))
    209             m_attributes.uncheckedAppend(Attribute(QualifiedName(nullAtom(), localName, nullAtom()), AtomString(attribute.value)));
     210            m_attributes.uncheckedAppend(Attribute(QualifiedName(nullAtom(), localName, nullAtom()), HTMLAtomStringCache::makeAttributeValue(attribute.value)));
    210211    }
    211212}
    … …  
    219220        return;
    220221    case HTMLToken::DOCTYPE:
    221         m_name = AtomString(token.name());
     222        m_name = HTMLAtomStringCache::makeTagOrAttributeName(token.name());
    222223        m_doctypeData = token.releaseDoctypeData();
    223224        return;
    … …  
    227228    case HTMLToken::EndTag:
    228229        m_selfClosing = token.selfClosing();
    229         m_name = AtomString(token.name());
     230        m_name = HTMLAtomStringCache::makeTagOrAttributeName(token.name());
    230231        initializeAttributes(token.attributes());
    231232        return;

  • trunk/Source/WebCore/page/MemoryRelease.cpp

    r275428 r282142  
    3939#include "Frame.h"
    4040#include "GCController.h"
     41#include "HTMLAtomStringCache.h"
    4142#include "HTMLMediaElement.h"
    4243#include "InlineStyleSheetOwner.h"
    … …  
    8687
    8788    InlineStyleSheetOwner::clearCache();
     89    HTMLAtomStringCache::clear();
    8890}
    8991

  • trunk/Source/WebCore/page/cocoa/MemoryReleaseCocoa.mm

    r271526 r282142  
    2929#import "FontFamilySpecificationCoreText.h"
    3030#import "GCController.h"
     31#import "HTMLAtomStringCache.h"
    3132#import "IOSurfacePool.h"
    3233#import "LayerPool.h"
    … …  
    8485void jettisonExpensiveObjectsOnTopLevelNavigation()
    8586{
    86 #if PLATFORM(IOS_FAMILY)
    8787    // Protect against doing excessive jettisoning during repeated navigations.
    8888    const auto minimumTimeSinceNavigation = 2_s;
    … …  
    9696        return;
    9797
     98#if PLATFORM(IOS_FAMILY)
    9899    // Throw away linked JS code. Linked code is tied to a global object and is not reusable.
    99100    // The immediate memory savings outweigh the cost of recompilation in case we go back again.
    100101    GCController::singleton().deleteAllLinkedCode(JSC::DeleteAllCodeIfNotCollecting);
    101102#endif
     103
     104    HTMLAtomStringCache::clear();
    102105}
    103106
Note: See TracChangeset for help on using the changeset viewer.