[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