emacs takes exhorbitantly long to read long, one-line files.

emacs takes exhorbitantly long to read long, one-line files.

[Randy Yates]

I have a file (a matlab .m file of a vector of data) that is all on
one line and about 2 MB:

  http://www.digitalsignallabs.com/dspin.m

emacs takes a very long time (6 minutes?) to read this in, and
practically becomes unusable in the mean time.

I'm thinking of looking into the code to get an idea of why this happens
and of course look for a fix. If anyone has any pointers or other info
on the problem, please inform me. 
-- 
Randy Yates
Digital Signal Labs
http://www.digitalsignallabs.com

Re: emacs takes exhorbitantly long to read long, one-line files.

[Eli Zaretskii]

> From: Randy Yates <yates@digitalsignallabs.com>
> Date: Sat, 18 May 2013 23:52:28 -0400
> 
> I have a file (a matlab .m file of a vector of data) that is all on
> one line and about 2 MB:
> 
>   http://www.digitalsignallabs.com/dspin.m
> 
> emacs takes a very long time (6 minutes?) to read this in, and
> practically becomes unusable in the mean time.

I think most of the time is taken by display, not by actually reading
the file.

> I'm thinking of looking into the code to get an idea of why this happens
> and of course look for a fix. If anyone has any pointers or other info
> on the problem, please inform me. 

It's a long known problem, whose reasons are closely related to the
implementation of the Emacs display engine.  See

  http://debbugs.gnu.org/cgi/bugreport.cgi?bug=13675#8

Re: emacs takes exhorbitantly long to read long, one-line files.

[Dmitry Antipov]

On 05/19/2013 07:52 AM, Randy Yates wrote:

> I have a file (a matlab .m file of a vector of data) that is all on
> one line and about 2 MB:
>
>    http://www.digitalsignallabs.com/dspin.m
>
> emacs takes a very long time (6 minutes?) to read this in, and
> practically becomes unusable in the mean time.

In this particular case, Emacs just thinks that your file is an Objective-C
source code, and tries to fontify it accordingly. This attempt implies a lot
of buffer scans, and substantial amount of them may be slow for the very
long lines. Since I suspect that you don't want to edit this as Obj-C, try:

emacs --eval "(setq auto-mode-alist (cons '(\"\\.m\" . fundamental-mode) auto-mode-alist))" dspin.m

Dmitry

Re: emacs takes exhorbitantly long to read long, one-line files.

[Randy Yates]

Dmitry Antipov <dmantipov@yandex.ru> writes:

> On 05/19/2013 07:52 AM, Randy Yates wrote:
>
>> I have a file (a matlab .m file of a vector of data) that is all on
>> one line and about 2 MB:
>>
>>    http://www.digitalsignallabs.com/dspin.m
>>
>> emacs takes a very long time (6 minutes?) to read this in, and
>> practically becomes unusable in the mean time.
>
> In this particular case, Emacs just thinks that your file is an Objective-C
> source code, and tries to fontify it accordingly. This attempt implies a lot
> of buffer scans, and substantial amount of them may be slow for the very
> long lines. Since I suspect that you don't want to edit this as Obj-C, try:
>
> emacs --eval "(setq auto-mode-alist (cons '(\"\\.m\" .
> fundamental-mode) auto-mode-alist))" dspin.m

I already had that in my init.el. I've also tried creating an empty
file and setting it to fundamental-mode. In both these cases the 
behavior is the same. 

I did notice that emacs is faster - but still unusably slow - when
toggle-truncate-lines is true.
-- 
Randy Yates
Digital Signal Labs
http://www.digitalsignallabs.com

Re: emacs takes exhorbitantly long to read long, one-line files.

[Dmitry Antipov]

On 05/20/2013 03:03 PM, Randy Yates wrote:

> I already had that in my init.el. I've also tried creating an empty
> file and setting it to fundamental-mode. In both these cases the
> behavior is the same.

Hm...is it the same with emacs -Q?

> I did notice that emacs is faster - but still unusably slow - when
> toggle-truncate-lines is true.

Try (setq-default cache-long-line-scans t) too.

Dmitry

