D11487: optimization of TextLineData::attribute

[Milian Wolff]

mwolff added a comment.


  In D11487#232258 <https://phabricator.kde.org/D11487#232258>, @jtamate wrote:
  
  > > One question to that though: Why do you sort/lookup by `x.offset + x.length <= p`? Note how lower_bound returns the first iterator that is _not_ going to return true.
  >
  > Assuming there are neither overlaps nor unsorted entries.
  >  Lets call X the iterator returned by lower_bound, suppose X is not cend(), so X.offset + X.length > p.
  
  
  Ah right, the offset + length is larger, not the offset itself - that's the error in my reasoning - thanks for clearing that up!
  Still, you'd get the same with an upper_bound and `x.offset + x.length < p` search, no? I ask this, because to me it is somewhat odd to use a `<=` comparison for a lower_bound.
  
  > If other iterator Y could satisfy Y.offset + Y.length > p and Y.offset <= X.offset, it means there are overlaps, contradiction.
  >  Therefore,  the rest of the iterators has the following properties:
  >  Y.offset + Y.length > p and Y.offset > X.offset
  > or
  >  Y.offset + Y.length <= p and Y.offset < X.offset
  > 
  >> To me, it looks like your code cannot actually work and will always return 0?
  > 
  > Nope. Otherwise the tests fail, more precisely kateindenttest.
  > 
  >> Personally, I'd try to use `upper_bound` with `x.offset < p` in the comparison. The iterator should then point to the first item that has it's offset larger than `p`. So decrementing the iterator once (while checking against `begin()`) yields the iterator that could potentially match. Thus, check if `p` is contained in its range and if so return it's attribute, otherwise return 0.
  > 
  > I've tried. The code gets uglier.
  
  See above, `upper_bound` with `offset + length < p` should return the same iterator as your search now, but be more natural (imo) to what one would see elsewhere.
  
  >> 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?
  > 
  > Perhaps some Ignored words? I have Amarok, KAddressBook, KDevelop, KHTML, KIO, ....
  
  Can you maybe check how often, and for what arguments `spellCheckWrtHighlightingRanges` 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.
  
  >> Also, what is "@mwolf solution"
  > 
  > we can return the iterator and take it as an argument again. I tried locally the python style, returning a QPair.
  > 
  >> Can you try that locally and see how it goes for you?
  > 
  > 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?
  
  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.

REPOSITORY
  R39 KTextEditor

REVISION DETAIL
  https://phabricator.kde.org/D11487

To: jtamate, #frameworks, #kate
Cc: anthonyfieroni, dhaumann, mwolff, cullmann, michaelh, kevinapavew, ngraham, demsking, sars
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.kde.org/pipermail/kde-frameworks-devel/attachments/20180323/452d0342/attachment.html>