Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

faster way to append to [text] #778

Open
reduzent opened this issue Oct 28, 2019 · 4 comments

Comments

@reduzent
Copy link
Contributor

@reduzent reduzent commented Oct 28, 2019

The help of [text] suggest to use [text set] for appending to the existing text with something like:

   [loadbang]
   |
   [1e15(
   |
[text set mytext]

However, this turns out to have O(n²) time complexity and thus is not feasible for appending to large texts. Currently, I see no alternative for appending to [text], thus I propose a new object [text append] that only appends to the existing text, but does so quickly (in linear time).

@Spacechild1

This comment has been minimized.

Copy link
Contributor

@Spacechild1 Spacechild1 commented Oct 28, 2019

that would be a leaky abstraction. I'm sure we can improve the [text set] / [text get] methods to behave in O(N) time. E.g. we can cache the line positions, so we don't have to calculate them over and over again.

@Spacechild1

This comment has been minimized.

Copy link
Contributor

@Spacechild1 Spacechild1 commented Oct 28, 2019

In fact, I've noticed this behavior in the past while reading the code and thought about fixing it, but didn't bother... But now that I'm not alone, I might give it a go :-)

@reduzent

This comment has been minimized.

Copy link
Contributor Author

@reduzent reduzent commented Oct 28, 2019

Sorry, I don't understand: What would be a leaky abstraction?

If [text set] can be made to always insert lines in linear time, that would be even better. I don't have a clue how [text] internally works or what data structure it uses, but when inserting a line not at the end of the text, it doesn't have to move data below that line around?

@Spacechild1

This comment has been minimized.

Copy link
Contributor

@Spacechild1 Spacechild1 commented Oct 28, 2019

leaky abstractions are abstractions where implementation details - in your case O(n) vs O(n²) - "leak" through.

but when inserting a line not at the end of the text, it doesn't have to move data below that line around?

yes, it does, but this is orthogonal to appending data. the real problem with [text set] / [text get] is that text is stored in a single binbuf, and whenever we insert a line, we have to traverse the whole binbuf to calculate the line position. This procedure can be sped up tremendously by caching the line positions. Additionally, we can optimize for the special case where we append a line (and don't need the line positions at all)).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
2 participants
You can’t perform that action at this time.