Region cache for bidi paragraphs?

Region cache for bidi paragraphs?

[Dmitry Antipov]

[-- Attachment #1: Type: text/plain, Size: 169 bytes --]

Eli,

what do you think about using region cache to speedup bidi_find_paragraph_start?
I wrote this just to illustrate an idea, which is fairly straightforward.

Dmitry

[-- Attachment #2: bidi_paragraph_cache.patch --]
[-- Type: text/plain, Size: 3723 bytes --]

=== modified file 'src/bidi.c'
--- src/bidi.c	2013-06-08 18:28:36 +0000
+++ src/bidi.c	2013-08-02 10:23:02 +0000
@@ -61,6 +61,7 @@
 #include "character.h"
 #include "buffer.h"
 #include "dispextern.h"
+#include "region-cache.h"
 
 static bool bidi_initialized = 0;
 
@@ -1100,7 +1101,8 @@
 {
   Lisp_Object re = paragraph_start_re;
   ptrdiff_t limit = ZV, limit_byte = ZV_BYTE;
-  ptrdiff_t n = 0;
+  struct region_cache *bpc = current_buffer->bidi_paragraph_cache;
+  ptrdiff_t n = 0, oldpos = pos, next;
 
   while (pos_byte > BEGV_BYTE
 	 && n++ < MAX_PARAGRAPH_SEARCH
@@ -1111,10 +1113,17 @@
 	 of the text over which we scan back includes
 	 paragraph_start_re?  */
       DEC_BOTH (pos, pos_byte);
-      pos = find_newline_no_quit (pos, pos_byte, -1, &pos_byte);
+      if (region_cache_backward (current_buffer, bpc, pos, &next))
+	{
+	  pos = next, pos_byte = CHAR_TO_BYTE (pos);
+	  break;
+	}
+      else
+	pos = find_newline_no_quit (pos, pos_byte, -1, &pos_byte);
     }
   if (n >= MAX_PARAGRAPH_SEARCH)
-    pos_byte = BEGV_BYTE;
+    pos = BEGV, pos_byte = BEGV_BYTE;
+  know_region_cache (current_buffer, bpc, pos, oldpos);
   return pos_byte;
 }
 

=== modified file 'src/buffer.c'
--- src/buffer.c	2013-07-16 21:35:45 +0000
+++ src/buffer.c	2013-08-02 08:42:50 +0000
@@ -590,6 +590,7 @@
 
   b->newline_cache = 0;
   b->width_run_cache = 0;
+  b->bidi_paragraph_cache = new_region_cache ();
   bset_width_table (b, Qnil);
   b->prevent_redisplay_optimizations_p = 1;
 
@@ -813,6 +814,7 @@
 
   b->newline_cache = 0;
   b->width_run_cache = 0;
+  b->bidi_paragraph_cache = new_region_cache ();
   bset_width_table (b, Qnil);
 
   name = Fcopy_sequence (name);
@@ -1957,6 +1959,11 @@
       free_region_cache (b->width_run_cache);
       b->width_run_cache = 0;
     }
+  if (b->bidi_paragraph_cache)
+    {
+      free_region_cache (b->bidi_paragraph_cache);
+      b->bidi_paragraph_cache = 0;
+    }
   bset_width_table (b, Qnil);
   unblock_input ();
   bset_undo_list (b, Qnil);
@@ -2367,6 +2374,7 @@
   current_buffer->clip_changed = 1;	other_buffer->clip_changed = 1;
   swapfield (newline_cache, struct region_cache *);
   swapfield (width_run_cache, struct region_cache *);
+  swapfield (bidi_paragraph_cache, struct region_cache *);
   current_buffer->prevent_redisplay_optimizations_p = 1;
   other_buffer->prevent_redisplay_optimizations_p = 1;
   swapfield (overlays_before, struct Lisp_Overlay *);

=== modified file 'src/buffer.h'
--- src/buffer.h	2013-07-16 21:35:45 +0000
+++ src/buffer.h	2013-08-02 08:38:14 +0000
@@ -839,9 +839,12 @@
      the character's width; if it maps a character to zero, we don't
      know what its width is.  This allows compute_motion to process
      such regions very quickly, using algebra instead of inspecting
-     each character.   See also width_table, below.  */
+     each character.   See also width_table, below.
+
+     The BIDI paragraph cache should be documented, too.  */
   struct region_cache *newline_cache;
   struct region_cache *width_run_cache;
+  struct region_cache *bidi_paragraph_cache;
 
   /* Non-zero means don't use redisplay optimizations for
      displaying this buffer.  */

=== modified file 'src/insdel.c'
--- src/insdel.c	2013-08-02 08:32:32 +0000
+++ src/insdel.c	2013-08-02 08:40:09 +0000
@@ -1873,6 +1873,10 @@
     invalidate_region_cache (current_buffer,
                              current_buffer->width_run_cache,
                              start - BEG, Z - end);
+  if (current_buffer->bidi_paragraph_cache)
+    invalidate_region_cache (current_buffer,
+                             current_buffer->bidi_paragraph_cache,
+                             start - BEG, Z - end);
 
   Vdeactivate_mark = Qt;
 }

