Changeset 278971 in webkit


Ignore:
Timestamp:
Jun 16, 2021 8:09:57 PM (13 months ago)
Author:
ysuzuki@apple.com
Message:

[JSC] Optimize JSON.parse with small data by changing Identifier pool mechanism
​https://bugs.webkit.org/show_bug.cgi?id=227101

Reviewed by Mark Lam.

Found that std::array<Identifier, 128> pool in LiteralParser is too costly for construction and destruction
if JSON.parse is invoked for small data. This patch changes this pool mechanism so that we do not waste effort
allocating null Identifiers to pre-populate the recent identifiers pool. Instead, we now use a m_recentIdentifiersIndex
uint8_t array to indicate whether there's a cached recent identifier for each given first character.

We also use KeywordLookup.h's COMPARE_XCHARS to perform "true" / "false" / "null" lexing in JSON parser.
Roughly 20% improvement in microbenchmark. And roughly 2-3% improvement in Speedometer2/Flight-TodoMVC.

ToT Patched

flight-todomvc-json 67.8755+-1.1202 56.7114+-0.5048 definitely 1.1969x faster

  • runtime/Identifier.cpp:

(JSC::Identifier::add):
(JSC::Identifier::add8):

  • runtime/Identifier.h:

(JSC::Identifier::Identifier):
(JSC::Identifier::add):

  • runtime/IdentifierInlines.h:

(JSC::Identifier::add):
(JSC::Identifier::fromString):

  • runtime/LiteralParser.cpp:

(JSC::compare3Chars):
(JSC::compare4Chars):
(JSC::LiteralParser<CharType>::makeIdentifier):
(JSC::LiteralParser<CharType>::Lexer::lex):

  • runtime/LiteralParser.h:
