Changeset 128002 in webkit


Ignore:
Timestamp:
Sep 9, 2012 3:26:52 PM (12 years ago)
Author:
kling@webkit.org
Message:

EventListenerMap: Use Vector instead of HashMap as backend.
<http://webkit.org/b/77982>

Reviewed by Geoff Garen.

Source/WebCore:

Refactor EventListenerMap to store pair<AtomicString, EventListenerVector> in a Vector
instead of using key/value HashMap stores. This is much more space efficient and actually
faster since we were spending more time/effort managing the hash map than it costs us
to iterate over and compare a couple of pointers. (It's very rare to have more than
4 different event types registered in a single EventListenerMap.)

This gets rid of the slightly hacky optimization for nodes with listeners of a single type,
reducing the complexity of EventListenerMap greatly.

~1.1MB progression on Membuster. Also strong (20+ MB on larger patches) savings on WebKit
bugzilla review pages, though they don't necessarily represent a common usecase.

  • dom/EventListenerMap.cpp:

(WebCore::EventListenerMap::contains):
(WebCore::EventListenerMap::clear):
(WebCore::EventListenerMap::eventTypes):
(WebCore::EventListenerMap::add):
(WebCore::EventListenerMap::remove):
(WebCore::EventListenerMap::find):
(WebCore::EventListenerMap::removeFirstEventListenerCreatedFromMarkup):
(WebCore::EventListenerMap::copyEventListenersNotCreatedFromMarkupToTarget):
(WebCore::EventListenerIterator::EventListenerIterator):
(WebCore::EventListenerIterator::nextListener):

  • dom/EventListenerMap.h:

(WebCore::EventListenerMap::isEmpty):
(WebCore::EventListenerMapEntry::EventListenerMapEntry):
(EventListenerMapEntry):
(EventListenerMap):
(EventListenerIterator):

LayoutTests:

Rebaseline inspector test whose output depended on the internal ordering of event
listeners (changed as listeners are no longer stored in an unordered HashMap.)

  • inspector/console/command-line-api-getEventListeners-expected.txt:
