xi-editor/xi-editor

improve memory efficiency of rope diffing

開放

#946 建立於 2018年10月26日

 (0 則留言) (0 個反應) (0 位負責人)Rust (708 個分叉)batch import
enhancementhelp wanted

倉庫指標

星標
 (19,842 顆星)
PR 合併指標
 (PR 指標待抓取)

描述

#802 introduced the ability to compute efficient deltas between arbitrary ropes, but there's one pretty glaring TODO: currently we have allocate a new string for the contents of the target buffer, which we use to build a hashmap. This is just laziness; there are work arounds but they're a bit fiddly and I didn't get around to it.

Two options seem reasonable, to me. Raph suggests,

Create a RopeSlice struct, which is a pair of (&Rope, Range). Custom implement Eq and Hash traits, to internally use iter_chunks to compute both. Don't use lines_raw iterator, use cursor with LinesMetric. I think this gives you maximum efficiency, as everything is borrowed and there's no allocation or copying, even in the case of very long lines.

I did verify that you can do DefaultHasher::write() with different slice boundaries and get the same state, though I don't believe that's written down explicitly.

Alternatively, I think it would be reasonable to add a fn to Rope itself that returns a pre-constructed hashmap; by doing the work inside the rope I believe we could get around the lifetime issues.

Any work on this should keep an eye on performance. I suspect it will be hard to be faster than the current version (for reasonably sized files) but it should be possible to stay close.

貢獻者指南