Re: Region cache for bidi paragraphs?

[Eli Zaretskii]

> Date: Fri, 02 Aug 2013 15:11:01 +0400
> From: Dmitry Antipov <dmantipov@yandex.ru>
> CC: Emacs development discussions <emacs-devel@gnu.org>
> 
> what do you think about using region cache to speedup bidi_find_paragraph_start?

Does it give any real speedup, and if so, in what use cases?

Re: Region cache for bidi paragraphs?

[Dmitry Antipov]

On 08/02/2013 06:03 PM, Eli Zaretskii wrote:

> Does it give any real speedup, and if so, in what use cases?

My benchmarks was:

;; 0
(defun scroll-both ()
   (interactive)
   (let ((start (float-time)))
     (progn
       (goto-char (point-min))
       (dotimes (n 500) (progn (scroll-up) (redisplay)))
       (goto-char (point-max))
       (dotimes (n 500) (progn (scroll-down) (redisplay)))
       (message "Elapsed %f seconds" (- (float-time) start)))))

;; 1
(defun scroll-both-line ()
   (interactive)
   (let ((start (float-time)))
     (progn
       (goto-char (point-min))
       (dotimes (n 5000) (progn (forward-line 1) (redisplay)))
       (goto-char (point-max))
       (dotimes (n 5000) (progn (forward-line -1) (redisplay)))
       (message "Elapsed %f seconds" (- (float-time) start)))))

Input 0: xdisp.c
Input 1: ASCII text 30K lines, 1000chr/line, no paragraph separators
Input 2: ASCII text 30K lines, 1000chr/line, paragraph separator after each line

Time is in seconds as reported, smaller is better.

Input  0        1        0 cached 1 cached
-------+--------+--------+--------+-------
0      30.2     12.7     30.4     12.7
1      11.1     34.5     6.4      15.3
2      6.0      13.1     5.2      13.1
------------------------------------------

I.e. longer lines and smaller amount of paragraph separators =>
more benefits from using region cache.

Dmitry
.

Re: Region cache for bidi paragraphs?

[Eli Zaretskii]

> Date: Mon, 05 Aug 2013 09:26:37 +0400
> From: Dmitry Antipov <dmantipov@yandex.ru>
> CC: emacs-devel@gnu.org
> 
> Input 0: xdisp.c
> Input 1: ASCII text 30K lines, 1000chr/line, no paragraph separators
> Input 2: ASCII text 30K lines, 1000chr/line, paragraph separator after each line
> 
> Time is in seconds as reported, smaller is better.
> 
> Input  0        1        0 cached 1 cached
> -------+--------+--------+--------+-------
> 0      30.2     12.7     30.4     12.7
> 1      11.1     34.5     6.4      15.3
> 2      6.0      13.1     5.2      13.1
> ------------------------------------------
> 
> I.e. longer lines and smaller amount of paragraph separators =>
> more benefits from using region cache.

