Re: fontlock-speed
Hrvoje Niksic wrote:
"Stephen J. Turnbull" <stephen(a)xemacs.org> writes:
>>>>>> "Hrvoje" == Hrvoje Niksic
<hniksic(a)arsdigita.com> writes:
>
> Hrvoje> I might be misreading the code, but to me this indicates a
> Hrvoje> possibility that get-text-property requires time
> Hrvoje> proportional to n^2, where n is the number of extents in
> Hrvoje> the buffer.
>
> I haven't done a careful analysis of extent_at_byteind, but note the
> "prior" argument in the call to extent_at_byteind:
I'm aware of the PRIOR argument; I just wasn't sure that it was
helping performance. extent_at_byteind calls the mapper function
every time, and then sorts the results, etc. Or is that not the case?
For example, wouldn't get-text-property be faster if it were
implemented with one call to map_extents_bytind which did all the
necessary magic? Am I wrong in assuming that map_extents_bytind
traverses the extents in display order?
hmm ... i see. yes, it would be faster to do only one map-extents call, but it
may not be significant. the logic of the current text-properties code is
largely left over from the implementation that jamie did before i rewrote the
extents code. basically, the current approach is (time to move SOE) + O(M^2)
where M == number of extents overlapping the position in question. your
approach would be (time to move SOE) + O(M). usually M is very small. i.e.
we're talking about differences in constant factors, not anything related to the
number of extents in the buffer. you still aren't changing the fact that you're
calling g-t-p at each position in the buffer, so the biggest speedup would come
from avoiding this by clever caching. but if the call to g-t-p is dominating
the font-lock time, you could get it noticeably faster -- maybe 1.5 to 2 times
if you're lucky.