[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: State of the overlay tree branch?
From: |
Eli Zaretskii |
Subject: |
Re: State of the overlay tree branch? |
Date: |
Sun, 25 Mar 2018 19:39:30 +0300 |
> From: Stefan Monnier <address@hidden>
> Cc: address@hidden
> Date: Sun, 25 Mar 2018 11:11:14 -0400
>
> B1- if find_newline uses the newline cache, at each newline encountered it
> will call buf_charpos_to_bytepos.
> B2- if find_newline does not use the newline cache, at each newline
> encountered it will call buf_bytepos_to_charpos.
Agree with B1, but not with B2. Unless I'm overlooking something,
when the newline cache is disabled, we use memchr, which can search a
contiguous sequence of bytes in a loop, without translating
byte-to-character positions. It only needs this translation at the
beginning of search, after hitting the gap, and when the search is
completed.
> So there are various ways to solve this problem. So far, I tried to
> make the markers-loop give up earlier, which helps (C) to some extent but
> without attacking the core of its problem which is to pay attention to
> the case where one of the bounds is already very close to POS even tho
> the other is still way off.
>
> The patch below tweaks my previous patch to take this into account.
> The result is now that my test cases stay fast (mostly unaffected by the
> number of markers) even for large buffers with a large number of markers.
This is a good change, I think. But it emphasizes even more the fact
that if we instead expose to Lisp display_count_lines, which is
basically a stripped-down version of find_newline with all the
unnecessary ballast removed, we will get an even better performance in
applications that need to count lines a lot.
> Note that the above shows that there are other optimisations which would
> also solve this problem (and would be worthwhile independently).
> A - change line-number-at-pos so it doesn't always rescan all the way
> from point-min. This would really circumvent the whole problem
> (contrarily to what I thought before with my blinders on, thanks Eli
> for insisting on that).
> B - change find_newline so it doesn't call
> buf_charpos_to_bytepos/buf_bytepos_to_charpos at each newline.
> E.g. in the no-newline-cache case it'd probably be faster to
> loop through each char using INC/DEC_BOTH and checking if we're at
> \n, than the current code which uses mem(r)chr to look for the
> bytepos of the next \n and then calls buf_bytepos_to_charpos to get
> the corresponding charpos. Alternatively, we could just delay the
> computation of the charpos until the end (currently we update it
> at each newline, for the purpose of filling the newline-cache).
I think we need not touch find_newline. It is a very frequently used
workhorse, and needs to produce decent performance for every one of
its callers. By contrast, applications whose primary need is to count
lines, let alone do that _thousands_ of times per keystroke, should
have a dedicated function optimized for that job alone. It's not a
coincidence the native line-number display uses display_count_lines ;-)
Thanks.
- Re: State of the overlay tree branch?, (continued)
- Re: State of the overlay tree branch?, Stefan Monnier, 2018/03/23
- Re: State of the overlay tree branch?, Sebastian Sturm, 2018/03/23
- Re: State of the overlay tree branch?, Eli Zaretskii, 2018/03/23
- Re: State of the overlay tree branch?, Stefan Monnier, 2018/03/23
- Re: State of the overlay tree branch?, Noam Postavsky, 2018/03/23
- Re: State of the overlay tree branch?, Stefan Monnier, 2018/03/23
- Re: State of the overlay tree branch?, Eli Zaretskii, 2018/03/23
- Re: State of the overlay tree branch?, Stefan Monnier, 2018/03/23
- Re: State of the overlay tree branch?, Stefan Monnier, 2018/03/23
- Re: State of the overlay tree branch?, Stefan Monnier, 2018/03/25
- Re: State of the overlay tree branch?,
Eli Zaretskii <=
- Re: State of the overlay tree branch?, Stefan Monnier, 2018/03/25
- Re: State of the overlay tree branch?, Eli Zaretskii, 2018/03/23
- Re: State of the overlay tree branch?, Eli Zaretskii, 2018/03/23
- Re: State of the overlay tree branch?, Sebastian Sturm, 2018/03/23
- Re: State of the overlay tree branch?, Eli Zaretskii, 2018/03/23
- Re: State of the overlay tree branch?, Stefan Monnier, 2018/03/23
- Re: State of the overlay tree branch?, Eli Zaretskii, 2018/03/23
- Re: State of the overlay tree branch?, Stefan Monnier, 2018/03/23
- Re: State of the overlay tree branch?, Eli Zaretskii, 2018/03/19
- Re: State of the overlay tree branch?, Eli Zaretskii, 2018/03/19