hcpl
commented
6 years ago How about having a configurable overhead? For example, when you care about speed more than memory consumption you can preallocate a bit more from the beginning. The opposite is also true: you may need to shrink the rope in place after every single mutation to get though strict RAM limits, especially when mutations are rare.
So Rope could have methods:
Methods (there are plenty of them)
```rust /// Returns the amount of memory in bytes this `Rope` currently uses. pub fn memory_consumption(&self) -> usize { ... } /// Returns the memory overhead ratio. pub fn memory_overhead(&self) -> f64 { self.memory_consumption() as f64 / self.len_bytes() as f64 } /// Computes the minimum amount of memory that is required for a `Rope` /// with contents of this one. pub fn minimal_memory_required(&self) -> usize { ... } /// Shrinks to the least possible amount of memory with which this `Rope` /// can still function. Equivalently, the method resizes this `Rope` to /// `self.minimal_memory_required()` bytes. /// /// # Notes /// /// Running this method might or might not occupy more than /// `self.memory_consumption()` called beforehand depending on contents /// and the algorithm used. pub fn shrink(&mut self) { ... } /// Tries to resize the `Rope` to fit its memory consumption between /// `min_overhead_coefficient * self.len_bytes()` and /// `max_overhead_coefficient * self.len_bytes()`. /// If it already fits in contraints, this method simply returns `Ok(())`. /// /// On success, returns `Ok(())`. /// On failure in any of following cases: /// - `max_overhead_coefficient * self.len_bytes()` is less than /// the amount of memory required for this `Rope` to function; /// - memory allocation failed for any reason; /// returns `Err(RopeResizeError { ... })`. /// /// # Panics /// /// Panics if `min_overhead_coefficient > max_overhead_coefficient`. pub fn resize( &mut self, min_overhead_coefficient: f64, max_overhead_coefficient: f64, ) -> Result<(), RopeResizeError> { ... } ```This may be far more sophisticated than you would like to have in ropey due to complexity of this proposal, but I'd be glad if you consider finer-grained ways to control memory consumption.
cessen
(This is a tracking issue for reducing the memory overhead of Ropey. The stats listed below are updated as improvements are made.)
The memory overhead for creating new ropes from existing text is pretty good (~10%). However, the memory overhead of building up a rope from many small insertions is worse (up to ~55% depending on insertion placement).
Improving this would be great!
The main culprit here is that since leaf nodes generally have a fixed-size text buffer, leaf nodes that aren't maximally filled contain wasted space. Trying to keep leaf nodes close to maximally filled should resolve the memory overhead back down to close to 10%. But how to do that without negatively impacting performance too much?