Hacker News Reader

Beside data structure based on B+ tree (ropes), what do you think about Relaxed Radix Balanced Vector tree[0]? It is cache-friendly and immutable as well.

[0](https://icfp17.sigplan.org/event/icfp-2017-papers-persistenc...)

View on HN

Looks pretty neat, thanks for the link. From a quick look, it seems like the performance characteristics will be pretty similar to a xi-style rope (it seems extremely unlikely to me that the time spent finding the child is significant, so the radix trick can't save much time), and it's a bit more complex. That said, I do expect it to perform nicely for read-only access to large documents, which is definitely an important use case.

It would make a fun project for somebody to implement it and compare the performance. I'd certainly take the PR for it if the performance was better :)

[edit: followup] The rope implementation in xi has an additional heuristic that tries not to split lines across leaf boundaries (ie most leaves should end in a newline). It also has a hard constraint of not splitting a unicode codepoint. Thus, leaves and subtrees would have an unpredictable number of elements (as opposed to being a clean power of two when full) and I think that pretty much invalidates using the radix to select the child.

Reply on news.ycombinator.com