[prev in list] [next in list] [prev in thread] [next in thread]
List: kfm-devel
Subject: Re: Review Request 112979: Make use of multi-threading in KItemListSizeHintResolver
From: "Frank Reininghaus" <frank78ac () googlemail ! com>
Date: 2013-12-17 17:40:06
Message-ID: 20131217174006.11877.34731 () vidsolbach ! de
[Download RAW message or body]
> On Sept. 30, 2013, 10:04 p.m., Frank Reininghaus wrote:
> > Thanks for looking into this! The layouting procedure is indeed one of \
> > the major bottlenecks when entering a directory, and I was also \
> > thinking that making use of multiple CPU cores is the easiest way for \
> > short-term improvements without major modifications in the layouting \
> > code. Your approach looks good to me - I think I would have also tried \
> > something like that.
> > I'm a bit surprised/disappointed though that it saves only 1/3 of the \
> > time. In can confirm that observation on my system (with a rather old \
> > dual-core AMD 64X2 5000+ CPU, which has to my knowledge no "Turbo \
> > boost" feature if only one core is busy, which might otherwise have \
> > been an explanation for this). I can currently see two possible \
> > explanations for this:
> > (a) Could it be that QtConcurrent::blockingMap() adds a lot of overhead \
> > to each function call? Maybe it's designed for the case that each \
> > invocation of the function is expensive (in which case the overhead \
> > wouldn't matter much). However, in our case, a single call of \
> > "itemSizeHint" is not extremely expensive - it's the large number of \
> > calls that is the problem.
> > But I don't know if that assumption is correct. Maybe \
> > QtConcurrent::blockingMap() is clever enough to split the input list \
> > into only a few large chunks.
> >
> > (b) Maybe some parts of the font/text code in Qt, which is called by \
> > KStandardItemListWidgetInformant::itemSizeHint(), are protected by a \
> > mutex internally. Then there could be several causes for performance \
> > loss. If a large part of the time is spent under mutex protection, then \
> > the gain from parallelization is severely limited by Amdahl's Law. \
> > Moreover, if the mutex is locked/released frequently by several \
> > competing threads, then the performance will suffer greatly because of \
> > mutex contention.
> >
> > An interesting experiment would be to test your patch on a system with \
> > more than 2 physical cores and check how much it improves the \
> > performance. If anyone with such a system is willing to try this:
> > * Uncomment the line "// #define KITEMLISTVIEWLAYOUTER_DEBUG" in \
> > dolphin/src/kitemviews/private/kitemlistviewlayouter.cpp
> >
> > * Either switch on all debug output with kdebugdialog or change the \
> > kDebug() in this file to qDebug()
> > * Open a folder with many files (100,000 or more) in Icons View \
> > (possibly reload it a couple of times with F5).
> > * Apply Emmanuel's patch and repeat the procedure.
> >
> > If mutex contention is indeed an issue here, then I would expect that 4 \
> > or more cores will not bring a much larger performance improvement \
> > (compared to the 1/3 that we get with 2 cores), or that it would even \
> > get worse.
> >
> > Another idea that I had recently (not tested yet, and orthogonal to \
> > your patch in the sense that it might improve the performance even in \
> > the single-thread case, and that it could be combined with a \
> > QtConcurrent approach to bring further improvements):
> > Much of the code inside \
> > KStandardItemListWidgetInformant::itemSizeHint() does exactly the same \
> > every time. In Icons View, this is everything except for the \
> > calculation of the number of lines for the item text. To improve this, \
> > one could replace the function
> > QSizeF KStandardItemListWidgetInformant::itemSizeHint(int index, const \
> > KItemListView* view) const
> > by
> >
> > void KStandardItemListWidgetInformant::itemSizeHint(QVector<QSizeF>& \
> > sizeHints, const KItemListView* view) const
> > or something like that, do most of the things only once, and then \
> > calculate only the number of lines in a loop.
> > A rough draft:
> >
> > void KStandardItemListWidgetInformant::itemSizeHint(QVector<QSizeF> \
> > sizeHints, const KItemListView* view) const {
> > //...
> >
> > switch (static_cast<const KStandardItemListView*>(view)->itemLayout()) \
> > { case KStandardItemListWidget::IconsLayout: {
> >
> > // Stuff that applies to all items, like...
> > const qreal itemWidth = view->itemSize().width();
> > const qreal maxWidth = itemWidth - 2 * option.padding;
> > const qreal additionalRolesHeight = additionalRolesCount * \
> > option.fontMetrics.lineSpacing();
> > for (int i = 0; i < sizeHints.count(); ++i) {
> > if (!sizeHints.at(i).isEmpty()) {
> > continue;
> > }
> >
> > const QString text = KStringHandler::preProcessWrap(itemText(index, \
> > view));
> > // Calculate the number of lines and the "textHeight"
> > //...
> >
> > const qreal totalHeight = qMin(textHeight + additionalRolesHeight, \
> > maxTextHeight); sizeHints[i] = QSizeF(itemWitdth, totalHeight);
> > }
> >
> > // ...
> > }
> > }
> >
> >
> >
> > Maybe it's worth trying how much time that saves, and how it can be \
> > combined with your QtConcurrent idea?
>
> Emmanuel Pescosta wrote:
> > Maybe it's worth trying how much time that saves, and how it can be \
> > combined with your QtConcurrent idea?
>
> Sounds great :)
> I'll test it!
I did have a chance to test your patch on a computer with 4 CPU cores, and \
restricted the number of threads by calling
QThreadPool::globalInstance()->setMaxThreadCount(number);
before the QtConcurrent call, with values for 'number' between 1 and 4. \
When using more than 2 threads, the time needed for the layout is not \
reduced further, but increases slightly. Moreover, the total CPU time \
required as reported by 'time dolphin /path/to/large/folder' increases \
significantly when using more than 1 thread. So it appears that contention \
is really a problem here, and the 'size hint' calculation using Qt's text \
engine stuff is not suitable for parallel computation.
Have you tried the "calculate all size hints in all function" approach yet?
- Frank
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
http://git.reviewboard.kde.org/r/112979/#review41057
-----------------------------------------------------------
On Sept. 28, 2013, 7:07 p.m., Emmanuel Pescosta wrote:
>
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> http://git.reviewboard.kde.org/r/112979/
> -----------------------------------------------------------
>
> (Updated Sept. 28, 2013, 7:07 p.m.)
>
>
> Review request for Dolphin.
>
>
> Repository: kde-baseapps
>
>
> Description
> -------
>
> Make use of multi-threading in KItemListSizeHintResolver.
>
> We need the item size hints of all items in \
> KItemListLayouter::doLayout(), so instead of resolving it sequentially \
> during layout calculation, we can resolve all item size hints in \
> parallel before we start the layout calculation.
>
>
> Diffs
> -----
>
> dolphin/src/kitemviews/private/kitemlistsizehintresolver.h 486f9b6
> dolphin/src/kitemviews/private/kitemlistsizehintresolver.cpp 0e2286b
> dolphin/src/kitemviews/private/kitemlistviewlayouter.h 306fcd3
> dolphin/src/kitemviews/private/kitemlistviewlayouter.cpp d6e78ae
>
> Diff: http://git.reviewboard.kde.org/r/112979/diff/
>
>
> Testing
> -------
>
> Everything works fine.
>
> It is about 1/3 faster on my machine (tested with 100k items in item view \
> mode).
>
> Thanks,
>
> Emmanuel Pescosta
>
>
[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="http://git.reviewboard.kde.org/r/112979/">http://git.reviewboard.kde.org/r/112979/</a>
</td>
</tr>
</table>
<br />
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; \
padding-left: 10px;"> <p style="margin-top: 0;">On September 30th, 2013, \
10:04 p.m. UTC, <b>Frank Reininghaus</b> wrote:</p> <blockquote \
style="margin-left: 1em; border-left: 2px solid #d0d0d0; padding-left: \
10px;"> <pre style="white-space: pre-wrap; white-space: -moz-pre-wrap; \
white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: \
break-word;">Thanks for looking into this! The layouting procedure is \
indeed one of the major bottlenecks when entering a directory, and I was \
also thinking that making use of multiple CPU cores is the easiest way for \
short-term improvements without major modifications in the layouting code. \
Your approach looks good to me - I think I would have also tried something \
like that.
I'm a bit surprised/disappointed though that it saves only 1/3 of the \
time. In can confirm that observation on my system (with a rather old \
dual-core AMD 64X2 5000+ CPU, which has to my knowledge no "Turbo \
boost" feature if only one core is busy, which might otherwise have \
been an explanation for this). I can currently see two possible \
explanations for this:
(a) Could it be that QtConcurrent::blockingMap() adds a lot of overhead to \
each function call? Maybe it's designed for the case that each \
invocation of the function is expensive (in which case the overhead \
wouldn't matter much). However, in our case, a single call of \
"itemSizeHint" is not extremely expensive - it's the large \
number of calls that is the problem.
But I don't know if that assumption is correct. Maybe \
QtConcurrent::blockingMap() is clever enough to split the input list into \
only a few large chunks.
(b) Maybe some parts of the font/text code in Qt, which is called by \
KStandardItemListWidgetInformant::itemSizeHint(), are protected by a mutex \
internally. Then there could be several causes for performance loss. If a \
large part of the time is spent under mutex protection, then the gain from \
parallelization is severely limited by Amdahl's Law. Moreover, if the \
mutex is locked/released frequently by several competing threads, then the \
performance will suffer greatly because of mutex contention.
An interesting experiment would be to test your patch on a system with more \
than 2 physical cores and check how much it improves the performance. If \
anyone with such a system is willing to try this:
* Uncomment the line "// #define KITEMLISTVIEWLAYOUTER_DEBUG" in \
dolphin/src/kitemviews/private/kitemlistviewlayouter.cpp
* Either switch on all debug output with kdebugdialog or change the \
kDebug() in this file to qDebug()
* Open a folder with many files (100,000 or more) in Icons View (possibly \
reload it a couple of times with F5).
* Apply Emmanuel's patch and repeat the procedure.
If mutex contention is indeed an issue here, then I would expect that 4 or \
more cores will not bring a much larger performance improvement (compared \
to the 1/3 that we get with 2 cores), or that it would even get worse.
Another idea that I had recently (not tested yet, and orthogonal to your \
patch in the sense that it might improve the performance even in the \
single-thread case, and that it could be combined with a QtConcurrent \
approach to bring further improvements):
Much of the code inside KStandardItemListWidgetInformant::itemSizeHint() \
does exactly the same every time. In Icons View, this is everything except \
for the calculation of the number of lines for the item text. To improve \
this, one could replace the function
QSizeF KStandardItemListWidgetInformant::itemSizeHint(int index, const \
KItemListView* view) const
by
void KStandardItemListWidgetInformant::itemSizeHint(QVector<QSizeF>& \
sizeHints, const KItemListView* view) const
or something like that, do most of the things only once, and then calculate \
only the number of lines in a loop.
A rough draft:
void KStandardItemListWidgetInformant::itemSizeHint(QVector<QSizeF> \
sizeHints, const KItemListView* view) const {
//...
switch (static_cast<const \
KStandardItemListView*>(view)->itemLayout()) { case \
KStandardItemListWidget::IconsLayout: {
// Stuff that applies to all items, like...
const qreal itemWidth = view->itemSize().width();
const qreal maxWidth = itemWidth - 2 * option.padding;
const qreal additionalRolesHeight = additionalRolesCount * \
option.fontMetrics.lineSpacing();
for (int i = 0; i < sizeHints.count(); ++i) {
if (!sizeHints.at(i).isEmpty()) {
continue;
}
const QString text = \
KStringHandler::preProcessWrap(itemText(index, view));
// Calculate the number of lines and the "textHeight"
//...
const qreal totalHeight = qMin(textHeight + \
additionalRolesHeight, maxTextHeight); sizeHints[i] = QSizeF(itemWitdth, \
totalHeight); }
// ...
}
}
Maybe it's worth trying how much time that saves, and how it can be \
combined with your QtConcurrent idea? </pre>
</blockquote>
<p>On October 4th, 2013, noon UTC, <b>Emmanuel Pescosta</b> wrote:</p>
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; \
padding-left: 10px;"> <pre style="white-space: pre-wrap; white-space: \
-moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: \
break-word;">> Maybe it's worth trying how much time that saves, and \
how it can be combined with your QtConcurrent idea?
Sounds great :)
I'll test it!</pre>
</blockquote>
</blockquote>
<pre style="white-space: pre-wrap; white-space: -moz-pre-wrap; white-space: \
-pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word;">I did have a \
chance to test your patch on a computer with 4 CPU cores, and restricted \
the number of threads by calling
QThreadPool::globalInstance()->setMaxThreadCount(number);
before the QtConcurrent call, with values for 'number' between 1 \
and 4. When using more than 2 threads, the time needed for the layout is \
not reduced further, but increases slightly. Moreover, the total CPU time \
required as reported by 'time dolphin /path/to/large/folder' \
increases significantly when using more than 1 thread. So it appears that \
contention is really a problem here, and the 'size hint' \
calculation using Qt's text engine stuff is not suitable for parallel \
computation.
Have you tried the "calculate all size hints in all function" \
approach yet?</pre> <br />
<p>- Frank</p>
<br />
<p>On September 28th, 2013, 7:07 p.m. UTC, Emmanuel Pescosta wrote:</p>
<table bgcolor="#fefadf" width="100%" cellspacing="0" cellpadding="8" \
style="background-image: \
url('http://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 Dolphin.</div>
<div>By Emmanuel Pescosta.</div>
<p style="color: grey;"><i>Updated Sept. 28, 2013, 7:07 p.m.</i></p>
<div style="margin-top: 1.5em;">
<b style="color: #575012; font-size: 10pt;">Repository: </b>
kde-baseapps
</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;">Make use of multi-threading in KItemListSizeHintResolver.
We need the item size hints of all items in KItemListLayouter::doLayout(),
so instead of resolving it sequentially during layout calculation,
we can resolve all item size hints in parallel before we start the
layout calculation.</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;">Everything works fine.
It is about 1/3 faster on my machine (tested with 100k items in item view \
mode).</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>dolphin/src/kitemviews/private/kitemlistsizehintresolver.h <span \
style="color: grey">(486f9b6)</span></li>
<li>dolphin/src/kitemviews/private/kitemlistsizehintresolver.cpp <span \
style="color: grey">(0e2286b)</span></li>
<li>dolphin/src/kitemviews/private/kitemlistviewlayouter.h <span \
style="color: grey">(306fcd3)</span></li>
<li>dolphin/src/kitemviews/private/kitemlistviewlayouter.cpp <span \
style="color: grey">(d6e78ae)</span></li>
</ul>
<p><a href="http://git.reviewboard.kde.org/r/112979/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