formatting file with zls causes infinite loop in memory allocator

[Jarred-Sumner]

Zig Version

0.11.0-dev.1393+38eebf3c4

Zig Language Server Version

384f227

Steps to Reproduce

When using zls to format files, it seems to infinite loop on certain input. Generally it seems to be more likely to happen on longer files. zig fmt works as expected.

File that reproduces the issue (too long to fit in an issue)

Expected Behavior

Formats successfully, like zig fmt

Actual Behavior

It infinite loops until it uses enough memory for the OOM killer to kill it. This type of issue is often caused by looping over or duplicating a slice that is undefined, in which cause the len field is something absurdly large (due to undefined memory)

[SuperAuguste]

Known issue relating to diffing large incremental edits using our current algorithm

[Jarred-Sumner]

i don't know if this would work but

what if when the input is longer than say 8 KB and the buffer is to a file on the filesystem, it spawns zig fmt and does something simpler to find the cursor position diff? on my machine, zig fmt takes 26ms so it would probably have acceptable perf

[SuperAuguste]

I’ll try to optimize this tonight.

[SuperAuguste]

Reproduced and got a beautiful GetLastError(1455): The paging file is too small for this operation to complete.; confirmed that the error cause is diff.edits. I'll try and implement a better algorithm which should hopefully fix this up! :)

[Jarred-Sumner]

If the code is still using page_allocator, that would cause the issue. If my understanding of page_allocator is correct (it might be completely wrong), every allocation is a new page in memory. Allocating 32 bytes is actually allocating 4 KB or 16 KB.

That means using c_allocator would be a very significant performance improvement (and help with this issue, as it would take longer to OOM)

[Jarred-Sumner]

ah it's using GPA

[SuperAuguste]

If the code is still using page_allocator, that would cause the issue. If my understanding of page_allocator is correct (it might be completely wrong), every allocation is a new page in memory. Allocating 32 bytes is actually allocating 4 KB or 16 KB.

That means using c_allocator would be a very significant performance improvement (and help with this issue, as it would take longer to OOM)

That is incorrect. Firstly, we use an Arena, so this is practically a non-issue as far as I know. Secondly, the method that diff.edits uses performs an allocation of size a.len * b.len which for your input is essentially 176,489 * 176,489 * 8 bytes after formatting, or in other words, it's attempting to allocate 249,186,936,968 bytes of memory, causing an OOM / reverting to swap regardless of which allocator we're using.

[Jarred-Sumner]

to speed up mem.eql(u8, slice, slice), consider copying this function https://github.com/oven-sh/bun/blob/main/src/string_immutable.zig#L766-L824

to speed up ComptimeStringMap, consider copying this https://github.com/oven-sh/bun/blob/main/src/comptime_string_map.zig#L1

[SuperAuguste]

These optimizations are not useful in this scenario.