Slow in some pathological cases

[purcell]

In the case of reformatting this Haskell file with ormolu v0.0.1.0, replacing the buffer contents takes an extraordinary and unacceptable amount of time (from 30s to many minutes), even though the formatter program itself executes quickly (< 0.25s).

Inputs/outputs are captured in this gist. They are somewhat pathological, in that the input source file is 64kb and the resulting diff is 36kb with 202 modified regions.

The problem is visible in Emacs 26.3: in Emacs > 26.1 we use Emacs' replace-buffer-contents function, which aims to preserve text properties, regions, markers etc. as much as possible during operations such as this. (The closest alternative insert-file-contents makes only limited attempts to do this, but generally preserves point quite effectively.)

It turns out that this is a known issue with replace-buffer-contents, which has even subsequently gained a new argument to limit execution time, after which it will revert to a simpler buffer content replacement method. This seems like a strange design choice.

The options for dealing with this in reformatter.el are, roughly:

• Skip using replace-buffer-contents entirely. Most reformatting code "in the wild" does this anyway, of course, because it pre-dates replace-buffer-contents.
• Use replace-buffer-contents only if it supports the time limit argument, and set the time limit to something like 0.5s. This makes the results somewhat nondeterministic, but may generally give the best results for users in the usual fast-replacement case. Here, also, the fallback behaviour may not work as well as just insert-file-contents, so this would require a little testing.
• Use replace-buffer-contents only if the current file is sufficiently small, ie. unlikely to be pathological. This limit might be around 5kb.

I'd probably favour the first approach (ie. avoid replace-buffer-contents).

/cc @mrkkrp, who raised this issue, and @wbolster & @ludwigpacifici, who encouraged the use of replace-buffer-contents in #10.

[purcell]

I'd also note that replace-buffer-contents is not used by any internal Emacs code or libraries, so I wouldn't particularly describe it as battle-tested.

[purcell]

For now, I have pushed the simple fix, which is to avoid replace-buffer-contents entirely.

[ludwigpacifici]

Hello @purcell,

I did a quick benchmark when formatting OCaml code with replace-buffer-contents and insert-file-contents https://github.com/ocaml-ppx/ocamlformat/issues/570#issuecomment-475992400. However, I never witness slowness above 30 seconds.

I wanted OCamlFormat to use reformatter.el (see issue https://github.com/ocaml-ppx/ocamlformat/issues/570). To do that, the new Elisp implementation should be as close as possible with their current implementation - they currently use replace-buffer-contents. As of today, it is unclear if OCamlFormat will use reformatter.el. For information, I'll link this topic in the OCamlFormat issue.

In practice, I never had any issue whether replace-buffer-contents or insert-file-contents was used under the hood. My personal opinion would be to keep the code simple, i.e. go for the first approach.

[purcell]

Closing, since there is no known speed issue currently.