search

yjs / yjs

Shared data types for building collaborative software
https://docs.yjs.dev
Other
15.95k stars 583 forks source link

Slow apply when garbage collecting large update #541

Open NilSet opened 1 year ago

NilSet commented 1 year ago

Checklist

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

Huly®: YJS-373

lijie1129 commented 1 year ago

hi, @NilSet

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

https://github.com/yjs/yjs/assets/5371749/2fc354d3-b871-4968-ba16-843ae8b1f730

Checklist

  • [x] Are you reporting a bug? Use github issues for bug reports and feature requests. For general questions, please use https://discuss.yjs.dev/
  • [x] 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 commented 1 year ago

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 commented 1 year ago

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

https://github.com/yjs/yjs/assets/5371749/1a4cdc13-234d-40d1-ad5b-b64f8ad9c955

NilSet commented 1 year ago

You are still on the wrong branch.

dmonad commented 12 months ago

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

dmonad commented 12 months ago

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