bug#9008: 23.2; Sluggishness when editing large latex files containing CJK text using preview-latex, due to slow buf_bytepos_to_charpos

[r6144]

This bug report will be sent to the Free Software Foundation,
not to your local site managers!
Please write in English if possible, because the Emacs maintainers
usually do not have translators to read other languages for them.

Your bug report will be posted to the bug-gnu-emacs@gnu.org mailing
list,
and to the gnu.emacs.bug news group.

Please describe exactly what actions triggered the bug
and the precise symptoms of the bug.  If you can, give
a recipe starting from `emacs -Q':
-------------------------------------------------------

I'm using auctex to edit a large latex file (about 400kB in size)
containing Chinese text as well as about 6000 equations previewed with
preview-latex.  Emacs feels a bit sluggish in this mode: individual
cursor movements are not delayed much, but when holding down the right
arrow key, the cursor does not keep moving but only shows up in the new
position after I release the key, while fill-paragraph can take more
than a second.  The CPU usage is high during these operations, even
though I have a modern Core 2 Quad CPU.

According to oprofile, the top consumer of CPU time is
buf_bytepos_to_charpos() within the loop over all the markers.  Indeed,
it seems that each preview image (which is an Emacs overlay) has two
markers at respectively its beginning and its end, so the total number
of markers in that buffer, according to

(with-current-buffer MY-BUFFER
  (loop for i from (point-min) to (point-max) count
(buffer-has-markers-at i)))

is 12856.  As buf_bytepos_to_charpos() seems to be called via the
BYTE_TO_CHAR() macro from many places, the sluggishness is well
expected.

Although having such a large number of markers slows down other
operations as well, they seem necessary when so many preview images are
present.  In any case, buf_bytepos_to_charpos() seems to be the most
important one, as operations on another English latex file with a
similar number of preview images is far less sluggish
(buf_bytepos_to_charpos() returns early when there are no multibyte
characters).

I guess the markers should be organized in something other than a linked
list.  Maybe a balanced binary tree ordered by position, with each node
storing the bytepos and charpos offsets compared to its parent?  In this
way lookups as well as insertions/deletions should be fast enough.

-------------------------------------------------------
If Emacs crashed, and you have the Emacs process in the gdb debugger,
please include the output from the following gdb commands:
    `bt full' and `xbacktrace'.
For information about debugging Emacs, please read the file
/usr/share/emacs/23.2/etc/DEBUG.


In GNU Emacs 23.2.1 (x86_64-redhat-linux-gnu, GTK+ Version 2.21.4)
 of 2010-07-09 on x86-10.phx2.fedoraproject.org
Windowing system distributor `Fedora Project', version 11.0.10904000
configured using `configure  '--build=x86_64-redhat-linux-gnu'
'--host=x86_64-redhat-linux-gnu' '--program-prefix='
'--disable-dependency-tracking' '--prefix=/usr' '--exec-prefix=/usr'
'--bindir=/usr/bin' '--sbindir=/usr/sbin' '--sysconfdir=/etc'
'--datadir=/usr/share' '--includedir=/usr/include' '--libdir=/usr/lib64'
'--libexecdir=/usr/libexec' '--localstatedir=/var'
'--sharedstatedir=/var/lib' '--mandir=/usr/share/man'
'--infodir=/usr/share/info' '--with-dbus' '--with-gif' '--with-jpeg'
'--with-png' '--with-rsvg' '--with-tiff' '--with-xft' '--with-xpm'
'--with-x-toolkit=gtk' 'build_alias=x86_64-redhat-linux-gnu'
'host_alias=x86_64-redhat-linux-gnu' 'CFLAGS=-DMAIL_USE_LOCKF -O2 -g
-pipe -Wall -Wp,-D_FORTIFY_SOURCE=2 -fexceptions -fstack-protector
--param=ssp-buffer-size=4 -m64 -mtune=generic
-fno-optimize-sibling-calls''

Important settings:
  value of $LC_ALL: nil
  value of $LC_COLLATE: nil
  value of $LC_CTYPE: nil
  value of $LC_MESSAGES: en_US.UTF-8
  value of $LC_MONETARY: nil
  value of $LC_NUMERIC: nil
  value of $LC_TIME: en_US.UTF-8
  value of $LANG: zh_CN.UTF-8
  value of $XMODIFIERS: @im=ibus
  locale-coding-system: utf-8-unix
  default enable-multibyte-characters: t

