[prev in list] [next in list] [prev in thread] [next in thread]
List: kwrite-devel
Subject: Re: Review Request 115976: Wildcard-like search string + edit distance-based sorting for Quick Open
From: "Milian Wolff" <mail () milianw ! de>
Date: 2014-02-24 8:58:39
Message-ID: 20140224085839.25983.80339 () probe ! kde ! org
[Download RAW message or body]
[Attachment #2 (multipart/alternative)]
> On Feb. 23, 2014, 6:57 p.m., Sven Brauch wrote:
> > We're starting to have a lot of those algorithms now -- kdevelop has \
> > one for quickopen, kate has one for the completion list and now one for \
> > quickopen too. Maybe we could determine some shared functionality and \
> > put it in KTextEditor for all three places to re-use? We'd just need to \
> > discus what functionality that would be.
> > Apart from that, my experience from kdevelop's quickopen is that \
> > arbitrary distance of characters easily yields weird results when \
> > applied to longer paths. But maybe that's fixed by your sorting \
> > algorithm.
> > Does kate's quickopen filter all files when you have a project open, or \
> > always just open files? In the former case, is the regex approach fast \
> > enough?
>
> Kirill Bogdanenko wrote:
> > Does kate's quickopen filter all files when you have a project open, or \
> > always just open files? In the former case, is the regex approach fast \
> > enough?
>
> quickopen filter is applied to all documents that are available, these \
> are: 1. Views
> 2. Opened documents
> 3. Project files
> (for details see KateQuickOpen::update method in \
> kate/app/katequickopen.cpp)
> In the case regex approach is fast enough (but actually can be replaced \
> by wildcard otherwise). At least I hadn't experienced any slowdowns on \
> kate.git project on my laptop (dual-core i7-2640M, 8 GiB RAM). But I \
> haven't done any real benchmarks.
> Kirill Bogdanenko wrote:
> ... but probably it's worth to override filter's filterAcceptsRow() \
> method and get rid of regexp matching.
> Algorhithm can be like as follows:
>
> int lastPos = -1;
>
> for (int i = pattern.length() - 1; i >= 0; i--) {
> int pos = candidate.lastIndexOf(pattern[i], lastPos);
> if (pos != -1) {
> lastPos = pos;
> } else {
> return false;
> }
> }
>
> Can you advice some benchmarking tool that will help to compare these \
> approaches?
> Sven Brauch wrote:
> Milian is the resident expert on benchmarks around here, but if you write \
> a unit test (which is always awesome anyways) you can easily use \
> QBENCHMARK to compare the approaches. A simpler method is just putting \
> QTime t; t.start; [do stuff] qDebug() << t.elapsed() around your code. \
> More serious benchmarking can use valgrind --tool=cachegrind or intel's \
> vtune, but I doubt that's worth it in this case.
Jup, a QBENCHMARK would be greatly appreciated.
QElapsedTimer based "profiling" is only a good tool to quickly verify \
hotspots found by other means, such as perf, callgrind or vtune. A \
QBENCHMARK is still needed in order to systematically improve performance \
and ensure that no performance regressions creep in.
- Milian
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://git.reviewboard.kde.org/r/115976/#review50608
-----------------------------------------------------------
On Feb. 23, 2014, 6:44 p.m., Kirill Bogdanenko wrote:
>
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://git.reviewboard.kde.org/r/115976/
> -----------------------------------------------------------
>
> (Updated Feb. 23, 2014, 6:44 p.m.)
>
>
> Review request for Kate, Christoph Cullmann and Dominik Haumann.
>
>
> Bugs: 328569
> http://bugs.kde.org/show_bug.cgi?id=328569
>
>
> Repository: kate
>
>
> Description
> -------
>
> Wildcard-like search string for Quick Open
>
> * Search string turns into regexp like:
>
> foo -> /f.*o.*o.*$/
>
> (special characters in original pattern are escaped)
>
> * Filtered items are sorted using edit (Levenstein) distance
>
>
> Diffs
> -----
>
> kate/app/CMakeLists.txt f39bf68
> kate/app/katequickopen.h 175826e
> kate/app/katequickopen.cpp 235f9f1
> kate/app/katequickopenproxymodel.h PRE-CREATION
> kate/app/katequickopenproxymodel.cpp PRE-CREATION
>
> Diff: https://git.reviewboard.kde.org/r/115976/diff/
>
>
> Testing
> -------
>
>
> Thanks,
>
> Kirill Bogdanenko
>
>
[Attachment #5 (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/115976/">https://git.reviewboard.kde.org/r/115976/</a>
</td>
</tr>
</table>
<br />
<blockquote style="margin-left: 1em; border-left: 2px solid #d0d0d0; \
padding-left: 10px;"> <p style="margin-top: 0;">On February 23rd, 2014, \
6:57 p.m. UTC, <b>Sven Brauch</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;">We're starting to have a lot of those algorithms now -- \
kdevelop has one for quickopen, kate has one for the completion list and \
now one for quickopen too. Maybe we could determine some shared \
functionality and put it in KTextEditor for all three places to re-use? \
We'd just need to discus what functionality that would be.
Apart from that, my experience from kdevelop's quickopen is that \
arbitrary distance of characters easily yields weird results when applied \
to longer paths. But maybe that's fixed by your sorting algorithm.
Does kate's quickopen filter all files when you have a project open, or \
always just open files? In the former case, is the regex approach fast \
enough?</pre> </blockquote>
<p>On February 23rd, 2014, 10:26 p.m. UTC, <b>Kirill Bogdanenko</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;">> Does kate's quickopen filter \
all files when you have a project open, or always just open files? In the \
former case, is the regex approach fast enough?
quickopen filter is applied to all documents that are available, these are:
1. Views
2. Opened documents
3. Project files
(for details see KateQuickOpen::update method in \
kate/app/katequickopen.cpp)
In the case regex approach is fast enough (but actually can be replaced by \
wildcard otherwise). At least I hadn't experienced any slowdowns on \
kate.git project on my laptop (dual-core i7-2640M, 8 GiB RAM). But I \
haven't done any real benchmarks.</pre> </blockquote>
<p>On February 23rd, 2014, 10:48 p.m. UTC, <b>Kirill Bogdanenko</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;">... but probably it's worth to \
override filter's filterAcceptsRow() method and get rid of regexp \
matching.
Algorhithm can be like as follows:
int lastPos = -1;
for (int i = pattern.length() - 1; i >= 0; i--) {
int pos = candidate.lastIndexOf(pattern[i], lastPos);
if (pos != -1) {
lastPos = pos;
} else {
return false;
}
}
Can you advice some benchmarking tool that will help to compare these \
approaches?</pre> </blockquote>
<p>On February 23rd, 2014, 11:39 p.m. UTC, <b>Sven Brauch</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;">Milian is the resident expert on benchmarks around here, but \
if you write a unit test (which is always awesome anyways) you can easily \
use QBENCHMARK to compare the approaches. A simpler method is just putting \
QTime t; t.start; [do stuff] qDebug() << t.elapsed() around your \
code. More serious benchmarking can use valgrind --tool=cachegrind or \
intel's vtune, but I doubt that's worth it in this case.</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;">Jup, a \
QBENCHMARK would be greatly appreciated.
QElapsedTimer based "profiling" is only a good tool to quickly \
verify hotspots found by other means, such as perf, callgrind or vtune. A \
QBENCHMARK is still needed in order to systematically improve performance \
and ensure that no performance regressions creep in.</pre> <br />
<p>- Milian</p>
<br />
<p>On February 23rd, 2014, 6:44 p.m. UTC, Kirill Bogdanenko 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 Kate, Christoph Cullmann and Dominik Haumann.</div>
<div>By Kirill Bogdanenko.</div>
<p style="color: grey;"><i>Updated Feb. 23, 2014, 6:44 p.m.</i></p>
<div style="margin-top: 1.5em;">
<b style="color: #575012; font-size: 10pt; margin-top: 1.5em;">Bugs: </b>
<a href="http://bugs.kde.org/show_bug.cgi?id=328569">328569</a>
</div>
<div style="margin-top: 1.5em;">
<b style="color: #575012; font-size: 10pt;">Repository: </b>
kate
</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;">Wildcard-like search string for Quick Open
* Search string turns into regexp like:
foo -> /f.*o.*o.*$/
(special characters in original pattern are escaped)
* Filtered items are sorted using edit (Levenstein) distance
</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>kate/app/CMakeLists.txt <span style="color: \
grey">(f39bf68)</span></li>
<li>kate/app/katequickopen.h <span style="color: \
grey">(175826e)</span></li>
<li>kate/app/katequickopen.cpp <span style="color: \
grey">(235f9f1)</span></li>
<li>kate/app/katequickopenproxymodel.h <span style="color: \
grey">(PRE-CREATION)</span></li>
<li>kate/app/katequickopenproxymodel.cpp <span style="color: \
grey">(PRE-CREATION)</span></li>
</ul>
<p><a href="https://git.reviewboard.kde.org/r/115976/diff/" \
style="margin-left: 3em;">View Diff</a></p>
</td>
</tr>
</table>
</div>
</body>
</html>
_______________________________________________
KWrite-Devel mailing list
KWrite-Devel@kde.org
https://mail.kde.org/mailman/listinfo/kwrite-devel
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic