<table><tr><td style="">mwolff added a comment.
</td><a style="text-decoration: none; padding: 4px 8px; margin: 0 8px 8px; float: right; color: #464C5C; font-weight: bold; border-radius: 3px; background-color: #F7F7F9; background-image: linear-gradient(to bottom,#fff,#f1f0f1); display: inline-block; border: 1px solid rgba(71,87,120,.2);" href="https://phabricator.kde.org/D11487">View Revision</a></tr></table><br /><div><div><blockquote style="border-left: 3px solid #8C98B8;
color: #6B748C;
font-style: italic;
margin: 4px 0 12px 0;
padding: 8px 12px;
background-color: #F8F9FC;">
<div style="font-style: normal;
padding-bottom: 4px;">In <a href="https://phabricator.kde.org/D11487#232258" style="background-color: #e7e7e7;
border-color: #e7e7e7;
border-radius: 3px;
padding: 0 4px;
font-weight: bold;
color: black;text-decoration: none;">D11487#232258</a>, <a href="https://phabricator.kde.org/p/jtamate/" style="
border-color: #f1f7ff;
color: #19558d;
background-color: #f1f7ff;
border: 1px solid transparent;
border-radius: 3px;
font-weight: bold;
padding: 0 4px;">@jtamate</a> wrote:</div>
<div style="margin: 0;
padding: 0;
border: 0;
color: rgb(107, 116, 140);"><blockquote style="border-left: 3px solid #a7b5bf; color: #464c5c; font-style: italic; margin: 4px 0 12px 0; padding: 4px 12px; background-color: #f8f9fc;"><p>One question to that though: Why do you sort/lookup by <tt style="background: #ebebeb; font-size: 13px;">x.offset + x.length <= p</tt>? Note how lower_bound returns the first iterator that is _not_ going to return true.</p></blockquote>
<p>Assuming there are neither overlaps nor unsorted entries.<br />
Lets call X the iterator returned by lower_bound, suppose X is not cend(), so X.offset + X.length > p.</p></div>
</blockquote>
<p>Ah right, the offset + length is larger, not the offset itself - that's the error in my reasoning - thanks for clearing that up!<br />
Still, you'd get the same with an upper_bound and <tt style="background: #ebebeb; font-size: 13px;">x.offset + x.length < p</tt> search, no? I ask this, because to me it is somewhat odd to use a <tt style="background: #ebebeb; font-size: 13px;"><=</tt> comparison for a lower_bound.</p>
<blockquote style="border-left: 3px solid #a7b5bf; color: #464c5c; font-style: italic; margin: 4px 0 12px 0; padding: 4px 12px; background-color: #f8f9fc;"><p>If other iterator Y could satisfy Y.offset + Y.length > p and Y.offset <= X.offset, it means there are overlaps, contradiction.<br />
Therefore, the rest of the iterators has the following properties:<br />
Y.offset + Y.length > p and Y.offset > X.offset<br />
or<br />
Y.offset + Y.length <= p and Y.offset < X.offset</p>
<blockquote style="border-left: 3px solid #a7b5bf; color: #464c5c; font-style: italic; margin: 4px 0 12px 0; padding: 4px 12px; background-color: #f8f9fc;"><p>To me, it looks like your code cannot actually work and will always return 0?</p></blockquote>
<p>Nope. Otherwise the tests fail, more precisely kateindenttest.</p>
<blockquote style="border-left: 3px solid #a7b5bf; color: #464c5c; font-style: italic; margin: 4px 0 12px 0; padding: 4px 12px; background-color: #f8f9fc;"><p>Personally, I'd try to use <tt style="background: #ebebeb; font-size: 13px;">upper_bound</tt> with <tt style="background: #ebebeb; font-size: 13px;">x.offset < p</tt> in the comparison. The iterator should then point to the first item that has it's offset larger than <tt style="background: #ebebeb; font-size: 13px;">p</tt>. So decrementing the iterator once (while checking against <tt style="background: #ebebeb; font-size: 13px;">begin()</tt>) yields the iterator that could potentially match. Thus, check if <tt style="background: #ebebeb; font-size: 13px;">p</tt> is contained in its range and if so return it's attribute, otherwise return 0.</p></blockquote>
<p>I've tried. The code gets uglier.</p></blockquote>
<p>See above, <tt style="background: #ebebeb; font-size: 13px;">upper_bound</tt> with <tt style="background: #ebebeb; font-size: 13px;">offset + length < p</tt> should return the same iterator as your search now, but be more natural (imo) to what one would see elsewhere.</p>
<blockquote style="border-left: 3px solid #a7b5bf; color: #464c5c; font-style: italic; margin: 4px 0 12px 0; padding: 4px 12px; background-color: #f8f9fc;"><blockquote style="border-left: 3px solid #a7b5bf; color: #464c5c; font-style: italic; margin: 4px 0 12px 0; padding: 4px 12px; background-color: #f8f9fc;"><p>Besides this: I am still looking for an explanation why spell checking is so extremely slow for you. I have the same settings enabled, and spell checking is seemingly fast for me... Am I missing some dictionary or something other to reproduce this?</p></blockquote>
<p>Perhaps some Ignored words? I have Amarok, KAddressBook, KDevelop, KHTML, KIO, ....</p></blockquote>
<p>Can you maybe check how often, and for what arguments <tt style="background: #ebebeb; font-size: 13px;">spellCheckWrtHighlightingRanges</tt> is called for you? I'll do the same, so maybe we can figure out what is going on then. Also, I'll try with a clean configuration and see if anything is different there.</p>
<blockquote style="border-left: 3px solid #a7b5bf; color: #464c5c; font-style: italic; margin: 4px 0 12px 0; padding: 4px 12px; background-color: #f8f9fc;"><blockquote style="border-left: 3px solid #a7b5bf; color: #464c5c; font-style: italic; margin: 4px 0 12px 0; padding: 4px 12px; background-color: #f8f9fc;"><p>Also, what is "<span class="phabricator-remarkup-mention-unknown">@mwolf</span> solution"</p></blockquote>
<p>we can return the iterator and take it as an argument again. I tried locally the python style, returning a QPair.</p>
<blockquote style="border-left: 3px solid #a7b5bf; color: #464c5c; font-style: italic; margin: 4px 0 12px 0; padding: 4px 12px; background-color: #f8f9fc;"><p>Can you try that locally and see how it goes for you?</p></blockquote>
<p>I only get one second less, 33 seconds. The problem is that attribute() is called from more places. Is it worth to have two implementations?</p></blockquote>
<p>OK - thanks for measuring. I was hoping for a bigger difference. I aggre that we can ignore the 3% improvement and stay with your binary search then as it's generic and will work without requiring code changes elsewhere.</p></div></div><br /><div><strong>REPOSITORY</strong><div><div>R39 KTextEditor</div></div></div><br /><div><strong>REVISION DETAIL</strong><div><a href="https://phabricator.kde.org/D11487">https://phabricator.kde.org/D11487</a></div></div><br /><div><strong>To: </strong>jtamate, Frameworks, Kate<br /><strong>Cc: </strong>anthonyfieroni, dhaumann, mwolff, cullmann, michaelh, kevinapavew, ngraham, demsking, sars<br /></div>