[patch] KConfig: Efficient iterators

[Thiago Macieira]

On Tuesday 22 April 2008 15:47:56 Aaron J. Seigo wrote:
> On Tuesday 22 April 2008, David Jarvie wrote:
> > If foreach has such a bad impact on performance, I suggest adding
> > comments
>
> btw, i doubt it's so much the foreach itself as it is the call to keys()
> which iterates over the whole list, allocates a QList and appends the keys
> one by one to them. not pretty when its performance critical code.

Indeed. Instead of iterating over the elements of the map, which would be an 
O(1) operation on memory, it has to create a list of the n elements, thereby 
making the code O(n) in memory. Since the items are appended to the list, 
there are several realloc()s going on.

An extra optimisation would be to add this to kdecore/config/kconfigdata.h:
Q_DECLARE_TYPEINFO(KEntryKey, Q_MOVABLE_TYPE)

before KEntryMap. That makes QMap understand that it can memcpy() the 
KEntryKey types, instead of having to call the copy constructor for each 
entry, then deleting the old item.

-- 
  Thiago Macieira  -  thiago (AT) macieira.info - thiago (AT) kde.org
    PGP/GPG: 0x6EF45358; fingerprint:
    E067 918B B660 DBD1 105C  966C 33F5 F005 6EF4 5358
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part.
URL: <http://mail.kde.org/pipermail/kde-core-devel/attachments/20080422/9572fc0c/attachment.sig>