PATCH/RFC Pool allocations of QStringData objects..
Maks Orlovich
kde-optimize@mail.kde.org
Fri, 17 Jan 2003 22:56:10 -0500
--Boundary-00=_aBNK+FRt8tqXT4X
Content-Type: text/plain;
charset="us-ascii"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
Hi...
The attached patch to Qt modifies the way QStringData objects are allocated
and freed to reuse upto 1000 recently freed ones, to speed up string
operations. (There is still a need to allocate space for the actual data, of
course; but that's a lot harder to optimize since it's not fixed size). Since
I didn't feel like touching qstring.h; the code uses a placement new form. It
also has some statistics code that would have to be removed in a final
version (and which was commented out for the benchmarks, of course)
I've timed it with konqueror modified to return() right before .exec() (which
causes it to core, BTW). The timings were done with my cycle counter-base
kcounterprof helper routines (grab them at
mail.rochester.edu/~mo002j/kcounterprof.h -- but warning: no docs, and
recursive cumulative context handling needs to be checked somewhat
thoroughly). The first timings are of the instrumentation overhead -
basically instrumenting an empty block with counters, and seeing how much
time it takes:
KCounterProf::Cumulative: alloc = 7.45
KCounterProf::Cumulative: free = 4.73
KCounterProf::Cumulative: alloc = 7.36
KCounterProf::Cumulative: free = 4.31
KCounterProf::Cumulative: alloc = 7.15
KCounterProf::Cumulative: free = 4.48
Total (min):11.63
Next, this is just the kdecore malloc/free (inserted into the overall
allocator framework so I have one spot were to measure):
KCounterProf::Cumulative: alloc = 21.79
KCounterProf::Cumulative: free = 10.82
KCounterProf::Cumulative: alloc = 21.76
KCounterProf::Cumulative: free = 10.76
KCounterProf::Cumulative: alloc = 22.11
KCounterProf::Cumulative: free = 10.75
Total (min):32.86
Real (min):21.05 [i.e. without the overhead]
Now, with the modified allocation code:
KCounterProf::Cumulative: alloc = 16.89
KCounterProf::Cumulative: free = 5.46
KCounterProf::Cumulative: alloc = 15.84
KCounterProf::Cumulative: free = 5.17
KCounterProf::Cumulative: alloc = 15.73
KCounterProf::Cumulative: free = 5.32
Total (min): 21.05
Real (min): 9.42
The difference is 11.81ms in favor of the pooling solution. Further speed up,
of course, can be achieved by doing smarter allocation as well, and not just
using malloc/freee.
Further, the following are statistics on the operations performed for various
scenarios:
Exit right before event loop: Had to do 27052/101085 allocs, 0/74301 frees
This means that 101085 allocation requests were performed, from which 27052
were done as actual malloc's, and that all the frees were just done by
linking in the nodes into a free list (I've abused the ascii field for that);
which basically means it just never accumulated > 1000 "freed" string.
This number of course, deserves a pause. This means, if it's correct, that we
have created 100,000 QStringData and hence QString objects during the
startup! And subtracting frees from allocs, we have some 26,784 strings in
memory!
Now, doing "konqueror www.kde.org" and waiting for page to load, render,
andthe number to stabilize produces:
Had to do 28570/138238 allocs, 0/109763 frees
konqueror dot.kde.org: Had to do 28589/136266 allocs, 0/107735 frees
konqueror developer.kde.org:Had to do 28205/126576 allocs, 0/98425 frees
konqueror ~, with the iconview: Had to do 44344/170671 allocs, 0/126330 frees
Where ls -l ~|wc -l produces 1256 :-) (hmm, seems kinda small, must have
cleaned it up sometime and forgot about it)..
Comments, thoughts, alternative numbers? Do you think this is worth submitting
to TT for consideration?
-Maksim
--Boundary-00=_aBNK+FRt8tqXT4X
Content-Type: text/x-diff;
charset="us-ascii";
name="qstring_data_pool.diff"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment; filename="qstring_data_pool.diff"
Index: tools/qstring.cpp
===================================================================
RCS file: /home/kde/qt-copy/src/tools/qstring.cpp,v
retrieving revision 1.51
diff -u -3 -p -r1.51 qstring.cpp
--- tools/qstring.cpp 17 Dec 2002 15:04:18 -0000 1.51
+++ tools/qstring.cpp 18 Jan 2003 03:25:56 -0000
@@ -63,6 +63,94 @@
# include <ctype.h>
#endif
+static struct QStringDataAllocatorTag
+{
+} poolQStringData;
+
+struct QStringDataAllocator
+{
+ static int realFreed;
+ static int realAlloced;
+ static int totalFreed;
+ static int totalAlloced;
+ static int opCount;
+
+ static void stats()
+ {
+ opCount++;
+ if (opCount % 1000 != 1)
+ return;
+
+ qDebug("Had to do %d/%d allocs, %d/%d frees",
+ realAlloced, totalAlloced,
+ realFreed , totalFreed);
+ }
+
+ static int count;
+ static QStringData* reuse;
+
+ //Doesn't call ctor; use placement new
+ static QStringData* alloc()
+ {
+ QStringData* toRet;
+ totalAlloced++;
+
+ if (reuse)
+ {
+ toRet = reuse;
+ reuse = (QStringData*) toRet->ascii;
+ count--;
+ }
+ else
+ {
+ realAlloced++;
+ toRet = (QStringData*) malloc(sizeof(QStringData));
+ }
+
+ stats();
+ return toRet;
+ }
+
+ //Calls dtor..
+ static void free(QStringData* alloc)
+ {
+ if (!alloc) return;
+
+ totalFreed++;
+
+ //Don't pool too many.
+ if (count > 1000)
+ {
+ ::free(alloc);
+ realFreed++;
+ }
+ else
+ {
+ alloc->ascii = (char*)reuse;
+ reuse = alloc;
+ count++;
+ }
+
+ stats();
+ }
+};
+
+
+void* operator new(size_t s, const QStringDataAllocatorTag& t)
+{
+ return QStringDataAllocator::alloc();
+}
+
+
+int QStringDataAllocator::count = 0;
+QStringData* QStringDataAllocator::reuse = 0;
+
+int QStringDataAllocator::opCount = 0;
+int QStringDataAllocator::realFreed = 0;
+int QStringDataAllocator::realAlloced = 0;
+int QStringDataAllocator::totalFreed = 0;
+int QStringDataAllocator::totalAlloced = 0;
+
/* -------------------------------------------------------------------------
* unicode information
@@ -13153,7 +13241,7 @@ QT_STATIC_CONST_IMPL QChar QChar::nbsp((
QStringData* QString::makeSharedNull()
{
- QString::shared_null = new QStringData;
+ QString::shared_null = new (poolQStringData) QStringData;
#if defined( Q_OS_MAC )
QString *that = const_cast<QString *>(&QString::null);
that->d = QString::shared_null;
@@ -13175,7 +13263,7 @@ QStringData* QString::makeSharedNull()
*/
QString::QString( QChar ch )
{
- d = new QStringData( QT_ALLOC_QCHAR_VEC( 1 ), 1, 1 );
+ d = new (poolQStringData) QStringData( QT_ALLOC_QCHAR_VEC( 1 ), 1, 1 );
d->unicode[0] = ch;
}
@@ -13206,9 +13294,9 @@ QString::QString( int size, bool /*dummy
if ( size ) {
int l = size;
QChar* uc = QT_ALLOC_QCHAR_VEC( l );
- d = new QStringData( uc, 0, l );
+ d = new (poolQStringData) QStringData( uc, 0, l );
} else {
- d = shared_null ? shared_null : (shared_null=new QStringData);
+ d = shared_null ? shared_null : (shared_null=new (poolQStringData) QStringData);
d->ref();
}
}
@@ -13229,7 +13317,7 @@ QString::QString( const QByteArray& ba )
#endif
uint l;
QChar *uc = internalLatin1ToUnicode(ba,&l);
- d = new QStringData(uc,l,l);
+ d = new (poolQStringData) QStringData(uc,l,l);
}
/*!
@@ -13256,7 +13344,7 @@ QString::QString( const QChar* unicode,
QChar* uc = QT_ALLOC_QCHAR_VEC( length );
if ( unicode )
memcpy(uc, unicode, length*sizeof(QChar));
- d = new QStringData(uc,unicode ? length : 0,length);
+ d = new (poolQStringData) QStringData(uc,unicode ? length : 0,length);
}
}
@@ -13288,7 +13376,7 @@ QString::QString( const char *str )
#endif
uint l;
QChar *uc = internalLatin1ToUnicode(str,&l);
- d = new QStringData(uc,l,l);
+ d = new (poolQStringData) QStringData(uc,l,l);
}
#ifndef QT_NO_STL
@@ -13309,7 +13397,7 @@ QString::QString( const std::string &str
#endif
uint l;
QChar *uc = internalLatin1ToUnicode(str.c_str(),&l);
- d = new QStringData(uc,l,l);
+ d = new (poolQStringData) QStringData(uc,l,l);
}
#endif
@@ -13339,14 +13427,18 @@ void QString::deref()
{
if ( d && d->deref() ) {
if ( d != shared_null )
- delete d;
+ {
+ d->~QStringData();
+ QStringDataAllocator::free(d);
+ }
d = 0;
}
}
void QStringData::deleteSelf()
{
- delete this;
+ this->~QStringData();
+ QStringDataAllocator::free(this);
}
/*!
@@ -13524,7 +13616,7 @@ void QString::setLength( uint newLen )
if ( d->unicode )
memcpy( nd, d->unicode, sizeof(QChar)*len );
deref();
- d = new QStringData( nd, newLen, newMax );
+ d = new (poolQStringData) QStringData( nd, newLen, newMax );
}
} else {
d->len = newLen;
@@ -13956,7 +14048,7 @@ QString& QString::fill( QChar c, int len
} else {
deref();
QChar * nd = QT_ALLOC_QCHAR_VEC( len );
- d = new QStringData(nd,len,len);
+ d = new (poolQStringData) QStringData(nd,len,len);
while (len--) *nd++ = c;
}
return *this;
@@ -16802,7 +16894,7 @@ QString QString::fromLatin1( const char*
if ( len < 0 )
len = -1;
uc = internalLatin1ToUnicode( chars, &l, len );
- return QString( new QStringData(uc, l, l), TRUE );
+ return QString( new (poolQStringData) QStringData(uc, l, l), TRUE );
}
/*!
@@ -16937,7 +17029,7 @@ const unsigned short *QString::ucs2() co
if ( d->unicode )
memcpy( nd, d->unicode, sizeof(QChar)*len );
((QString *)this)->deref();
- ((QString *)this)->d = new QStringData( nd, len, newMax );
+ ((QString *)this)->d = new (poolQStringData) QStringData( nd, len, newMax );
}
}
d->unicode[len] = 0;
@@ -16962,7 +17054,7 @@ QString QString::fromUcs2( const unsigne
length++;
QChar* uc = QT_ALLOC_QCHAR_VEC( length );
memcpy( uc, str, length*sizeof(QChar) );
- return QString( new QStringData( uc, length, length ), TRUE );
+ return QString( new (poolQStringData) QStringData( uc, length, length ), TRUE );
}
}
@@ -17098,7 +17190,7 @@ QString& QString::setUnicode( const QCha
if ( unicode )
memcpy( nd, unicode, sizeof(QChar)*len );
deref();
- d = new QStringData( nd, len, newMax );
+ d = new (poolQStringData) QStringData( nd, len, newMax );
} else {
d->len = len;
d->setDirty();
@@ -17788,7 +17880,7 @@ QDataStream &operator>>( QDataStream &s,
guarantee that \a unicode will not be deleted or modified.
*/
QConstString::QConstString( const QChar* unicode, uint length ) :
- QString( new QStringData( (QChar*)unicode, length, length ), TRUE )
+ QString( new (poolQStringData) QStringData( (QChar*)unicode, length, length ), TRUE )
{
}
--Boundary-00=_aBNK+FRt8tqXT4X--