SVN commit 1121571 by orlovich: Give the list code an inlinemectory, and simplify things somewhat. Should also make future optimizations easier.. M +53 -61 list.cpp M +37 -12 list.h --- trunk/KDE/kdelibs/kjs/list.cpp #1121570:1121571 @@ -32,18 +32,17 @@ // tunable parameters const int poolSize = 512; -const int inlineValuesSize = 5; + enum ListImpState { unusedInPool = 0, usedInPool, usedOnHeap, immortal }; struct ListImp : ListImpBase { ListImpState state; - int capacity; - JSValue** overflow; + int capacity; // or 0 if data is inline union { - JSValue *values[inlineValuesSize]; + JSValue *values[inlineListValuesSize]; ListImp *nextInFreeList; }; @@ -101,21 +100,12 @@ inline void ListImp::markValues() { - int inlineSize = min(size, inlineValuesSize); - for (int i = 0; i != inlineSize; ++i) { - if (!values[i]->marked()) { - values[i]->mark(); + for (int i = 0; i != size; ++i) { + if (!data[i]->marked()) + data[i]->mark(); } } - int overflowSize = size - inlineSize; - for (int i = 0; i != overflowSize; ++i) { - if (!overflow[i]->marked()) { - overflow[i]->mark(); - } - } -} - void List::markProtectedLists() { int seen = 0; @@ -164,7 +154,7 @@ imp->size = 0; imp->refCount = 1; imp->capacity = 0; - imp->overflow = 0; + imp->data = imp->values; #if DUMP_STATISTICS if (++numLists > numListsHighWaterMark) @@ -191,8 +181,9 @@ ++numListsBiggerThan[i]; #endif - delete [] imp->overflow; - imp->overflow = 0; + if (imp->capacity) + delete [] imp->data; + imp->data = 0; if (imp->state == usedInPool) { imp->state = unusedInPool; @@ -220,50 +211,41 @@ } } -JSValue *List::at(int i) const -{ - ListImp *imp = static_cast(_impBase); - if ((unsigned)i >= (unsigned)imp->size) - return jsUndefined(); - if (i < inlineValuesSize) - return imp->values[i]; - return imp->overflow[i - inlineValuesSize]; -} - void List::clear() { _impBase->size = 0; } -void List::append(JSValue *v) +void List::appendSlowCase(JSValue *v) { ListImp *imp = static_cast(_impBase); - int i = imp->size++; + int i = imp->size++; // insert index/old size #if DUMP_STATISTICS if (imp->size > listSizeHighWaterMark) listSizeHighWaterMark = imp->size; #endif - if (i < inlineValuesSize) { - imp->values[i] = v; - return; - } + // If we got here, we need to use an out-of-line buffer. if (i >= imp->capacity) { int newCapacity = i * 2; - JSValue** newOverflow = new JSValue* [newCapacity - inlineValuesSize]; - JSValue** oldOverflow = imp->overflow; - int oldOverflowSize = i - inlineValuesSize; - for (int j = 0; j != oldOverflowSize; j++) - newOverflow[j] = oldOverflow[j]; - delete [] oldOverflow; - imp->overflow = newOverflow; + + JSValue** newBuffer = new JSValue*[newCapacity]; + + // Copy everything over + for (int c = 0; c < i; ++c) + newBuffer[c] = imp->data[c]; + + if (imp->capacity) // had an old out-of-line buffer + delete[] imp->data; + + imp->data = newBuffer; imp->capacity = newCapacity; } - imp->overflow[i - inlineValuesSize] = v; + imp->data[i] = v; } List List::copy() const @@ -275,37 +257,47 @@ void List::copyFrom(const List& other) { - ListImp *imp = static_cast(other._impBase); + // Assumption: we're empty (e.g. called from copy) - int size = imp->size; + ListImp* otherImp = static_cast(other._impBase); + ListImp* ourImp = static_cast(_impBase); - int inlineSize = min(size, inlineValuesSize); - for (int i = 0; i != inlineSize; ++i) - append(imp->values[i]); + assert(ourImp->size == 0 && ourImp->capacity == 0); - JSValue** overflow = imp->overflow; - int overflowSize = size - inlineSize; - for (int i = 0; i != overflowSize; ++i) - append(overflow[i]); + int size = otherImp->size; + int cap = otherImp->capacity; + ourImp->size = size; + ourImp->capacity = cap; + + if (cap) { + // other used out-of-line buffer -- we should to + ourImp->data = new JSValue*[cap]; } + for (int c = 0; c < size; ++c) + ourImp->data[c] = otherImp->data[c]; +} + List List::copyTail() const { List copy; - ListImp *imp = static_cast(_impBase); + ListImp* ourImp = static_cast(_impBase); + ListImp* otherImp = static_cast(copy._impBase); - int size = imp->size; + // We allocate as much space as the other one (even if we could have + // done it inline) + int size = otherImp->size; + int cap = otherImp->capacity; + ourImp->size = size - 1; + ourImp->capacity = cap; - int inlineSize = min(size, inlineValuesSize); - for (int i = 1; i < inlineSize; ++i) - copy.append(imp->values[i]); + if (cap) + ourImp->data = new JSValue*[cap]; - JSValue** overflow = imp->overflow; - int overflowSize = size - inlineSize; - for (int i = 0; i < overflowSize; ++i) - copy.append(overflow[i]); + for (int c = 1; c < size; ++c) + ourImp->data[c-1] = otherImp->data[c]; return copy; } --- trunk/KDE/kdelibs/kjs/list.h #1121570:1121571 @@ -27,9 +27,12 @@ namespace KJS { + const int inlineListValuesSize = 5; + struct ListImpBase { int size; int refCount; + JSValue** data; // points either to inline or out-of-line buffer }; class ListIterator; @@ -49,9 +52,7 @@ List(); ~List() { deref(); } - List(const List &b) : _impBase(b._impBase) { - ++_impBase->refCount; - } + List(const List &b) : _impBase(b._impBase) { ++_impBase->refCount; } List &operator=(const List &); /** @@ -71,19 +72,12 @@ */ void reset() { deref(); ++(_impBase = empty()._impBase)->refCount; } - /** * Make a copy of the list */ List copy() const; - /** - * Copy all elements from the second list here - */ - void copyFrom(const List& other); - - /** * Make a copy of the list, omitting the first element. */ List copyTail() const; @@ -92,28 +86,31 @@ * @return true if the list is empty. false otherwise. */ bool isEmpty() const { return _impBase->size == 0; } + /** * @return the current size of the list. */ int size() const { return _impBase->size; } + /** * @return A KJS::ListIterator pointing to the first element. */ ListIterator begin() const; + /** * @return A KJS::ListIterator pointing to the last element. */ ListIterator end() const; /** - * Retrieve an element at an indexed position. If you want to iterate - * trough the whole list using KJS::ListIterator will be faster. + * Retrieve an element at an indexed position. * * @param i List index. * @return Return the element at position i. KJS::Undefined if the * index is out of range. */ JSValue *at(int i) const; + /** * Equivalent to at. */ @@ -127,6 +124,13 @@ static void markProtectedLists(); private: + /** + * Copy all elements from the second list here + */ + void copyFrom(const List& other); + + void appendSlowCase(JSValue* val); + ListImpBase *_impBase; void deref() { if (--_impBase->refCount == 0) release(); } @@ -135,6 +139,25 @@ void markValues(); }; + inline JSValue* List::at(int i) const { + if (i < _impBase->size) + return _impBase->data[i]; + else + return jsUndefined(); + } + + inline void List::append(JSValue *val) { + int size = _impBase->size; + int newSize = size + 1; + if (newSize < inlineListValuesSize) { + // Can just write to the inline byffer + _impBase->data[size] = val; + _impBase->size = newSize; + } else { + appendSlowCase(val); + } + } + /** * @short Iterator for KJS::List objects. */ @@ -192,3 +215,5 @@ } // namespace KJS #endif // KJS_LIST_H + +// kate: indent-width 4; replace-tabs on; tab-width 4; space-indent on;