redisplay - very long lines

redisplay - very long lines

[David Reitter]

The redisplay code seems to be unable to deal efficiently with very  
long lines, that is, lines that go beyond the currently displayed  
window.

This was pointed out by a blogger who wanted to abuse Emacs to make a  
quick change to a binary file.  I could reproduce the problem using a  
17MB binary file, which loaded and displayed fine initially.  I then  
removed all newlines from the file, upon which redisplay gets  
unbearably slow (minutes to redisplay once).

Setting truncate-lines makes things faster, but not to the point where  
one could work.

This is in version 22 and 23.  The profiler output (Shark) is below.   
Would it be possible to add a termination condition in move_it_to to  
stop after leaving the window vertically or horizontally (with  
truncate-lines)?  Or simply use a large enough threshold?



	0.0%	99.8%	Emacs	start	
	0.0%	99.8%	Emacs	 main	
	0.0%	99.8%	Emacs	  Frecursive_edit	
	0.0%	99.8%	Emacs	   recursive_edit_1	
	0.0%	99.8%	Emacs	    command_loop	
	0.0%	99.8%	Emacs	     internal_catch	
	0.0%	99.8%	Emacs	      command_loop_2	
	0.0%	99.8%	Emacs	       internal_condition_case	
	0.0%	99.8%	Emacs	        command_loop_1	
	0.0%	99.8%	Emacs	         call3	
	0.0%	99.8%	Emacs	          Ffuncall	
	0.0%	99.8%	Emacs	           Fcall_interactively	
	0.0%	99.8%	Emacs	            apply1	
	0.0%	99.8%	Emacs	             Fapply	
	0.0%	99.8%	Emacs	              Ffuncall	
	0.0%	99.8%	Emacs	               funcall_lambda	
	0.0%	99.8%	Emacs	                Fbyte_code	
	0.0%	99.8%	Emacs	                 Ffuncall	
	0.0%	99.8%	Emacs	                  funcall_lambda	
	0.0%	99.8%	Emacs	                   Fbyte_code	
	0.0%	99.8%	Emacs	                    Ffuncall	
	0.0%	99.8%	Emacs	                     funcall_lambda	
	0.0%	99.8%	Emacs	                      Fbyte_code	
	0.0%	99.8%	Emacs	                       Ffuncall	
	0.0%	99.8%	Emacs	                        Freplace_match	
	0.0%	99.8%	Emacs	                         replace_range	
	0.0%	99.8%	Emacs	                          signal_after_change	
	0.0%	99.8%	Emacs	                           run_hook_with_args	
	0.0%	99.8%	Emacs	                            Ffuncall	
	0.0%	99.8%	Emacs	                             Fgarbage_collect	
	0.0%	99.8%	Emacs	                              truncate_undo_list	
	0.0%	99.8%	Emacs	                               call1	
	0.0%	99.8%	Emacs	                                Ffuncall	
	0.0%	99.8%	Emacs	                                 funcall_lambda	
	0.0%	99.8%	Emacs	                                  Fbyte_code	
	0.0%	99.8%	Emacs	                                   Ffuncall	
	0.0%	99.8%	Emacs	                                    funcall_lambda	
	0.0%	99.8%	Emacs	                                     Fbyte_code	
	0.0%	99.8%	Emacs	                                      Ffuncall	
	0.0%	99.8%	Emacs	                                       funcall_lambda	
	0.0%	99.8%	Emacs	                                        Fbyte_code	
	0.0%	99.8%	Emacs	                                         Ffuncall	
	0.0%	99.8%	Emacs	                                          Fredisplay	
	0.0%	99.8%	Emacs	                                            
redisplay_preserve_echo_area	
	0.0%	99.8%	Emacs	                                             
redisplay_internal	
	0.0%	99.8%	Emacs	                                              
redisplay_windows	
	0.0%	99.8%	Emacs	                                               
redisplay_windows	
	0.0%	99.8%	Emacs	                                                
internal_condition_case_1	
	0.0%	99.8%	Emacs	                                                 
redisplay_window_0	
	0.0%	99.8%	Emacs	                                                  
