[prev in list] [next in list] [prev in thread] [next in thread]
List: kde-commits
Subject: KDE/kdelibs/kjs
From: Maks Orlovich <maksim () kde ! org>
Date: 2010-05-01 18:48:39
Message-ID: 20100501184839.D2D43AC8AA () svn ! kde ! org
[Download RAW message or body]
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<ListImp *>(_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<ListImp *>(_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<ListImp *>(other._impBase);
+ // Assumption: we're empty (e.g. called from copy)
- int size = imp->size;
+ ListImp* otherImp = static_cast<ListImp *>(other._impBase);
+ ListImp* ourImp = static_cast<ListImp *>(_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<ListImp *>(_impBase);
+ ListImp* ourImp = static_cast<ListImp *>(_impBase);
+ ListImp* otherImp = static_cast<ListImp *>(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;
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic