Changeset 244745 in webkit


Ignore:
Timestamp:
Apr 29, 2019 12:21:02 PM (5 years ago)
Author:
ysuzuki@apple.com
Message:

JITStubRoutineSet wastes 180KB of HashTable capacity on can.com
​https://bugs.webkit.org/show_bug.cgi?id=186732

Reviewed by Saam Barati.

Source/JavaScriptCore:

Our current mechanism of JITStubRoutineSet consumes more memory than needed. Basically we have HashMap<uintptr_t, StubRoutine*> and register
each executable address by 16 byte to this entry. So if your StubRoutine has 128bytes, it just adds 8 entries to this hash table.
In Gmail, we see a ~2MB table size.

Instead, this patch uses Vector<pair<uintptr_t, StubRoutine*>> and performs binary search onto this sorted vector. Before conservative
scanning, we sort this vector. And doing binary search with the sorted vector to find executing stub routines from the conservative roots.
This vector includes uintptr_t startAddress to make binary searching fast.

Large amount of conservative scan should be filtered by range check, so I think binary search here is OK, but we can decide based on what the
performance bots say.

  • heap/Heap.cpp:

(JSC::Heap::addCoreConstraints):

  • heap/JITStubRoutineSet.cpp:

(JSC::JITStubRoutineSet::~JITStubRoutineSet):
(JSC::JITStubRoutineSet::add):
(JSC::JITStubRoutineSet::prepareForConservativeScan):
(JSC::JITStubRoutineSet::clearMarks):
(JSC::JITStubRoutineSet::markSlow):
(JSC::JITStubRoutineSet::deleteUnmarkedJettisonedStubRoutines):
(JSC::JITStubRoutineSet::traceMarkedStubRoutines):

  • heap/JITStubRoutineSet.h:

(JSC::JITStubRoutineSet::mark):
(JSC::JITStubRoutineSet::prepareForConservativeScan):
(JSC::JITStubRoutineSet::size const): Deleted.
(JSC::JITStubRoutineSet::at const): Deleted.

Source/WTF:

  • wtf/Range.h:

(WTF::Range::contains const):

