6 ms·

You can't beat the efficiency of a gap buffer for just typing. The downside of gap buffers is its a linear operation to move the cursor.

moonchild 5y ago
I see no reason why a rope would be slower than a gap buffer for 'just typing'. And the gap buffer will choke when you fill it up and want to continue typing.
- searealist 5y ago
  I'm just saying that "gap buffer" is not a reason any editor is perceived to be slow unless its slow when moving the cursor in a large buffer (or as you point out, the amortized growth of a large buffer, which will happen max log n times in a buffer of size n)
  - moonchild 5y ago
    > amortized growth of a large buffer, which will happen max log n times in a buffer of size n You can do better than log if you care to; just grow the buffer more quickly. It's just that exponential growth tends to work pretty well (and, notably, amortizes the overhead of copying such that it is O(1)). Also: people tend to take breaks when typing, so you can asynchronously try to grow the buffer when it is close to full.
- SamReidHughes 5y ago
  A rope could frequently call malloc, or cause more time spent garbage collecting, and it takes up more memory, and the code is slower, especially in the 80's. Before modern JavaScript VMs, I made an in-browser text editor, and I tried using a finger-tree data structure with string segments. It was extremely slow. I replaced it with two strings. Then it ran at human speeds. Memcpying the whole string upon a keypress was faster than some fancy data structure.
  - vidarh 5y ago
    As I noted in another comment, I think a lot of complexity in many editors is because they worry about handling absurdly large files without thinking about whether they need to. The moment you're willing to set an arbitrary limit above which you're ok with dropping performance, you can go very simple the way you did. And that limit where things start to slow down can be far over the size of files most people need most of the time. For my own part I'm fine with falling back to e.g. emacs the one time every few months I need do do something with an unusually large file.
    - Ygg2 5y ago
      You still can't avoid the performance penalty of a tree allocation for something like bracket pairing. Or AST analysis or any one of billion things people want from a code editor.
      - vidarh 5y ago
        Depends on the analysis. For bracket pairing and quite a bit of analysis you can avoid it quite easily by storing the state of a parser at intervals. E.g.for syntax highlighting I use Rouge augmented with serialization of the lexer state, which also provides enough state for bracket matching and the internal state I need to store is typically one symbol every few lines. For complex analysis of the code-base, sure, you may want to build an AST. For my part I have no interest in having that functionality in-process in the editor - I'd rather have that provided by an external service.
        Ygg2 5y ago
        > For bracket pairing and quite a bit of analysis you can avoid it quite easily How? You have a bracket `[` at start of 2GB file and the closing bracket `]` somewhere at end at end of the file. Without analysis you can't tell where it is.
        vidarh 5y ago

moonchild 5y ago

I see no reason why a rope would be slower than a gap buffer for 'just typing'. And the gap buffer will choke when you fill it up and want to continue typing.

searealist 5y ago
I'm just saying that "gap buffer" is not a reason any editor is perceived to be slow unless its slow when moving the cursor in a large buffer (or as you point out, the amortized growth of a large buffer, which will happen max log n times in a buffer of size n)
- moonchild 5y ago
  > amortized growth of a large buffer, which will happen max log n times in a buffer of size n You can do better than log if you care to; just grow the buffer more quickly. It's just that exponential growth tends to work pretty well (and, notably, amortizes the overhead of copying such that it is O(1)). Also: people tend to take breaks when typing, so you can asynchronously try to grow the buffer when it is close to full.
SamReidHughes 5y ago
A rope could frequently call malloc, or cause more time spent garbage collecting, and it takes up more memory, and the code is slower, especially in the 80's. Before modern JavaScript VMs, I made an in-browser text editor, and I tried using a finger-tree data structure with string segments. It was extremely slow. I replaced it with two strings. Then it ran at human speeds. Memcpying the whole string upon a keypress was faster than some fancy data structure.
- vidarh 5y ago
  As I noted in another comment, I think a lot of complexity in many editors is because they worry about handling absurdly large files without thinking about whether they need to. The moment you're willing to set an arbitrary limit above which you're ok with dropping performance, you can go very simple the way you did. And that limit where things start to slow down can be far over the size of files most people need most of the time. For my own part I'm fine with falling back to e.g. emacs the one time every few months I need do do something with an unusually large file.
  - Ygg2 5y ago
    You still can't avoid the performance penalty of a tree allocation for something like bracket pairing. Or AST analysis or any one of billion things people want from a code editor.
    - vidarh 5y ago
      Depends on the analysis. For bracket pairing and quite a bit of analysis you can avoid it quite easily by storing the state of a parser at intervals. E.g.for syntax highlighting I use Rouge augmented with serialization of the lexer state, which also provides enough state for bracket matching and the internal state I need to store is typically one symbol every few lines. For complex analysis of the code-base, sure, you may want to build an AST. For my part I have no interest in having that functionality in-process in the editor - I'd rather have that provided by an external service.
      - Ygg2 5y ago
        > For bracket pairing and quite a bit of analysis you can avoid it quite easily How? You have a bracket `[` at start of 2GB file and the closing bracket `]` somewhere at end at end of the file. Without analysis you can't tell where it is.
        vidarh 5y ago