Degrading scroll performance in terminal mode

# The Problem #

Since I switched to emacs I noticed how scrolling sporadically became worse. At times, it would take 3-4s to redraw 40 lines of code.

# Apparent relevant factors #

After doing a lot of analyzing I narrowed it down to the following combination of things:

1) Emacs must run in terminal, in GUI either the problem is not as apparent or its non-existant.
2) gc-cons-threshold must be set to a high value. LSP users likely have something like `(setq gc-cons-threshold 100000000)`
3) `haskell-mode` and `font-lock-mode` must be enabled
4) Do some text editing

Watch drawing lines become slower. The presence of constructor names seems especially bad. Note, that the entire line is drawn much slower, so if you vertically tile your emacs to have some unrelated buffer on the right hand side, then the entire line with many data constructors on the left hand window will be drawn slowly.

5) If you then cause a `(garbage-collect)`, scrolling becomes fast again.
[test.hs.gz](https://github.com/haskell/haskell-mode/files/6681259/test.hs.gz)

# Reproduce #

Locally I used emacs 27.1 installed through the emacs nix overlay:

Click to see/use my nixos module

```nix
{ config, pkgs, ... }:

let
emacsOverlay = import (builtins.fetchTarball {
# Descriptive name to make the store path easier to identify
name = "emacs-overlay-2020-09-11";
# Commit hash for nixos-unstable as of 2018-09-12
url = https://github.com/nix-community/emacs-overlay/archive/a69588a3f7de6d68f20cea21562ab7f6f91a400a.tar.gz;
# Hash obtained using `nix-prefetch-url --unpack `
sha256 = "180jp31zfrlhnz490x6hckz6z3bvfxwz1613cg4zmf0lrflrl3gp";
});

myEmacs = pkgs.emacs;
emacsWithPackages = (pkgs.emacsPackagesGen myEmacs).emacsWithPackages;
emacs = emacsWithPackages (epkgs: (with epkgs.melpaStablePackages; [
# melpa stable
ripgrep
magit
# dockerfile-mode
# markdown-mode
# yaml-mode
# json-mode
# go-mode
# nix-mode
use-package
projectile
# direnv
# swiper
# ox-gfm
# pdf-tools
]) ++ (with epkgs.melpaPackages; [
# melpa unstable
solarized-theme
gruvbox-theme
company
counsel
counsel-projectile
ivy
evil
evil-collection
evil-magit
haskell-mode
lsp-mode
lsp-ui
lsp-haskell
lsp-treemacs
treemacs
flycheck
]) ++ (with epkgs.elpaPackages; [
# elpa packages
undo-tree
]) ++ [
# main packages
]);
in

{
nixpkgs.overlays = [emacsOverlay];

services.emacs.enable = true;
services.emacs.install = true;
services.emacs.defaultEditor = true;
services.emacs.package = emacs;
}

```

1. Download the attached test file and edit with `emacsclient -nw`
2. Ensure you do *not* have `undo-tree-mode` enabled. This minor mode causes GCs during the test case, leading to inconsistent behavior.
3. Set `(setq garbage-collection-messages t)` to have emacs tell you if a GC is run
Note: This is just for your own sanity so you do know if for some reason there's an unexpected GC
4. Set `(setq gc-cons-threshold most-positive-fixnum)`
Note: We use the highest value to ensure the GC doesn't interfere with our testcase due to some unforseen circumstances. It's an unreasonable value for the real world.
5. Repeatedly `cut+paste` the block below the definition of `info` until the end of the file. Ideally keep a small terminal (say 80x24), this lets you see the redisplay of the definitions of `info Attr ...` nicely during `cut+paste`. Repeating this 4-5 times is enough to make performance absolutely unbearable.

Watch the performance degrade with every `cut+paste`.

5. Run a `(garbage-collect)` and watch performance be fast again.

# Notes of interest: #

1. If the block at the end is wrapped inside a comment, performance stays stable during `cut+paste`
2. ~~If the block at the end is not font locked (as far as I can tell), performance degrades during `cut+paste`~~
I'm beginning to think there's font-locking on whatever context is there - and the code behind it introduces markers, perhaps per-character or line.
3. The redisplay degradation is particularly linked to the font locking on data constructors.
If we add more data constructors in those definitions of `info`, then the performance
degradation is much worse.
4. The redisplay performance extends to the entire frame, not just the buffer. Two ways to demonstrate this: If you resize the frame to full screen, watch how every line including toolbar and mode line is drawn slowly too. You can also create horizontal/vertical split windows, and watch how these get redrawn slowly too when the frame is switched between full screen and windowed.
5. The problem is reproducible with `undo-tree-mode` present, `(setq gc-cons-threshold 100000000)` and normal editing of text.
Often writing a 60 line region can cause quite bad performance degradation already, it's just more inconsistent. This I want to point out before someone makes a comment about how repeatedly `cut+paste` on 10k lines of code is not normal emacs usage. This is just a synthesized test case with a clear communicatable description how to reproduce.
6) The emacs profiler does not help at all.
7) During degraded performance, the CPU usage spikes to 100% while scrolling.

