Repository navigation
✨ Editing Performance #132
Description
Editing a large file can take up to multiple seconds per character. Right now CodeEditTextView uses the default NSTextStorage as a text store, which stores text contiguously in memory. This means that for each insert all characters after the insert location must be copied one spot over in memory to make room for the inserted character.
For the most part this isn't a problem for smaller files. But opening a file like sqlite.c (~151,000 LOC) the performance impact becomes very noticeable. I've attached a screen recording of typing a few characters into this file, it's easy to see how long it takes.
Screen.Recording.2023-01-25.at.10.31.59.PM.mov
The way to fix this issue is to implement a custom NSTextStorage object using a data structure more suited to a text editor. By default, NSTextStorage uses an NSMutableAttributedString to store both text and attributes. These implementations are very general and don't perform well with edits.
Therefore the problem is twofold: text storage and attribute storage.
There are a few algorithms that are generally used in text editors for storing text:
In my opinion, a piece table would be the best option. A gap buffer may be a solid solution, but doesn't offer the same append-only type performance a piece table can offer. With a piece table every edit is added to the text buffer as an immutable, appended, chunk of text which completely removes the need to copy text when inserting characters.
The only downside of a piece table comes around when a lot of edits happen as found by the VSCode team.
The other problem is attribute storage. Attributes consist of a range (UInt-UInt) and a dictionary of attributes NSDictionary. A solution for attribute storage may be to implement a tree that stores ranges as it's nodes and allows for O(log n) lookup time for a given index. However, a tree structure will have a large space requirement, and ranges may be very small (or even a single index) when we're talking about syntax highlighting, leading to many nodes in a tree.
Another option would be to somehow store a small amount of metadata about each range alongside the string itself. We already have a ThemeAttributesProviding protocol that can be used to convert a capture type into attributes. We could store the capture type (sqrt(21 available captures) = ~5 needed bits, rounded up) using 1 extra byte for every highlighted range and when asked for attribute data convert the capture into attributes.
Any thoughts or discussion on implementation and performance is welcome!
Metadata
Metadata
Assignees
Type
Projects
- Status
Activity
thecoolwinter commentedon Jan 26, 2023
Also a custom
NSTextStorageimplementation would allow us to do things like stream files from disk instead of loading them atomically into memory first.lukepistrol commentedon Jan 26, 2023
This may be total garbage (I haven't looked into it yet) but couldn't we just reuse/extend the tree structure already provided by tree-sitter? Or would you rather keep them separate since we might use additional highlighters/parsers in the future?
thecoolwinter commentedon Jan 28, 2023
I'd like to keep them separate for that reason and for any files that may not be supported by tree-sitter.
neil-ptr commentedon Feb 3, 2023
I'm not sure where to put this but I have performance issues just opening and trying to view a large file (~10k lines of code)
Screen.Recording.2023-02-03.at.3.20.07.PM.mov
thecoolwinter commentedon Feb 13, 2023
@Neilzon with #138 merged opening and scrolling (slowly) should be much faster. There's some issues on the CodeEdit side with opening the file, but it will no longer hang and explode in memory.
thecoolwinter commentedon Mar 2, 2023
Upon further investigation, it looks like the culprit is more likely
tree-sitter. Doing some benchmark tests tree-sitter can take 100's of milliseconds to edit very large documents.NSTextStoragewith attributes can take a few milliseconds to edit large documents, so this is maybe related to #143.thecoolwinter commentedon Mar 2, 2023
Here's an example printing the time between editing a document and finishing highlighting the edit (in ms).
Screen.Recording.2023-03-01.at.7.14.15.PM.mov
matthijseikelenboom commentedon Mar 2, 2023
Do we still load the full content of the file into the (scroll)view? Or do load the content that is visible + a (scrolling)margin? I don't know if that has anything to do with it, but I can imagine so
thecoolwinter commentedon Mar 3, 2023
@matthijseikelenboom We load the whole document but all edits + highlights are restricted to the visible area.
serg-vinnie commentedon Mar 9, 2023
this implementation might help you https://github.com/GitHawkApp/StyledTextKit,
it's iOS-only, but anyway
thecoolwinter commentedon Mar 16, 2023
@serg-vinnie That might be useful, but since the slow part of the problem isn't rendering or creating the attributed text I'm not sure how much it'll help.
Async TreeSitterClient (#191)
austincondiff commentedon Dec 20, 2023
@thecoolwinter is this still an issue since merging the new text view?