[prev in list] [next in list] [prev in thread] [next in thread]
List: kfm-devel
Subject: Re: Review Request 111398: Fix O(N^2) complexity issue in KItemListView::slotItemsRemoved
From: "Elvis Stansvik" <elvstone () gmail ! com>
Date: 2013-07-05 10:16:46
Message-ID: 20130705101646.31002.35043 () vidsolbach ! de
[Download RAW message or body]
> On July 4, 2013, 10:27 p.m., Elvis Stansvik wrote:
> > dolphin/src/kitemviews/kitemlistview.cpp, line 1129
> > <http://git.reviewboard.kde.org/r/111398/diff/1/?file=168518#file168518line1129>
> >
> > 'i' could be const here I guess.
>
> Frank Reininghaus wrote:
> Yes, a const won't hurt here, but it is rather uncommon to add a const to \
> POD types in function arguments and foreach loops (just look through the \
> source of Dolphin or any other part of KDE with "grep foreach * -r | grep \
> cpp | grep int" or "grep :: * -r | grep cpp | grep "(int"") because it \
> doesn't have a big benefit. In other kinds of foreach loops, the const \
> prevents that you accidentally modify the container contents, which would \
> cause the implicitly shared copy to detach and force a rather expensive \
> deep copy. However, POD types are copied anyway, so it doesn't matter \
> much if you modify them.
Ah. But I wasn't thinking of copying, but of accidental modification. (E.g. \
same reason const is used for newIndex a few lines down). But you're right, \
it's not the norm to do that. I've worked on a Java code base recently \
where "final" is used all over the place for this reason, so I guess I was \
a little influenced by that :)
- Elvis
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
http://git.reviewboard.kde.org/r/111398/#review35608
-----------------------------------------------------------
On July 4, 2013, 10:10 p.m., Frank Reininghaus wrote:
>
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> http://git.reviewboard.kde.org/r/111398/
> -----------------------------------------------------------
>
> (Updated July 4, 2013, 10:10 p.m.)
>
>
> Review request for Dolphin.
>
>
> Description
> -------
>
> In a directory which is shown in Dolphin, try the following (where N is a \
> large number > 100000):
> touch {1..N}.png
> touch {1..N}.jpg
>
> (wait until all files are shown in the view)
>
> rm *.jpg
>
> This will freeze Dolphin for quite some time (if not, try to increase the \
> number of files). This is because KItemListView::slotItemsRemoved() has a \
> loop over all removed item ranges (100000 in this case), and in each \
> loop, it has another loop that iterates through all items and tries to \
> find visible ones. This is bad because there is always only a small \
> number of visible items, so we better just iterate over those (similar to \
> the approach in KItemListView::slotItemsInserted).
>
> Diffs
> -----
>
> dolphin/src/kitemviews/kitemlistview.cpp 2ea6657
>
> Diff: http://git.reviewboard.kde.org/r/111398/diff/
>
>
> Testing
> -------
>
> Dolphin takes a lot less time to remove many item ranges.
>
>
> Thanks,
>
> Frank Reininghaus
>
>
[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/111398/">http://git.reviewboard.kde.org/r/111398/</a>
</td>
</tr>
</table>
<br />
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; \
padding-left: 10px;"> <p style="margin-top: 0;">On July 4th, 2013, 10:27 \
p.m. UTC, <b>Elvis Stansvik</b> wrote:</p> <blockquote style="margin-left: \
1em; border-left: 2px solid #d0d0d0; padding-left: 10px;">
<table width="100%" border="0" bgcolor="white" style="border: 1px solid \
#C0C0C0; border-collapse: collapse; margin: 2px padding: 2px;"> <thead>
<tr>
<th colspan="4" bgcolor="#F0F0F0" style="border-bottom: 1px solid \
#C0C0C0; font-size: 9pt; padding: 4px 8px; text-align: left;"> <a \
href="http://git.reviewboard.kde.org/r/111398/diff/1/?file=168518#file168518line1129" \
style="color: black; font-weight: bold; text-decoration: \
underline;">dolphin/src/kitemviews/kitemlistview.cpp</a> <span \
style="font-weight: normal;">
(Diff revision 1)
</span>
</th>
</tr>
</thead>
<tbody style="background-color: #e4d9cb; padding: 4px 8px; text-align: \
center;"> <tr>
<td colspan="4"><pre style="font-size: 8pt; line-height: 140%; margin: \
0; ">void KItemListView::slotItemsRemoved(const KItemRangeList& \
itemRanges)</pre></td>
</tr>
</tbody>
<tbody>
<tr>
<th bgcolor="#b1ebb0" style="border-right: 1px solid #C0C0C0;" \
align="right"><font size="2"></font></th> <td bgcolor="#c5ffc4" \
width="50%"><pre style="font-size: 8pt; line-height: 140%; margin: 0; \
"></pre></td> <th bgcolor="#b1ebb0" style="border-left: 1px solid #C0C0C0; \
border-right: 1px solid #C0C0C0;" align="right"><font \
size="2">1122</font></th> <td bgcolor="#c5ffc4" width="50%"><pre \
style="font-size: 8pt; line-height: 140%; margin: 0; "> <span \
class="n">foreach</span> <span class="p">(</span><span \
class="kt">int</span> <span class="n">i</span><span class="p">,</span> \
<span class="n">itemsToMove</span><span class="p">)</span> <span \
class="p">{</span></pre></td> </tr>
</tbody>
</table>
<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' could be const here I guess.</pre> </blockquote>
<p>On July 5th, 2013, 9:15 a.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;">Yes, a const won't hurt here, but it is rather uncommon to \
add a const to POD types in function arguments and foreach loops (just look \
through the source of Dolphin or any other part of KDE with "grep \
foreach * -r | grep cpp | grep int" or "grep :: * -r | grep cpp | \
grep "(int"") because it doesn't have a big benefit. In \
other kinds of foreach loops, the const prevents that you accidentally \
modify the container contents, which would cause the implicitly shared copy \
to detach and force a rather expensive deep copy. However, POD types are \
copied anyway, so it doesn't matter much if you modify them.</pre> \
</blockquote>
</blockquote>
<pre style="margin-left: 1em; white-space: pre-wrap; white-space: \
-moz-pre-wrap; white-space: -pre-wrap; white-space: -o-pre-wrap; word-wrap: \
break-word;">Ah. But I wasn't thinking of copying, but of accidental \
modification. (E.g. same reason const is used for newIndex a few lines \
down). But you're right, it's not the norm to do that. I've \
worked on a Java code base recently where "final" is used all \
over the place for this reason, so I guess I was a little influenced by \
that :)</pre> <br />
<p>- Elvis</p>
<br />
<p>On July 4th, 2013, 10:10 p.m. UTC, Frank Reininghaus 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 Frank Reininghaus.</div>
<p style="color: grey;"><i>Updated July 4, 2013, 10:10 p.m.</i></p>
<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;">In a directory which is shown in Dolphin, try the following \
(where N is a large number > 100000):
touch {1..N}.png
touch {1..N}.jpg
(wait until all files are shown in the view)
rm *.jpg
This will freeze Dolphin for quite some time (if not, try to increase the \
number of files). This is because KItemListView::slotItemsRemoved() has a \
loop over all removed item ranges (100000 in this case), and in each loop, \
it has another loop that iterates through all items and tries to find \
visible ones. This is bad because there is always only a small number of \
visible items, so we better just iterate over those (similar to the \
approach in KItemListView::slotItemsInserted).</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;">Dolphin takes a lot less time to remove many item \
ranges.</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/kitemlistview.cpp <span style="color: \
grey">(2ea6657)</span></li>
</ul>
<p><a href="http://git.reviewboard.kde.org/r/111398/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