Implement Ropes for shared string construction

[jridgewell]

One of our biggest pain points right now is memory pressure, and I believe the biggest contributor to this is the concatenation of strings for outputs. By implementing an efficient append-only Rope data structure, we can share the contents of any Rope instance without cloning the underlying data.

For instance, most of the files that we send are the concatenation of several chunk items. These items are usually the StringVc output from some other task, e.g. the parse/transform/print of a JS file. Before were taking each output string and copying them over into a brand new concatenation, which we may concatenate again! This is wildly inefficient.

With ropes, we essentially build up individual slices of shareable memory. In order to concatenate a rope with another rope, we only need to clone the reference and not the underlying data. In effect, the output from the chunk item is only ever present in memory once, and then shared by many ropes.

I initially implemented this with an Arcs holding onto the Vec<u8>. However, Hyper does not accept arcs of data and instead use the bytes crate. This is fine as it essentially accomplishes the same goal of shared references.

[vercel[bot]]

The latest updates on your projects. Learn more about Vercel for Git ↗︎

Name	Status	Preview	Comments	Updated
examples-kitchensink-blog	🔄 Building (Inspect)			Nov 4, 2022 at 4:03PM (UTC)
turbo-site	✅ Ready (Inspect)	Visit Preview	💬 Add your feedback	Nov 4, 2022 at 4:03PM (UTC)

4 Ignored Deployments

Name	Status	Preview	Comments	Updated
examples-basic-web	⬜️ Ignored (Inspect)			Nov 4, 2022 at 4:03PM (UTC)
examples-designsystem-docs	⬜️ Ignored (Inspect)			Nov 4, 2022 at 4:03PM (UTC)
examples-native-web	⬜️ Ignored (Inspect)			Nov 4, 2022 at 4:03PM (UTC)
examples-svelte-web	⬜️ Ignored (Inspect)			Nov 4, 2022 at 4:03PM (UTC)

[jridgewell]

Current dependencies on/for this PR:

• main
  • PR #2521
    • PR #2525 👈

This comment was auto-generated by Graphite.

[wbinnssmith]

🎉 Do you have any examples of the memory impact of this change?

[jridgewell]

Only about 20mb on the with the default test app, which is disappointingly little. There's other memory pressure, but this is a step.