Thanks for the data.

The gains sound marginal to me, especially given that the use case
where the gains are tangible (Input 1, very long line and no paragraph
separators anywhere in sight) doesn't look like a frequent use case.
Even in that case you get a speedup of a few milliseconds per
redisplay cycle.

I'm not sure this is worth the extra complexity, but if Stefan thinks
otherwise, I won't object.

There's one problem with your suggestion that perhaps needs to be
fixed before this is installed: you invalidate the cache on each
modification of the buffer, so scrolling through a buffer in a mode
that has font-lock set up will constantly invalidate the cache, since
adding text properties constitutes a "modification" of the buffer
text.  When I scroll through xdisp.c, I see the breakpoint set where
you invalidate the cache in insdel.c being constantly hit whenever
Emacs scrolls some new text into view.

Since most modes have font lock nowadays, I think leaving this
unhandled will all but eliminate the gains in most use cases.

Re: Region cache for bidi paragraphs?

[Stefan Monnier]

> The gains sound marginal to me, especially given that the use case
> where the gains are tangible (Input 1, very long line and no paragraph
> separators anywhere in sight) doesn't look like a frequent use case.
> Even in that case you get a speedup of a few milliseconds per
> redisplay cycle.

I like performance improvements, but I tend to agree that in this case,
I'd first like to see some concrete use-case that benefit from it (and
"benefit" in this case should probably mean "finally keeps up while
scolling" or "makes it useable again").

So, does it help keep up with scrolling in the recent C++ example?
Or dos it make it possible to edit that 1MB file with no newlines?
Or is there some other concrete use case where it makes a tangible
difference (other than benchmarks)?

Of course, maybe in itself this patch doesn't do any such thing, but
combined with some other patches it will.  So, even if it doesn't seem
worth the trouble now, it might be worth keeping it around.


        Stefan

Re: Region cache for bidi paragraphs?

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: Dmitry Antipov <dmantipov@yandex.ru>,  emacs-devel@gnu.org
> Date: Mon, 05 Aug 2013 12:00:33 -0400
> 
> So, does it help keep up with scrolling in the recent C++ example?

For that, we will need first to avoid invalidating the cache when a
new chunk of text scrolls into view, and jit-lock marks the buffer
"modified" while fontifying it.

Re: Region cache for bidi paragraphs?

[Dmitry Antipov]

On 08/05/2013 08:52 PM, Eli Zaretskii wrote:

>> From: Stefan Monnier <monnier@iro.umontreal.ca>
>> Cc: Dmitry Antipov <dmantipov@yandex.ru>,  emacs-devel@gnu.org
>> Date: Mon, 05 Aug 2013 12:00:33 -0400
>>
>> So, does it help keep up with scrolling in the recent C++ example?

What C++ example you're talking about?

Dmitry

Re: Region cache for bidi paragraphs?

[Eli Zaretskii]

> Date: Mon, 05 Aug 2013 21:12:56 +0400
> From: Dmitry Antipov <dmantipov@yandex.ru>
> CC: Stefan Monnier <monnier@iro.umontreal.ca>, emacs-devel@gnu.org
> 
> On 08/05/2013 08:52 PM, Eli Zaretskii wrote:
> 
> >> From: Stefan Monnier <monnier@iro.umontreal.ca>
> >> Cc: Dmitry Antipov <dmantipov@yandex.ru>,  emacs-devel@gnu.org
> >> Date: Mon, 05 Aug 2013 12:00:33 -0400
> >>
> >> So, does it help keep up with scrolling in the recent C++ example?
> 
> What C++ example you're talking about?

See bug #15011, I think.  But I don't see any files attached to that,
or maybe I'm blind.

Re: Region cache for bidi paragraphs?

[Dmitry Antipov]

On 08/05/2013 08:52 PM, Eli Zaretskii wrote:

