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

Changeset 282227 in webkit


Ignore:
Timestamp:
Sep 9, 2021, 11:04:27 AM (5 years ago)
Author:
Russell Epstein
Message:

Cherry-pick r282142. rdar://problem/82931317

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.

git-svn-id: ​https://svn.webkit.org/repository/webkit/trunk@282142 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Location:
branches/safari-612-branch/Source/WebCore
Files:
2 added
6 edited

Legend:

Unmodified
Added
Removed

  • branches/safari-612-branch/Source/WebCore/ChangeLog

    r281904 r282227  
     12021-09-09  Russell Epstein  <repstein@apple.com>
     2
     3        Cherry-pick r282142. rdar://problem/82931317
     4
     5    Add a fast path for atomizing strings when parsing HTML
     6    https://bugs.webkit.org/show_bug.cgi?id=229907
     7    rdar://82854612
     8   
     9    Reviewed by Yusuke Suzuki and Darin Adler.
     10   
     11    On various subtests in Speedometer 2, a nontrivial amount of time is spent mapping raw UChar data vectors into
     12    AtomStrings while parsing HTML tag names, attribute names and attribute values. Most of this happens underneath
     13    the AtomHTMLToken constructor, which computes a hash for each string in the process of adding it to the atom
     14    string table; the time it takes to compute this string hash increases linearly with the length of the string.
     15   
     16    However, over the course of the benchmark, the vast majority of AtomStrings created out of tag names, attribute
     17    names and attribute values are both:
     18   
     19    (1) Strings that we've already recently atomized, and
     20    (2) Usually distinguishable from other atom strings based solely on their first character, last character, and
     21        overall string length.
     22   
     23    As such, it's possible to slightly improve string atomization performance in this particular case (i.e. parsing
     24    HTML) by maintaining a smaller cache of recently atomized AtomStrings that we index using a simple, constant-
     25    time hash function that considers only the first character, last character, and length of the string. In terms
     26    of the cache hit rate in this AtomString cache, the default string hashing algorithm only barely outperforms
     27    this simple hash function on Speedometer (i.e., a cache hit rate of 99.24% using the default hash algorithm vs.
     28    99.15% using the "first/last character and length" hash).
     29   
     30    Using this technique, we can get a significant performance improvement on Speedometer by introducing two small,
     31    fixed-size (512 capacity) AtomString tables: one to hold tag names and attribute names, and another to hold
     32    attribute values (which seems to contain a much larger set of unique strings); we additionally use the cheap "2-
     33    char & length" hash algorithm described above to index into these fixed-size tables.
     34   
     35    This allows us to more efficiently atomize not only known tag and attribute names, but also custom element tag
     36    names and attribute names and values that tend to appear frequently in markup (e.g. due to using certain
     37    JavaScript frameworks that get and set HTML attributes).
     38   
     39    * Sources.txt:
     40    * WebCore.xcodeproj/project.pbxproj:
     41    * html/parser/AtomHTMLToken.h:
     42    (WebCore::AtomHTMLToken::initializeAttributes):
     43    (WebCore::AtomHTMLToken::AtomHTMLToken):
     44    * html/parser/HTMLAtomStringCache.cpp: Added.
     45    (WebCore::HTMLAtomStringCache::cache):
     46    * html/parser/HTMLAtomStringCache.h: Added.
     47   
     48    Add a helper class that exposes three static inline helper methods: `makeTagOrAttributeName` and
     49    `makeAttributeValue`, which return AtomStrings for the given `Vector<UChar>` (consulting the corresponding
     50    cache if possible); and `clear`, which empties all cached atom strings.
     51   
     52    (WebCore::HTMLAtomStringCache::makeTagOrAttributeName):
     53    (WebCore::HTMLAtomStringCache::makeAttributeValue):
     54    (WebCore::HTMLAtomStringCache::clear):
     55    (WebCore::HTMLAtomStringCache::make):
     56   
     57    Additionally add an upper length limit for characters that we include in this cache; in practice, longer strings
     58    tend to be repeatedly atomized less frequently than shorter strings. The 36-character limit also allows for
     59    frequently-parsed (and atomized) UUIDs to be cached.
     60   
     61    (WebCore::HTMLAtomStringCache::cacheSlot):
     62   
     63    This hashing algorithm was inspired by `calculateWithTwoCharacters`, but with constants specifically chosen to
     64    minimize collisions between common HTML tag and attribute names.
     65   
     66    * page/MemoryRelease.cpp:
     67    (WebCore::releaseNoncriticalMemory):
     68    * page/cocoa/MemoryReleaseCocoa.mm:
     69    (WebCore::jettisonExpensiveObjectsOnTopLevelNavigation):
     70   
     71    Add logic to clear the HTML atom string cache upon receiving a low memory warning, and upon top-level
     72    navigation.
     73   
     74   
     75    git-svn-id: https://svn.webkit.org/repository/webkit/trunk@282142 268f45cc-cd09-0410-ab3c-d52691b4dbfc
     76
     77    2021-09-08  Wenson Hsieh  <wenson_hsieh@apple.com>
     78
     79            Add a fast path for atomizing strings when parsing HTML
     80            https://bugs.webkit.org/show_bug.cgi?id=229907
     81            rdar://82854612
     82
     83            Reviewed by Yusuke Suzuki and Darin Adler.
     84
     85            On various subtests in Speedometer 2, a nontrivial amount of time is spent mapping raw UChar data vectors into
     86            AtomStrings while parsing HTML tag names, attribute names and attribute values. Most of this happens underneath
     87            the AtomHTMLToken constructor, which computes a hash for each string in the process of adding it to the atom
     88            string table; the time it takes to compute this string hash increases linearly with the length of the string.
     89
     90            However, over the course of the benchmark, the vast majority of AtomStrings created out of tag names, attribute
     91            names and attribute values are both:
     92
     93            (1) Strings that we've already recently atomized, and
     94            (2) Usually distinguishable from other atom strings based solely on their first character, last character, and
     95                overall string length.
     96
     97            As such, it's possible to slightly improve string atomization performance in this particular case (i.e. parsing
     98            HTML) by maintaining a smaller cache of recently atomized AtomStrings that we index using a simple, constant-
     99            time hash function that considers only the first character, last character, and length of the string. In terms
     100            of the cache hit rate in this AtomString cache, the default string hashing algorithm only barely outperforms
     101            this simple hash function on Speedometer (i.e., a cache hit rate of 99.24% using the default hash algorithm vs.
     102            99.15% using the "first/last character and length" hash).
     103
     104            Using this technique, we can get a significant performance improvement on Speedometer by introducing two small,
     105            fixed-size (512 capacity) AtomString tables: one to hold tag names and attribute names, and another to hold
     106            attribute values (which seems to contain a much larger set of unique strings); we additionally use the cheap "2-
     107            char & length" hash algorithm described above to index into these fixed-size tables.
     108
     109            This allows us to more efficiently atomize not only known tag and attribute names, but also custom element tag
     110            names and attribute names and values that tend to appear frequently in markup (e.g. due to using certain
     111            JavaScript frameworks that get and set HTML attributes).
     112
     113            * Sources.txt:
     114            * WebCore.xcodeproj/project.pbxproj:
     115            * html/parser/AtomHTMLToken.h:
     116            (WebCore::AtomHTMLToken::initializeAttributes):
     117            (WebCore::AtomHTMLToken::AtomHTMLToken):
     118            * html/parser/HTMLAtomStringCache.cpp: Added.
     119            (WebCore::HTMLAtomStringCache::cache):
     120            * html/parser/HTMLAtomStringCache.h: Added.
     121
     122            Add a helper class that exposes three static inline helper methods: `makeTagOrAttributeName` and
     123            `makeAttributeValue`, which return AtomStrings for the given `Vector<UChar>` (consulting the corresponding
     124            cache if possible); and `clear`, which empties all cached atom strings.
     125
     126            (WebCore::HTMLAtomStringCache::makeTagOrAttributeName):
     127            (WebCore::HTMLAtomStringCache::makeAttributeValue):
     128            (WebCore::HTMLAtomStringCache::clear):
     129            (WebCore::HTMLAtomStringCache::make):
     130
     131            Additionally add an upper length limit for characters that we include in this cache; in practice, longer strings
     132            tend to be repeatedly atomized less frequently than shorter strings. The 36-character limit also allows for
     133            frequently-parsed (and atomized) UUIDs to be cached.
     134
     135            (WebCore::HTMLAtomStringCache::cacheSlot):
     136
     137            This hashing algorithm was inspired by `calculateWithTwoCharacters`, but with constants specifically chosen to
     138            minimize collisions between common HTML tag and attribute names.
     139
     140            * page/MemoryRelease.cpp:
     141            (WebCore::releaseNoncriticalMemory):
     142            * page/cocoa/MemoryReleaseCocoa.mm:
     143            (WebCore::jettisonExpensiveObjectsOnTopLevelNavigation):
     144
     145            Add logic to clear the HTML atom string cache upon receiving a low memory warning, and upon top-level
     146            navigation.
     147
    11482021-09-01  Russell Epstein  <repstein@apple.com>
    2149

  • branches/safari-612-branch/Source/WebCore/Sources.txt

    r281263 r282227  
    13031303html/forms/FileIconLoader.cpp
    13041304html/parser/CSSPreloadScanner.cpp
     1305html/parser/HTMLAtomStringCache.cpp
    13051306html/parser/HTMLConstructionSite.cpp
    13061307html/parser/HTMLDocumentParser.cpp

  • branches/safari-612-branch/Source/WebCore/WebCore.xcodeproj/project.pbxproj

    r281263 r282227  
    53855385                F48D2AA52159740D00C6752B /* ColorCocoa.h in Headers */ = {isa = PBXBuildFile; fileRef = F48D2AA32159740D00C6752B /* ColorCocoa.h */; settings = {ATTRIBUTES = (Private, ); }; };
    53865386                F49786881FF45FA500E060AB /* PasteboardItemInfo.h in Headers */ = {isa = PBXBuildFile; fileRef = F49786871FF45FA500E060AB /* PasteboardItemInfo.h */; settings = {ATTRIBUTES = (Private, ); }; };
     5387                F4B0018926E7F21F006EAABE /* HTMLAtomStringCache.h in Headers */ = {isa = PBXBuildFile; fileRef = F4B0018726E7F21F006EAABE /* HTMLAtomStringCache.h */; };
    53875388                F4B2A909265030BA009E7286 /* DataDetectorHighlight.h in Headers */ = {isa = PBXBuildFile; fileRef = F4B2A90626502BA0009E7286 /* DataDetectorHighlight.h */; };
    53885389                F4B422C4220C0568009E1E7D /* DOMPasteAccess.h in Headers */ = {isa = PBXBuildFile; fileRef = F4B422C2220C0000009E1E7D /* DOMPasteAccess.h */; settings = {ATTRIBUTES = (Private, ); }; };
    … …  
    1655616557                F49786871FF45FA500E060AB /* PasteboardItemInfo.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = PasteboardItemInfo.h; sourceTree = "<group>"; };
    1655716558                F49E98E421DEE6C1009AE55E /* EditAction.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = EditAction.cpp; sourceTree = "<group>"; };
     16559                F4B0018726E7F21F006EAABE /* HTMLAtomStringCache.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = HTMLAtomStringCache.h; sourceTree = "<group>"; };
     16560                F4B0018826E7F21F006EAABE /* HTMLAtomStringCache.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = HTMLAtomStringCache.cpp; sourceTree = "<group>"; };
    1655816561                F4B2A90626502BA0009E7286 /* DataDetectorHighlight.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = DataDetectorHighlight.h; sourceTree = "<group>"; };
    1655916562                F4B2A90826502BC0009E7286 /* DataDetectorHighlight.mm */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.objcpp; path = DataDetectorHighlight.mm; sourceTree = "<group>"; };
    … …  
    2403624039                                977B3849122883E900B81FF8 /* CSSPreloadScanner.cpp */,
    2403724040                                977B384A122883E900B81FF8 /* CSSPreloadScanner.h */,
     24041                                F4B0018826E7F21F006EAABE /* HTMLAtomStringCache.cpp */,
     24042                                F4B0018726E7F21F006EAABE /* HTMLAtomStringCache.h */,
    2403824043                                977B384B122883E900B81FF8 /* HTMLConstructionSite.cpp */,
    2403924044                                977B384C122883E900B81FF8 /* HTMLConstructionSite.h */,
    … …  
    3214132146                                A8CFF7AB0A156978000A4234 /* HTMLAnchorElement.h in Headers */,
    3214232147                                A8EA7D2E0A19385500A8EF5F /* HTMLAreaElement.h in Headers */,
     32148                                F4B0018926E7F21F006EAABE /* HTMLAtomStringCache.h in Headers */,
    3214332149                                7C5F28FC1A827D8400C0F31F /* HTMLAttachmentElement.h in Headers */,
    3214432150                                E44613A20CD6331000FADA75 /* HTMLAudioElement.h in Headers */,

  • branches/safari-612-branch/Source/WebCore/html/parser/AtomHTMLToken.h

    r280199 r282227  
    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;

  • branches/safari-612-branch/Source/WebCore/page/MemoryRelease.cpp

    r275428 r282227  
    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

  • branches/safari-612-branch/Source/WebCore/page/cocoa/MemoryReleaseCocoa.mm

    r271526 r282227  
    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.