* Region cache for bidi paragraphs?
@ 2013-08-02 11:11 Dmitry Antipov
2013-08-02 14:03 ` Eli Zaretskii
0 siblings, 1 reply; 12+ messages in thread
From: Dmitry Antipov @ 2013-08-02 11:11 UTC (permalink / raw)
To: Eli Zaretskii; +Cc: Emacs development discussions
[-- 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;
}
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Region cache for bidi paragraphs?
2013-08-02 11:11 Region cache for bidi paragraphs? Dmitry Antipov
@ 2013-08-02 14:03 ` Eli Zaretskii
2013-08-05 5:26 ` Dmitry Antipov
0 siblings, 1 reply; 12+ messages in thread
From: Eli Zaretskii @ 2013-08-02 14:03 UTC (permalink / raw)
To: Dmitry Antipov; +Cc: emacs-devel
> 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?
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Region cache for bidi paragraphs?
2013-08-02 14:03 ` Eli Zaretskii
@ 2013-08-05 5:26 ` Dmitry Antipov
2013-08-05 15:18 ` Eli Zaretskii
0 siblings, 1 reply; 12+ messages in thread
From: Dmitry Antipov @ 2013-08-05 5:26 UTC (permalink / raw)
To: Eli Zaretskii; +Cc: emacs-devel
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
.
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Region cache for bidi paragraphs?
2013-08-05 5:26 ` Dmitry Antipov
@ 2013-08-05 15:18 ` Eli Zaretskii
2013-08-05 16:00 ` Stefan Monnier
0 siblings, 1 reply; 12+ messages in thread
From: Eli Zaretskii @ 2013-08-05 15:18 UTC (permalink / raw)
To: Dmitry Antipov, Stefan Monnier; +Cc: emacs-devel
> 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.
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Region cache for bidi paragraphs?
2013-08-05 15:18 ` Eli Zaretskii
@ 2013-08-05 16:00 ` Stefan Monnier
2013-08-05 16:52 ` Eli Zaretskii
0 siblings, 1 reply; 12+ messages in thread
From: Stefan Monnier @ 2013-08-05 16:00 UTC (permalink / raw)
To: Eli Zaretskii; +Cc: Dmitry Antipov, emacs-devel
> 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
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Region cache for bidi paragraphs?
2013-08-05 16:00 ` Stefan Monnier
@ 2013-08-05 16:52 ` Eli Zaretskii
2013-08-05 17:12 ` Dmitry Antipov
2013-08-06 7:15 ` Dmitry Antipov
0 siblings, 2 replies; 12+ messages in thread
From: Eli Zaretskii @ 2013-08-05 16:52 UTC (permalink / raw)
To: Stefan Monnier; +Cc: dmantipov, emacs-devel
> 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.
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Region cache for bidi paragraphs?
2013-08-05 16:52 ` Eli Zaretskii
@ 2013-08-05 17:12 ` Dmitry Antipov
2013-08-05 17:17 ` Eli Zaretskii
2013-08-06 7:15 ` Dmitry Antipov
1 sibling, 1 reply; 12+ messages in thread
From: Dmitry Antipov @ 2013-08-05 17:12 UTC (permalink / raw)
To: Eli Zaretskii; +Cc: Stefan Monnier, emacs-devel
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
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Region cache for bidi paragraphs?
2013-08-05 17:12 ` Dmitry Antipov
@ 2013-08-05 17:17 ` Eli Zaretskii
0 siblings, 0 replies; 12+ messages in thread
From: Eli Zaretskii @ 2013-08-05 17:17 UTC (permalink / raw)
To: Dmitry Antipov; +Cc: monnier, emacs-devel
> 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.
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Region cache for bidi paragraphs?
2013-08-05 16:52 ` Eli Zaretskii
2013-08-05 17:12 ` Dmitry Antipov
@ 2013-08-06 7:15 ` Dmitry Antipov
2013-08-06 14:51 ` Eli Zaretskii
1 sibling, 1 reply; 12+ messages in thread
From: Dmitry Antipov @ 2013-08-06 7:15 UTC (permalink / raw)
To: emacs-devel; +Cc: Eli Zaretskii, Stefan Monnier
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
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Region cache for bidi paragraphs?
2013-08-06 7:15 ` Dmitry Antipov
@ 2013-08-06 14:51 ` Eli Zaretskii
2013-08-06 16:04 ` Yet another redisplay question Dmitry Antipov
0 siblings, 1 reply; 12+ messages in thread
From: Eli Zaretskii @ 2013-08-06 14:51 UTC (permalink / raw)
To: Dmitry Antipov; +Cc: monnier, emacs-devel
> 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.
^ permalink raw reply [flat|nested] 12+ messages in thread
* Yet another redisplay question
2013-08-06 14:51 ` Eli Zaretskii
@ 2013-08-06 16:04 ` Dmitry Antipov
2013-08-06 16:42 ` Eli Zaretskii
0 siblings, 1 reply; 12+ messages in thread
From: Dmitry Antipov @ 2013-08-06 16:04 UTC (permalink / raw)
To: Eli Zaretskii; +Cc: emacs-devel
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
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: Yet another redisplay question
2013-08-06 16:04 ` Yet another redisplay question Dmitry Antipov
@ 2013-08-06 16:42 ` Eli Zaretskii
0 siblings, 0 replies; 12+ messages in thread
From: Eli Zaretskii @ 2013-08-06 16:42 UTC (permalink / raw)
To: Dmitry Antipov; +Cc: emacs-devel
> 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.
^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~2013-08-06 16:42 UTC | newest]
Thread overview: 12+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2013-08-02 11:11 Region cache for bidi paragraphs? Dmitry Antipov
2013-08-02 14:03 ` Eli Zaretskii
2013-08-05 5:26 ` Dmitry Antipov
2013-08-05 15:18 ` Eli Zaretskii
2013-08-05 16:00 ` Stefan Monnier
2013-08-05 16:52 ` Eli Zaretskii
2013-08-05 17:12 ` Dmitry Antipov
2013-08-05 17:17 ` Eli Zaretskii
2013-08-06 7:15 ` Dmitry Antipov
2013-08-06 14:51 ` Eli Zaretskii
2013-08-06 16:04 ` Yet another redisplay question Dmitry Antipov
2013-08-06 16:42 ` Eli Zaretskii
Code repositories for project(s) associated with this public inbox
https://git.savannah.gnu.org/cgit/emacs.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).