> For that, we will need first to avoid invalidating the cache when a
> new chunk of text scrolls into view, and jit-lock marks the buffer
> "modified" while fontifying it.

Eventually I decided to do r113712 and then r113713; since all
caching is disabled by default, everyone interested are pleased
to do (setq cache-long-scans t) and see what happens.

Dmitry

Re: Region cache for bidi paragraphs?

[Eli Zaretskii]

> Date: Tue, 06 Aug 2013 11:15:40 +0400
> From: Dmitry Antipov <dmantipov@yandex.ru>
> CC: Eli Zaretskii <eliz@gnu.org>, 
>  Stefan Monnier <monnier@iro.umontreal.ca>
> 
> On 08/05/2013 08:52 PM, Eli Zaretskii wrote:
> 
> > For that, we will need first to avoid invalidating the cache when a
> > new chunk of text scrolls into view, and jit-lock marks the buffer
> > "modified" while fontifying it.
> 
> Eventually I decided to do r113712 and then r113713; since all
> caching is disabled by default, everyone interested are pleased
> to do (setq cache-long-scans t) and see what happens.

Thanks.

You have renamed an existing variable.  I think this warrants a NEWS
entry, and probably also a defvaralias, to avoid breaking backward
compatibility.

Yet another redisplay question

[Dmitry Antipov]

AFAICS redisplay engine does a lot of iterator movements backward to BEGV
or forward to ZV.  From the redisplay's point of view, how much of buffer
text beyond its visible boundaries (window-start) and (window-end) we
should process to be sure that the visible part is displayed correctly?
In particular, when we're looking for the beginning of the previous line,
or the end of the current line, why not limit the search within the
visible part of text?

Dmitry

Re: Yet another redisplay question

[Eli Zaretskii]

> Date: Tue, 06 Aug 2013 20:04:23 +0400
> From: Dmitry Antipov <dmantipov@yandex.ru>
> CC: emacs-devel@gnu.org
> 
> AFAICS redisplay engine does a lot of iterator movements backward to BEGV
> or forward to ZV.

We don't currently have a way of moving the iterator backward, only
forward.  When we need to go back, we just scan through the text, and
then re-seat the iterator at the new place and re-initialize it.

> From the redisplay's point of view, how much of buffer text beyond
> its visible boundaries (window-start) and (window-end) we should
> process to be sure that the visible part is displayed correctly?

It depends on what you mean by "redisplay".  When the display engine
has already decided where window-start should be, and is just
redrawing the window, the answer is "none": it never processes any
text outside of the visible portion of text.

But in order to decide where the window should start, the display
engine many times needs to look beyond the window edges.  As a simple
example, consider a case where point was moved to some arbitrary
position outside of the window (e.g., with goto-char) -- how can the
display engine know what should be the new window-start that will
bring point back into view, when each line could be of different
height?  To do that, the display engine processes some text outside of
the window until it finds buffer position that satisfies user
requirements for this case (the various scroll-* variables).

> In particular, when we're looking for the beginning of the previous line,
> or the end of the current line, why not limit the search within the
> visible part of text?

Depends on why are we looking for the beginning of the line.
Sometimes we can just start from the window-start position, in that
case we don't need to search at all (because the window's start is
part of the window object data).  But if you want to know which
character is the first character of the line (e.g., for determining
the base direction of the paragraph for bidi display purposes), then
you must go to the beginning of the line.

Another example when you cannot stop at the beginning of the window is
when you need to start from a known horizontal position, e.g. as part
of vertical-motion: the only place in a line where the horizontal
position is known in advance is the line's beginning.

There are other cases.  Search the sources for "start_display" --
almost all of its calls are needed to find buffer positions which
satisfy some requirements, like given pixel coordinates.  Many of
these places examine text outside of the window, because at that point
it is not yet known where the window will start and end.

So to summarize, there are some cases where you cannot optimize these
searches.  Of course, looking for clever algorithms or caches that
would optimize more cases than we have now is always welcome.