cessen / ropey

A utf8 text rope for manipulating and editing large texts.
MIT License
1.04k stars 46 forks source link

Make Lines iterator more efficient #25

Closed cessen closed 1 year ago

cessen commented 5 years ago

Currently the Lines iterator is roughly equivalent to just calling Rope::line() repeatedly with an incrementing index. This is O(log N) for each call to Lines::next(), and also is just generally less efficient than it needs to be. This is not only sub-optimal, but also stands out compared to the other iterators which are all O(1) and very fast.

It should be possible to also make Lines O(1) and just generally more efficient.

poliorcetics commented 2 years ago

I was exploring this issue this weekend and I think I have a possible solution, I'll try to post a PR within the month :), it needs lots of polishing and perf testing (thankfully testing for correctness is just comparing to the slow version so that part is easy)

pascalkuthe commented 2 years ago

I was exploring this issue this weekend and I think I have a possible solution, I'll try to post a PR within the month :), it needs lots of polishing and perf testing (thankfully testing for correctness is just comparing to the slow version so that part is easy)

That's a bit unfortunate timing we did some duplicate work here (see my comment in helix-editor/helix#4457). Perhaphs we can combinme efforts