[prev in list] [next in list] [prev in thread] [next in thread]
List: kde-core-devel
Subject: Re: Review Request 118586: Optimize KConfigGroup::exists and similar operations.
From: "Oswald Buddenhagen" <ossi () kde ! org>
Date: 2014-06-07 9:40:06
Message-ID: 20140607094006.5420.20898 () probe ! kde ! org
[Download RAW message or body]
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://git.reviewboard.kde.org/r/118586/#review59497
-----------------------------------------------------------
Ship it!
fwiw, this could be optimized much more reasonably if the entry map was an actual \
tree. thomas braxton sent me a preliminary version of that years ago, but never \
finished it. are you interested in picking this up?
- Oswald Buddenhagen
On June 6, 2014, 11:22 a.m., Milian Wolff wrote:
>
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://git.reviewboard.kde.org/r/118586/
> -----------------------------------------------------------
>
> (Updated June 6, 2014, 11:22 a.m.)
>
>
> Review request for kdelibs, David Faure, Matthew Dawson, and Oswald Buddenhagen.
>
>
> Repository: kdelibs
>
>
> Description
> -------
>
> Optimize KConfigGroup::exists and similar operations.
>
> Before, these kind of read-only operations did a lot of allocations:
>
> 1) allocate a list of all sub groups
> 2) for the above, also allocate a sub-group match key
> 3) iterate over sub groups, allocate a list of all keys in there
> and then finally check whether that list is non-empty
>
> All of the above is now done without a single allocation, by simply
> iterating over the list of entries.
>
> Note: The whole list was iterated even before in allSubGroups. Now
> we still do that, but check for non-empty keys in the group or
> sub group directly. Much more efficient.
>
> Note2: While at it, allSubGroups is also optimized to not require the
> allocation of the subgroup match key.
>
>
> Diffs
> -----
>
> kdecore/config/kconfig.cpp b941983
>
> Diff: https://git.reviewboard.kde.org/r/118586/diff/
>
>
> Testing
> -------
>
> The unit tests all run just fine. I broke it while implementing this patch, so I'm \
> confident this functionality is actually properly tested and covered :)
> The saved allocations are plenty. This is e.g. from the startup of kwrite:
>
> 2844 allocations at:
> 0x7ff7fbc490e9 QHashData::allocateNode(int) /usr/lib/libQtCore.so.4
> 0x7ff7fc152f8e QHash<QString, QHashDummyValue>::createNode(unsigned int, QString \
> const&, QHashDummyValue const&, QHashNode<QString, QHashDumm yValue>**) in \
> /usr/include/qt4/QtCore/qhash.h:543 \
> /ssd/milian/projects/compiled/kde4/lib/libkdecore.so.5 0x7ff7fc152472 \
> QHash<QString, QHashDummyValue>::insert(QString const&, QHashDummyValue const&) in \
> /usr/include/qt4/QtCore/qhash.h:763 /ssd/mi \
> lian/projects/compiled/kde4/lib/libkdecore.so.5 0x7ff7fc1515f9 \
> QSet<QString>::insert(QString const&) in /usr/include/qt4/QtCore/qset.h:181 \
> /ssd/milian/projects/compiled/kde4/lib/libkdecore. so.5
> 0x7ff7fc1501ab QSet<QString>::operator<<(QString const&) in \
> /usr/include/qt4/QtCore/qset.h:201 /ssd/milian/projects/compiled/kde4/lib/libkdec \
> ore.so.5 0x7ff7fc14b4a7 KConfigPrivate::keyListImpl(QByteArray const&) const in \
> /ssd/milian/projects/kde4/kdelibs/kdecore/config/kconfig.cpp:367 /ssd/ \
> milian/projects/compiled/kde4/lib/libkdecore.so.5 0x7ff7fc14b25d \
> KConfigPrivate::hasNonDeletedEntries(QByteArray const&) const in \
> /ssd/milian/projects/kde4/kdelibs/kdecore/config/kconfig.cpp: 347 \
> /ssd/milian/projects/compiled/kde4/lib/libkdecore.so.5 0x7ff7fc14dfeb \
> KConfig::hasGroupImpl(QByteArray const&) const in \
> /ssd/milian/projects/kde4/kdelibs/kdecore/config/kconfig.cpp:856 \
> /ssd/milian
> /projects/compiled/kde4/lib/libkdecore.so.5
> 0x7ff7fc1536b4 KConfigBase::hasGroup(QByteArray const&) const in \
> /ssd/milian/projects/kde4/kdelibs/kdecore/config/kconfigbase.cpp:42 /ssd/mil \
> ian/projects/compiled/kde4/lib/libkdecore.so.5 0x7ff7fc158fcd \
> KConfigGroup::exists() const in \
> /ssd/milian/projects/kde4/kdelibs/kdecore/config/kconfiggroup.cpp:592 \
> /ssd/milian/projects/com piled/kde4/lib/libkdecore.so.5
>
> 2844 allocations at:
> 0x7ff7fbc71426 QString::QString(int, Qt::Initialization) /usr/lib/libQtCore.so.4
> 0x7ff7fbd66820 ? /usr/lib/libQtCore.so.4
> 0x7ff7fbc737db QString::fromUtf8(char const*, int) /usr/lib/libQtCore.so.4
> 0x7ff7fc14b494 KConfigPrivate::keyListImpl(QByteArray const&) const in \
> /ssd/milian/projects/kde4/kdelibs/kdecore/config/kconfig.cpp:367 \
> /ssd/milian/projects/compiled/kde4/lib/libkdecore.so.5 0x7ff7fc14b25d \
> KConfigPrivate::hasNonDeletedEntries(QByteArray const&) const in \
> /ssd/milian/projects/kde4/kdelibs/kdecore/config/kconfig.cpp:347 \
> /ssd/milian/projects/compiled/kde4/lib/libkdecore.so.5 0x7ff7fc14dfeb \
> KConfig::hasGroupImpl(QByteArray const&) const in \
> /ssd/milian/projects/kde4/kdelibs/kdecore/config/kconfig.cpp:856 \
> /ssd/milian/projects/compiled/kde4/lib/libkdecore.so.5 0x7ff7fc1536b4 \
> KConfigBase::hasGroup(QByteArray const&) const in \
> /ssd/milian/projects/kde4/kdelibs/kdecore/config/kconfigbase.cpp:42 \
> /ssd/milian/projects/compiled/kde4/lib/libkdecore.so.5 0x7ff7fc158fcd \
> KConfigGroup::exists() const in \
> /ssd/milian/projects/kde4/kdelibs/kdecore/config/kconfiggroup.cpp:592 \
> /ssd/milian/projects/compiled/kde4/lib/libkdecore.so.5
> All of these are gone with the patch.
>
>
> Thanks,
>
> Milian Wolff
>
>
[Attachment #3 (text/html)]
<html>
<body>
<div style="font-family: Verdana, Arial, Helvetica, Sans-Serif;">
<table bgcolor="#f9f3c9" width="100%" cellpadding="8" style="border: 1px #c9c399 \
solid;"> <tr>
<td>
This is an automatically generated e-mail. To reply, visit:
<a href="https://git.reviewboard.kde.org/r/118586/">https://git.reviewboard.kde.org/r/118586/</a>
</td>
</tr>
</table>
<br />
<p>Ship it!</p>
<pre style="white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: \
-pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">fwiw, this could be \
optimized much more reasonably if the entry map was an actual tree. thomas braxton \
sent me a preliminary version of that years ago, but never finished it. are you \
interested in picking this up? </pre>
<br />
<p>- Oswald Buddenhagen</p>
<br />
<p>On June 6th, 2014, 11:22 a.m. UTC, Milian Wolff wrote:</p>
<table bgcolor="#fefadf" width="100%" cellspacing="0" cellpadding="8" \
style="background-image: \
url('https://git.reviewboard.kde.org/static/rb/images/review_request_box_top_bg.ab6f3b1072c9.png'); \
background-position: left top; background-repeat: repeat-x; border: 1px black \
solid;"> <tr>
<td>
<div>Review request for kdelibs, David Faure, Matthew Dawson, and Oswald \
Buddenhagen.</div> <div>By Milian Wolff.</div>
<p style="color: grey;"><i>Updated June 6, 2014, 11:22 a.m.</i></p>
<div style="margin-top: 1.5em;">
<b style="color: #575012; font-size: 10pt;">Repository: </b>
kdelibs
</div>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Description </h1>
<table width="100%" bgcolor="#ffffff" cellspacing="0" cellpadding="10" \
style="border: 1px solid #b8b5a0"> <tr>
<td>
<pre style="margin: 0; padding: 0; white-space: pre-wrap; white-space: \
-moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: \
break-word;">Optimize KConfigGroup::exists and similar operations.
Before, these kind of read-only operations did a lot of allocations:
1) allocate a list of all sub groups
2) for the above, also allocate a sub-group match key
3) iterate over sub groups, allocate a list of all keys in there
and then finally check whether that list is non-empty
All of the above is now done without a single allocation, by simply
iterating over the list of entries.
Note: The whole list was iterated even before in allSubGroups. Now
we still do that, but check for non-empty keys in the group or
sub group directly. Much more efficient.
Note2: While at it, allSubGroups is also optimized to not require the
allocation of the subgroup match key.</pre>
</td>
</tr>
</table>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Testing </h1>
<table width="100%" bgcolor="#ffffff" cellspacing="0" cellpadding="10" style="border: \
1px solid #b8b5a0"> <tr>
<td>
<pre style="margin: 0; padding: 0; white-space: pre-wrap; white-space: \
-moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: \
break-word;">The unit tests all run just fine. I broke it while implementing this \
patch, so I'm confident this functionality is actually properly tested and \
covered :)
The saved allocations are plenty. This is e.g. from the startup of kwrite:
2844 allocations at:
0x7ff7fbc490e9 QHashData::allocateNode(int) /usr/lib/libQtCore.so.4
0x7ff7fc152f8e QHash<QString, QHashDummyValue>::createNode(unsigned int, \
QString const&, QHashDummyValue const&, QHashNode<QString, QHashDumm \
yValue>**) in /usr/include/qt4/QtCore/qhash.h:543 \
/ssd/milian/projects/compiled/kde4/lib/libkdecore.so.5 0x7ff7fc152472 \
QHash<QString, QHashDummyValue>::insert(QString const&, QHashDummyValue \
const&) in /usr/include/qt4/QtCore/qhash.h:763 /ssd/mi \
lian/projects/compiled/kde4/lib/libkdecore.so.5 0x7ff7fc1515f9 \
QSet<QString>::insert(QString const&) in /usr/include/qt4/QtCore/qset.h:181 \
/ssd/milian/projects/compiled/kde4/lib/libkdecore. so.5
0x7ff7fc1501ab QSet<QString>::operator<<(QString const&) in \
/usr/include/qt4/QtCore/qset.h:201 /ssd/milian/projects/compiled/kde4/lib/libkdec \
ore.so.5 0x7ff7fc14b4a7 KConfigPrivate::keyListImpl(QByteArray const&) const in \
/ssd/milian/projects/kde4/kdelibs/kdecore/config/kconfig.cpp:367 /ssd/ \
milian/projects/compiled/kde4/lib/libkdecore.so.5 0x7ff7fc14b25d \
KConfigPrivate::hasNonDeletedEntries(QByteArray const&) const in \
/ssd/milian/projects/kde4/kdelibs/kdecore/config/kconfig.cpp: 347 \
/ssd/milian/projects/compiled/kde4/lib/libkdecore.so.5 0x7ff7fc14dfeb \
KConfig::hasGroupImpl(QByteArray const&) const in \
/ssd/milian/projects/kde4/kdelibs/kdecore/config/kconfig.cpp:856 \
/ssd/milian
/projects/compiled/kde4/lib/libkdecore.so.5
0x7ff7fc1536b4 KConfigBase::hasGroup(QByteArray const&) const in \
/ssd/milian/projects/kde4/kdelibs/kdecore/config/kconfigbase.cpp:42 /ssd/mil \
ian/projects/compiled/kde4/lib/libkdecore.so.5 0x7ff7fc158fcd KConfigGroup::exists() \
const in /ssd/milian/projects/kde4/kdelibs/kdecore/config/kconfiggroup.cpp:592 \
/ssd/milian/projects/com piled/kde4/lib/libkdecore.so.5
2844 allocations at:
0x7ff7fbc71426 QString::QString(int, Qt::Initialization) /usr/lib/libQtCore.so.4
0x7ff7fbd66820 ? /usr/lib/libQtCore.so.4
0x7ff7fbc737db QString::fromUtf8(char const*, int) /usr/lib/libQtCore.so.4
0x7ff7fc14b494 KConfigPrivate::keyListImpl(QByteArray const&) const in \
/ssd/milian/projects/kde4/kdelibs/kdecore/config/kconfig.cpp:367 \
/ssd/milian/projects/compiled/kde4/lib/libkdecore.so.5 0x7ff7fc14b25d \
KConfigPrivate::hasNonDeletedEntries(QByteArray const&) const in \
/ssd/milian/projects/kde4/kdelibs/kdecore/config/kconfig.cpp:347 \
/ssd/milian/projects/compiled/kde4/lib/libkdecore.so.5 0x7ff7fc14dfeb \
KConfig::hasGroupImpl(QByteArray const&) const in \
/ssd/milian/projects/kde4/kdelibs/kdecore/config/kconfig.cpp:856 \
/ssd/milian/projects/compiled/kde4/lib/libkdecore.so.5 0x7ff7fc1536b4 \
KConfigBase::hasGroup(QByteArray const&) const in \
/ssd/milian/projects/kde4/kdelibs/kdecore/config/kconfigbase.cpp:42 \
/ssd/milian/projects/compiled/kde4/lib/libkdecore.so.5 0x7ff7fc158fcd \
KConfigGroup::exists() const in \
/ssd/milian/projects/kde4/kdelibs/kdecore/config/kconfiggroup.cpp:592 \
/ssd/milian/projects/compiled/kde4/lib/libkdecore.so.5
All of these are gone with the patch.</pre>
</td>
</tr>
</table>
<h1 style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Diffs</b> </h1>
<ul style="margin-left: 3em; padding-left: 0;">
<li>kdecore/config/kconfig.cpp <span style="color: grey">(b941983)</span></li>
</ul>
<p><a href="https://git.reviewboard.kde.org/r/118586/diff/" style="margin-left: \
3em;">View Diff</a></p>
</td>
</tr>
</table>
</div>
</body>
</html>
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic