[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: "Emmanuel Pescosta" <emmanuelpescosta099 () gmail ! com>
Date: 2013-07-05 12:49:14
Message-ID: 20130705124914.15992.61960 () vidsolbach ! de
[Download RAW message or body]
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
http://git.reviewboard.kde.org/r/111398/#review35631
-----------------------------------------------------------
Ship it!
Works for me. Ship it from my side!
Maybe we should replace QHash.remove(key) calls by QHash.erase(iterator) calls in \
KItemListView to avoid expensive rehashing (esp. in setWidgetIndex, \
moveWidgetToIndex, ...)? What do you think?
https://qt-project.org/doc/qt-5.0/qtcore/qhash.html#erase
- Emmanuel Pescosta
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 />
<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;">Works for me. Ship it \
from my side!
Maybe we should replace QHash.remove(key) calls by QHash.erase(iterator) calls in \
KItemListView to avoid expensive rehashing (esp. in setWidgetIndex, \
moveWidgetToIndex, ...)? What do you think?
https://qt-project.org/doc/qt-5.0/qtcore/qhash.html#erase</pre>
<br />
<p>- Emmanuel</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