Location:
trunk
Files:
1 added
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r278966 r278971  
     12021-06-16  Yusuke Suzuki  <ysuzuki@apple.com>
     2
     3        [JSC] Optimize JSON.parse with small data by changing Identifier pool mechanism
     4        https://bugs.webkit.org/show_bug.cgi?id=227101
     5
     6        Reviewed by Mark Lam.
     7
     8        Found that std::array<Identifier, 128> pool in LiteralParser is too costly for construction and destruction
     9        if JSON.parse is invoked for small data. This patch changes this pool mechanism so that we do not waste effort
     10        allocating null Identifiers to pre-populate the recent identifiers pool. Instead, we now use a m_recentIdentifiersIndex
     11        uint8_t array to indicate whether there's a cached recent identifier for each given first character.
     12
     13        We also use KeywordLookup.h's COMPARE_XCHARS to perform "true" / "false" / "null" lexing in JSON parser.
     14        Roughly 20% improvement in microbenchmark. And roughly 2-3% improvement in Speedometer2/Flight-TodoMVC.
     15
     16                                            ToT                     Patched
     17
     18            flight-todomvc-json       67.8755+-1.1202     ^     56.7114+-0.5048        ^ definitely 1.1969x faster
     19
     20        * runtime/Identifier.cpp:
     21        (JSC::Identifier::add):
     22        (JSC::Identifier::add8):
     23        * runtime/Identifier.h:
     24        (JSC::Identifier::Identifier):
     25        (JSC::Identifier::add):
     26        * runtime/IdentifierInlines.h:
     27        (JSC::Identifier::add):
     28        (JSC::Identifier::fromString):
     29        * runtime/LiteralParser.cpp:
     30        (JSC::compare3Chars):
     31        (JSC::compare4Chars):
     32        (JSC::LiteralParser<CharType>::makeIdentifier):
     33        (JSC::LiteralParser<CharType>::Lexer::lex):
     34        * runtime/LiteralParser.h:
     35
    1362021-06-16  Mark Lam  <mark.lam@apple.com>
    237

  • trunk/Source/JavaScriptCore/runtime/Identifier.cpp

    r261895 r278971  
    2828namespace JSC {
    2929
    30 Ref<StringImpl> Identifier::add(VM& vm, const char* c)
     30Ref<AtomStringImpl> Identifier::add(VM& vm, const char* c)
    3131{
    3232    ASSERT(c);
    … …  
    3838}
    3939
    40 Ref<StringImpl> Identifier::add8(VM& vm, const UChar* s, int length)
     40Ref<AtomStringImpl> Identifier::add8(VM& vm, const UChar* s, int length)
    4141{
    4242    if (length == 1) {
    … …  
    4747    }
    4848    if (!length)
    49         return *StringImpl::empty();
     49        return *static_cast<AtomStringImpl*>(StringImpl::empty());
    5050
    5151    return *AtomStringImpl::add(s, length);

  • trunk/Source/JavaScriptCore/runtime/Identifier.h

    r278921 r278971  
    118118    static Identifier fromString(VM&, const String&);
    119119    static Identifier fromString(VM&, AtomStringImpl*);
     120    static Identifier fromString(VM&, Ref<AtomStringImpl>&&);
    120121    static Identifier fromString(VM&, const AtomString&);
    121122    static Identifier fromString(VM& vm, SymbolImpl*);
    … …  
    160161
    161162    // Only to be used with string literals.
    162     JS_EXPORT_PRIVATE static Ref<StringImpl> add(VM&, const char*);
     163    JS_EXPORT_PRIVATE static Ref<AtomStringImpl> add(VM&, const char*);
    163164
    164165    void dump(PrintStream&) const;
    … …  
    178179    Identifier(VM& vm, StringImpl* rep) : m_string(add(vm, rep)) { ASSERT(m_string.impl()->isAtom()); }
    179180
     181    Identifier(VM&, Ref<AtomStringImpl>&& impl)
     182        : m_string(WTFMove(impl))
     183    { }
     184
    180185    Identifier(SymbolImpl& uid)
    181186        : m_string(&uid)
    182     {
    183     }
     187    { }
    184188
    185189    template <typename CharType>
    … …  
    189193    static bool equal(const Identifier& a, const LChar* b) { return equal(a.m_string.impl(), b); }
    190194
    191     template <typename T> static Ref<StringImpl> add(VM&, const T*, int length);
    192     static Ref<StringImpl> add8(VM&, const UChar*, int length);
     195    template <typename T> static Ref<AtomStringImpl> add(VM&, const T*, int length);
     196    static Ref<AtomStringImpl> add8(VM&, const UChar*, int length);
    193197    template <typename T> ALWAYS_INLINE static constexpr bool canUseSingleCharacterString(T);
    194198
    195     static Ref<StringImpl> add(VM&, StringImpl*);
     199    static Ref<AtomStringImpl> add(VM&, StringImpl*);
    196200
    197201#ifndef NDEBUG
    … …  
    214218
    215219template <typename T>
    216 Ref<StringImpl> Identifier::add(VM& vm, const T* s, int length)
     220Ref<AtomStringImpl> Identifier::add(VM& vm, const T* s, int length)
    217221{
    218222    if (length == 1) {
    … …  
    222226    }
    223227    if (!length)
    224         return *StringImpl::empty();
     228        return *static_cast<AtomStringImpl*>(StringImpl::empty());
    225229
    226230    return *AtomStringImpl::add(s, length);

  • trunk/Source/JavaScriptCore/runtime/IdentifierInlines.h

    r249175 r278971  
    5656}
    5757
    58 inline Ref<StringImpl> Identifier::add(VM& vm, StringImpl* r)
     58inline Ref<AtomStringImpl> Identifier::add(VM& vm, StringImpl* r)
    5959{
    6060#ifndef NDEBUG
    … …  
    112112}
    113113
     114inline Identifier Identifier::fromString(VM& vm, Ref<AtomStringImpl>&& atomStringImpl)
     115{
     116    return Identifier(vm, WTFMove(atomStringImpl));
     117}
     118
    114119inline Identifier Identifier::fromString(VM& vm, const AtomString& atomString)
    115120{

  • trunk/Source/JavaScriptCore/runtime/LiteralParser.cpp

    r278921 r278971  
    3737#include <wtf/text/StringConcatenate.h>
    3838
     39#include "KeywordLookup.h"
     40
    3941namespace JSC {
     42
     43template<typename CharType>
     44ALWAYS_INLINE bool compare3Chars(const CharType* source, CharType c0, CharType c1, CharType c2)
     45{
     46    if constexpr (sizeof(CharType) == 1)
     47        return COMPARE_3CHARS(source, c0, c1, c2);
     48    else
     49        return COMPARE_3UCHARS(source, c0, c1, c2);
     50}
     51
     52template<typename CharType>
     53ALWAYS_INLINE bool compare4Chars(const CharType* source, CharType c0, CharType c1, CharType c2, CharType c3)
     54{
     55    if constexpr (sizeof(CharType) == 1)
     56        return COMPARE_4CHARS(source, c0, c1, c2, c3);
     57    else
     58        return COMPARE_4UCHARS(source, c0, c1, c2, c3);
     59}
    4060
    4161template <typename CharType>
    … …  
    142162    if (length == 1) {
    143163        if constexpr (sizeof(LiteralCharType) == 1)
    144             return Identifier::fromString(vm, vm.smallStrings.singleCharacterStringRep(firstCharacter).ptr());
     164            return Identifier::fromString(vm, vm.smallStrings.singleCharacterStringRep(firstCharacter));
    145165        if (firstCharacter <= maxSingleCharacterString)
    146             return Identifier::fromString(vm, vm.smallStrings.singleCharacterStringRep(firstCharacter).ptr());
     166            return Identifier::fromString(vm, vm.smallStrings.singleCharacterStringRep(firstCharacter));
    147167        return Identifier::fromString(vm, characters, length);
    148168    }
    … …  
    150170    if (firstCharacter >= maximumCachableCharacter)
    151171        return Identifier::fromString(vm, characters, length);
    152     if (!m_recentIdentifiers[firstCharacter].isNull() && Identifier::equal(m_recentIdentifiers[firstCharacter].impl(), characters, length))
    153         return m_recentIdentifiers[firstCharacter];
    154     m_recentIdentifiers[firstCharacter] = Identifier::fromString(vm, characters, length);
    155     return m_recentIdentifiers[firstCharacter];
     172
     173    // 0 means no entry since m_recentIdentifiersIndex is zero-filled initially.
     174    uint8_t indexPlusOne = m_recentIdentifiersIndex[firstCharacter];
     175    if (indexPlusOne) {
     176        uint8_t index = indexPlusOne - 1;
     177        auto& ident = m_recentIdentifiers[index];
     178        if (Identifier::equal(ident.impl(), characters, length))
     179            return ident;
     180        auto result = Identifier::fromString(vm, characters, length);
     181        m_recentIdentifiers[index] = result;
     182        return result;
     183    }
     184
     185    auto result = Identifier::fromString(vm, characters, length);
     186    m_recentIdentifiers.uncheckedAppend(result);
     187    indexPlusOne = m_recentIdentifiers.size();
     188    m_recentIdentifiersIndex[firstCharacter] = indexPlusOne;
     189    return result;
    156190}
    157191
    … …  
    709743            switch (character) {
    710744            case 't':
    711                 if (m_end - m_ptr >= 4 && m_ptr[1] == 'r' && m_ptr[2] == 'u' && m_ptr[3] == 'e') {
     745                if (m_end - m_ptr >= 4 && compare3Chars<CharType>(m_ptr + 1, 'r', 'u', 'e')) {
    712746                    m_ptr += 4;
    713747                    token.type = TokTrue;
    … …  
    717751                break;
    718752            case 'f':
    719                 if (m_end - m_ptr >= 5 && m_ptr[1] == 'a' && m_ptr[2] == 'l' && m_ptr[3] == 's' && m_ptr[4] == 'e') {
     753                if (m_end - m_ptr >= 5 && compare4Chars<CharType>(m_ptr + 1, 'a', 'l', 's', 'e')) {
    720754                    m_ptr += 5;
    721755                    token.type = TokFalse;
    … …  
    725759                break;
    726760            case 'n':
    727                 if (m_end - m_ptr >= 4 && m_ptr[1] == 'u' && m_ptr[2] == 'l' && m_ptr[3] == 'l') {
     761                if (m_end - m_ptr >= 4 && compare3Chars<CharType>(m_ptr + 1, 'u', 'l', 'l')) {
    728762                    m_ptr += 4;
    729763                    token.type = TokNull;

  • trunk/Source/JavaScriptCore/runtime/LiteralParser.h

    r278921 r278971  
    176176       
    177177    private:
    178         String m_lexErrorMessage;
    179178        TokenType lex(LiteralParserToken<CharType>&);
    180179        ALWAYS_INLINE TokenType lexIdentifier(LiteralParserToken<CharType>&);
    … …  
    182181        TokenType lexStringSlow(LiteralParserToken<CharType>&, const CharType* runStart, CharType terminator);
    183182        ALWAYS_INLINE TokenType lexNumber(LiteralParserToken<CharType>&);
     183
     184        String m_lexErrorMessage;
    184185        LiteralParserToken<CharType> m_currentToken;
    185186        ParserMode m_mode;
    … …  
    195196    JSValue parse(ParserState);
    196197
     198    template<typename LiteralCharType>
     199    ALWAYS_INLINE Identifier makeIdentifier(const LiteralCharType* characters, size_t length);
     200
    197201    JSGlobalObject* m_globalObject;
    198202    CodeBlock* m_nullOrCodeBlock;
    … …  
    201205    String m_parseErrorMessage;
    202206    static constexpr unsigned maximumCachableCharacter = 128;
    203     std::array<Identifier, maximumCachableCharacter> m_recentIdentifiers;
    204     template<typename LiteralCharType>
    205     ALWAYS_INLINE Identifier makeIdentifier(const LiteralCharType* characters, size_t length);
     207    std::array<uint8_t, maximumCachableCharacter> m_recentIdentifiersIndex { };
     208    Vector<Identifier, maximumCachableCharacter> m_recentIdentifiers;
    206209};
    207210
Note: See TracChangeset for help on using the changeset viewer.