Inefficient redisplay

Inefficient redisplay

[Stefan Monnier]

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

I'm still playing around with my nhexl-mode attempt and I'm encournering
some serious performance problems.  One of them seems to be linked to
the fact that the redisplay code somehow seems to treat nhexl-mode's
buffers as one single long-line.

This is probably because all the \n have a display property on them that
makes them appear as an "␊" char.  The buffer's display does have
line separators in the overlays's before-strings, but apparently the
redisplay doesn't pay enough attention to them to notice that they can
be used to stop the search for the beginning of a line.

One related problem (which can be witnessed firsthand from Elisp) is
that all the text between point-min and the window's point is jit-locked
(even though only the text visible in the window should need to be
jit-locked).

Try the code below in the following way:

  % emacs -Q -l .../nhexl-mode.el <someasciifile> -f nhexl-mode
  M-x trace-function-background RET jit-lock-function RET
  M-: (display-buffer "*trace-output*") RET
  C-v C-v C-v C-v C-v
  M-: (put-text-property (point-min) (point-max) 'fontified nil)
  <move mouse to the other frame>

You should now see that jit-lock-function was called for positions 1,
508, 1032, and a few more, even though these are all before window-start.

This makes nhexl-mode completely unusable except on small buffers
(whereas some of the motivation for nhexl-mode was to have an
hex-editor that works even for very large files).


        Stefan



[-- Attachment #2: nhexl-mode.el --]
[-- Type: application/emacs-lisp, Size: 10945 bytes --]

Re: Inefficient redisplay

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Date: Mon, 12 Apr 2010 00:34:05 -0400
> 
> I'm still playing around with my nhexl-mode attempt and I'm encournering
> some serious performance problems.  One of them seems to be linked to
> the fact that the redisplay code somehow seems to treat nhexl-mode's
> buffers as one single long-line.
> 
> This is probably because all the \n have a display property on them that
> makes them appear as an "␊" char.  The buffer's display does have
> line separators in the overlays's before-strings, but apparently the
> redisplay doesn't pay enough attention to them to notice that they can
> be used to stop the search for the beginning of a line.

What do you mean by ``stop the search''?  Redisplay does not search
for newlines, but when they are encountered (as part of normal
iteration through buffer text and any `display' properties and overlay
strings that are found along the way), it treats them as the end of
display line.  It doesn't (or shouldn't) matter that the newline comes
from an overlay as opposed to a buffer.  At least that's the theory.

Are you saying that in the following code fragment from display_line,
the main workhorse of displaying a single screen line, the condition
is never true in your case?

      /* Is this a line end?  If yes, we're also done, after making
	 sure that a non-default face is extended up to the right
	 margin of the window.  */
      if (ITERATOR_AT_END_OF_LINE_P (it))
	{
	  int used_before = row->used[TEXT_AREA];

	  row->ends_in_newline_from_string_p = STRINGP (it->object);

(There are a few more places where the code tests for the end of a
line.)

> One related problem (which can be witnessed firsthand from Elisp) is
> that all the text between point-min and the window's point is jit-locked
> (even though only the text visible in the window should need to be
> jit-locked).

I believe this is because of the following heuristics in jit-lock.el:

	   ;; Decide which range of text should be fontified.
	   ;; The problem is that START and NEXT may be in the
	   ;; middle of something matched by a font-lock regexp.
	   ;; Until someone has a better idea, let's start
	   ;; at the start of the line containing START and
	   ;; stop at the start of the line following NEXT.
	   (goto-char next)  (setq next (line-beginning-position 2))
	   (goto-char start) (setq start (line-beginning-position))

> This makes nhexl-mode completely unusable except on small buffers

I suggest, first of all, to understand why the display engine misses
the newlines you say you have in the before-strings.  The Emacs
display code is known to behave very unfriendly when lines are too
long, so my first advice would be not to do what hurts.

Re: Inefficient redisplay

[Stefan Monnier]

>> One related problem (which can be witnessed firsthand from Elisp) is
>> that all the text between point-min and the window's point is jit-locked
>> (even though only the text visible in the window should need to be
>> jit-locked).

> I believe this is because of the following heuristics in jit-lock.el:

> 	   ;; Decide which range of text should be fontified.
> 	   ;; The problem is that START and NEXT may be in the
> 	   ;; middle of something matched by a font-lock regexp.
> 	   ;; Until someone has a better idea, let's start
> 	   ;; at the start of the line containing START and
> 	   ;; stop at the start of the line following NEXT.
> 	   (goto-char next)  (setq next (line-beginning-position 2))
> 	   (goto-char start) (setq start (line-beginning-position))

No, the trace I showed was for jit-lock-function which comes before this
piece of code (jit-lock-function calls jit-lock-fontify-now).

And even if that had some impact, it wouldn't explain the behavior,
since line-beginning-position works fine: it find the buffer's \n chars
and stops there, oblivious to the fact that they have a `display'
property which makes them appear differently.

>> This makes nhexl-mode completely unusable except on small buffers
> I suggest, first of all, to understand why the display engine misses
> the newlines you say you have in the before-strings.

Given my lack of understanding of the redisplay code, this is
more difficult.

> The Emacs display code is known to behave very unfriendly when lines
> are too long, so my first advice would be not to do what hurts.

The buffer's actual text doesn't have long lines, and the display
doesn't have long lines either, so it really *should* work fine.

And of course there isn't much I can do about it: the whole point of the
exercise is to make a hexl-mode variant which works only by modifying
the display but not the buffer's text (so it doesn't mess with the
undo-list, etc...).


        Stefan

Re: Inefficient redisplay

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: emacs-devel@gnu.org
> Date: Mon, 12 Apr 2010 15:28:22 -0400
> 
> And even if that had some impact, it wouldn't explain the behavior,
> since line-beginning-position works fine: it find the buffer's \n chars
> and stops there, oblivious to the fact that they have a `display'
> property which makes them appear differently.

Yes, right.  I was confused.

> >> This makes nhexl-mode completely unusable except on small buffers
> > I suggest, first of all, to understand why the display engine misses
> > the newlines you say you have in the before-strings.
> 
> Given my lack of understanding of the redisplay code, this is
> more difficult.

I could try, but is it possible to have a test case simpler than the
whole package?  Something like one or two lines of text with whatever
properties and overlays are needed to exhibit the problem?

Also, what _is_ the problem, exactly?  Is that only that jit-lock
misbehaves, or is there something else?  You said in your original
mail that "redisplay code somehow seems to treat nhexl-mode's buffers
as one single long-line", but what are the symptoms of this?

> > The Emacs display code is known to behave very unfriendly when lines
> > are too long, so my first advice would be not to do what hurts.
> 
> The buffer's actual text doesn't have long lines, and the display
> doesn't have long lines either, so it really *should* work fine.

The display engine does not see newlines that are covered by `display'
properties and overlay strings, it sees the contents of the strings
instead.  So if it _really_ misses the newlines in the
`before-strings' you set up, it will behave as if the buffer had one
long line.

The question is: how and why (and whether) does it miss those
newlines.

Re: Inefficient redisplay

[Stefan Monnier]

>> >> This makes nhexl-mode completely unusable except on small buffers
>> > I suggest, first of all, to understand why the display engine misses
>> > the newlines you say you have in the before-strings.
>> Given my lack of understanding of the redisplay code, this is
>> more difficult.
> I could try, but is it possible to have a test case simpler than the
> whole package?  Something like one or two lines of text with whatever
> properties and overlays are needed to exhibit the problem?

I haven't gotten down to that yet.

> Also, what _is_ the problem, exactly?  Is that only that jit-lock
> misbehaves, or is there something else?  You said in your original
> mail that "redisplay code somehow seems to treat nhexl-mode's buffers
> as one single long-line", but what are the symptoms of this?

Several problems:
1- it seems that I'm not able to have position N displayed without
   having all positions 1..N with fontified set to non-nil (I.e. I have
   to have all the prefix of the buffer fontified).  That's a major
   problem since I use overlays: if N is large, that implies a large
   number of overlays, which implies serious performance problems.
2- performance sucks.  Maybe it's because of 1, but it's probably not
   only due to that, because performance is better when I go back to the
   beginning of the buffer (which doesn't remove overlays).

>> > The Emacs display code is known to behave very unfriendly when lines
>> > are too long, so my first advice would be not to do what hurts.
>> The buffer's actual text doesn't have long lines, and the display
>> doesn't have long lines either, so it really *should* work fine.
> The display engine does not see newlines that are covered by `display'
> properties and overlay strings, it sees the contents of the strings
> instead.  So if it _really_ misses the newlines in the
> `before-strings' you set up, it will behave as if the buffer had one
> long line.

The behavior I see seems consistent with a situation where the redisplay
"doesn't see" the newlines in the before-strings (although it does
display them correctly).

> The question is: how and why (and whether) does it miss those
> newlines.

Yes, we're still in the dark here.


        Stefan

Re: Inefficient redisplay

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: emacs-devel@gnu.org
> Date: Mon, 12 Apr 2010 17:46:21 -0400
> 
> > Also, what _is_ the problem, exactly?  Is that only that jit-lock
> > misbehaves, or is there something else?  You said in your original
> > mail that "redisplay code somehow seems to treat nhexl-mode's buffers
> > as one single long-line", but what are the symptoms of this?
> 
> Several problems:
> 1- it seems that I'm not able to have position N displayed without
>    having all positions 1..N with fontified set to non-nil (I.e. I have
>    to have all the prefix of the buffer fontified).  That's a major
>    problem since I use overlays: if N is large, that implies a large
>    number of overlays, which implies serious performance problems.
> 2- performance sucks.  Maybe it's because of 1, but it's probably not
>    only due to that, because performance is better when I go back to the
>    beginning of the buffer (which doesn't remove overlays).

I'm not sure I see the root cause yet, or even the most expensive
part, but one thing seems to be quite clear: the way you move overlays
disables quite a few of redisplay optimizations.  For example, if I
just move cursor, in a normal buffer redisplay calls
try_cursor_movement, and that's it.  But in a buffer under nhexl-mode,
try_cursor_movement is not even called because of this condition:

  current_matrix_up_to_date_p
    = (!NILP (w->window_end_valid)
       && !current_buffer->clip_changed
       && !current_buffer->prevent_redisplay_optimizations_p
       && XFASTINT (w->last_modified) >= MODIFF
       && XFASTINT (w->last_overlay_modified) >= OVERLAY_MODIFF);

It seems like the games you play in post-command-hook constantly
increment OVERLAY_MODIFF, and that prevents this optimization.
Instead, redisplay invokes try_window_id, which promptly gives up
here:

  if (current_buffer->clip_changed
      || current_buffer->prevent_redisplay_optimizations_p)
    GIVE_UP (3);

because someone turned on the prevent_redisplay_optimizations_p flag
(I don't yet know why).  Then try_window is called, which is much
heavier, and it does the job.  This happens for every cursor movement!

Why do you need to modify overlays in a post-command-hook?  That seems
to be at least part of the trouble.

Re: Inefficient redisplay

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Date: Mon, 12 Apr 2010 17:46:21 -0400
> Cc: emacs-devel@gnu.org
> 
> Several problems:
> 1- it seems that I'm not able to have position N displayed without
>    having all positions 1..N with fontified set to non-nil (I.e. I have
>    to have all the prefix of the buffer fontified).  That's a major
>    problem since I use overlays: if N is large, that implies a large
>    number of overlays, which implies serious performance problems.
> 2- performance sucks.  Maybe it's because of 1, but it's probably not
>    only due to that, because performance is better when I go back to the
>    beginning of the buffer (which doesn't remove overlays).

I don't think the amount of overlays is the reason for 2.  My evidence
is that if I invoke nhexl-flush-overlays manually, performance does
not improve a bit.

I started looking at what nhexl-mode does, and I'm puzzled by the
logic of its design.  Why do you arrange for nhexl-jit to be called
via fontification-functions, if you also have it on post-command-hook?
Is one of them a remnant of an idea that was rejected? if so, which
one?  If you really do need both, can you explain why?

If invoking nhexl-jit via fontification-functions is really needed,
then where do you expect redisplay to invoke it?  IOW, if you make
assumptions regarding the value of START and END arguments passed to
nhexl-jit by redisplay, what are those assumptions?

> The behavior I see seems consistent with a situation where the redisplay
> "doesn't see" the newlines in the before-strings

I don't see any sign that redisplay "doesn't see" the newlines.  The
mere fact that you see several lines on the screen is the proof that
redisplay did see the newlines: that's how it knows that one line ends
and another begins.

I think performance "sucks" for a different reason, but I don't yet
know what it is.

Re: Inefficient redisplay

[Stefan Monnier]

> I started looking at what nhexl-mode does, and I'm puzzled by the
> logic of its design.  Why do you arrange for nhexl-jit to be called
> via fontification-functions, if you also have it on post-command-hook?
> Is one of them a remnant of an idea that was rejected? if so, which
> one?  If you really do need both, can you explain why?

AFAIK I need both: nhexl-jit is used to add the hexdump lines to all the
text that's displayed, whereas the post-command-hook is used to update
the cursor highlighting (which is why it only updates the overlays on
the old point position and the new point position).

I guess the cursor updating could be more efficient by only changing the
`face' text-properties on the overlay's before strings rather than
building new overlays from scratch.  I haven't tried that yet, but I'm
afraid this will lead to problems because the redisplay code won't
notice that a before-string was modified so it may forget to redisplay
the corresponding part of the screen.

> If invoking nhexl-jit via fontification-functions is really needed,
> then where do you expect redisplay to invoke it?  IOW, if you make
> assumptions regarding the value of START and END arguments passed to
> nhexl-jit by redisplay, what are those assumptions?

I don't make any particular assumptions about start and end (at least
not consciously).

>> The behavior I see seems consistent with a situation where the redisplay
>> "doesn't see" the newlines in the before-strings
> I don't see any sign that redisplay "doesn't see" the newlines.

I only say that because the performance behavior is very similar to what
we get in long-single-line buffers.

> The mere fact that you see several lines on the screen is the proof
> that redisplay did see the newlines: that's how it knows that one line
> ends and another begins.

Yes, clearly it sees them in this sense.  


        Stefan

Re: Inefficient redisplay

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: emacs-devel@gnu.org
> Date: Thu, 15 Apr 2010 00:38:16 -0400
> 
> AFAIK I need both: nhexl-jit is used to add the hexdump lines to all the
> text that's displayed, whereas the post-command-hook is used to update
> the cursor highlighting (which is why it only updates the overlays on
> the old point position and the new point position).

post-command-hook also invokes nhexl-jit, albeit with different
arguments.  So you may end up doing double work.

> I guess the cursor updating could be more efficient by only changing the
> `face' text-properties on the overlay's before strings rather than
> building new overlays from scratch.  I haven't tried that yet, but I'm
> afraid this will lead to problems because the redisplay code won't
> notice that a before-string was modified so it may forget to redisplay
> the corresponding part of the screen.

Is it really the case that modifying an overlay string does not
trigger redisplay?  That'd be a bug.

> > If invoking nhexl-jit via fontification-functions is really needed,
> > then where do you expect redisplay to invoke it?  IOW, if you make
> > assumptions regarding the value of START and END arguments passed to
> > nhexl-jit by redisplay, what are those assumptions?
> 
> I don't make any particular assumptions about start and end (at least
> not consciously).

But then you should be aware that there's nothing in
fontification-functions or in the redisplay that makes sure they are
only invoked on the displayed portion of the buffer.  As your C-v
experiment proves, it really happens that nhexl-jit is invoked on
portions of the buffer that are outside the window.  And since
nhexl-jit does not validate its arguments against window's first and
last line, it ends up doing unnecessary work.

> >> The behavior I see seems consistent with a situation where the redisplay
> >> "doesn't see" the newlines in the before-strings
> > I don't see any sign that redisplay "doesn't see" the newlines.
> 
> I only say that because the performance behavior is very similar to what
> we get in long-single-line buffers.

I have a few ideas why you get the performance hit, and I will look
into them in a day or two.

Re: Inefficient redisplay

[Stefan Monnier]

> post-command-hook also invokes nhexl-jit, albeit with different
> arguments.  So you may end up doing double work.

That is true.  But I don't know how to avoid it, and I don't think this
redundancy is a big problem in practice.

> Is it really the case that modifying an overlay string does not
> trigger redisplay?  That'd be a bug.

If it works I don't know how it's implemented.  But I haven't actually
tried it anyway.

>> > If invoking nhexl-jit via fontification-functions is really needed,
>> > then where do you expect redisplay to invoke it?  IOW, if you make
>> > assumptions regarding the value of START and END arguments passed to
>> > nhexl-jit by redisplay, what are those assumptions?
>> 
>> I don't make any particular assumptions about start and end (at least
>> not consciously).

> But then you should be aware that there's nothing in
> fontification-functions or in the redisplay that makes sure they are
> only invoked on the displayed portion of the buffer.

Indeed, and the nhexl-jit part of the code itself doesn't make any such
assumption: it just fontifies whatever jit-lock deems useful/necessary.

The part where I make such an assumption (which turns out to be
unwarranted because of the bug we're tracking) is in
nhexl-flush-overlays where I assume that I can throw away the overlays
that are currently not displayed without causing them to be immediately
rebuilt by jit-lock.

> As your C-v experiment proves, it really happens that nhexl-jit is
> invoked on portions of the buffer that are outside the window.
> And since nhexl-jit does not validate its arguments against window's
> first and last line, it ends up doing unnecessary work.

When jit-lock asks for part of a buffer to be fontified, it would be
a bug for nhexl-jit (or font-lock-fontify-buffer for that matter) to not
fontify it (because the corresponding piece of text is then labeled as
`fontified' and if it gets displayed later on jit-lock won't be
triggered so nhexl-jit won't have a chance to change its mind and
fontify it after all).
So it's not up to nhexl-jit to decide whether it's necessary or not.


        Stefan