regexpengine=1 slow in RestructuredText Files

[gavinhoward]

• nvim --version:

  NVIM v0.4.4
  Build type: Gentoo
  Lua 5.1
  Compilation: /usr/bin/x86_64-pc-linux-gnu-gcc -O2 -pipe -U_FORTIFY_SOURCE -D_FORTIFY_SOURCE=1 -Wall -Wextra -pedantic -Wno-unused-parameter -Wstrict-prototypes -std=gnu99 -Wshadow -Wconversion -Wmissing-prototypes -Wimplicit-fallthrough -Wvla -fstack-protector-strong -fno-common -fdiagnostics-color=always -DINCLUDE_GENERATED_DECLARATIONS -D_GNU_SOURCE -DNVIM_MSGPACK_HAS_FLOAT32 -DNVIM_UNIBI_HAS_VAR_FROM -I/var/tmp/portage/app-editors/neovim-0.4.4-r100/work/neovim-0.4.4_build/config -I/var/tmp/portage/app-editors/neovim-0.4.4-r100/work/neovim-0.4.4/src -I/usr/include -I/var/tmp/portage/app-editors/neovim-0.4.4-r100/work/neovim-0.4.4_build/src/nvim/auto -I/var/tmp/portage/app-editors/neovim-0.4.4-r100/work/neovim-0.4.4_build/include
  Compiled by portage@localhost
  
  Features: +acl +iconv +tui
  See ":help feature-compile"
  
     system vimrc file: "/etc/vim/sysinit.vim"
    fall-back for $VIM: "/usr/share/nvim"
  
  Run :checkhealth for more info
  

• Operating system/version: Gentoo Linux x86_64, up to date.

• Terminal name/version: kitty 0.20.3 running tmux 3.1c

• $TERM: screen-256color

[ ] vim -u DEFAULTS (version: 8.2) behaves differently

vim version info:

VIM - Vi IMproved 8.2 (2019 Dec 12, compiled Jun  1 2021 22:57:11)
Included patches: 1-814
Modified by Gentoo-8.2.0814-r100
Compiled by gavin@localhost
Huge version without GUI.  Features included (+) or not (-):
+acl               -farsi             +mouse_sgr         +tag_binary
+arabic            +file_in_path      -mouse_sysmouse    -tag_old_static
+autocmd           +find_in_path      +mouse_urxvt       -tag_any_white
+autochdir         +float             +mouse_xterm       -tcl
-autoservername    +folding           +multi_byte        +termguicolors
-balloon_eval      -footer            +multi_lang        -terminal
+balloon_eval_term +fork()            -mzscheme          +terminfo
-browse            +gettext           +netbeans_intg     +termresponse
++builtin_terms    -hangul_input      +num64             +textobjects
+byte_offset       +iconv             +packages          +textprop
+channel           +insert_expand     +path_extra        +timers
+cindent           +ipv6              -perl              +title
+clientserver      +job               +persistent_undo   -toolbar
+clipboard         +jumplist          +popupwin          +user_commands
+cmdline_compl     +keymap            +postscript        +vartabs
+cmdline_hist      +lambda            +printer           +vertsplit
+cmdline_info      +langmap           +profile           +virtualedit
+comments          +libcall           -python            +visual
+conceal           +linebreak         -python3           +visualextra
+cryptv            +lispindent        +quickfix          +viminfo
-cscope            +listcmds          +reltime           +vreplace
+cursorbind        +localmap          +rightleft         +wildignore
+cursorshape       -lua               -ruby              +wildmenu
+dialog_con        +menu              +scrollbind        +windows
+diff              +mksession         +signs             +writebackup
+digraphs          +modify_fname      +smartindent       +X11
-dnd               +mouse             -sound             +xfontset
-ebcdic            -mouseshape        +spell             -xim
+emacs_tags        +mouse_dec         +startuptime       -xpm
+eval              +mouse_gpm         +statusline        +xsmp_interact
+ex_extra          -mouse_jsbterm     -sun_workshop      +xterm_clipboard
+extra_search      +mouse_netterm     +syntax            -xterm_save
   system vimrc file: "/etc/vim/vimrc"
     user vimrc file: "$HOME/.vimrc"
 2nd user vimrc file: "~/.vim/vimrc"
      user exrc file: "$HOME/.exrc"
       defaults file: "$VIMRUNTIME/defaults.vim"
  fall-back for $VIM: "/usr/share/vim"
