Slow apply when garbage collecting large update

[NilSet]

Checklist

• Are you reporting a bug? Use github issues for bug reports and feature requests. For general questions, please use https://discuss.yjs.dev/
• Try to report your issue in the correct repository. Yjs consists of many modules. When in doubt, report it to https://github.com/yjs/yjs/issues/

Describe the bug Given a large, ungarbagecollected doc which was persisted as an encoded update, if you apply the update to a document with garbage collection enabled, the apply can take a very long time. Based on my profiling, the time is all in tryToMergeWithLeft, possibly due to calling structs.splice(pos, 1) many times, requiring the shifting of a very large array each time.

To Reproduce A anonymized document which reproduces this problem can be found here: https://github.com/NilSet/yjs-stack-overflow/tree/slow-gc On my machine it takes 38 seconds to apply the document with garbage collection enabled. Note that if you change the test script to disable gc on the doc, it only takes 1.6 seconds to apply the document.

Expected behavior A clear and concise description of what you expected to happen.

Screenshots If applicable, add screenshots to help explain your problem.

Environment Information

• Node 18
• Yjs 13.6.4

_{Huly®: YJS-373}

[lijie1129]

hi, @NilSet

This issue is not reproduce on the Yjs 13.6.5 via your repo .

2023-06-29.18.46.18.mov

Checklist

• Are you reporting a bug? Use github issues for bug reports and feature requests. For general questions, please use https://discuss.yjs.dev/
• Try to report your issue in the correct repository. Yjs consists of many modules. When in doubt, report it to https://github.com/yjs/yjs/issues/

Describe the bug Given a large, ungarbagecollected doc which was persisted as an encoded update, if you apply the update to a document with garbage collection enabled, the apply can take a very long time. Based on my profiling, the time is all in tryToMergeWithLeft, possibly due to calling structs.splice(pos, 1) many times, requiring the shifting of a very large array each time.

To Reproduce A anonymized document which reproduces this problem can be found here: https://github.com/NilSet/yjs-stack-overflow/tree/slow-gc On my machine it takes 38 seconds to apply the document with garbage collection enabled. Note that if you change the test script to disable gc on the doc, it only takes 1.6 seconds to apply the document.

Expected behavior A clear and concise description of what you expected to happen.

Screenshots If applicable, add screenshots to help explain your problem.

Environment Information

• Node 18
• Yjs 13.6.4

[NilSet]

You are on main branch, this issue links to the slow-gc branch which checks a different anonymized sample with different characteristics than the main branch.

[lijie1129]

You are on main branch, this issue links to the slow-gc branch which checks a different anonymized sample with different characteristics than the main branch.

Hi, @NilSet

I swithed the slow-iterate-deleted-structs branch and reproduce it. 🤝

And this issue is not reproduce on the Yjs 14.0.0-1

2023-06-30.10.33.42.mov

[NilSet]

You are still on the wrong branch.

[dmonad]

I published a fix in 13.6.7. I will close this ticket when I/somebody confirms this is fixed.

[dmonad]

@NilSet I can run your reproduction repo now in 9 seconds (45 seconds using Yjs@v13.6.4).