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

From: Gerd Möllmann <[email-masked]>
Date: Fri, 25 Apr 2025 20:21:42 +0200

Gerd Möllmann <[email-masked]> writes:

> Gerd Möllmann <[email-masked]> writes:
>
>> Stefan Monnier <[email-masked]> writes:
>>
>>>>   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.
>>>
>>> I don't see how that would explain such a large slowdown: re-indenting
>>> the whole buffer means reindenting each line, one by one starting from
>>> the first, where indentation of a line modifies only that line and
>>> usually looks only at that line and preceding text.
>>>
>>> So it should cause an O(1) rebuilding of the index: the index will be
>>> flushed when we start indenting the first line, and after that it
>>> will get progressively re-filled and there shouldn't be much more
>>> flushing going on during that time because we rarely look much beyond
>>> the point where we last flushed (and hence beyond the point where we
>>> will next flush).
>>>
>>> Rebuilding the index once should take a very small amount of time
>>> compared to performing the indentation.
>>>
>>> Also, such modifications patterns are not specific to reindentation, so...
>>> "think if the same reasons could slow down other cases?"
>>
>> IÄm thinking of something like this:
>>
>> Assume we initially are position P, and the next index
>> entry > P is I0 and so on.
>>
>>    -----P---------I0-----------I1.....
>>
>> After insertion at P, the index is invalidated
>>
>>    -----P------------------------.....
>>
>> Someone asks for a position P2 < I0, index is built up to
>> I0. If P2 > I0 then more.
>>
>>    -----P--P2-----I0-------------.....
>>
>> We insert at P2, index is invalidated
>>
>>    -----P--P2--------------------.....
>>
>> and so on. Maybe a save-excursion?
>>
>> Hm, and the effect of TEXT_INDEX_INTERVAL might be interesting, if it's
>> somethings like that.
>
> Not well explained. What I simply mean is that we again and again
> might be invalidating the index and need it right after, throw it away,
> need it again.

With interval 4096:

>>> * 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% |

With interval 512

* Results

  | test          | non-gc (s) | gc (s) | gcs | total (s) | err |
  |---------------+------------+--------+-----+-----------+-----|
  | font-lock     |       0.51 |   0.32 |  23 |      0.83 |  0% |
  | smie          |       1.18 |   0.47 |  33 |      1.65 |  0% |
  | smie-nonascii |       5.48 |   0.50 |  35 |      5.98 |  0% |
  |---------------+------------+--------+-----+-----------+-----|
  | total         |       7.18 |   1.29 |  92 |      8.47 |  0% |

Kind of interesting, and a bit surprising for me. So maybe my hypothesis
is wrong. Damn benchmarks.