Major mode: Lisp Interaction

Minor modes in effect:
  eldoc-mode: t
  diff-auto-refine-mode: t
  desktop-save-mode: t
  icomplete-mode: t
  show-paren-mode: t
  which-function-mode: t
  iswitchb-mode: t
  tooltip-mode: t
  mouse-wheel-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-encryption-mode: t
  auto-compression-mode: t
  column-number-mode: t
  line-number-mode: t

Recent input:
<up> <down> <switch-frame> <down> <down> <down> <down> 
<prior> <next> <prior> <up> <up> <up> <up> <up> <up> 
<up> <right> <right> <f11> <M-right> <M-right> <M-right> 
<M-right> <M-right> <right> M-w <next> <next> <up> 
<up> <down> <down> <up> <M-left> <M-left> <M-left> 
<M-left> <M-left> <M-left> <M-left> <M-left> <M-left> 
<left> C-y <f11> <M-right> <M-right> <M-right> <M-right> 
<M-right> <M-right> <M-right> <right> <right> <right> 
C-w <down> <M-left> C-SPC <ibus-receive-event> u i 
5 <down> <M-left> u i 5 C-SPC <down> <down> <down> 
<down> <down> <down> <down> <down> <down> <down> <down> 
<down> <down> <down> <down> <down> <down> <down> <down> 
<down> <down> <down> <down> <down> <next> <prior> <prior> 
<prior> <prior> <prior> <next> <next> <next> <next> 
<prior> <prior> <prior> <prior> C-x C-s C-x s <next> 
<next> <prior> <next> <next> <next> <prior> <down> 
<down> <next> <next> <up> <up> <down> <down> <up> <left> 
<f4> <prior> <prior> <f6> C-r d e x t b i t <left> 
<right> <right> <M-right> L <M-right> <M-right> L C-x 
C-s C-x s <prior> <prior> <prior> <prior> <f6> <f6> 
C-s d e x t b i t C-s C-s C-s C-s C-s C-s C-s C-s C-s 
<up> C-x C-s <f12> <next> <prior> <next> <next> <next> 
<next> <next> <next> <next> <next> <next> <next> <next> 
<next> <down> <down> <down> <down> <down> <down> <down> 
<down> <down> <down> <down> <down> <down> <down> <down> 
<down> <down> <down> <down> <down> <up> <up> <up> <up> 
<up> <next> <next> <down> <down> <down> <down> <down> 
<down> <down> <down> <down> <down> <down> <down> <down> 
<down> <down> <down> <down> <down> <down> <down> <down> 
<down> <up> <up> <up> <up> <up> <up> <up> <up> <up> 
<up> <up> <up> <down> <left> <left> <left> <right> 
<f6> C-r d e x t b i t C-r C-r C-r C-r C-r C-r C-r 
<up> <help-echo> <help-echo> <switch-frame> <help-echo> 
<f6> M-x r e p o r t SPC e m a c s SPC b u g <retu
rn>

Recent messages:
Wrote /home/r6144/research/degree/thesis/thesis.tex
(No files need saving)
IBus: <left> is undefined
Mark saved where search started
Saving file /home/r6144/research/degree/thesis/thesis.tex...
Wrote /home/r6144/research/degree/thesis/thesis.tex
(No files need saving)
Mark saved where search started
(No changes need to be saved)
Mark saved where search started