## Profiler output ##
If the performance has degraded, running the `profiler` while scrolling up and down for a minute gives these CPU and Memory reports

### CPU Profiler output ###

Click me to expand!

```
Function CPU samples %
- command-execute 3417 99%
- call-interactively 3417 99%
- funcall-interactively 3284 96%
- execute-extended-command 2300 67%
- sit-for 2287 66%
- redisplay 2287 66%
+ redisplay_internal (C function) 1 0%
+ command-execute 12 0%
scroll-down-command 534 15%
- scroll-up-command 450 13%
+ scroll-up 1 0%
+ byte-code 133 3%
+ evil-repeat-post-hook 1 0%
evil--jump-hook 1 0%
+ timer-event-handler 1 0%
+ ... 0 0%
```

### Memory profiler output ###

Click me to expand!

```
Function Bytes %
- command-execute 8,755,700 99%
- call-interactively 8,755,700 99%
- byte-code 4,469,695 50%
- read-extended-command 4,469,695 50%
- completing-read 4,469,695 50%
- ivy-completing-read 4,469,695 50%
- ivy-read 4,469,695 50%
- read-from-minibuffer 2,628,499 29%
+ ivy--queue-exhibit 2,068,301 23%
+ command-execute 49,096 0%
+ redisplay_internal (C function) 12,416 0%
+ minibuffer-inactive-mode 7,392 0%
+ # 1,056 0%
+ undo-auto--add-boundary 1,056 0%
+ undo-auto--undoable-change 72 0%
+ ivy--reset-state 256,404 2%
+ ivy-call 1,056 0%
+ ivy--update-prompt 1,024 0%
- funcall-interactively 4,286,005 48%
- execute-extended-command 4,259,293 48%
- command-execute 3,791,263 43%
- call-interactively 3,791,263 43%
- funcall-interactively 3,791,247 43%
profiler-stop 3,790,592 43%
profiler-start 655 0%
+ sit-for 273,374 3%
+ scroll-down-command 15,960 0%
+ scroll-up-command 10,752 0%
+ redisplay_internal (C function) 23,224 0%
+ jit-lock--antiblink-post-command 8,360 0%
+ timer-event-handler 6,200 0%
evil--jump-handle-buffer-crossing 2,112 0%
+ global-font-lock-mode-check-buffers 1,056 0%
+ internal-echo-keystrokes-prefix 1,056 0%
... 0 0%
```

### GC Output ###

I first did `cut+paste` to degrade performance, then executed two `(garbage-collect)` in a row

The first, which fixed performance, gave us the following output

First GC (After degraded performance): Click me to expand!

```
((conses 16 4979055 645610)
(symbols 48 93078 29)
(strings 32 158480 15678)
(string-bytes 1 8876291)
(vectors 16 92580)
(vector-slots 8 1958997 416166)
(floats 8 336 1527)
(intervals 56 1006222 9317)
(buffers 1000 42))
```

Second GC, immediately again. This is just to observe whether the first GC has collected
huge amounts of memory. Note: It did not. The output is very similar to that of the run before.

First GC (After degraded performance): Click me to expand!

```
((conses 16 4947118 644997)
(symbols 48 93078 29)
(strings 32 158477 15588)
(string-bytes 1 8875403)
(vectors 16 92579)
(vector-slots 8 1958985 414138)
(floats 8 336 1527)
(intervals 56 1006220 9301)
(buffers 1000 42))
```