Subject: Re: Slow highlighting (Re: "drop-in replacement" and transpose-words-match)
From: Sebastian Gniazdowski <[email-masked]>
To: Bart Schaefer <[email-masked]>
Cc: Zsh hackers list <[email-masked]>
Date: Thu, 11 Feb 2016 11:43:50 +0100
List-Id: Zsh Workers List <zsh-workers.zsh.org>

Hello,

a=""; a=${(r:100000::_:)a}; zshstyle() { repeat 100; do
b=${a[-5000,-1]}; done }; shstyle() { repeat 100; do b=${a:
-5000:5000}; done }; time ( zshstyle ); time ( shstyle )

( zshstyle; )  0,66s user 0,01s system 99% cpu 0,673 total
( shstyle; )  0,40s user 0,00s system 99% cpu 0,402 total

The point of this tangent example is: every indexing works by
iterating over buffer and counting characters. By using ":5000" one
pass of finding where an index points to is skipped, as it says "5000
characters from now on". Index -1 iterates from the beginning again to
find end of string.

Here Zsyh indexes buffer, uses -1 and also (i):

    if [[ $arg == ';' ]] ; then
      local needle=$'[;\n]'
      integer offset=${${buf[start_pos+1,-1]}[(i)$needle]}
      (( start_pos += offset - 1 ))
      (( end_pos = start_pos + $#arg ))
    else
      ((start_pos+=${#buf[$start_pos+1,-1]}-${#${buf[$start_pos+1,-1]##([[:space:]]|\\[[:space:]])#}}))
      ((end_pos=$start_pos+${#arg}))
    fi

The longer the buffer the more time -1 consumes. Of course any
indexing is slow, not only -1, but this is nice emphasis of the issue.
The only solution is apparently making Zsh storing strings as real
arrays, of wint_t type.

As for the (i), as far as I remember from the time I worked on C
source, reverse indexing uses one additional "iterate counting
characters" block:

https://github.com/zsh-users/zsh/blob/master/Src/params.c#L1360-L1396

That said, zsyh could be somewhat optimized if the ":howmany" syntax
would be utilized.

Best regards,
Sebastian Gniazdowski