Changeset 2748 in webkit for trunk/JavaScriptCore


Ignore:
Timestamp:
Nov 18, 2002, 10:20:58 PM (23 years ago)
Author:
mjs
Message:

Change List to completely avoid going through the GC
allocator. 3.6% performance improvement on JavaScript iBench.

  • kjs/internal.cpp: (InterpreterImp::mark): Don't mark the empty list.

For all the methods below I basically lifted the ListImp version
up to the List method with minor tweaks.

  • kjs/types.cpp: (ListIterator::ListIterator): (List::List): (List::operator=): (List::~List): (List::mark): (List::append): (List::prepend): (List::appendList): (List::prependList): (List::removeFirst): (List::removeLast): (List::remove): (List::clear): (List::clearInternal): (List::copy): (List::begin): (List::end): (List::isEmpty): (List::size): (List::at): (List::operator[]): (List::empty): (List::erase): (List::refAll): (List::derefAll): (List::swap): (List::globalClear):
  • kjs/types.h:
Location:
trunk/JavaScriptCore
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/JavaScriptCore/ChangeLog

    r2747 r2748  
     12002-11-18  Maciej Stachowiak  <[email protected]>
     2
     3        Change List to completely avoid going through the GC
     4        allocator. 3.6% performance improvement on JavaScript iBench.
     5       
     6        * kjs/internal.cpp:
     7        (InterpreterImp::mark): Don't mark the empty list.
     8
     9        For all the methods below I basically lifted the ListImp version
     10        up to the List method with minor tweaks.
     11       
     12        * kjs/types.cpp:
     13        (ListIterator::ListIterator):
     14        (List::List):
     15        (List::operator=):
     16        (List::~List):
     17        (List::mark):
     18        (List::append):
     19        (List::prepend):
     20        (List::appendList):
     21        (List::prependList):
     22        (List::removeFirst):
     23        (List::removeLast):
     24        (List::remove):
     25        (List::clear):
     26        (List::clearInternal):
     27        (List::copy):
     28        (List::begin):
     29        (List::end):
     30        (List::isEmpty):
     31        (List::size):
     32        (List::at):
     33        (List::operator[]):
     34        (List::empty):
     35        (List::erase):
     36        (List::refAll):
     37        (List::derefAll):
     38        (List::swap):
     39        (List::globalClear):
     40        * kjs/types.h:
     41
    1422002-11-18  Maciej Stachowiak  <[email protected]>
    243

  • trunk/JavaScriptCore/ChangeLog-2002-12-03

    r2747 r2748  
     12002-11-18  Maciej Stachowiak  <[email protected]>
     2
     3        Change List to completely avoid going through the GC
     4        allocator. 3.6% performance improvement on JavaScript iBench.
     5       
     6        * kjs/internal.cpp:
     7        (InterpreterImp::mark): Don't mark the empty list.
     8
     9        For all the methods below I basically lifted the ListImp version
     10        up to the List method with minor tweaks.
     11       
     12        * kjs/types.cpp:
     13        (ListIterator::ListIterator):
     14        (List::List):
     15        (List::operator=):
     16        (List::~List):
     17        (List::mark):
     18        (List::append):
     19        (List::prepend):
     20        (List::appendList):
     21        (List::prependList):
     22        (List::removeFirst):
     23        (List::removeLast):
     24        (List::remove):
     25        (List::clear):
     26        (List::clearInternal):
     27        (List::copy):
     28        (List::begin):
     29        (List::end):
     30        (List::isEmpty):
     31        (List::size):
     32        (List::at):
     33        (List::operator[]):
     34        (List::empty):
     35        (List::erase):
     36        (List::refAll):
     37        (List::derefAll):
     38        (List::swap):
     39        (List::globalClear):
     40        * kjs/types.h:
     41
    1422002-11-18  Maciej Stachowiak  <[email protected]>
    243

  • trunk/JavaScriptCore/ChangeLog-2003-10-25

    r2747 r2748  
     12002-11-18  Maciej Stachowiak  <[email protected]>
     2
     3        Change List to completely avoid going through the GC
     4        allocator. 3.6% performance improvement on JavaScript iBench.
     5       
     6        * kjs/internal.cpp:
     7        (InterpreterImp::mark): Don't mark the empty list.
     8
     9        For all the methods below I basically lifted the ListImp version
     10        up to the List method with minor tweaks.
     11       
     12        * kjs/types.cpp:
     13        (ListIterator::ListIterator):
     14        (List::List):
     15        (List::operator=):
     16        (List::~List):
     17        (List::mark):
     18        (List::append):
     19        (List::prepend):
     20        (List::appendList):
     21        (List::prependList):
     22        (List::removeFirst):
     23        (List::removeLast):
     24        (List::remove):
     25        (List::clear):
     26        (List::clearInternal):
     27        (List::copy):
     28        (List::begin):
     29        (List::end):
     30        (List::isEmpty):
     31        (List::size):
     32        (List::at):
     33        (List::operator[]):
     34        (List::empty):
     35        (List::erase):
     36        (List::refAll):
     37        (List::derefAll):
     38        (List::swap):
     39        (List::globalClear):
     40        * kjs/types.h:
     41
    1422002-11-18  Maciej Stachowiak  <[email protected]>
    243

  • trunk/JavaScriptCore/kjs/internal.cpp

    r2741 r2748  
    668668  if (BooleanImp::staticFalse && !BooleanImp::staticFalse->marked())
    669669    BooleanImp::staticFalse->mark();
    670   List::markEmptyList();
    671670  //fprintf( stderr, "InterpreterImp::mark this=%p global.imp()=%p\n", this, global.imp() );
    672671  if (global.imp())

  • trunk/JavaScriptCore/kjs/types.cpp

    r2747 r2748  
    4040
    4141namespace KJS {
    42   // ---------------------------------------------------------------------------
    43   //                            Internal type impls
    44   // ---------------------------------------------------------------------------
    45 
    46   /**
    47    * @internal
    48    */
     42
    4943  class ListNode {
    5044    friend class List;
    51     friend class ListImp;
    5245    friend class ListIterator;
    53     ListNode(Value val, ListNode *p, ListNode *n)
     46  protected:
     47    ListNode(const Value &val, ListNode *p, ListNode *n)
    5448      : member(val.imp()), prev(p), next(n) {};
    5549    ValueImp *member;
    … …  
    5751  };
    5852
    59   class ListImp : public ValueImp {
    60     friend class ListIterator;
     53  class ListHookNode : public ListNode {
    6154    friend class List;
    62     friend class InterpreterImp;
    63     friend class ObjectImp;
    64   private:
    65     ListImp();
    66     ~ListImp();
    67 
    68     Type type() const { return ListType; }
    69 
    70     virtual void mark();
    71 
    72     Value toPrimitive(ExecState *exec, Type preferred = UnspecifiedType) const;
    73     bool toBoolean(ExecState *exec) const;
    74     double toNumber(ExecState *exec) const;
    75     UString toString(ExecState *exec) const;
    76     Object toObject(ExecState *exec) const;
    77 
    78     void append(const Value& val);
    79     void prepend(const Value& val);
    80     void appendList(const List& lst);
    81     void prependList(const List& lst);
    82     void removeFirst();
    83     void removeLast();
    84     void remove(const Value &val);
    85     void clear();
    86     ListImp *copy() const;
    87     ListIterator begin() const { return ListIterator(hook->next); }
    88     ListIterator end() const { return ListIterator(hook); }
    89     //    bool isEmpty() const { return (hook->prev == hook); }
    90     bool isEmpty() const;
    91     int size() const;
    92     Value at(int i) const;
    93     Value operator[](int i) const { return at(i); }
    94     static ListImp* empty();
    95 
    96 #ifdef KJS_DEBUG_MEM
    97     static int count;
    98 #endif
    99   private:
    100     void erase(ListNode *n);
    101     ListNode *hook;
    102     static ListImp *emptyList;
     55   
     56    ListHookNode() : ListNode(Value(), NULL, NULL), refcount(1) { prev = this; next = this; }
     57    int refcount;
    10358  };
    104  
    105 }
     59  }
    10660
    10761
    10862// ------------------------------ ListIterator ---------------------------------
    10963
    110 //d  dont add   ListIterator();
    111 
    11264ListIterator::ListIterator(ListNode *n) : node(n)
    11365{
    … …  
    11567
    11668ListIterator::ListIterator(const List &l)
    117   : node(l.imp->hook->next)
     69  : node(l.hook->next)
    11870{
    11971}
    … …  
    170122
    171123List::List(bool needsMarking)
    172   : m_needsMarking(needsMarking)
    173 {
    174   imp = m_needsMarking ? ListImp::empty() : new ListImp();
    175   imp->setGcAllowed();
    176    
    177   if (!m_needsMarking) {
    178     imp->ref();
     124  : hook(new ListHookNode()),
     125    m_needsMarking(needsMarking)
     126{
     127  if (!m_needsMarking) {
     128    refAll();
    179129  }
    180130}
    … …  
    182132
    183133List::List(const List& l)
    184   : m_needsMarking(false)
     134  : hook(l.hook),
     135    m_needsMarking(false)
    185136{ 
    186   imp = l.imp;
    187 
    188   if (!m_needsMarking) {
    189     imp->ref();
    190   }
    191 }
    192 
    193 List::List(ListImp *p_imp)
    194   : m_needsMarking(false)
    195 {
    196   imp = p_imp;
    197   imp->setGcAllowed();
    198 
    199   if (!m_needsMarking) {
    200     imp->ref();
    201   }
    202 }
    203 
     137  hook->refcount++;
     138  if (!m_needsMarking) {
     139    refAll();
     140  }
     141}
    204142
    205143List& List::operator=(const List& l)
    206144{
    207   if (!m_needsMarking) {
    208     l.imp->ref();
    209     imp->deref();
    210   }
    211 
    212   imp = l.imp;
     145  List tmp(l);
     146
     147  tmp.swap(*this);
    213148
    214149  return *this;
    … …  
    218153{
    219154  if (!m_needsMarking) {
    220     imp->deref();
     155    derefAll();
     156  }
     157 
     158  hook->refcount--;
     159  if (hook->refcount == 0) {
     160    clearInternal();
     161    delete hook;
    221162  }
    222163}
    223164
    224165void List::mark()
    225 {
    226   if (!imp->marked()) {
    227     imp->mark();
    228   }
    229 }
    230 
    231 void List::append(const Value& val)
    232 {
    233   imp->append(val);
    234 }
    235 
    236 void List::prepend(const Value& val)
    237 {
    238   imp->prepend(val);
    239 }
    240 
    241 void List::appendList(const List& lst)
    242 {
    243   imp->appendList(lst);
    244 }
    245 
    246 void List::prependList(const List& lst)
    247 {
    248   imp->prependList(lst);
    249 }
    250 
    251 void List::removeFirst()
    252 {
    253   imp->removeFirst();
    254 }
    255 
    256 void List::removeLast()
    257 {
    258   imp->removeLast();
    259 }
    260 
    261 void List::remove(const Value &val)
    262 {
    263   imp->remove(val);
    264 }
    265 
    266 void List::clear()
    267 {
    268   imp->clear();
    269 }
    270 
    271 List List::copy() const
    272 {
    273   return imp->copy();
    274 }
    275 
    276 ListIterator List::begin() const
    277 {
    278   return imp->begin();
    279 }
    280 
    281 ListIterator List::end() const
    282 {
    283   return imp->end();
    284 }
    285 
    286 bool List::isEmpty() const
    287 {
    288   return imp->isEmpty();
    289 }
    290 
    291 int List::size() const
    292 {
    293   return imp->size();
    294 }
    295 
    296 Value List::at(int i) const
    297 {
    298   return imp->at(i);
    299 }
    300 
    301 Value List::operator[](int i) const
    302 {
    303   return imp->at(i);
    304 }
    305 
    306 const List List::empty()
    307 {
    308   return ListImp::empty();
    309 }
    310 
    311 #ifdef KJS_DEBUG_MEM
    312 void List::globalClear()
    313 {
    314   delete ListImp::emptyList;
    315   ListImp::emptyList = 0L;
    316 }
    317 #endif
    318 
    319 void List::markEmptyList()
    320 {
    321   if (ListImp::emptyList && !ListImp::emptyList->marked())
    322     ListImp::emptyList->mark();
    323 }
    324 
    325 
    326 // ------------------------------ ListImp --------------------------------------
    327 
    328 #ifdef KJS_DEBUG_MEM
    329 int ListImp::count = 0;
    330 #endif
    331 
    332 Value ListImp::toPrimitive(ExecState */*exec*/, Type /*preferredType*/) const
    333 {
    334   // invalid for List
    335   assert(false);
    336   return Value();
    337 }
    338 
    339 bool ListImp::toBoolean(ExecState */*exec*/) const
    340 {
    341   // invalid for List
    342   assert(false);
    343   return false;
    344 }
    345 
    346 double ListImp::toNumber(ExecState */*exec*/) const
    347 {
    348   // invalid for List
    349   assert(false);
    350   return 0;
    351 }
    352 
    353 UString ListImp::toString(ExecState */*exec*/) const
    354 {
    355   // invalid for List
    356   assert(false);
    357   return UString::null;
    358 }
    359 
    360 Object ListImp::toObject(ExecState */*exec*/) const
    361 {
    362   // invalid for List
    363   assert(false);
    364   return Object();
    365 }
    366 
    367 ListImp::ListImp()
    368 {
    369 #ifdef KJS_DEBUG_MEM
    370   count++;
    371 #endif
    372 
    373   hook = new ListNode(Null(), 0L, 0L);
    374   hook->next = hook;
    375   hook->prev = hook;
    376   //fprintf(stderr,"ListImp::ListImp %p hook=%p\n",this,hook);
    377 }
    378 
    379 ListImp::~ListImp()
    380 {
    381   //fprintf(stderr,"ListImp::~ListImp %p\n",this);
    382 #ifdef KJS_DEBUG_MEM
    383   count--;
    384 #endif
    385 
    386   clear();
    387   delete hook;
    388 
    389   if ( emptyList == this )
    390     emptyList = 0L;
    391 }
    392 
    393 void ListImp::mark()
    394166{
    395167  ListNode *n = hook->next;
    … …  
    399171    n = n->next;
    400172  }
    401   ValueImp::mark();
    402 }
    403 
    404 void ListImp::append(const Value& obj)
    405 {
    406   ListNode *n = new ListNode(obj, hook->prev, hook);
     173}
     174
     175void List::append(const Value& val)
     176{
     177  ListNode *n = new ListNode(val, hook->prev, hook);
     178  if (!m_needsMarking) {
     179    n->member->ref();
     180  }
    407181  hook->prev->next = n;
    408182  hook->prev = n;
    409183}
    410184
    411 void ListImp::prepend(const Value& obj)
    412 {
    413   ListNode *n = new ListNode(obj, hook, hook->next);
     185void List::prepend(const Value& val)
     186{
     187  ListNode *n = new ListNode(val, hook, hook->next);
     188  if (!m_needsMarking) {
     189    n->member->ref();
     190  }
    414191  hook->next->prev = n;
    415192  hook->next = n;
    416193}
    417194
    418 void ListImp::appendList(const List& lst)
     195void List::appendList(const List& lst)
    419196{
    420197  ListIterator it = lst.begin();
    … …  
    426203}
    427204
    428 void ListImp::prependList(const List& lst)
     205void List::prependList(const List& lst)
    429206{
    430207  ListIterator it = lst.end();
    … …  
    436213}
    437214
    438 void ListImp::removeFirst()
     215void List::removeFirst()
    439216{
    440217  erase(hook->next);
    441218}
    442219
    443 void ListImp::removeLast()
     220void List::removeLast()
    444221{
    445222  erase(hook->prev);
    446223}
    447224
    448 void ListImp::remove(const Value &obj)
    449 {
    450   if (obj.isNull())
     225void List::remove(const Value &val)
     226{
     227  if (val.isNull())
    451228    return;
    452229  ListNode *n = hook->next;
    453230  while (n != hook) {
    454     if (n->member == obj.imp()) {
     231    if (n->member == val.imp()) {
    455232      erase(n);
    456233      return;
    … …  
    460237}
    461238
    462 void ListImp::clear()
     239
     240void List::clear()
     241{
     242  if (!m_needsMarking) {
     243    derefAll();
     244  }
     245  clearInternal();
     246}
     247
     248void List::clearInternal()
    463249{
    464250  ListNode *n = hook->next;
    … …  
    472258}
    473259
    474 ListImp *ListImp::copy() const
    475 {
    476   ListImp* newList = new ListImp;
     260List List::copy() const
     261{
     262  List newList;
    477263
    478264  ListIterator e = end();
    … …  
    480266
    481267  while(it != e) {
    482     newList->append(*it);
     268    newList.append(*it);
    483269    ++it;
    484270  }
    485271
    486   //fprintf( stderr, "ListImp::copy returning newList=%p\n", newList );
    487272  return newList;
    488273}
    489274
    490 void ListImp::erase(ListNode *n)
    491 {
    492   if (n != hook) {
    493     n->next->prev = n->prev;
    494     n->prev->next = n->next;
    495     delete n;
    496   }
    497 }
    498 
    499 bool ListImp::isEmpty() const
     275ListIterator List::begin() const
     276{
     277  return ListIterator(hook->next);
     278}
     279
     280ListIterator List::end() const
     281{
     282  return ListIterator(hook);
     283}
     284
     285bool List::isEmpty() const
    500286{
    501287  return (hook->prev == hook);
    502288}
    503289
    504 int ListImp::size() const
     290int List::size() const
    505291{
    506292  int s = 0;
    … …  
    512298}
    513299
    514 Value ListImp::at(int i) const
     300Value List::at(int i) const
    515301{
    516302  if (i < 0 || i >= size())
    … …  
    525311}
    526312
    527 ListImp *ListImp::emptyList = 0L;
    528 
    529 ListImp *ListImp::empty()
    530 {
    531   if (!emptyList)
    532     emptyList = new ListImp();
    533   return emptyList;
    534 }
    535 
     313Value List::operator[](int i) const
     314{
     315  return at(i);
     316}
     317
     318const List List::empty()
     319{
     320  return List();
     321}
     322
     323
     324void List::erase(ListNode *n)
     325{
     326  if (n != hook) {
     327    if (!m_needsMarking) {
     328      n->member->deref();
     329    }
     330    n->next->prev = n->prev;
     331    n->prev->next = n->next;
     332    delete n;
     333  }
     334}
     335
     336void List::refAll()
     337{
     338  ListNode *n = hook->next;
     339
     340  while (n != hook) {
     341    n->member->ref();
     342    n = n->next;
     343  }
     344}
     345
     346void List::derefAll()
     347{
     348  ListNode *n = hook->next;
     349
     350  while (n != hook) {
     351    n->member->deref();
     352    n = n->next;
     353  }
     354}
     355
     356void List::swap(List &other)
     357{
     358  if (m_needsMarking && !other.m_needsMarking) {
     359    refAll();
     360    other.derefAll();
     361  } else if (!m_needsMarking && other.m_needsMarking) {
     362    other.refAll();
     363    derefAll();
     364  }
     365
     366  ListHookNode *tmp = hook;
     367  hook = other.hook;
     368  other.hook = tmp;
     369}
     370
     371#ifdef KJS_DEBUG_MEM
     372void List::globalClear()
     373{
     374}
     375#endif
     376

  • trunk/JavaScriptCore/kjs/types.h

    r2744 r2748  
    3636  class ListIterator;
    3737  class ListNode;
     38  class ListHookNode;
    3839
    3940  /**
    … …  
    4243  class ListIterator {
    4344    friend class List;
    44     friend class ListImp;
    4545    ListIterator();
    4646    ListIterator(ListNode *n);
    … …  
    195195#endif
    196196    void mark();
    197     static void markEmptyList();
    198197  private:
    199     List(ListImp *);
    200 
    201     ListImp *imp;
     198
     199    void erase(ListNode *n);
     200    void clearInternal();
     201    void refAll();
     202    void derefAll();
     203    void swap(List &other);
     204
     205    ListHookNode *hook;
    202206    bool m_needsMarking;
    203     friend class ListNode;
    204207  };
    205208
Note: See TracChangeset for help on using the changeset viewer.