bug#13675: 24.2.93; Extremely slow redisplay when lines are very long

[Eli Zaretskii <eliz@gnu.org>]

This is a very long-standing deficiency of the Emacs display engine:
it is awfully slow in buffers with very long (thousands of characters)
lines.  Specifically, many simple movement commands, scrolling, or
even typing "M-x" can take several seconds(!) to complete.

A simple Awk script attached below can be used to generate such files.

For the latest discussions of this and some data, see this thread:

  http://lists.gnu.org/archive/html/emacs-devel/2013-02/msg00135.html

The solution for this bug should produce algorithmic changes in the
display engine and possibly also supporting changes in data structures
that would prevent such a terrible slow-down with long lines.
Ideally, redisplay of such buffers should not be much slower than
buffers with "normal" line length.

Here's a script that can be used to produce test files for this bug:

---------------------------------------------
BEGIN {
    # 500 lines
    for (i = 1; i <= 500; i++)
    {
	# Line length between 10K and 20K characters + newline
	line_len = 10000 * rand() + 10000;
	for (j = 1; j <= line_len; j++)
	{
	    # 15% of punctuation and digit charcaters, the rest letters
	    if (rand() < 0.15)
	    {
		# Start at SPACE
		lbase = 32;
		llen = 33;
	    }
	    else
	    {
		# Start at 'a'
		lbase = 97;
		llen = 26;
	    }
	    printf "%c", llen * rand() + lbase;
	}
	printf "\n";
    }
}

---------------------------------------------


In GNU Emacs 24.2.93.1 (i386-mingw-nt5.1.2600)
 of 2013-02-07 on HOME-C4E4A596F7
Windowing system distributor `Microsoft Corp.', version 5.1.2600
Configured using:
 `configure --with-gcc (3.4) --cflags -Id:/usr/include/libxml2'

Important settings:
  value of $LANG: ENU
  locale-coding-system: cp1255
  default enable-multibyte-characters: t

Major mode: Mail

Minor modes in effect:
  shell-dirtrack-mode: t
  diff-auto-refine-mode: t
  flyspell-mode: t
  desktop-save-mode: t
  show-paren-mode: t
  display-time-mode: t
  tooltip-mode: t
  mouse-wheel-mode: t
  tool-bar-mode: t
  menu-bar-mode: t
  file-name-shadow-mode: t
  global-font-lock-mode: t
  font-lock-mode: t
  blink-cursor-mode: t
  auto-composition-mode: t
  auto-encryption-mode: t
  auto-compression-mode: t
  temp-buffer-resize-mode: t
  line-number-mode: t
  auto-fill-function: mail-mode-auto-fill
  abbrev-mode: t

Recent input:
e t a i l s . <return> <up> <up> <C-right> <C-right> 
<C-right> C-x C-e <help-echo> <help-echo> <down> <down> 
<down> <return> T h e SPC r e a s o n SPC f o r SPC 
t h e SPC d e f a u l t SPC v a l u e SPC i s SPC t 
o SPC a v o i d SPC t h e SPC a n n o y i n g SPC j 
u m p s SPC o f SPC t h e SPC m o d e SPC l i n e <up> 
<M-right> <C-left> <C-left> <C-left> <left> SPC a <backspace> 
u p SPC a n d SPC d o w n M-q <down> SPC w h e n SPC 
t h e SPC e c h o SPC a r e a SPC d i s p l a y s SPC 
m e s s a g e s SPC o f SPC d i f f e r e n t SPC l 
e n g t h . <return> <C-home> C-c C-s <help-echo> <switch-frame> 
d d d d d d d d d SPC d d o P O <tab> <return> d d 
d d d d d d d d n d SPC d d d SPC <prior> <next> <next> 
d SPC d d d d d C-z C-z C-z C-z C-z C-z C-z C-z d d 
d d d d SPC SPC <prior> <next> <next> <next> <next> 
<next> <next> <next> <next> <next> <next> <next> <next> 
<next> <next> <next> <next> <next> <next> <next> <next> 
<next> d <C-home> C-x C-s <switch-frame> <switch-frame> 
<help-echo> <help-echo> <switch-frame> <switch-frame> 
<help-echo> <switch-frame> <help-echo> M-x r e p o 
r t - e m a c s - b u <tab> <return>

Recent messages:
Sending...
Added to d:/usr/eli/rmail/SENT.MAIL
Sending email 
Sending email done
Sending...done
Added to d:/usr/eli/rmail/PORTS.rmail
No following nondeleted message
Mark set
Saving file d:/usr/eli/rmail/INBOX...
Wrote d:/usr/eli/rmail/INBOX [2 times]

Load-path shadows:
None found.

Features:
(shadow emacsbug cc-awk tar-mode etags texinfo mule-util ebuff-menu
electric bug-reference add-log misearch multi-isearch dabbrev
time-stamp rmailout network-stream starttls tls mail-extr smtpmail
auth-source eieio password-cache shell mailalias sendmail help-mode
tcl nxml-uchnm rng-xsd xsd-regexp rng-cmpct rng-nxml rng-valid rng-loc
rng-uri rng-parse nxml-parse rng-match rng-dt rng-util rng-pttrn
nxml-ns nxml-mode nxml-outln nxml-rap nxml-util nxml-glyph nxml-enc
xmltok sgml-mode conf-mode generic arc-mode archive-mode diff-mode
dired-x cl-macs gv dired face-remap org-wl org-w3m org-vm org-rmail
org-mhe org-mew org-irc org-jsinfo org-infojs org-html org-exp ob-exp
org-exp-blocks org-agenda org-info org-gnus gnus-util org-docview
org-bibtex bibtex org-bbdb org byte-opt warnings bytecomp byte-compile
cconv advice help-fns advice-preload ob-tangle ob-ref ob-lob ob-table
org-footnote org-src ob-comint ob-keys org-pcomplete pcomplete
org-list org-faces org-entities org-version ob-emacs-lisp ob
org-compat org-macs ob-eval org-loaddefs find-func cal-menu calendar
cal-loaddefs parse-time vc-cvs gud comint ansi-color ring sh-script
smie executable autoconf autoconf-mode make-mode autorevert noutline
outline easy-mmode jka-compr info vc-bzr cc-langs cl cl-lib cc-mode
cc-fonts cc-guess cc-menus cc-cmds cc-styles cc-align cc-engine
cc-vars cc-defs flyspell rmailsum qp rmailmm message format-spec
rfc822 mml mml-sec mm-decode mm-bodies mm-encode mailabbrev gmm-utils
mailheader mail-parse rfc2231 rmail rfc2047 rfc2045 ietf-drums mm-util
mail-prsvr mail-utils desktop server filecache mairix cus-edit
easymenu cus-start cus-load wid-edit saveplace midnight ispell
generic-x paren battery time time-date tooltip ediff-hook vc-hooks
lisp-float-type mwheel dos-w32 ls-lisp w32-common-fns disp-table
w32-win w32-vars tool-bar dnd fontset image regexp-opt fringe
tabulated-list newcomment lisp-mode register page menu-bar rfn-eshadow
timer select scroll-bar mouse jit-lock font-lock syntax facemenu
font-core frame cham georgian utf-8-lang misc-lang vietnamese tibetan
thai tai-viet lao korean japanese hebrew greek romanian slovak czech
european ethiopic indian cyrillic chinese case-table epa-hook
jka-cmpr-hook help simple abbrev minibuffer loaddefs button faces
cus-face macroexp files text-properties overlay sha1 md5 base64 format
env code-pages mule custom widget hashtable-print-readable backquote
make-network-process w32 multi-tty emacs)