redisplay_window	
	0.0%	99.8%	Emacs	                                                   
move_it_vertically_backward	
	0.0%	62.3%	Emacs	                                                    
move_it_to	
	8.9%	62.0%	Emacs	                                                     
move_it_in_display_line_to	
	14.2%	30.5%	 
Emacs	                                                      
x_produce_glyphs	
	2.1%	9.3%	Emacs	                                                       
get_per_char_metric	
	7.1%	7.1%	 
Emacs	                                                        
nsfont_text_extents	
	3.3%	6.5%	Emacs	                                                       
get_char_face_and_encoding	
	0.5%	0.5%	Emacs	                                                       
take_vertical_position_into_account	
	0.1%	0.1%	Emacs	                                                       
nsfont_text_extents	
	8.3%	17.5%	Emacs	                                                      
get_next_display_element	
	3.5%	4.4%	Emacs	                                                      
set_iterator_to_next	
	0.4%	0.4%	Emacs	                                                      
next_element_from_display_vector	
	0.1%	0.1%	Emacs	                                                      
next_element_from_buffer	
	0.1%	0.1%	Emacs	                                                      
get_char_face_and_encoding	
	0.0%	0.0%	Emacs	                                                      
char_table_ref	
	0.1%	0.1%	Emacs	                                                     
set_iterator_to_next	
	0.1%	0.1%	Emacs	                                                     
x_produce_glyphs	
	0.1%	0.1%	Emacs	                                                     
get_next_display_element	
	0.0%	0.0%	Emacs	                                                     
recenter_overlay_lists	
	0.0%	37.3%	Emacs	                                                    
move_it_by_lines	
	0.0%	0.1%	Emacs	                                                    
back_to_previous_visible_line_start	
	0.0%	0.0%	Emacs	                                                    
line_bottom_y	
	0.0%	0.0%	Emacs	                                                   
try_window	
	0.0%	0.0%	Emacs	                                                   
move_it_by_lines	
	0.0%	0.0%	Emacs	                                              
prepare_menu_bars	
	0.1%	0.1%	mach_kernel	lo_alltraps	
	0.0%	0.0%	mach_kernel	i386_astintr	
	0.0%	0.0%	mach_kernel	lo_unix_scall	
	0.0%	0.0%	mach_kernel	IOWorkLoop::threadMain()	
	0.0%	0.0%	mach_kernel	thread_continue	
	0.0%	0.0%	mach_kernel	ml_set_interrupts_enabled	
	0.0%	0.0%	mach_kernel	lo_mach_scall	

Re: redisplay - very long lines

[Eli Zaretskii]

> From: David Reitter <david.reitter@gmail.com>
> Date: Mon, 16 Feb 2009 08:44:23 -0500
> 
> The redisplay code seems to be unable to deal efficiently with very  
> long lines, that is, lines that go beyond the currently displayed  
> window.

This is a known limitation of the Emacs display engine, but IIRC it
has nothing to do with display margins.  The same slowdown happens if
your display is as wide as the longest line.

> Would it be possible to add a termination condition in move_it_to to  
> stop after leaving the window vertically or horizontally (with  
> truncate-lines)?

If we can tolerate an incorrect display, maybe.  The invisible part of
the line could in principle include characters and faces whose
presence may have global effects on the rest of the displayed portion,
such as faces that use larger fonts, to say nothing of inline images.

But it's been a while since I last took a good look at display code,
so perhaps I'm misremembering something, or maybe things changed.

Re: redisplay - very long lines

[David Reitter]

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

On 16 Feb 2009, at 14:27, Eli Zaretskii wrote:
>
>> Would it be possible to add a termination condition in move_it_to to
>> stop after leaving the window vertically or horizontally (with
>> truncate-lines)?
>
> If we can tolerate an incorrect display, maybe.  The invisible part of
> the line could in principle include characters and faces whose
> presence may have global effects on the rest of the displayed portion,
> such as faces that use larger fonts, to say nothing of inline images.


Are such consequences wanted even if the line continues beyond the  
window vertically (i.e. truncate-lines == nil || word-wrap != nil)?

