Re: [RFC] position caches

[Eli Zaretskii]

> Date: Tue, 12 Mar 2013 11:56:26 +0400
> From: Dmitry Antipov <address@hidden>
> CC: Eli Zaretskii <address@hidden>
> 
> This was designed in attempt to avoid long buffer scans in 
> bidi_find_paragraph_start.
> The same stuff may be used to implement simple per-buffer charpos <-> bytepos 
> cache.
> Caching the result of bidi_find_paragraph_start may improve the speed of 
> backward
> scrolling/movement (I've seen ~6x speedup for 60M buffer with average string 
> of 5K
> characters). Comments are highly appreciated.

Thank you for doing this.

> +BUFFER_INLINE bool
> +valid_pos_cache (struct buffer *b, struct pos_cache *pc)
> +{
> +  return BUF_MODIFF (b) == pc->modiff;
> +}

I think there's a fundamental design problem here, when this cache is
used for holding the paragraph start.  bidi_paragraph_cache is
intended to be used by bidi.c, which is invoked as part of iterating
through all the visible parts of a buffer in order to display them.
(Sometimes, it iterates across characters immediately before and after
the window, and very rarely it does that for positions that are very
far from the displayed portion of text.)  The visible portion of a
buffer can include more than one paragraph (each empty line starts a
new paragraph), and each one of these paragraphs can have a different
base direction, depending on the first strong directional character of
each paragraph.

Therefore, bidi.c needs to determine the paragraph start each time it
enters a new paragraph.  It needs to do that even if the buffer didn't
change a bit, because a new paragraph can have a different base
direction.  The bidi_it->new_paragraph flag is set when the iteration
goes out of a paragraph or when the iterator is re-seated far away of
its current position.  In those cases, xdisp.c calls
bidi_paragraph_init, which in turn calls bidi_find_paragraph_start.
You cannot return the beginning of previously found paragraph just
because the buffer didn't change.

So I think the cache needs to track both the beginning and the end
position of a paragraph, and invalidate the cache whenever the
iterator position (bidi_it->charpos etc.) is outside of these limits.

OTOH, I think you can avoid the need to invalidate the cache on every
buffer change, if you use markers for storing the paragraph beginning
and end.  Then you only need to invalidate if the change is at the
marker position itself, or if the paragraph was emptied.  This might
hold the cache valid for quite some time.

Thanks.