Location:
trunk
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • trunk/LayoutTests/ChangeLog

    r127993 r128002  
     12012-09-09  Andreas Kling  <kling@webkit.org>
     2
     3        EventListenerMap: Use Vector instead of HashMap as backend.
     4        <http://webkit.org/b/77982>
     5
     6        Reviewed by Geoff Garen.
     7
     8        Rebaseline inspector test whose output depended on the internal ordering of event
     9        listeners (changed as listeners are no longer stored in an unordered HashMap.)
     10
     11        * inspector/console/command-line-api-getEventListeners-expected.txt:
     12
    1132012-09-09  Dominic Mazzoni  <dmazzoni@google.com>
    214
  • trunk/LayoutTests/inspector/console/command-line-api-getEventListeners-expected.txt

    r125654 r128002  
    2121    }
    2222}
     23mousedown: {
     24    0: {
     25        listener: function listener2() { }
     26        useCapture: true
     27    }
     28}
    2329keydown: {
    2430    0: {
     
    2733    }
    2834}
    29 mousedown: {
     35- attribute event listeners -
     36click: {
    3037    0: {
    31         listener: function listener2() { }
    32         useCapture: true
     38        listener: function onclick(event) { alert(1) }
     39        useCapture: false
    3340    }
    3441}
    35 - attribute event listeners -
    3642mouseover: {
    3743    0: {
    3844        listener: function onmouseover(event) { listener2() }
    39         useCapture: false
    40     }
    41 }
    42 click: {
    43     0: {
    44         listener: function onclick(event) { alert(1) }
    4545        useCapture: false
    4646    }
  • trunk/Source/WebCore/ChangeLog

    r127998 r128002  
     12012-09-09  Andreas Kling  <kling@webkit.org>
     2
     3        EventListenerMap: Use Vector instead of HashMap as backend.
     4        <http://webkit.org/b/77982>
     5
     6        Reviewed by Geoff Garen.
     7
     8        Refactor EventListenerMap to store pair<AtomicString, EventListenerVector> in a Vector
     9        instead of using key/value HashMap stores. This is much more space efficient and actually
     10        faster since we were spending more time/effort managing the hash map than it costs us
     11        to iterate over and compare a couple of pointers. (It's very rare to have more than
     12        4 different event types registered in a single EventListenerMap.)
     13
     14        This gets rid of the slightly hacky optimization for nodes with listeners of a single type,
     15        reducing the complexity of EventListenerMap greatly.
     16
     17        ~1.1MB progression on Membuster. Also strong (20+ MB on larger patches) savings on WebKit
     18        bugzilla review pages, though they don't necessarily represent a common usecase.
     19
     20        * dom/EventListenerMap.cpp:
     21        (WebCore::EventListenerMap::contains):
     22        (WebCore::EventListenerMap::clear):
     23        (WebCore::EventListenerMap::eventTypes):
     24        (WebCore::EventListenerMap::add):
     25        (WebCore::EventListenerMap::remove):
     26        (WebCore::EventListenerMap::find):
     27        (WebCore::EventListenerMap::removeFirstEventListenerCreatedFromMarkup):
     28        (WebCore::EventListenerMap::copyEventListenersNotCreatedFromMarkupToTarget):
     29        (WebCore::EventListenerIterator::EventListenerIterator):
     30        (WebCore::EventListenerIterator::nextListener):
     31        * dom/EventListenerMap.h:
     32        (WebCore::EventListenerMap::isEmpty):
     33        (WebCore::EventListenerMapEntry::EventListenerMapEntry):
     34        (EventListenerMapEntry):
     35        (EventListenerMap):
     36        (EventListenerIterator):
     37
    1382012-09-09  Lucas Forschler  <lforschler@apple.com>
    239
  • trunk/Source/WebCore/dom/EventListenerMap.cpp

    r127752 r128002  
    7070}
    7171
    72 bool EventListenerMap::isEmpty() const
    73 {
    74     if (m_hashMap)
    75         return m_hashMap->isEmpty();
    76     return !m_singleEventListenerVector;
    77 }
    78 
    7972bool EventListenerMap::contains(const AtomicString& eventType) const
    8073{
    81     if (m_hashMap)
    82         return m_hashMap->contains(eventType);
    83     return m_singleEventListenerType == eventType;
     74    for (unsigned i = 0; i < m_entries.size(); ++i) {
     75        if (m_entries[i].first == eventType)
     76            return true;
     77    }
     78    return false;
    8479}
    8580
     
    8883    assertNoActiveIterators();
    8984
    90     if (m_hashMap)
    91         m_hashMap.clear();
    92     else {
    93         m_singleEventListenerType = nullAtom;
    94         m_singleEventListenerVector.clear();
    95     }
     85    m_entries.clear();
    9686}
    9787
     
    9989{
    10090    Vector<AtomicString> types;
    101 
    102     if (m_hashMap) {
    103         EventListenerHashMap::iterator it = m_hashMap->begin();
    104         EventListenerHashMap::iterator end = m_hashMap->end();
    105         for (; it != end; ++it)
    106             types.append(it->first);
    107     } else if (m_singleEventListenerVector)
    108         types.append(m_singleEventListenerType);
     91    types.reserveInitialCapacity(m_entries.size());
     92
     93    for (unsigned i = 0; i < m_entries.size(); ++i)
     94        types.uncheckedAppend(m_entries[i].first);
    10995
    11096    return types;
     
    126112    assertNoActiveIterators();
    127113
    128     if (m_singleEventListenerVector && m_singleEventListenerType != eventType) {
    129         // We already have a single (first) listener vector, and this event is not
    130         // of that type, so create the hash map and move the first listener vector there.
    131         ASSERT(!m_hashMap);
    132         m_hashMap = adoptPtr(new EventListenerHashMap);
    133         m_hashMap->add(m_singleEventListenerType, m_singleEventListenerVector.release());
    134         m_singleEventListenerType = nullAtom;
    135     }
    136 
    137     if (m_hashMap) {
    138         EventListenerHashMap::AddResult result = m_hashMap->add(eventType, nullptr);
    139         if (result.isNewEntry)
    140             result.iterator->second = adoptPtr(new EventListenerVector);
    141 
    142         return addListenerToVector(result.iterator->second.get(), listener, useCapture);
    143     }
    144 
    145     if (!m_singleEventListenerVector) {
    146         m_singleEventListenerType = eventType;
    147         m_singleEventListenerVector = adoptPtr(new EventListenerVector);
    148     }
    149 
    150     ASSERT(m_singleEventListenerType == eventType);
    151     return addListenerToVector(m_singleEventListenerVector.get(), listener, useCapture);
     114    for (unsigned i = 0; i < m_entries.size(); ++i) {
     115        if (m_entries[i].first == eventType)
     116            return addListenerToVector(m_entries[i].second.get(), listener, useCapture);
     117    }
     118
     119    m_entries.append(std::make_pair(eventType, adoptPtr(new EventListenerVector)));
     120    return addListenerToVector(m_entries.last().second.get(), listener, useCapture);
    152121}
    153122
     
    166135    assertNoActiveIterators();
    167136
    168     if (!m_hashMap) {
    169         if (m_singleEventListenerType != eventType)
    170             return false;
    171         bool wasRemoved = removeListenerFromVector(m_singleEventListenerVector.get(), listener, useCapture, indexOfRemovedListener);
    172         if (m_singleEventListenerVector->isEmpty()) {
    173             m_singleEventListenerVector.clear();
    174             m_singleEventListenerType = nullAtom;
     137    for (unsigned i = 0; i < m_entries.size(); ++i) {
     138        if (m_entries[i].first == eventType) {
     139            bool wasRemoved = removeListenerFromVector(m_entries[i].second.get(), listener, useCapture, indexOfRemovedListener);
     140            if (m_entries[i].second->isEmpty())
     141                m_entries.remove(i);
     142            return wasRemoved;
    175143        }
    176         return wasRemoved;
    177     }
    178 
    179     EventListenerHashMap::iterator it = m_hashMap->find(eventType);
    180     if (it == m_hashMap->end())
    181         return false;
    182 
    183     bool wasRemoved = removeListenerFromVector(it->second.get(), listener, useCapture, indexOfRemovedListener);
    184     if (it->second->isEmpty())
    185         m_hashMap->remove(it);
    186     return wasRemoved;
     144    }
     145
     146    return false;
    187147}
    188148
     
    191151    assertNoActiveIterators();
    192152
    193     if (m_hashMap) {
    194         EventListenerHashMap::iterator it = m_hashMap->find(eventType);
    195         if (it == m_hashMap->end())
    196             return 0;
    197         return it->second.get();
    198     }
    199 
    200     if (m_singleEventListenerType == eventType)
    201         return m_singleEventListenerVector.get();
     153    for (unsigned i = 0; i < m_entries.size(); ++i) {
     154        if (m_entries[i].first == eventType)
     155            return m_entries[i].second.get();
     156    }
    202157
    203158    return 0;
     
    225180    assertNoActiveIterators();
    226181
    227     if (m_hashMap) {
    228         EventListenerHashMap::iterator result = m_hashMap->find(eventType);
    229         ASSERT(result != m_hashMap->end());
    230 
    231         EventListenerVector* listenerVector = result->second.get();
    232         ASSERT(listenerVector);
    233 
    234         removeFirstListenerCreatedFromMarkup(listenerVector);
    235 
    236         if (listenerVector->isEmpty())
    237             m_hashMap->remove(result);
    238 
    239         return;
    240     }
    241 
    242     ASSERT(m_singleEventListenerVector);
    243     ASSERT(m_singleEventListenerType == eventType);
    244 
    245     removeFirstListenerCreatedFromMarkup(m_singleEventListenerVector.get());
    246     if (m_singleEventListenerVector->isEmpty()) {
    247         m_singleEventListenerVector.clear();
    248         m_singleEventListenerType = nullAtom;
     182    for (unsigned i = 0; i < m_entries.size(); ++i) {
     183        if (m_entries[i].first == eventType) {
     184            removeFirstListenerCreatedFromMarkup(m_entries[i].second.get());
     185            if (m_entries[i].second->isEmpty())
     186                m_entries.remove(i);
     187            return;
     188        }
    249189    }
    250190}
     
    264204    assertNoActiveIterators();
    265205
    266     if (m_hashMap) {
    267         EventListenerHashMap::iterator end = m_hashMap->end();
    268         for (EventListenerHashMap::iterator it = m_hashMap->begin(); it != end; ++it)
    269             copyListenersNotCreatedFromMarkupToTarget(it->first, it->second.get(), target);
    270         return;
    271     }
    272 
    273     if (!m_singleEventListenerVector)
    274         return;
    275 
    276     copyListenersNotCreatedFromMarkupToTarget(m_singleEventListenerType, m_singleEventListenerVector.get(), target);
     206    for (unsigned i = 0; i < m_entries.size(); ++i)
     207        copyListenersNotCreatedFromMarkupToTarget(m_entries[i].first, m_entries[i].second.get(), target);
    277208}
    278209
     
    281212EventListenerIterator::EventListenerIterator()
    282213    : m_map(0)
     214    , m_entryIndex(0)
    283215    , m_index(0)
    284216{
     
    287219EventListenerIterator::EventListenerIterator(EventTarget* target)
    288220    : m_map(0)
     221    , m_entryIndex(0)
    289222    , m_index(0)
    290223{
     
    303236    }
    304237#endif
    305 
    306     if (m_map->m_hashMap) {
    307         m_mapIterator = m_map->m_hashMap->begin();
    308         m_mapEnd = m_map->m_hashMap->end();
    309     }
    310238}
    311239
     
    325253        return 0;
    326254
    327     if (m_map->m_hashMap) {
    328         for (; m_mapIterator != m_mapEnd; ++m_mapIterator) {
    329             EventListenerVector& listeners = *m_mapIterator->second;
    330             if (m_index < listeners.size())
    331                 return listeners[m_index++].listener.get();
    332             m_index = 0;
    333         }
    334         return 0;
    335     }
    336 
    337     if (!m_map->m_singleEventListenerVector)
    338         return 0;
    339     EventListenerVector& listeners = *m_map->m_singleEventListenerVector;
    340     if (m_index < listeners.size())
    341         return listeners[m_index++].listener.get();
     255    for (; m_entryIndex < m_map->m_entries.size(); ++m_entryIndex) {
     256        EventListenerVector& listeners = *m_map->m_entries[m_entryIndex].second;
     257        if (m_index < listeners.size())
     258            return listeners[m_index++].listener.get();
     259        m_index = 0;
     260    }
     261
    342262    return 0;
    343263}
  • trunk/Source/WebCore/dom/EventListenerMap.h

    r103556 r128002  
    33 *           (C) 1999 Antti Koivisto (koivisto@kde.org)
    44 *           (C) 2001 Dirk Mueller (mueller@kde.org)
    5  * Copyright (C) 2004, 2005, 2006, 2007 Apple Inc. All rights reserved.
     5 * Copyright (C) 2004, 2005, 2006, 2007, 2012 Apple Inc. All rights reserved.
    66 * Copyright (C) 2006 Alexey Proskuryakov (ap@webkit.org)
    77 *           (C) 2007, 2008 Nikolas Zimmermann <zimmermann@kde.org>
     
    3636#include "RegisteredEventListener.h"
    3737#include <wtf/Forward.h>
    38 #include <wtf/HashMap.h>
     38#include <wtf/PassOwnPtr.h>
    3939#include <wtf/text/AtomicStringHash.h>
    4040
     
    4949    EventListenerMap();
    5050
    51     bool isEmpty() const;
     51    bool isEmpty() const { return m_entries.isEmpty(); }
    5252    bool contains(const AtomicString& eventType) const;
    5353
     
    6868    void assertNoActiveIterators();
    6969
    70     struct EventListenerHashMapTraits : HashTraits<WTF::AtomicString> {
    71         static const int minimumTableSize = 32;
    72     };
    73     typedef HashMap<AtomicString, OwnPtr<EventListenerVector>, AtomicStringHash, EventListenerHashMapTraits> EventListenerHashMap;
    74 
    75     OwnPtr<EventListenerHashMap> m_hashMap;
    76 
    77     AtomicString m_singleEventListenerType;
    78     OwnPtr<EventListenerVector> m_singleEventListenerVector;
     70    Vector<std::pair<AtomicString, OwnPtr<EventListenerVector> >, 2> m_entries;
    7971
    8072#ifndef NDEBUG
     
    9688private:
    9789    EventListenerMap* m_map;
    98     EventListenerMap::EventListenerHashMap::iterator m_mapIterator;
    99     EventListenerMap::EventListenerHashMap::iterator m_mapEnd;
     90    unsigned m_entryIndex;
    10091    unsigned m_index;
    10192};
Note: See TracChangeset for help on using the changeset viewer.