bug#81623: 32.0.50; Long-line optimization severely slows redisplay of invisible newlines

Scott Guest <[email protected]>
Newsgroups gmane.emacs.bugs
Message-ID <CA+Mt--nrp2bYCFon85Y3ibAgNfG9NTgDeL_twHL8PFusm0Z7Dw@mail.gmail.com>
Thanks for the reply. I see the argument that this isn't an outright
bug, and I understand that raising or disabling `long-line-threshold`
is a possible workaround.

My concerns, however, are that:

- The limitation that there are no significant invisible regions is
  not documented (to my knowledge). "Significant portions" is also
  relative: the cost depends on the absolute number of hidden
  newlines, so the problematic region need only be a small relative
  portion of a larger buffer.
- The long line in the reproducer is not itself invisible and is
  off-screen during the timed redisplay. A non-invisible but
  off-screen long line enables a per-buffer optimization flag which
  then causes pathological work in a separate invisible region. This
  feels quite surprising.
- Once a buffer has been recognized as containing a long line,
  `long_line_optimizations_p` is never cleared. Changing
  `long-line-threshold` afterward therefore does not disable the
  optimizations in that buffer; the workaround must be applied before
  the first redisplay that detects an over-threshold line, which may
  be much earlier than the pathological redisplay.

For my use case, visible long lines are quite frequent, while this
pathological case is fairly rare (but still just frequent enough to
cause issues). It would be unfortunate to lose the optimization's
benefit for the common case because of this rarer pathological case.

The redisplay time with the optimization enabled grows roughly
linearly with the number of invisible lines. The real input where I
encountered this had a few MiB of such lines, which made the
slowdown severe enough that redisplay appeared to hang.

More importantly, this appears to be caused by avoidable, redundant
work. [Disclaimer: the analysis below was developed with LLM
assistance, then checked against the source and verified with an
instrumented build. I may still have missed something.]

Redisplay calls `back_to_previous_visible_line_start`, which walks
backward over all 40,000 invisible newlines. After the first step,
each iteration already begins at BOL, immediately after the newline
ending the line just traversed. (This occurs regardless of whether that
line was empty or contained text; the reproducer has bare newlines
solely for minimality.) With long-line optimization enabled, it
nevertheless calls `get_nearby_bol_pos` to find that BOL again.

For almost all iterations in this reproducer, each call scans a
500-character chunk and invokes `find_newline1` about 500
times. Inserting counters around this path, each full backward
traversal made 39,753,460 calls to `find_newline1`. The timed
redisplay invoked that expensive traversal three times. The non-ASCII
character is not required for these redundant scans; it only amplifies
the associated byte/character conversion cost.

A fast path returning `pos` when the preceding byte is a newline
preserves the result of the existing scan and eliminates the slowdown
in this reproducer. [I have omitted the concrete patch since it was
generated by an LLM.]
lmpx.com only provides a reader for public news (NNTP) servers. It is not affiliated with the servers or forums shown here and is not responsible for the content of articles, which is written by their respective authors.