Load-path shadows:
~/site-lisp/latex hides /usr/share/emacs/site-lisp/auctex/latex
/usr/share/cscope/xcscope hides /usr/share/emacs/site-lisp/xcscope
/usr/share/emacs/site-lisp/lilypond-init
hides /usr/share/emacs/site-lisp/site-start.d/lilypond-init
/usr/share/emacs/site-lisp/systemc-mode
hides /usr/share/emacs/site-lisp/site-start.d/systemc-mode
/usr/share/emacs/site-lisp/site-start.d/maxima-modes
hides /usr/share/emacs/site-lisp/maxima/site_start.d/maxima-modes
/usr/share/emacs/site-lisp/coq
hides /usr/share/emacs/site-lisp/proofgeneral/coq/coq
/usr/share/emacs/site-lisp/mmm-noweb
hides /usr/share/emacs/site-lisp/proofgeneral/mmm/mmm-noweb
/usr/share/emacs/site-lisp/mmm-rpm
hides /usr/share/emacs/site-lisp/proofgeneral/mmm/mmm-rpm
/usr/share/emacs/site-lisp/mmm-mason
hides /usr/share/emacs/site-lisp/proofgeneral/mmm/mmm-mason
/usr/share/emacs/site-lisp/mmm-mode
hides /usr/share/emacs/site-lisp/proofgeneral/mmm/mmm-mode
/usr/share/emacs/site-lisp/mmm-compat
hides /usr/share/emacs/site-lisp/proofgeneral/mmm/mmm-compat
/usr/share/emacs/site-lisp/mmm-utils
hides /usr/share/emacs/site-lisp/proofgeneral/mmm/mmm-utils
/usr/share/emacs/site-lisp/mmm-univ
hides /usr/share/emacs/site-lisp/proofgeneral/mmm/mmm-univ
/usr/share/emacs/site-lisp/mmm-auto
hides /usr/share/emacs/site-lisp/proofgeneral/mmm/mmm-auto
/usr/share/emacs/site-lisp/mmm-cmds
hides /usr/share/emacs/site-lisp/proofgeneral/mmm/mmm-cmds
/usr/share/emacs/site-lisp/mmm-vars
hides /usr/share/emacs/site-lisp/proofgeneral/mmm/mmm-vars
/usr/share/emacs/site-lisp/mmm-sample
hides /usr/share/emacs/site-lisp/proofgeneral/mmm/mmm-sample
/usr/share/emacs/site-lisp/mmm-cweb
hides /usr/share/emacs/site-lisp/proofgeneral/mmm/mmm-cweb
/usr/share/emacs/site-lisp/mmm-region
hides /usr/share/emacs/site-lisp/proofgeneral/mmm/mmm-region
/usr/share/emacs/site-lisp/mmm-class
hides /usr/share/emacs/site-lisp/proofgeneral/mmm/mmm-class
~/site-lisp/gud hides /usr/share/emacs/23.2/lisp/progmodes/gud

Features:
(shadow sort mail-extr message idna sendmail ecomplete rfc822 mml
mml-sec password-cache mm-decode mm-bodies mm-encode mailcap mail-parse
rfc2231 rfc2047 rfc2045 qp ietf-drums mailabbrev nnheader gnus-util
netrc time-date mm-util mail-prsvr gmm-utils mailheader canlock sha1
hex-util hashcash mail-utils emacsbug debug etags reftex-sel cal-julian
lunar solar cal-dst cal-move cal-menu calendar cal-loaddefs thingatpt
asy-mode cl-specs cl cl-19 reftex-ref reftex-cite help-mode view
reftex-parse multi-isearch mule-util texmathp bibtex gud asm-mode
fortran cus-edit wid-edit matlab derived tempo rpm-spec-mode compile
conf-mode newcomment autoconf autoconf-mode python-21 python comint ring
edebug eldoc sh-script executable diff-mode jka-compr make-mode cc-mode
cc-fonts cc-menus cc-cmds cc-styles cc-align cc-engine cc-vars cc-defs
latexenc vc-git reftex-vcr reftex-dcr reftex-auc reftex reftex-vars
flyspell preview prv-emacs byte-opt tex-buf noutline outline font-latex
bytecomp byte-compile latex easy-mmode edmacro kmacro tex-style tex
desktop cus-start cus-load uniquify ispell-multi regexp-opt ispell
server info-look info easymenu icomplete paren which-func imenu iswitchb
preview-latex proof-site proof-autoloads pg-vars ibus advice help-fns
advice-preload tex-site auto-loads china-util tooltip ediff-hook
vc-hooks lisp-float-type mwheel x-win x-dnd font-setting tool-bar dnd
fontset image fringe lisp-mode register page menu-bar rfn-eshadow timer
select scroll-bar mldrag 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 loaddefs button minibuffer faces
cus-face files text-properties overlay md5 base64 format env code-pages
mule custom widget hashtable-print-readable backquote
make-network-process dbusbind system-font-setting font-render-setting
gtk x-toolkit x multi-tty emacs)