From kde-devel  Wed Apr 21 22:21:35 2004
From: "Fred P." <fprog26 () hotmail ! com>
Date: Wed, 21 Apr 2004 22:21:35 +0000
To: kde-devel
Subject: [KDE-Devel] QString optimization using a Proxy class called
Message-Id: <BAY14-F26aLiduH0J580006f58a () hotmail ! com>
X-MARC-Message: https://marc.info/?l=kde-devel&m=108258610631883


For more information see:
http://kde-apps.org/content/show.php?content=12158&forumexplevel=2

It should work on Qt2, Qt3 or higher, need small modification on QString 
class:

- QString(int buffer_length, bool dummy);
  is currently private, you have to change it to public or protected.

- You also have to put ~QString to be a virtual function.

===============

Improve speed performance of QString
while keeping the syntax readable as is.

e.g.
QStringTemp tmp( 4096 );
QString s = tmp + a + b + c + d;

OR

uint sz = a::length() + b::length() + c::length() + d::length();
QStringTemp tmp( sz );
QString s = tmp + a + b + c + d;

Another way is to modify the
QString::operator+
to use QStringTemp implicitely.

Performance increase from few ms to 4x faster depending on the buffer size
and the size of each string.

See test cases screenshots
for various buffer size algorithms.

The Qt version of this code may be released under the GPL/QPL, if needed.

--------------------------------------------------------------------------------
Changelog:
0.1: Initial version for VCL/AnsiString and VCL/WideString
0.2: Revised for MFC/CString
0.3: Revised for Qt2-Win32/QString
0.4: Revised for Qt2-Linux/QString
0.5: Added Makefile
1.0: Official release.
--------------------------------------------------------------------------------
Licence: LGPL

How it works...
==========

Basically, the algorithm is a "Temporary String Proxy Design Pattern"

http://www.google.com/search?q=design+pattern+proxy

http://www.dofactory.com/patterns/PatternProxy.aspx

http://www.javaworld.com/javaworld/jw-02-2002/jw-0222-designpatterns.html?

http://www.openloop.com/softwareEngineering/patterns/designPattern/dPattern_Proxy.htm

The idea is that the QStringTemp proxy
has the same behavior than QString.

The difference is that we "know" that it's a QStringTemp not a QString;
therefore, we can leverage this opportunity to optimize.

In other words, we are doing this:
inline QStringTemp& operator+( T )
{
  QString::operator+=( T );
  return *this;
}

So, instead of being tedious
and write by hand:

uint sz = a::length() + b::length() + c::length() + d::length();

QString tmp( (int)sz, true );

tmp += a;
tmp += b;
tmp += c;
tmp += d;

QString s = tmp;

We simply write:

uint sz = a::length() + b::length() + c::length() + d::length();

QStringTemp tmp( (int)sz, true );
QString s = tmp + a + b + c + d;

which WAY MORE NATURAL!

The thing is that, if QString::operator+( T ) always returned a QStringTemp 
and would always make a good estimate, see in the screenshot the section: 
"WITHOUT KNOWING QStringTemp buffer size in advance" then you would simply 
have to recompile KDE and get the improvement all over the place!

Needs a bit of tweaking around:

#ifndef QStringTempSize

#ifndef QStringTempShift
#define QStringTempShift 3
#endif

#define QStringTempSize( sz ) ( ((sz) + (sz) >> (QStringTempShift)) | 16 )

//#define QStringTempSize( sz ) ( ((sz) + (sz) >> 3) | 16 )
#endif

Needs more benchmarking on various String concatenation scenarios.

In the meanwhile,
Enjoy!

Long life to KDE! =)

Fred P.

_________________________________________________________________
Tired of spam? Get advanced junk mail protection with MSN Premium   
http://join.msn.com/?pgmarket=en-ca&page=byoa/prem&xAPID=1994&DI=1034&SU=http://hotmail.com/enca&HL=Market_MSNIS_Taglines

 
>> Visit http://mail.kde.org/mailman/listinfo/kde-devel#unsub to unsubscribe <<