Slow with large inputs

[danielshahaf]

Highlighting of long, multiline buffers is slow.

Example: fned compdef (and type <SPACE> to trigger highlighting after the buffer loads).

zprof:

num  calls                time                       self            name
-----------------------------------------------------------------------------------
 1)    1        3667.13  3667.13   97.24%   1738.93  1738.93   46.11%  zed
 2)    6        1949.29   324.88   51.69%   1179.83   196.64   31.29%  _zsh_highlight_main_highlighter
 3)  730         525.18     0.72   13.93%    525.18     0.72   13.93%  _zsh_highlight_main_add_region_highlight
 4)  210         167.10     0.80    4.43%    157.38     0.75    4.17%  _zsh_highlight_main_highlighter_check_path

Breaking out the last line of _zsh_highlight_main_add_region_highlight` to its own anonymous function gives:

num  calls                time                       self            name
-----------------------------------------------------------------------------------
 1)    1        4527.99  4527.99   94.19%   2615.75  2615.75   54.41%  zed
 2)   18        2010.15   111.67   41.82%   1200.16    66.68   24.97%  _zsh_highlight_main_highlighter
 3) 1088         542.19     0.50   11.28%    542.19     0.50   11.28%  (anon)
 4)  220         172.81     0.79    3.59%    161.77     0.74    3.37%  _zsh_highlight_main_highlighter_check_path
 5)    2          56.66    28.33    1.18%     56.66    28.33    1.18%  VCS_INFO_quilt
 6)  749         554.89     0.74   11.54%     53.08     0.07    1.10%  _zsh_highlight_main_add_region_highlight

And indeed:

% zsh -fc 'local -a a; time ( repeat 5000 { a+=(foo) } )' 
( repeat 5000; do; a+=(foo) ; done; )  1.26s user 0.00s system 99% cpu 1.268 total
% zsh -fc 'local -a a; time ( repeat 10000 { a+=(foo) } )' 
( repeat 10000; do; a+=(foo) ; done; )  5.02s user 0.00s system 99% cpu 5.028 total
% zsh -fc 'local -a a; time ( repeat 20000 { a+=(foo) } )' 
( repeat 20000; do; a+=(foo) ; done; )  19.94s user 0.08s system 99% cpu 20.036 total

So:

• Around a quarter of syntax highlighting runtime is due to array appends.
• Array appends are O(n²) (using zsh 5.1.1-test-1, i.e., a 5.1.2 prerelease).
• 75% of the runtime is in _zsh_highlight_main_highlighter itself.

Action items:

• Follow up with zsh upstream about quadratic behaviour. Done in workers/37236
  • Make any necessary fixes in zsh upstream
• Investigate the 75% that are in _zsh_highlight_main_highlighter.
• Document ZSH_HIGHLIGHT_MAXLENGTH (including the tip from Add ability to temporarily disable highlighting #86).
  Status: spun off to Document ZSH_HIGHLIGHT_MAXLENGTH #698.