bug#77924: 31.0.50; [Feature branch] Change marker implementation

[Eli Zaretskii]

> From: Gerd Möllmann <gerd.moellmann@gmail.com>
> Cc: monnier@iro.umontreal.ca,  stefankangas@gmail.com,  77924@debbugs.gnu.org
> Date: Fri, 25 Apr 2025 18:19:12 +0200
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> >> From: Gerd Möllmann <gerd.moellmann@gmail.com>
> >> Cc: Eli Zaretskii <eliz@gnu.org>,  stefankangas@gmail.com,
> >>   77924@debbugs.gnu.org
> >> Date: Fri, 25 Apr 2025 16:08:14 +0200
> >> 
> >> > * master Results
> >> >
> >> >   | test          | non-gc (s) | gc (s) | gcs | total (s) | err |
> >> >   |---------------+------------+--------+-----+-----------+-----|
> >> >   | font-lock     |       0.52 |   0.32 |  24 |      0.84 |  0% |
> >> >   | smie          |       1.19 |   0.50 |  36 |      1.69 |  0% |
> >> >   | smie-nonascii |       2.13 |   0.53 |  39 |      2.66 |  0% |
> >> >   |---------------+------------+--------+-----+-----------+-----|
> >> >   | total         |       3.83 |   1.35 |  99 |      5.19 |  0% |
> >> >
> >> > * text-index Results
> >> >
> >> >   | test          | non-gc (s) | gc (s) | gcs | total (s) | err |
> >> >   |---------------+------------+--------+-----+-----------+-----|
> >> >   | font-lock     |       0.51 |   0.31 |  23 |      0.82 |  0% |
> >> >   | smie          |       1.18 |   0.45 |  33 |      1.63 |  0% |
> >> >   | smie-nonascii |       5.49 |   0.48 |  35 |      5.98 |  0% |
> >> >   |---------------+------------+--------+-----+-----------+-----|
> >> >   | total         |       7.19 |   1.24 |  92 |      8.43 |  0% |
> >> >
> >> > That shows also the difference in smie-nonascii, i.e. in a C file
> >> > containing multi-byte characters (one should suffice to make
> >> > Z != Z_BYTE, and the index is used).
> >> 
> >> I've been reading smie a bit, to get an impression what the smie
> >> slowdown might mean in daily use. As far as I can see elb-smie is basically
> >> 5 times
> >> 
> >>   (indent-region (point-min) (point-max)
> >>   -> indent-region-line-by-line for all lines
> >>   -> indent-region-according-to-mode
> >>   ...
> >> 
> >> xmenu.c has ca. 2500 lines, so 12500 line-by-line indentations.
> >> in 5.49s -> ca. 0.44ms per line. Or, taking 50ms as something a user might
> >> perceive, 113 lines.
> >> 
> >> TBH, I feel somewhat under-motivated to try and optimize that.
> >
> > Do you understand why the branch is slower here?  If so, can you
> > describe the reasons, so we could then think if thye same reasons
> > could slow down other cases?
> 
> I haven't profiled anything .but I'd bet a small amount that it is what
> I wrote in another mail:
> 
>   Stefan Monnier <monnier@iro.umontreal.ca> writes:
> 
>   > - Finally `smie-nonascii` is the same as `smie` except that it uses
>   >   a file that's identical to `xmenu.c` but where all the letters of
>   >   comments/strings/identifiers were replaced by non-ASCII ones.
>   >   Here, we see that TINDEX` is *much* slower than BASE.
>   >   This doesn't seem to be a fluke: I see the exact same performance
>   >   difference in my other pair of builds.
>   >
>   > This last one is a serious problem that we need to address before we can
>   > merge the branch.
> 
>   ASCII means that the text index is basically not used.
> 
>   In the non-ASCII case it is used. Re-indentation means text modification
>   which in turns leads to index invalidation and re-building the index as
>   needed. Index invalidation discards the index from the modification
>   position to the end of the text. Re-building goes from the last valid
>   position the index contains to the next position that is needed to do a
>   position conversion.

If code that causes invalidation and rebuilding of the index makes the
branch much slower, we should perhaps consider how to avoid such
slowdown.  Because there will be more cases which cause something
similar.

Is it possible to invalidate only part(s) of the index?  Surely, at
least some parts can remain intact?