Don't split small nodes

an-cabal / an-rope

an rope data structure

https://docs.rs/an-rope

MIT License

11 stars 2 forks source link

Don't split small nodes #73

Open deepinthebuild opened 7 years ago

deepinthebuild commented 7 years ago

We should change the behavior of insert etc. to not split leaves that are below a certain size threshold. It might help with performance due to cache friendliness.

hawkw commented 7 years ago

I'm down for this; but I'm not gonna make it a priority, just because I think it could take a lot of effort to implement under the hood.

hawkw commented 7 years ago

Having done some profiling, though, it does look like this is close to the only big performance optimisation we have left – Rope.split() does spend a majority of it's time in &str.to_owned(). Avoiding splits on small strings might help us here...