Location:
trunk/Source
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/JavaScriptCore/ChangeLog

    r244741 r244745  
     12019-04-29  Yusuke Suzuki  <ysuzuki@apple.com>
     2
     3        JITStubRoutineSet wastes 180KB of HashTable capacity on can.com
     4        https://bugs.webkit.org/show_bug.cgi?id=186732
     5
     6        Reviewed by Saam Barati.
     7
     8        Our current mechanism of JITStubRoutineSet consumes more memory than needed. Basically we have HashMap<uintptr_t, StubRoutine*> and register
     9        each executable address by 16 byte to this entry. So if your StubRoutine has 128bytes, it just adds 8 entries to this hash table.
     10        In Gmail, we see a ~2MB table size.
     11
     12        Instead, this patch uses Vector<pair<uintptr_t, StubRoutine*>> and performs binary search onto this sorted vector. Before conservative
     13        scanning, we sort this vector. And doing binary search with the sorted vector to find executing stub routines from the conservative roots.
     14        This vector includes uintptr_t startAddress to make binary searching fast.
     15
     16        Large amount of conservative scan should be filtered by range check, so I think binary search here is OK, but we can decide based on what the
     17        performance bots say.
     18
     19        * heap/Heap.cpp:
     20        (JSC::Heap::addCoreConstraints):
     21        * heap/JITStubRoutineSet.cpp:
     22        (JSC::JITStubRoutineSet::~JITStubRoutineSet):
     23        (JSC::JITStubRoutineSet::add):
     24        (JSC::JITStubRoutineSet::prepareForConservativeScan):
     25        (JSC::JITStubRoutineSet::clearMarks):
     26        (JSC::JITStubRoutineSet::markSlow):
     27        (JSC::JITStubRoutineSet::deleteUnmarkedJettisonedStubRoutines):
     28        (JSC::JITStubRoutineSet::traceMarkedStubRoutines):
     29        * heap/JITStubRoutineSet.h:
     30        (JSC::JITStubRoutineSet::mark):
     31        (JSC::JITStubRoutineSet::prepareForConservativeScan):
     32        (JSC::JITStubRoutineSet::size const): Deleted.
     33        (JSC::JITStubRoutineSet::at const): Deleted.
     34
    1352019-04-29  Basuke Suzuki  <Basuke.Suzuki@sony.com>
    236

  • trunk/Source/JavaScriptCore/heap/Heap.cpp

    r243560 r244745  
    26882688            TimingScope preConvergenceTimingScope(*this, "Constraint: conservative scan");
    26892689            m_objectSpace.prepareForConservativeScan();
     2690            m_jitStubRoutines->prepareForConservativeScan();
    26902691
    26912692            {

  • trunk/Source/JavaScriptCore/heap/JITStubRoutineSet.cpp

    r164229 r244745  
    3838JITStubRoutineSet::~JITStubRoutineSet()
    3939{
    40     for (size_t i = m_listOfRoutines.size(); i--;) {
    41         GCAwareJITStubRoutine* routine = m_listOfRoutines[i];
    42        
     40    for (auto& entry : m_routines) {
     41        GCAwareJITStubRoutine* routine = entry.routine;
    4342        routine->m_mayBeExecuting = false;
    4443       
    … …  
    5857    ASSERT(!routine->m_isJettisoned);
    5958   
    60     m_listOfRoutines.append(routine);
    61    
    62     uintptr_t start = routine->startAddress();
    63     uintptr_t end = routine->endAddress();
    64     uintptr_t step = JITStubRoutine::addressStep();
    65     for (uintptr_t iter = start; iter < end; iter += step) {
    66         ASSERT(m_addressToRoutineMap.find(iter) == m_addressToRoutineMap.end());
    67         m_addressToRoutineMap.add(iter, routine);
     59    m_routines.append(Routine {
     60        routine->startAddress(),
     61        routine
     62    });
     63}
     64
     65void JITStubRoutineSet::prepareForConservativeScan()
     66{
     67    if (m_routines.isEmpty()) {
     68        m_range = Range<uintptr_t> { 0, 0 };
     69        return;
    6870    }
     71    std::sort(
     72        m_routines.begin(), m_routines.end(),
     73        [&] (const Routine& a, const Routine& b) {
     74            return a.startAddress < b.startAddress;
     75        });
     76    m_range = Range<uintptr_t> {
     77        m_routines.first().startAddress,
     78        m_routines.last().routine->endAddress()
     79    };
    6980}
    7081
    7182void JITStubRoutineSet::clearMarks()
    7283{
    73     for (size_t i = m_listOfRoutines.size(); i--;)
    74         m_listOfRoutines[i]->m_mayBeExecuting = false;
     84    for (auto& entry : m_routines)
     85        entry.routine->m_mayBeExecuting = false;
    7586}
    7687
    7788void JITStubRoutineSet::markSlow(uintptr_t address)
    7889{
    79     HashMap<uintptr_t, GCAwareJITStubRoutine*>::iterator iter =
    80         m_addressToRoutineMap.find(address & ~(JITStubRoutine::addressStep() - 1));
    81    
    82     if (iter == m_addressToRoutineMap.end())
    83         return;
    84    
    85     iter->value->m_mayBeExecuting = true;
     90    ASSERT(isJITPC(bitwise_cast<void*>(address)));
     91    ASSERT(!m_routines.isEmpty());
     92
     93    Routine* result = approximateBinarySearch<Routine>(
     94        m_routines.begin(), m_routines.size(), address,
     95        [] (const Routine* routine) -> uintptr_t { return routine->startAddress; });
     96    if (result) {
     97        auto markIfContained = [&] (const Routine& routine, uintptr_t address) {
     98            if (routine.startAddress <= address && address < routine.routine->endAddress()) {
     99                routine.routine->m_mayBeExecuting = true;
     100                return true;
     101            }
     102            return false;
     103        };
     104
     105        if (result > m_routines.begin()) {
     106            if (markIfContained(result[-1], address))
     107                return;
     108        }
     109        if (markIfContained(result[0], address))
     110            return;
     111        if (result + 1 < m_routines.end()) {
     112            if (markIfContained(result[1], address))
     113                return;
     114        }
     115    }
    86116}
    87117
    88118void JITStubRoutineSet::deleteUnmarkedJettisonedStubRoutines()
    89119{
    90     for (size_t i = 0; i < m_listOfRoutines.size(); i++) {
    91         GCAwareJITStubRoutine* routine = m_listOfRoutines[i];
    92         if (!routine->m_isJettisoned || routine->m_mayBeExecuting)
     120    unsigned srcIndex = 0;
     121    unsigned dstIndex = srcIndex;
     122    while (srcIndex < m_routines.size()) {
     123        Routine routine = m_routines[srcIndex++];
     124        if (!routine.routine->m_isJettisoned || routine.routine->m_mayBeExecuting) {
     125            m_routines[dstIndex++] = routine;
    93126            continue;
    94        
    95         uintptr_t start = routine->startAddress();
    96         uintptr_t end = routine->endAddress();
    97         uintptr_t step = JITStubRoutine::addressStep();
    98         for (uintptr_t iter = start; iter < end; iter += step) {
    99             ASSERT(m_addressToRoutineMap.find(iter) != m_addressToRoutineMap.end());
    100             ASSERT(m_addressToRoutineMap.find(iter)->value == routine);
    101             m_addressToRoutineMap.remove(iter);
    102127        }
    103        
    104         routine->deleteFromGC();
    105        
    106         m_listOfRoutines[i] = m_listOfRoutines.last();
    107         m_listOfRoutines.removeLast();
    108         i--;
     128        routine.routine->deleteFromGC();
    109129    }
     130    m_routines.shrink(dstIndex);
    110131}
    111132
    112133void JITStubRoutineSet::traceMarkedStubRoutines(SlotVisitor& visitor)
    113134{
    114     for (size_t i = m_listOfRoutines.size(); i--;) {
    115         GCAwareJITStubRoutine* routine = m_listOfRoutines[i];
     135    for (auto& entry : m_routines) {
     136        GCAwareJITStubRoutine* routine = entry.routine;
    116137        if (!routine->m_mayBeExecuting)
    117138            continue;

  • trunk/Source/JavaScriptCore/heap/JITStubRoutineSet.h

    r230129 r244745  
    2929#include <wtf/FastMalloc.h>
    3030#include <wtf/HashMap.h>
     31#include <wtf/Range.h>
    3132#include <wtf/Vector.h>
    3233
    … …  
    5354    {
    5455        uintptr_t address = removeCodePtrTag<uintptr_t>(candidateAddress);
    55         if (!JITStubRoutine::passesFilter(address))
     56        if (!m_range.contains(address))
    5657            return;
    57        
    5858        markSlow(address);
    5959    }
     60
     61    void prepareForConservativeScan();
    6062   
    6163    void deleteUnmarkedJettisonedStubRoutines();
    … …  
    6365    void traceMarkedStubRoutines(SlotVisitor&);
    6466   
    65     unsigned size() const { return m_listOfRoutines.size(); }
    66     GCAwareJITStubRoutine* at(unsigned i) const { return m_listOfRoutines[i]; }
    67    
    6867private:
    6968    void markSlow(uintptr_t address);
    7069   
    71     HashMap<uintptr_t, GCAwareJITStubRoutine*> m_addressToRoutineMap;
    72     Vector<GCAwareJITStubRoutine*> m_listOfRoutines;
     70    struct Routine {
     71        uintptr_t startAddress;
     72        GCAwareJITStubRoutine* routine;
     73    };
     74    Vector<Routine> m_routines;
     75    Range<uintptr_t> m_range { 0, 0 };
    7376};
    7477
    … …  
    8689    void clearMarks() { }
    8790    void mark(void*) { }
     91    void prepareForConservativeScan() { }
    8892    void deleteUnmarkedJettisonedStubRoutines() { }
    8993    void traceMarkedStubRoutines(SlotVisitor&) { }

  • trunk/Source/WTF/ChangeLog

    r244741 r244745  
     12019-04-29  Yusuke Suzuki  <ysuzuki@apple.com>
     2
     3        JITStubRoutineSet wastes 180KB of HashTable capacity on can.com
     4        https://bugs.webkit.org/show_bug.cgi?id=186732
     5
     6        Reviewed by Saam Barati.
     7
     8        * wtf/Range.h:
     9        (WTF::Range::contains const):
     10
    1112019-04-29  Basuke Suzuki  <Basuke.Suzuki@sony.com>
    212

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

    r215565 r244745  
    110110    }
    111111
     112    bool contains(Type point) const
     113    {
     114        return m_begin <= point && point < m_end;
     115    }
     116
    112117    void dump(PrintStream& out) const
    113118    {
Note: See TracChangeset for help on using the changeset viewer.