Re: emacs takes exhorbitantly long to read long, one-line files.

[Karl Fogel]

Dmitry Antipov <dmantipov@yandex.ru> writes:
>> I already had that in my init.el. I've also tried creating an empty
>> file and setting it to fundamental-mode. In both these cases the
>> behavior is the same.
>
>Hm...is it the same with emacs -Q?
>
>> I did notice that emacs is faster - but still unusably slow - when
>> toggle-truncate-lines is true.
>
>Try (setq-default cache-long-line-scans t) too.

That should help a lot.

If there are any other tricks for making Emacs behave better with long
lines, you might be able to find them in the Ale source code, which is
reachable from http://red-bean.com/ale/ .

Ale is a genetic sequence alignment editor written in Emacs.  Each line
a buffer represents one organism's sequence, e.g. a ribosomal RNA
sequence, so can easily be 2MB or more in length.  cache-long-line-scans
was in fact added partly to support this, IIRC; there may be other
tricks in the Ale source code (I don't remember after all these years),
so it might be worth a look.

-K

Re: emacs takes exhorbitantly long to read long, one-line files.

[Eli Zaretskii]

> From: Karl Fogel <kfogel@red-bean.com>
> Date: Mon, 20 May 2013 09:32:23 -0500
> Cc: Dmitry Antipov <dmantipov@yandex.ru>
> 
> Dmitry Antipov <dmantipov@yandex.ru> writes:
> >> I already had that in my init.el. I've also tried creating an empty
> >> file and setting it to fundamental-mode. In both these cases the
> >> behavior is the same.
> >
> >Hm...is it the same with emacs -Q?
> >
> >> I did notice that emacs is faster - but still unusably slow - when
> >> toggle-truncate-lines is true.
> >
> >Try (setq-default cache-long-line-scans t) too.
> 
> That should help a lot.

But it won't succeed to make Emacs usable with such files.  E.g., try
this:

  M->
  C-p

and count the seconds it takes to perform the second command.

What Emacs does behind the scenes is go to the beginning of the
previous _physical_ line (which is quite fast in this case), and the
go all the way down the humongously long line, one character at a
time, until it finds the place to put the cursor.  Unless we make
radical changes in this algorithm, how can anyone expect reasonable
performance from this?

Re: emacs takes exhorbitantly long to read long, one-line files.

[Dmitry Antipov]

On 05/20/2013 07:59 PM, Eli Zaretskii wrote:

> But it won't succeed to make Emacs usable with such files.  E.g., try
> this:
>
>    M->
>    C-p
>
> and count the seconds it takes to perform the second command.
>
> What Emacs does behind the scenes is go to the beginning of the
> previous _physical_ line (which is quite fast in this case), and the
> go all the way down the humongously long line, one character at a
> time, until it finds the place to put the cursor.  Unless we make
> radical changes in this algorithm, how can anyone expect reasonable
> performance from this?

This is pretty ugly because both previous-line and next-line uses
Fforward_line, which uses scan_newline, which _does not_ use newline
cache :-(. Due to the above, I believe that the use of scan_newline
should be limited to *Messages* buffer tricks, and other users should
be converted to use find_newline instead.

Dmitry

Re: emacs takes exhorbitantly long to read long, one-line files.

[Eli Zaretskii]

> Date: Mon, 20 May 2013 20:25:55 +0400
> From: Dmitry Antipov <dmantipov@yandex.ru>
> CC: Karl Fogel <kfogel@red-bean.com>, yates@digitalsignallabs.com, 
>  emacs-devel@gnu.org
> 
> >    M->
> >    C-p
> >
> > and count the seconds it takes to perform the second command.
> >
> > What Emacs does behind the scenes is go to the beginning of the
> > previous _physical_ line (which is quite fast in this case), and the
> > go all the way down the humongously long line, one character at a
> > time, until it finds the place to put the cursor.  Unless we make
> > radical changes in this algorithm, how can anyone expect reasonable
> > performance from this?
> 
> This is pretty ugly because both previous-line and next-line uses
> Fforward_line, which uses scan_newline, which _does not_ use newline
> cache :-(.

Emacs doesn't use previous-line and next-line in the scenario I
described.  It uses back_to_previous_visible_line_start, which in turn
uses find_newline_no_quit, and that does use the cache.

But you are missing the point.  First, this particular file has only
one line, so not using the cache means we only miss a single newline.
More importantly, even if we do cache newlines, how will that help us
with such long lines?  It should be clear that traversing such lines
from left to right, one character at a time, is _the_ bottleneck, not
how fast can we find the previous/next newline.

Re: emacs takes exhorbitantly long to read long, one-line files.

[Randy Yates]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Karl Fogel <kfogel@red-bean.com>
>> Date: Mon, 20 May 2013 09:32:23 -0500
>> Cc: Dmitry Antipov <dmantipov@yandex.ru>
>> 
>> Dmitry Antipov <dmantipov@yandex.ru> writes:
>> >> I already had that in my init.el. I've also tried creating an empty
>> >> file and setting it to fundamental-mode. In both these cases the
>> >> behavior is the same.
>> >
>> >Hm...is it the same with emacs -Q?
>> >
>> >> I did notice that emacs is faster - but still unusably slow - when
>> >> toggle-truncate-lines is true.
>> >
>> >Try (setq-default cache-long-line-scans t) too.
>> 
>> That should help a lot.
>
> But it won't succeed to make Emacs usable with such files.  E.g., try
> this:
>
>   M->
>   C-p
>
> and count the seconds it takes to perform the second command.
>
> What Emacs does behind the scenes is go to the beginning of the
> previous _physical_ line (which is quite fast in this case), and the
> go all the way down the humongously long line, one character at a
> time, until it finds the place to put the cursor.  Unless we make
> radical changes in this algorithm, how can anyone expect reasonable
> performance from this?

I've noticed that xemacs does not have this problem. Would it be
fruitful to look at xemacs' display algorithm?
-- 
Randy Yates
Digital Signal Labs
http://www.digitalsignallabs.com

Re: emacs takes exhorbitantly long to read long, one-line files.

[Stephen J. Turnbull]

Randy Yates writes:

 > I've noticed that xemacs does not have this problem. Would it be
 > fruitful to look at xemacs' display algorithm?

Unlikely.  XEmacs not only lacks several of the features of Emacs's
display which seem to be relevant to this problem (in particular, bidi
display), the main algorithm is quite different as I understand it.

Re: emacs takes exhorbitantly long to read long, one-line files.

[Eli Zaretskii]

> From: Randy Yates <yates@digitalsignallabs.com>
> Cc: Karl Fogel <kfogel@red-bean.com>,  dmantipov@yandex.ru,  emacs-devel@gnu.org
> Date: Mon, 20 May 2013 17:43:54 -0400
> 
> I've noticed that xemacs does not have this problem. Would it be
> fruitful to look at xemacs' display algorithm?

It depends on what level the differences are.  We need changes on a
very specific level, because rewriting the entire display engine,
while a welcome project, is unlikely to happen.

Since Stephen says the differences are on a much higher level, I agree
with him that this is not likely to help.

Re: emacs takes exhorbitantly long to read long, one-line files.

[Ulrich Mueller]

>>>>> On Mon, 20 May 2013, Eli Zaretskii wrote:

> But it won't succeed to make Emacs usable with such files.  E.g., try
> this:

>   M->
>   C-p

> and count the seconds it takes to perform the second command.

I've done this test for a file with one line of 16 MB, and I get the
following times for the first and second commands (emacs -Q -nw in
an 80x24 xterm):

  Emacs 23.4:   4 s /  9 s
  Emacs 24.3:  16 s / 34 s

Is this degradation of performance expected?

Ulrich

Re: emacs takes exhorbitantly long to read long, one-line files.

[Dmitry Antipov]

On 05/21/2013 11:57 AM, Ulrich Mueller wrote:

> I've done this test for a file with one line of 16 MB, and I get the
> following times for the first and second commands (emacs -Q -nw in
> an 80x24 xterm):
>
>    Emacs 23.4:   4 s /  9 s
>    Emacs 24.3:  16 s / 34 s
>
> Is this degradation of performance expected?

Can you try 24.3 with (setq-default bidi-display-reordering nil)?
With BIDI disabled, it shouldn't be 4x at least.

Dmitry

Re: emacs takes exhorbitantly long to read long, one-line files.

[Ulrich Mueller]

>>>>> On Tue, 21 May 2013, Dmitry Antipov wrote:

>> I've done this test for a file with one line of 16 MB, and I get
>> the following times for the first and second commands (emacs -Q -nw
>> in an 80x24 xterm):
>> 
>> Emacs 23.4:   4 s /  9 s
>> Emacs 24.3:  16 s / 34 s
>> 
>> Is this degradation of performance expected?

> Can you try 24.3 with (setq-default bidi-display-reordering nil)?
> With BIDI disabled, it shouldn't be 4x at least.

It's 6 s / 11 s then.

Ulrich

Re: emacs takes exhorbitantly long to read long, one-line files.

[Eli Zaretskii]

> From: Dmitry Antipov <dmantipov@yandex.ru>
> CC: Eli Zaretskii <eliz@gnu.org>, Karl Fogel <kfogel@red-bean.com>, 
>  Randy Yates <yates@digitalsignallabs.com>,
>  emacs-devel@gnu.org
> 
> Can you try 24.3 with (setq-default bidi-display-reordering nil)?
> With BIDI disabled, it shouldn't be 4x at least.

2 to 3 times in my experience, unless you specifically choose
character classes to trip the bidi iterator.

Re: emacs takes exhorbitantly long to read long, one-line files.

[Eli Zaretskii]

> Date: Tue, 21 May 2013 14:06:04 +0200
> Cc: Ulrich Mueller <ulm@gentoo.org>, Eli Zaretskii <eliz@gnu.org>,
>         Karl Fogel <kfogel@red-bean.com>,
>         Randy Yates <yates@digitalsignallabs.com>, emacs-devel@gnu.org
> From: Ulrich Mueller <ulm@gentoo.org>
> 
> >> Emacs 23.4:   4 s /  9 s
> >> Emacs 24.3:  16 s / 34 s
> >> 
> >> Is this degradation of performance expected?
> 
> > Can you try 24.3 with (setq-default bidi-display-reordering nil)?
> > With BIDI disabled, it shouldn't be 4x at least.
> 
> It's 6 s / 11 s then.

Not sure the bidi display is involved in 6 vs 4 sec, but you should
know that turning off bidi-display-reordering doesn't revert all the
differences between the old unidirectional display and the
bidirectional one.  It was never meant to do that in the first place.

Re: emacs takes exhorbitantly long to read long, one-line files.

[Eli Zaretskii]

> Date: Tue, 21 May 2013 09:57:35 +0200
> Cc: Karl Fogel <kfogel@red-bean.com>,
>         Randy Yates <yates@digitalsignallabs.com>, dmantipov@yandex.ru,
>         emacs-devel@gnu.org
> From: Ulrich Mueller <ulm@gentoo.org>
> 
> >   M->
> >   C-p
> 
> > and count the seconds it takes to perform the second command.
> 
> I've done this test for a file with one line of 16 MB, and I get the
> following times for the first and second commands (emacs -Q -nw in
> an 80x24 xterm):
> 
>   Emacs 23.4:   4 s /  9 s
>   Emacs 24.3:  16 s / 34 s
> 
> Is this degradation of performance expected?

I see no degradation in performance: both 4 sec and 6 sec, let alone 9
and 34, are the same as infinity.  You cannot have any useful editing
with such reaction times to a simple cursor movement command.  It is
therefore meaningless to compare such "performance" figures and draw
any conclusions from them.

Emacs 24 has got a bidirectional display engine.  Bidirectional
display needs to do much more work than the previous unidirectional
one in Emacs 23 and before.  In a nutshell, where the unidirectional
display simply incremented a pointer, the bidirectional display calls
a complex function that does some very non-trivial processing based on
the bidirectional class of each character.

Now, this sounds scary, but really isn't.  The bidirectional display
was optimized so that in all the known uses where the old display
provided reasonable performance, the new one does, too.  While the
bidi display is still slower than the unidirectional one, the
optimizations keep the slowdown in check, such that the delays are
below humanly perceptible threshold on reasonably modern and even
fairly old machines.  (I developed and debugged most of the code on a
7-year old machine that died less than a year ago.)

By contrast, use cases such as the above, where the old code performs
abysmally inadequately, were explicitly excluded from the scope of the
optimizations, because it doesn't make sense to punish 99.9% of users
on behalf of the rest.  And that is what you see above.

Emacs needs some non-trivial changes in display-related algorithms to
adequately support very long lines.  When those changes are designed
and implemented, I promise you that the bidirectional display will
keep up.

Re: emacs takes exhorbitantly long to read long, one-line files.

[Randy Yates]

Eli Zaretskii <eliz@gnu.org> writes:
> [...]
> Emacs needs some non-trivial changes in display-related algorithms to
> adequately support very long lines.  

Allow me to take a look. Are these algorithms documented? Or is it RTSL?
-- 
Randy Yates
Digital Signal Labs
http://www.digitalsignallabs.com

Re: emacs takes exhorbitantly long to read long, one-line files.

[Dmitry Antipov]

On 05/21/2013 10:03 PM, Randy Yates wrote:

> Allow me to take a look. Are these algorithms documented? Or is it RTSL?

RTSL, it's better to start from comments in xdisp.c and dispextern.h.

Dmitry

Re: emacs takes exhorbitantly long to read long, one-line files.

[Ulrich Mueller]

>>>>> On Tue, 21 May 2013, Eli Zaretskii wrote:

>> I've done this test for a file with one line of 16 MB, and I get the
>> following times for the first and second commands (emacs -Q -nw in
>> an 80x24 xterm):
>> 
>> Emacs 23.4:   4 s /  9 s
>> Emacs 24.3:  16 s / 34 s
>> 
>> Is this degradation of performance expected?

> I see no degradation in performance: both 4 sec and 6 sec, let alone
> 9 and 34, are the same as infinity. You cannot have any useful
> editing with such reaction times to a simple cursor movement
> command. It is therefore meaningless to compare such "performance"
> figures and draw any conclusions from them.

Sure, the example with 16 MB in one line is unrealistic. I made it so,
simply because I wanted the times to be long enough to be measurable
with a stop watch.

But wouldn't the factors between 23.4 and 24.3 be similar for more
realistic examples?

Ulrich

Re: emacs takes exhorbitantly long to read long, one-line files.

[Eli Zaretskii]

> Date: Wed, 22 May 2013 07:10:38 +0200
> Cc: kfogel@red-bean.com, yates@digitalsignallabs.com, dmantipov@yandex.ru,
>         emacs-devel@gnu.org
> From: Ulrich Mueller <ulm@gentoo.org>
> 
> >>>>> On Tue, 21 May 2013, Eli Zaretskii wrote:
> 
> >> Emacs 23.4:   4 s /  9 s
> >> Emacs 24.3:  16 s / 34 s
> >> 
> >> Is this degradation of performance expected?
> 
> > I see no degradation in performance: both 4 sec and 6 sec, let alone
> > 9 and 34, are the same as infinity. You cannot have any useful
> > editing with such reaction times to a simple cursor movement
> > command. It is therefore meaningless to compare such "performance"
> > figures and draw any conclusions from them.
> 
> Sure, the example with 16 MB in one line is unrealistic. I made it so,
> simply because I wanted the times to be long enough to be measurable
> with a stop watch.
> 
> But wouldn't the factors between 23.4 and 24.3 be similar for more
> realistic examples?

Define "realistic".

The definition I used (and still do) is "where Emacs 23 provided
adequate behavior people wouldn't complain about."  In each such case
which I found or which was described to me, if Emacs 24 slowed things
down so they got past the humanly perceptible delay threshold, I
looked for and found optimizations that pushed Emacs 24 back below the
threshold, where the times used by Emacs 23 and 24 could not be
distinguished by humans.

If you find "realistic examples" by that definition, please by all
means report them as bugs.

But it was never a goal to make the performance of the bidirectional
display adequate where Emacs 23 wasn't, nor make it as inadequate as
Emacs 23.  That is another project, which needs to change display
algorithms and design on a different level.