Format a JSON file takes 5+ seconds as time is spend in computeMoreMinimalEdits

[7sDream]

Issue Type: Bug

1. Download test json file: generated.json.zip
2. Unzip generated.json and open it in VSCode
3. Use built-in Format Document command to format this file

Does this issue occur when all extensions are disabled?: Yes

Screenshot:

When using built-in format command, I need to wait so long(about 5~6 seconds):

But with third party extension named json, it's done very quickly:

Maybe dup of #94661, but it's closed and don't have any progress on solve this problem.

VS Code version:

• Code 1.44.2 (ff915844119ce9485abfe8aa9076ec76b5300ddd, 2020-04-16T17:07:18.473Z)
• Code 1.45.0 (d69a79b73808559a91206d73d7717ff5f798f23c, 2020-05-07T15:57:33.467Z)

OS version: Darwin x64 19.3.0

System Info

|Item|Value| |---|---| |CPUs|Intel(R) Core(TM) i7-8559U CPU @ 2.70GHz (8 x 2700)| |GPU Status|2d_canvas: enabled
flash_3d: enabled
flash_stage3d: enabled
flash_stage3d_baseline: enabled
gpu_compositing: enabled
metal: disabled_off
multiple_raster_threads: enabled_on
oop_rasterization: disabled_off
protected_video_decode: unavailable_off
rasterization: enabled
skia_renderer: disabled_off_ok
video_decode: enabled
viz_display_compositor: enabled_on
viz_hit_test_surface_layer: disabled_off_ok
webgl: enabled
webgl2: enabled| |Load (avg)|2, 2, 2| |Memory (System)|16.00GB (2.33GB free)| |Process Argv|| |Screen Reader|no| |VM|0%|

Extensions (47)

Extension|Author (truncated)|Version ---|---|--- language-x86-64-assembly|13x|2.3.0 rainbow-brackets|2gu|0.0.6 jce-plugin|abe|3.0.3 markdown-toc|Ala|1.5.6 markdown-emoji|bie|0.0.9 better-toml|bun|0.3.2 gitignore|cod|0.6.0 doxdocgen|csc|0.6.0 markdown-table-prettify|dar|2.4.0 vscode-markdownlint|Dav|0.35.1 vscode-eslint|dba|2.1.5 gitlens|eam|10.2.1 json-tools|eri|1.0.2 code-runner|for|0.10.0 kotlin|fwc|0.2.11 mdmath|goe|2.4.0 todo-tree|Gru|0.0.174 latex-workshop|Jam|8.9.0 plantuml|jeb|2.13.8 restructuredtext|lex|126.0.0 fish-ide|lun|0.4.0 rust-analyzer|mat|0.2.159 vscoq|max|0.3.1 rainbow-csv|mec|1.7.0 git-graph|mhu|1.22.0 gitignore|mic|1.0.1 dotenv|mik|1.0.1 vscode-language-pack-zh-hans|MS-|1.44.2 python|ms-|2020.4.76186 remote-containers|ms-|0.112.0 cmake-tools|ms-|1.3.1 cpptools|ms-|0.28.0-insiders Go|ms-|0.14.1 material-icon-theme|PKi|4.1.0 polacode|pnp|0.3.4 code-settings-sync|Sha|3.4.3 markdown-preview-enhanced|shd|0.5.3 indenticator|Sir|0.6.0 fish-vscode|sky|0.2.1 vscode-hexdump|sle|1.7.2 rewrap|stk|1.9.1 code-spell-checker|str|1.8.0 cmake|twx|0.0.17 vscode-lldb|vad|1.5.0 markdown-pdf|yza|1.4.4 markdown-all-in-one|yzh|2.8.0 json|Zai|1.0.4 (1 theme extensions excluded)

[7sDream]

Any progress or investigate on this issue?

I do not want to(and should not have to, IMHO) install extra extension just for a simple code format feature.

[aeschli]

The JSON language server takes 22ms to create and send the formatting edits to the client. It sends it as a single edit as the number of changes exceed 1000 (3277 edits for the given sample). Document size is 21197 characters.

Assigning to @jrieken as the time is spend in computeMoreMinimalEdits. Let me know if there's a way for me to hint that optimization should not happen.

[jrieken]

@aeschli Sure about those 5secs? When I run with trace logging enabled it shows 600ms for me.

TRACE FORMAT#computeMoreMinimalEdits file:///Users/jrieken/Code/_samples/devfest/generated.json 602.1800000453368

It sends it as a single edit as the number of changes exceed 1000 (3277 edits for the given sample).

So, you know all changes and then make it into a single change, e.g after the fact? So, I'd say it will be much, much better if you simply give us all edits.

[aeschli]

https://github.com/microsoft/vscode/issues/79014#issuecomment-576299081 was the reason for the change.

Running some tests with documents of ever increasing sizes (16723, 21196, 42391, 127177, ...), with the original number of edits or with one edit. Times in ms.

edits	model size before	after	provideDocumentFormattingEdits	computeMoreMinimalEdits	applyEdits
2621	16723		66	26	31
3276	21196		66	43	32
6551	42391		151	79	81
9826	63586		197	101	59
13101	84781		266	82	105
19649	127177		385	154	193
39299	254347		741	321	289
117899	763046		2221	1347	662
1061100	6867395		21398	13271	5528
1	16723	42880	20	4699	58
1	21196	53892	24	6661	72
1	42391	107782	46	2	23
1	63586	161672	57	2	45
1	84781	215562	46	4	35
1	127177	323342	54	5	91
1	254347	646682	112	10	127
1	763046	1940042	257	50	219
1	6607657		1694	436	712

[jrieken]

Now I am even more confused. Where do these numbers come from? How do you measure these things?

[aeschli]

I added StopWatches and log statements to formatDocumentWithProvider

Right now the JSON server emits all in a singe edit as soon as there are more than 1000 edits. Looks like increasing to 20000 is reasonable. That code is at https://github.com/microsoft/vscode/blob/4be0a2b9d571b9f9707ab2d7cf35c5012bfc12cc/extensions/json-language-features/server/src/jsonServer.ts#L428

I'm doing more measurements... For now, no need for any action your side.

[aeschli]

I increased the max number of edits emitted by the JSON server to 10000. That way, the formatting time of the sample above will remain under 0.5 s. computeMoreMinimalEdits also has a limit of 10000 diffs which will be reached due to the 10000 edits.

[aeschli]

@jrieken Speak up if you disagree with the action taken. If not I'll reassign the the item back to me and close the issue.

[jrieken]

computeMoreMinimalEdits also has a limit of 10000 diffs which will be reached due to the 10000 edits.

It's 100_000 and only applied when a single edit replaces more than 100_000 characters. That's throwing the towel when an edit replaces too many characters so that diffing becomes too expensive.

[aeschli]

I added the model size after formatting, which confirms the 100_000 limit. It still seems to me that the limit might be a bit high. 4.6 sec for a 42880 char doc is quite high and I'm not on a slow machine.

For now I'll go with the fix to increase the max edit limit in the JSON server.