I can see why you might want to increase line height in case there is  
a high glyph or an inline image, but I could equally see the argument  
for displaying as many lines as possible and only increasing line  
heights when the user scrolls horizontally and the glyph is made  
visible.

If this redisplay issue is all that hinders users from editing such  
files (e.g., XML without newlines), fixing it would be a good idea  
IMHO.   It seems to me that Emacs handles large files quite well  
otherwise - loading and search&replace were blazing fast when I tried  
it.

Also, note that the new word-wrap feature means that users will more  
often deal with long "lines".







[-- Attachment #2: smime.p7s --]
[-- Type: application/pkcs7-signature, Size: 2193 bytes --]

Re: redisplay - very long lines

[Eli Zaretskii]

> Cc: emacs-devel@gnu.org
> From: David Reitter <david.reitter@gmail.com>
> Date: Mon, 16 Feb 2009 18:02:57 -0500
> 
> > If we can tolerate an incorrect display, maybe.  The invisible part of
> > the line could in principle include characters and faces whose
> > presence may have global effects on the rest of the displayed portion,
> > such as faces that use larger fonts, to say nothing of inline images.
> 
> 
> Are such consequences wanted even if the line continues beyond the  
> window vertically (i.e. truncate-lines == nil || word-wrap != nil)?

Sorry, I don't understand: which consequences?  I think we want a
correct display under all supported varieties of display-related
settings.

> I could equally see the argument for displaying as many lines as
> possible and only increasing line heights when the user scrolls
> horizontally and the glyph is made visible.

That'd be horrible, I think: display jumping back and forth as point
moves horizontally.

> If this redisplay issue is all that hinders users from editing such  
> files (e.g., XML without newlines), fixing it would be a good idea  
> IMHO.

I agree.  If someone volunteers to remove this limitation or make it
less painful, they'll have my support.  But I don't think leaving the
display in so blatantly incorrect state is a way to do it.

Re: redisplay - very long lines

[Stefan Monnier]

>> I could equally see the argument for displaying as many lines as
>> possible and only increasing line heights when the user scrolls
>> horizontally and the glyph is made visible.

> That'd be horrible, I think: display jumping back and forth as point
> moves horizontally.

This would only happen with truncated lines, not with wrapped
lines, right?  So we (c|sh)ould at least do it for wrapped lines.
That should cover 99.99% of the cases where unbearably long lines make
Emacs too slow (if they're really that long, you probably want to wrap
them rather than truncate them).

[ Also, I'd much rather see occasional jumping than unbearably
  slow display.  In many cases (e.g. unibyte fundamental-mode for binary
  files), the likelihood of varying line height is pretty low. ]


        Stefan

Re: redisplay - very long lines

[grischka]

> > Would it be possible to add a termination condition in move_it_to to
> > stop after leaving the window vertically or horizontally (with
> > truncate-lines)?
>
> If we can tolerate an incorrect display, maybe.  The invisible part of
> the line could in principle include characters and faces whose
> presence may have global effects on the rest of the displayed portion,
> such as faces that use larger fonts, to say nothing of inline images.

That is not a necessary consequence at all.

After all faces and images don't come fallen from outer space into
the text but if they exist then it was the emacs program itself that
has put them there.  So instead of scanning lines each time it could
as well just remember where and how big they are.

Re: redisplay - very long lines

[Eli Zaretskii]

> Date: Tue, 17 Feb 2009 18:16:10 +0100
> From: grischka <grishka@gmx.de>
> CC:  emacs-devel@gnu.org
> 
> > If we can tolerate an incorrect display, maybe.  The invisible part of
> > the line could in principle include characters and faces whose
> > presence may have global effects on the rest of the displayed portion,
> > such as faces that use larger fonts, to say nothing of inline images.
> 
> That is not a necessary consequence at all.
> 
> After all faces and images don't come fallen from outer space into
> the text but if they exist then it was the emacs program itself that
> has put them there.  So instead of scanning lines each time it could
> as well just remember where and how big they are.

AFAIU, you are talking about a complete redesign and rewrite not only
of the Emacs display engine, but also of one of the most important
parts of its top-level design, because in the current design code that
modifies buffers and code that displays them are almost completely
decoupled, i.e. there's almost no control flow between them, and the
only data flow is thru the buffer text itself.

IOW, under the current design, Lisp application code modifies buffers,
and then, when Emacs is idle, redisplay kicks in, walks the buffers,
decides which parts need to be redisplayed (by comparing the current
and the new display contents), and finally redraws those parts.  This
way, the code that works with buffer text knows (almost) nothing about
display, and the code that displays knows (almost) nothing about
editing.

Re: redisplay - very long lines

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: David Reitter <david.reitter@gmail.com>,  emacs-devel@gnu.org
> Date: Tue, 17 Feb 2009 08:40:36 -0500
> 
> >> I could equally see the argument for displaying as many lines as
> >> possible and only increasing line heights when the user scrolls
> >> horizontally and the glyph is made visible.
> 
> > That'd be horrible, I think: display jumping back and forth as point
> > moves horizontally.
> 
> This would only happen with truncated lines, not with wrapped
> lines, right?

If by ``wrapped lines'' you mean continuation lines, then (AFAIK) we
still need to walk to the end of a line before we are able to display
it and all the lines after it.  If by ``wrapped lines'' you mean
something else, perhaps that belongs to the recent features whose
effect on display engine I didn't yet have time to grasp, so I cannot
answer the question.

> [ Also, I'd much rather see occasional jumping than unbearably
>   slow display.  In many cases (e.g. unibyte fundamental-mode for binary
>   files), the likelihood of varying line height is pretty low. ]

[How come you are suddenly in favor of unibyte operations?]

FWIW, I think editing binary files other than via hexl is playing with
fire, anyway.  But that's me.

Re: redisplay - very long lines

[David Reitter]

On 17 Feb 2009, at 14:41, Eli Zaretskii wrote:
> If by ``wrapped lines'' you mean continuation lines, then (AFAIK) we
> still need to walk to the end of a line before we are able to display
> it and all the lines after it.  If by ``wrapped lines'' you mean
> something else, perhaps that belongs to the recent features whose
> effect on display engine I didn't yet have time to grasp, so I cannot
> answer the question.

I understood Stefan to refer to soft-wrapped (`word-wrap') lines,  
which necessitate the optimization we're talking about.

Displaying any lines "after it" would not be relevant, because we'd  
stop processing the line if the end of the portion of the buffer is  
reached that is shown in the window.

As for displaying the actual line (wrapped): can you give an example  
how the previous visual lines of a line are affected something that  
could come afterwards?
(I'm not doubting you, I just want to understand.)


>> [ Also, I'd much rather see occasional jumping than unbearably
>>  slow display.  In many cases (e.g. unibyte fundamental-mode for  
>> binary
>>  files), the likelihood of varying line height is pretty low. ]
>
> [How come you are suddenly in favor of unibyte operations?]
>
> FWIW, I think editing binary files other than via hexl is playing with
> fire, anyway.  But that's me.

It is, but Emacs shouldn't slow down to the point where undoing the  
find-file operation is impossible.
Also, I gave the example of XML files w/o newlines. 

Re: redisplay - very long lines

[Stefan Monnier]

>> This would only happen with truncated lines, not with wrapped
>> lines, right?
> If by ``wrapped lines'' you mean continuation lines, then (AFAIK) we

Yes, I meant "overly long, but not truncated".  Whether the wrapping is
done at a word boundary or at a char boundary shouldn't make much
difference in this respect.

> still need to walk to the end of a line before we are able to display
> it and all the lines after it.

In the above, when you say "line" do you mean "visual line" or "textual
line"?  IIUC we need to walk till the end of the visual line, but not
till the end of the textual line, so that shouldn't cause a slowdown
proportional to the length of the textual line.

>> [ Also, I'd much rather see occasional jumping than unbearably
>> slow display.  In many cases (e.g. unibyte fundamental-mode for binary
>> files), the likelihood of varying line height is pretty low. ]
> [How come you are suddenly in favor of unibyte operations?]

I'm not in favor of it, but binary files seem to be the most common
example of data where lines can grow to insane length.  And these are
better handled in unibyte buffers.

> FWIW, I think editing binary files other than via hexl is playing with
> fire, anyway.  But that's me.

Agreed, but if the file is sufficiently large (as is common for binary
files), hexl is impractical.


        Stefan

Re: redisplay - very long lines

[Eli Zaretskii]

> From: David Reitter <david.reitter@gmail.com>
> Date: Tue, 17 Feb 2009 16:21:48 -0500
> Cc: Stefan Monnier <monnier@iro.umontreal.ca>, emacs-devel@gnu.org
> 
> As for displaying the actual line (wrapped): can you give an example  
> how the previous visual lines of a line are affected something that  
> could come afterwards?

I thought I did: what if there's an inline image there? the next line
would then have to be pushed downwards to where the image's display
ends.

Or am I misunderstanding what you are asking?

Re: redisplay - very long lines

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: david.reitter@gmail.com,  emacs-devel@gnu.org
> Date: Tue, 17 Feb 2009 21:26:25 -0500
> 
> > still need to walk to the end of a line before we are able to display
> > it and all the lines after it.
> 
> In the above, when you say "line" do you mean "visual line" or "textual
> line"?  IIUC we need to walk till the end of the visual line, but not
> till the end of the textual line, so that shouldn't cause a slowdown
> proportional to the length of the textual line.

I thought we walked to the end of the textual line, but maybe I'm
misremembering what redisplay does.

Re: redisplay - very long lines

[David Reitter]

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

On 17 Feb 2009, at 23:09, Eli Zaretskii wrote:
>> As for displaying the actual line (wrapped): can you give an example
>> how the previous visual lines of a line are affected something that
>> could come afterwards?
>
> I thought I did: what if there's an inline image there? the next line
> would then have to be pushed downwards to where the image's display
> ends.
>
> Or am I misunderstanding what you are asking?

I think you are.  I was thinking about the truncate-lines==nil or word- 
wrap==t case.  Maybe I didn't

The next visual line would have to be pushed downward, but I don't see  
how it would affect the visual lines resulting from the current buffer  
line.
Also, the next visual line isn't visible anyways because it is beyond  
the last displayed line.  We're proposing to stop processing a buffer  
line when we have left the portion of the buffer that is currently  
visible in the window.

(The truncate-lines==t case is something else of course.)

[-- Attachment #2: smime.p7s --]
[-- Type: application/pkcs7-signature, Size: 2193 bytes --]

Re: redisplay - very long lines

[Stefan Monnier]

>> > still need to walk to the end of a line before we are able to display
>> > it and all the lines after it.
>> 
>> In the above, when you say "line" do you mean "visual line" or "textual
>> line"?  IIUC we need to walk till the end of the visual line, but not
>> till the end of the textual line, so that shouldn't cause a slowdown
>> proportional to the length of the textual line.

> I thought we walked to the end of the textual line, but maybe I'm
> misremembering what redisplay does.

Indeed, the performance problems we're seeing seems to indicate that we
walkt to the end of the textual line, but I think we're here discussing
why that is.  Why not stop at the end of the last visual line
displayable in the window?


        Stefan

Re: redisplay - very long lines

[Eli Zaretskii]

> From: Stefan Monnier <monnier@iro.umontreal.ca>
> Cc: david.reitter@gmail.com,  emacs-devel@gnu.org
> Date: Tue, 17 Feb 2009 23:56:17 -0500
> 
> Indeed, the performance problems we're seeing seems to indicate that we
> walkt to the end of the textual line, but I think we're here discussing
> why that is.  Why not stop at the end of the last visual line
> displayable in the window?

Sorry, I don't remember.  I would need to refresh my memory when I
have time.

Re: redisplay - very long lines

[Eli Zaretskii]

> Cc: monnier@iro.umontreal.ca,
>  emacs-devel@gnu.org
> From: David Reitter <david.reitter@gmail.com>
> Date: Tue, 17 Feb 2009 23:50:42 -0500
> 
> We're proposing to stop processing a buffer line when we have left
> the portion of the buffer that is currently visible in the window.

I think Emacs already does that, but I might be mistaken.

Re: redisplay - very long lines

[Stefan Monnier]

>> We're proposing to stop processing a buffer line when we have left
>> the portion of the buffer that is currently visible in the window.
> I think Emacs already does that, but I might be mistaken.

If it does, then the performance issue is elsewhere.


        Stefan

Re: redisplay - very long lines

[David Reitter]

On 18 Feb 2009, at 14:44, Stefan Monnier wrote:

>>> We're proposing to stop processing a buffer line when we have left
>>> the portion of the buffer that is currently visible in the window.
>> I think Emacs already does that, but I might be mistaken.
>
> If it does, then the performance issue is elsewhere.

Here's the profiler output again:

	0.0%	99.8%	Emacs	                                                  
redisplay_window	
	0.0%	99.8%	Emacs	                                                   
move_it_vertically_backward	
	0.0%	62.3%	Emacs	                                                    
move_it_to	
	8.9%	62.0%	Emacs	                                                     
move_it_in_display_line_to	
	14.2%	30.5%	 
Emacs	                                                      
x_produce_glyphs	

Re: redisplay - very long lines

[grischka]

Eli Zaretskii wrote:
>> Date: Tue, 17 Feb 2009 18:16:10 +0100
>> From: grischka <grishka@gmx.de>
>> CC:  emacs-devel@gnu.org
>>
>>> If we can tolerate an incorrect display, maybe.  The invisible part of
>>> the line could in principle include characters and faces whose
>>> presence may have global effects on the rest of the displayed portion,
>>> such as faces that use larger fonts, to say nothing of inline images.
>> That is not a necessary consequence at all.
>>
>> After all faces and images don't come fallen from outer space into
>> the text but if they exist then it was the emacs program itself that
>> has put them there.  So instead of scanning lines each time it could
>> as well just remember where and how big they are.
> 
> AFAIU, you are talking about a complete redesign and rewrite not only
> of the Emacs display engine, but also of one of the most important
> parts of its top-level design, because in the current design code that
> modifies buffers and code that displays them are almost completely
> decoupled, i.e. there's almost no control flow between them, and the
> only data flow is thru the buffer text itself.

The buffer text itself is not the only data to control the display, there
are also properties that refer to regions of that text, and in fact that
is the part that matters here.  It is certainly possible to check for at
least the presence of extra properties in a line without walking each
character one by one.

> 
> IOW, under the current design, Lisp application code modifies buffers,
> and then, when Emacs is idle, redisplay kicks in, walks the buffers,
> decides which parts need to be redisplayed (by comparing the current
> and the new display contents), and finally redraws those parts.  This
> way, the code that works with buffer text knows (almost) nothing about
> display, and the code that displays knows (almost) nothing about
> editing.
> 

Re: redisplay - very long lines

[Eli Zaretskii]

> Date: Wed, 18 Feb 2009 21:41:32 +0100
> From: grischka <grishka@gmx.de>
> CC:  emacs-devel@gnu.org
> 
> The buffer text itself is not the only data to control the display, there
> are also properties that refer to regions of that text, and in fact that
> is the part that matters here.  It is certainly possible to check for at
> least the presence of extra properties in a line without walking each
> character one by one.

AFAIR, Emacs display code already includes this optimization.

Re: redisplay - very long lines

[grischka]

Eli Zaretskii wrote:
>> Date: Wed, 18 Feb 2009 21:41:32 +0100
>> From: grischka <grishka@gmx.de>
>> CC:  emacs-devel@gnu.org
>>
>> The buffer text itself is not the only data to control the display, there
>> are also properties that refer to regions of that text, and in fact that
>> is the part that matters here.  It is certainly possible to check for at
>> least the presence of extra properties in a line without walking each
>> character one by one.
> 
> AFAIR, Emacs display code already includes this optimization.
> 

I'll believe you anything you want if you can fix the problem.