Re: [RFC] position caches

[Eli Zaretskii]

> Date: Thu, 14 Mar 2013 09:40:17 +0400
> From: Dmitry Antipov <address@hidden>
> CC: address@hidden
> 
> On 03/12/2013 09:08 PM, Eli Zaretskii wrote:
> 
> > 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.
> 
> I do not understand this.

Sorry, this is entirely my fault: I failed to write something without
which the above indeed makes no sense.

> I'm trying to cache not just the previously
> find paragraph start, but the previously find paragraph start against
> [bidi_it->charpos, bidi_it->bytepos] buffer position; so if bidi_it is
> moved in any way, cache becomes invalid even if the buffer is not changed.

You are talking about the line marked below:

> -  while (pos_byte > BEGV_BYTE
> -      && n++ < MAX_PARAGRAPH_SEARCH
> -      && fast_looking_at (re, pos, pos_byte, limit, limit_byte, Qnil) < 0)
> +  if (valid_pos_cache (b, &b->bidi_paragraph_cache)
> +      && b->bidi_paragraph_cache.bufpos == pos_byte)  <<<<<<<<<<<<<<<<<
> +    return b->bidi_paragraph_cache.posval;
> +  else

Yes, this does invalidate the cache when the iterator moves, but it
also makes the cache almost entirely useless, because the iterator
moves all the time (that's why it's called "iterator").  It almost
never needs to find the paragraph start starting at the same buffer
position.  I intended to tell you that this condition will render the
caching much less useful than it could have been, but somehow forgot.

This code runs when the iterator is "re-seated" to a different
position in the buffer.  An example which is frequently met, and thus
might benefit from caching, is when the display code calls
move_it_vertically and/or move_it_vertically_backward, which start by
moving backwards one or more lines, and then start working from there.
If the line we end up on is still within the same paragraph, being
able to not search for paragraph start again is a big win.

Another relevant example is the implementation of vertical-motion.
Each time you press C-n or C-p, we call start_display, which forces
the move_it_* routines called after that to look for the beginning of
the current paragraph, starting at a line that is not the current one.
Again per-buffer cache of the current paragraph would help here a lot,
especially when lines in the buffer are very long.

IOW, if you invalidate the cache whenever the iterator changes its
position, keeping a separate cache for each buffer is redundant,
because the next time we will display the same buffer, we will almost
surely begin from a different buffer position.

So to be useful, the cache cannot be invalidated so frequently.  It
should only be invalidated when we exit the paragraph, i.e. find
ourselves before its beginning or after its end.