Compilation: x86_64-pc-linux-gnu-gcc -c -I. -Iproto -DHAVE_CONFIG_H     -O2 -pipe -U_FORTIFY_SOURCE -D_FORTIFY_SOURCE=1
Linking: x86_64-pc-linux-gnu-gcc   -Wl,-O1 -L/usr/local/lib -Wl,--as-needed -o vim    -lSM -lICE -lXpm -lXt -lX11 -lXdmcp -lSM -lICE  -lm -ltinfo -lelf  -lacl -lattr -lgpm -ldl

Steps to reproduce using nvim -u NORC

nvim -u NORC
# Alternative for shell-related problems:
# env -i TERM=ansi-256color "$(which nvim)"
:set regexpengine=1
:e <location_of_main.rst_in_Actual_Behavior_below>
:570
o<BS>* Pointers should not be typed (

Actual behaviour

When opening the file that can be found at https://git.yzena.com/Yzena/Yc/src/branch/master/docs/yvm/design/main.rst, Neovim takes several seconds to render the file, eventually spitting out the message:

'redrawtime' exceeded, syntax highlighting disabled

If you go down to the bottom of the file, just above the line:

.. toctree::

on line 570, insert a new line, and type:

* Pointers should not be typed (

Neovim freezes when trying to type the (.

When I profiled the problem with the procedure recommended here, and when using the reproducer with nvim -u NORC above, I got the following in my profile.log:

FUNCTIONS SORTED ON SELF TIME
count  total (s)   self (s)  function
   66            366.269548  <SNR>12_Highlight_Matching_Pair()
  591              0.000869  RstFold#GetRstFold()
   48              0.000693  <SNR>26_DefineOneInlineMarkup()
    6   0.001034   0.000342  <SNR>26_DefineInlineMarkup()
    1   0.000405   0.000326  <SNR>2_LoadFTPlugin()
    1   0.028966   0.000116  <SNR>5_SynSet()
    1   0.000102   0.000063  <SNR>3_LoadIndent()
    1              0.000057  GetRSTIndent()
    1              0.000030  <SNR>13_LocalBrowse()

which obviously shows 73_Highlight_Matching_Pair() as the problem.

When finding Highlight_Matching_Pair() in profile.log, I see this:

FUNCTION  <SNR>12_Highlight_Matching_Pair()
    Defined: /usr/share/nvim/runtime/plugin/matchparen.vim line 39
Called 66 times
Total time: 366.269548
 Self time: 366.269548

count  total (s)   self (s)
                              " Remove any previous match.
   66              0.000335   if exists('w:paren_hl_on') && w:paren_hl_on
                                silent! call matchdelete(3)
                                let w:paren_hl_on = 0
   66              0.000058   endif
                            
                              " Avoid that we remove the popup menu.
                              " Return when there are no colors (looks like the cursor jumps).
   66              0.000207   if pumvisible() || (&t_Co < 8 && !has("gui_running"))
                                return
   66              0.000023   endif
                            
                              " Get the character under the cursor and check if it's in 'matchpairs'.
   66              0.000153   let c_lnum = line('.')
   66              0.000114   let c_col = col('.')
   66              0.000060   let before = 0
                            
   66              0.000134   let text = getline(c_lnum)
   66              0.000758   let matches = matchlist(text, '\(.\)\=\%'.c_col.'c\(.\=\)')
   66              0.000096   if empty(matches)
                                let [c_before, c] = ['', '']
   66              0.000036   else
   66              0.000180     let [c_before, c] = matches[1:2]
   66              0.000027   endif
   66              0.000369   let plist = split(&matchpairs, '.\zs[:,]')
   66              0.000144   let i = index(plist, c)
   66              0.000054   if i < 0
                                " not found, in Insert mode try character before the cursor
   65              0.000166     if c_col > 1 && (mode() == 'i' || mode() == 'R')
   62              0.000111       let before = strlen(c_before)
   62              0.000060       let c = c_before
   62              0.000097       let i = index(plist, c)
   65              0.000026     endif
   65              0.000046     if i < 0
                                  " not found, nothing to do
   63              0.000042       return
    2              0.000001     endif
    3              0.000001   endif
                            
                              " Figure out the arguments for searchpairpos().
    3              0.000003   if i % 2 == 0
    3              0.000003     let s_flags = 'nW'
    3              0.000005     let c2 = plist[i + 1]
                              else
                                let s_flags = 'nbW'
                                let c2 = c
                                let c = plist[i - 1]
    3              0.000001   endif
    3              0.000003   if c == '['
                                let c = '\['
                                let c2 = '\]'
    3              0.000001   endif
                            
                              " Find the match.  When it was just before the cursor move it there for a
                              " moment.
    3              0.000002   if before > 0
    2              0.000006     let has_getcurpos = exists("*getcurpos")
    2              0.000002     if has_getcurpos
                                  " getcurpos() is more efficient but doesn't exist before 7.4.313.
    2              0.000005       let save_cursor = getcurpos()
                                else
                                  let save_cursor = winsaveview()
    2              0.000001     endif
    2              0.000006     call cursor(c_lnum, c_col - before)
    3              0.000001   endif
                            
    3              0.000017   if !has("syntax") || !exists("g:syntax_on")
                                let s_skip = "0"
    3              0.000001   else
                                " Build an expression that detects whether the current cursor position is
                                " in certain syntax types (string, comment, etc.), for use as
                                " searchpairpos()'s skip argument.
                                " We match "escape" for special items, such as lispEscapeSpecial.
    3              0.000008     let s_skip = '!empty(filter(map(synstack(line("."), col(".")), ''synIDattr(v:val, "name")''), ' . '''v:val =~? "string\\|character\\|singlequote\\|escape\\|comment"''))'
                                " If executing the expression determines that the cursor is currently in
                                " one of the syntax types, then we want searchpairpos() to find the pair
                                " within those syntax types (i.e., not skip).  Otherwise, the cursor is
                                " outside of the syntax types and s_skip should keep its value so we skip
                                " any matching pair inside the syntax types.
                                " Catch if this throws E363: pattern uses more memory than 'maxmempattern'.
    3              0.000003     try
    3              0.000820       execute 'if ' . s_skip . ' | let s_skip = "0" | endif'
                                catch /^Vim\%((\a\+)\)\=:E363/
                                  " We won't find anything, so skip searching, should keep Vim responsive.
                                  return
    3              0.000002     endtry
    3              0.000001   endif
                            
                              " Limit the search to lines visible in the window.
    3              0.000007   let stoplinebottom = line('w$')
    3              0.000007   let stoplinetop = line('w0')
    3              0.000003   if i % 2 == 0
    3              0.000004     let stopline = stoplinebottom
                              else
                                let stopline = stoplinetop
    3              0.000001   endif
                            
                              " Limit the search time to 300 msec to avoid a hang on very long lines.
                              " This fails when a timeout is not supported.
    3              0.000006   if mode() == 'i' || mode() == 'R'
    2              0.000007     let timeout = exists("b:matchparen_insert_timeout") ? b:matchparen_insert_timeout : g:matchparen_insert_timeout
    1              0.000000   else
    1              0.000003     let timeout = exists("b:matchparen_timeout") ? b:matchparen_timeout : g:matchparen_timeout
    3              0.000001   endif
    3              0.000001   try
    3            366.264369     let [m_lnum, m_col] = searchpairpos(c, '', c2, s_flags, s_skip, stopline, timeout)
                              catch /E118/
                                " Can't use the timeout, restrict the stopline a bit more to avoid taking
                                " a long time on closed folds and long lines.
                                " The "viewable" variables give a range in which we can scroll while
                                " keeping the cursor at the same position.
                                " adjustedScrolloff accounts for very large numbers of scrolloff.
                                let adjustedScrolloff = min([&scrolloff, (line('w$') - line('w0')) / 2])
                                let bottom_viewable = min([line('$'), c_lnum + &lines - adjustedScrolloff - 2])
                                let top_viewable = max([1, c_lnum-&lines+adjustedScrolloff + 2])
                                " one of these stoplines will be adjusted below, but the current values are
                                " minimal boundaries within the current window
                                if i % 2 == 0
                                  if has("byte_offset") && has("syntax_items") && &smc > 0
                            	let stopbyte = min([line2byte("$"), line2byte(".") + col(".") + &smc * 2])
                            	let stopline = min([bottom_viewable, byte2line(stopbyte)])
                                  else
                            	let stopline = min([bottom_viewable, c_lnum + 100])
                                  endif
                                  let stoplinebottom = stopline
                                else
                                  if has("byte_offset") && has("syntax_items") && &smc > 0
                            	let stopbyte = max([1, line2byte(".") + col(".") - &smc * 2])
                            	let stopline = max([top_viewable, byte2line(stopbyte)])
                                  else
                            	let stopline = max([top_viewable, c_lnum - 100])
                                  endif
                                  let stoplinetop = stopline
                                endif
                                let [m_lnum, m_col] = searchpairpos(c, '', c2, s_flags, s_skip, stopline)
    3              0.000002   endtry
                            
    3              0.000004   if before > 0
    2              0.000002     if has_getcurpos
    2              0.000008       call setpos('.', save_cursor)
                                else
                                  call winrestview(save_cursor)
    2              0.000001     endif
    3              0.000001   endif
                            
                              " If a match is found setup match highlighting.
    3              0.000004   if m_lnum > 0 && m_lnum >= stoplinetop && m_lnum <= stoplinebottom 
                                if exists('*matchaddpos')
                                  call matchaddpos('MatchParen', [[c_lnum, c_col - before], [m_lnum, m_col]], 10, 3)
                                else
                                  exe '3match MatchParen /\(\%' . c_lnum . 'l\%' . (c_col - before) . 'c\)\|\(\%' . m_lnum . 'l\%' . m_col . 'c\)/'
                                endif
                                let w:paren_hl_on = 1
    3              0.000001   endif

So it appears that searchpairpos() may be the problem.

In addition, editing RestructuredText files in Neovim just feels slow, and when profiling the slow editing, nothing really stands out.

Expected behaviour

Instant, or near instant, editing of RestructuredText files.

Other

I would love to help fix this, but I am not familiar enough with Neovim's code to help. If I can get some pointers, I can try to track it down further and fix it.

[glacambre]

I would love to help fix this, but I am not familiar enough with Neovim's code to help. If I can get some pointers, I can try to track it down further and fix it.

What I would do here is start by reproducing the bug on master (you can compile from source by following the instructions here). Once you've confirmed that the bug still exists on master there are multiple paths:

• Attempt to reproduce the bug with an old Vim. If you're able to do that, you'll be able to bisect Vim until you find the patch that fixed it. Would certainly help a lot.
• Attempt to figure out what exactly in searchpairpos is taking time. You can use the perf command to do that (e.g. perf record --user-callchains --call-graph=dwarf ./nvim and then perf report -s sym --branch-history). This might show you something that could be optimized.
• Go through the list of unported Vim patches that seem related to searchpairpos (you can list unported patches by running ./scripts/vim-patch.sh -l in the neovim repo) and see if one seems likely to fix the bug you're encountering.

[gavinhoward]

A couple things.

First, I made a mistake in my vim test. vim does not behave differently. I have updated my first comment accordingly.

Second, I actually ran :help regexpengine=1, and found out that regexpengine=1 sets the old regex engine. The default is 0, which selects the old or new automatically based on performance and capability (if I read it right).

So I guess technically, this isn't a bug, since the old engine probably isn't getting some love. And with the default, Neovim runs fine.

I changed the title of this bug report to point future users in the right direction.

Future users: if you run into this problem, you probably have set regexpengine=1 in your .config/nvim/init.vim. Delete it, and Neovim should select the new, faster engine automatically.

I am closing this report, but the maintainers are welcome to reopen it if they wish.

[chrisbra]

We actually do care about regexp engine 1. But it's actually the skip expression (meaning evaluating the syntax stack) that is so expensive. I wondered about it, because the searchpairpos() call is called with a timeout value. But that is not the problem here. Evaluating the syntax stack takes so long. Check the output of :syntime report (see below). What helps is using :unlet g:syntax_on which will make the matparen plugin to use a skip expression of 0. I had a quick look at passing the timeout value into the eval() stack, but that is turns out to be very convoluted :/

It may also help to tune the syn sync from rules.

Ping @brammool and @marshallward, because the rstExDirective syntax region might be tuned (e.g. by adding an atom to force the regexp-engine 2):

execute 'syn region rstExDirective contained matchgroup=rstDirective' .
      \ ' start=+' . s:ReferenceName . '::\_s+' .
      \ ' skip=+^$+' .
      \ ' end=+^\s\@!+ contains=@rstCruft,rstLiteralBlock'

The ^\s\@! - That looks expensive :/

FWIW, the output of syntime report on my development machine:

  5.480519   9      3       1.790491    0.608947  rstExDirective     [[:alnum:]]\%([-_.:+]\?[[:alnum:]]\+\)*::\_s
  0.364432   393    0       0.121854    0.000927  rstHyperlinkReference \<[[:alnum:]]\%([-_.:+]\?[[:alnum:]]\+\)*__\=\ze\%($\|\s\|['")\]}>/:.,;!?\\-]\)
  0.007962   393    0       0.000090    0.000020  rstInlineInternalTargets \%(^\|\s\|\%ua0\|['"([{</:]\)\zs_`[^[:space:]`] `\ze\%($\|\s\|['")\]}>/:.,;!?\\-]\)
  0.007803   393    0       0.000070    0.000020  rstEmphasis        \%(^\|\s\|\%ua0\|['"([{</:]\)\zs\*[^[:space:]*] \*\ze\%($\|\s\|['")\]}>/:.,;!?\\-]\)
  0.007796   393    0       0.000093    0.000020  rstStrongEmphasis  \%(^\|\s\|\%ua0\|['"([{</:]\)\zs\*\*[^[:space:]*] \*\*\ze\%($\|\s\|['")\]}>/:.,;!?\\-]\)
  0.007736   393    0       0.000064    0.000020  rstInlineLiteral   \%(^\|\s\|\%ua0\|['"([{</:]\)\zs``[^[:space:]`] ``\ze\%($\|\s\|['")\]}>/:.,;!?\\-]\)
  0.007722   384    0       0.000075    0.000020  rstInterpretedTextOrHyperlinkReference \%(^\|\s\|\%ua0\|['"([{</:]\)\zs`[^[:space:]`] `_\{0,2}\ze\%($\|\s\|['")\]}>/:.,;!?\\-]\)
  0.007702   393    0       0.000058    0.000020  rstSubstitutionReference \%(^\|\s\|\%ua0\|['"([{</:]\)\zs|[^[:space:]|] |_\{0,2}\ze\%($\|\s\|['")\]}>/:.,;!?\\-]\)
  0.007394   393    0       0.000182    0.000019  rstSubstitutionReference \%(^\|\s\|\%ua0\|[/:]\)\zs|\ze[^[:space:]|]
  0.007262   393    0       0.000118    0.000018  rstInlineInternalTargets \%(^\|\s\|\%ua0\|[/:]\)\zs_`\ze[^[:space:]`]
  0.007258   399    6       0.000156    0.000018  rstInlineLiteral   \%(^\|\s\|\%ua0\|[/:]\)\zs``\ze[^[:space:]`]
  0.007203   393    0       0.000076    0.000018  rstEmphasis        \%(^\|\s\|\%ua0\|[/:]\)\zs\*\ze[^[:space:]*]
  0.007172   384    0       0.000119    0.000019  rstInterpretedTextOrHyperlinkReference \%(^\|\s\|\%ua0\|[/:]\)\zs`\ze[^[:space:]`]
  0.007125   393    0       0.000061    0.000018  rstStrongEmphasis  \%(^\|\s\|\%ua0\|[/:]\)\zs\*\*\ze[^[:space:]*]
  0.003964   384    0       0.000039    0.000010  rstDirectivepython \c\%(sourcecode\|code\%(-block\)\=\)::\s\+\%(python\)\_s*\n\ze\z(\s\+\)
  0.003791   384    0       0.000062    0.000010  rstDirectivecpp    \c\%(sourcecode\|code\%(-block\)\=\)::\s\+\%(cpp\|c++\)\_s*\n\ze\z(\s\+\)
  0.003786   384    0       0.000070    0.000010  rstDirectivevim    \c\%(sourcecode\|code\%(-block\)\=\)::\s\+\%(vim\)\_s*\n\ze\z(\s\+\)
  0.003772   384    0       0.000085    0.000010  rstDirectivephp    \c\%(sourcecode\|code\%(-block\)\=\)::\s\+\%(php\)\_s*\n\ze\z(\s\+\)
  0.003679   384    6       0.000052    0.000010  rstStandaloneHyperlink \<\%(\%(\%(https\=\|file\|ftp\|gopher\)://\|\%(mailto\|news\):\)[^[:space:]'\"<>]\+\|www[[:alnum:]_-]*\.[[:alnum:]_-]\+\.[^[:space:]'\"<>]\+\)[[:alnum:]/]
  0.003661   384    0       0.000043    0.000010  rstDirectivesh     \c\%(sourcecode\|code\%(-block\)\=\)::\s\+\%(sh\)\_s*\n\ze\z(\s\+\)
  0.003650   384    0       0.000033    0.000010  rstDirectivejava   \c\%(sourcecode\|code\%(-block\)\=\)::\s\+\%(java\)\_s*\n\ze\z(\s\+\)
  0.003649   384    0       0.000039    0.000010  rstDirectiveperl   \c\%(sourcecode\|code\%(-block\)\=\)::\s\+\%(perl\)\_s*\n\ze\z(\s\+\)
  0.003644   384    0       0.000048    0.000009  rstDirectivelisp   \c\%(sourcecode\|code\%(-block\)\=\)::\s\+\%(lisp\)\_s*\n\ze\z(\s\+\)
  0.003482   384    0       0.000041    0.000009  rstCitationReference \%(\s\|^\)\[[[:alnum:]]\%([-_.:+]\?[[:alnum:]]\+\)*\]_\ze\%($\|\s\|['")\]}>/:.,;!?\\-]\)
  0.003399   393    0       0.000056    0.000009  rstFootnoteReference \%(\s\|^\)\[\%(\d\+\|#\%([[:alnum:]]\%([-_.:+]\?[[:alnum:]]\+\)*\)\=\|\*\)\]_
  0.002163   393    3       0.000068    0.000006  rstLiteralBlock    \(^\z(\s*\).*\)\@<=::\n\s*\n
  0.001176   384    3       0.000058    0.000003  rstSections        \v^%(([=`:.'"~^_*+#-])\1{2,}\n)?.{3,}\n([=`:.'"~^_*+#-])\2{2,}$
  0.000298   393    0       0.000002    0.000001  rstInlineInternalTargets ’\zs_`\ze[^[:space:]’`]
  0.000266   393    0       0.000002    0.000001  rstStrongEmphasis  ’\zs\*\*\ze[^[:space:]’*]

[chrisbra]

BTW: wondering if this:

end=+^\s@!+ contains=@rstCruft,rstLiteralBlock'

couldn't easily be written as end=+^\S\|$' not sure

[gavinhoward]

Okay. I will reopen this issue and investigate with syntime.

[marshallward]

I think the end=+^\s\@!+ must be from Nikolai's original implementation.

Most of his regions were terminated by a block without leading whitespace, which was never strictly correct and has been gradually relaxed throughout other regions, so I would think that it could be replaced with something less expensive.