7 ms·

Interesting article, and I love to see performance numbers to back up engineering decisions. I'm also glad xi-rope wasn't included, as I'm sure it's performance

Interesting article, and I love to see performance numbers to back up engineering decisions. I'm also glad xi-rope wasn't included, as I'm sure it's performance lags :) That said, it's not measuring what I would measure. The jumprope benchmarks are reported as the total time to complete a number of tasks. To me, the massive strength of the rope data structure is its O(log n) worst case performance when performing a simple operation such as inserting or deleting a character. That translates into user-perceivable latency. If you have a sequence of a thousand edits, and your rope accomplishes each in 200µs, while your gap buffer has a mean of 100µs but variance extending to 10ms, then I'd much prefer the former, even though this benchmark would indicate the latter is 2x faster.

loeg 3y ago
Also, the author is quick to dismiss 20-100ms latencies as imperceptible, or nearly so. That is too high.
- chongli 3y ago
  Yeah. 20ms is more than a full frame at 60hz. This sort of delay is unacceptable in 3D games! And here we’re talking about inserting a character into the data structure used to keep track of edits to a text file! It’s also ignorant of the heavily pipelined nature of input and output on modern computers. If you add up all of the latency from the time you press a key on the keyboard to the time a character appears on the screen — even if you subtract all the time spent inside your text editor — it adds up to many ms of delay. Now the author thinks it’s okay to add another 20-100ms to that just for the basic data structure holding the text? No thank you! Edit: I have to add this link to a classic post by Dan Luu [1]. The Apple IIe leads the pack with 30ms latency from keystroke down to character on the screen. 20ms for a data structure (in the key-to-screen critical path) on a 2023 computer, even if it only occurs 1% of the time, is totally unacceptable. [1] https://danluu.com/input-lag/ https://danluu.com/input-lag/
  - kaba0 3y ago
    Maybe reread the relevant part of the article. It’s not average case at all.
  - _a_a_a_ 3y ago
    I thought your first para was sarcasm. Now I'm just not sure. It sits on the razor's edge, ready to fall either way in my mind. NB. Elite running on Emacs https://www.salkosuo.net/2015/10/22/elite-for-emacs.html https://www.salkosuo.net/2015/10/22/elite-for-emacs.html
    - intelVISA 3y ago
      The true end goal of all posts here, such craftsmanship.
    - codetrotter 3y ago
      To be sarcastic is human, but to be on the razor's edge is divine
  - jenadine 3y ago
    > And here we’re talking about inserting a character We are talking about the worst case when the buffer needs to be resized. This is not for every character. Just once in a while while editing very large texts. Not that it makes it acceptable. But also not as bad as what you're making it sound.
  - HerculePoirot 3y ago
    Yeah, I'd have dismissed your comment before I tried running a scheme repl on a raspberry pi over ssh (local) vs a clojure repl running on the jvm on my machine. Day and night.
- celeritascelery 3y ago
  depends on the context. The rule of thumb I have seen is that anything under 100ms is perceived as instantaneous by a user. So for interactive editing those latencies are acceptable. Though is should be noted those latencies are only for 1 GB file, so they will get worse as the edited file gets larger. But if you are building something like a CRDT where you can have edits coming in from many sources then those will start to compound, and will destroy your responsiveness. Also if you are performing edits while doing something like scrolling you will start to drop frames. Jumprope and Xi-rope were specifically designed for the CRDT use case. As Raph points out, the latencies are what will really bite you. And latency is actually why I picked a gap buffer; the ropes have too high of latency with regex searches. If that was ever fixed I would be tempted to switch to ropes.
  - raphlinus 3y ago
    Search is 100% a valid justification to use contiguous storage. It wasn't high in my list of considerations when I was starting out.
  - gary_0 3y ago
    An occasional 100ms pause while I'm editing a huge 1GB file wouldn't be a deal-breaker for me, as long as regular-sized files have <10ms latency. It's been a long time since I opened a text file that huge, and I think the editor I was using at the time chugged something awful. VSCode is slightly laggy for me just editing a 10k line text file, so my standards are sadly not that high, even though I find typing latency really annoying.
  - vlovich123 3y ago
    I’ve always found that latency number to be suspect. In some contexts, it’s imperceivable. In others it is. For example, dragging an item around a screen with your finger, 100ms is definitely noticeable. Typing seems to be less although I had a coworker claim he could. So it’s hard to say if we don’t notice it vs we’ve just become accustomed to interacting with text with 100ms of latency (or something about the task of typing is more latency insensitive). I would be interested in seeing the the same data driven analysis for human factors as HCI is even less intuitive than computer algorithm performance. Searching is not a particularly latency sensitive task as your next match is probably significantly within 1 gib where you’re paying 250ms at worst. But yeah, if regex searching is the task to optimize around, ropes in Rust won’t work well due to the lack of incremental search at this time.
- IshKebab 3y ago
  I don't think he's quick to dismiss it. He talks about it several times. Those latencies are when editing files in the hundreds of MB, and only in the worst case non-local edit. How often do you edit I file that big? Also I expect if that was a real problem you could probably implement a system where you have more than one gap. Does that exist?
  - celeritascelery 3y ago
    > Also I expect if that was a real problem you could probably implement a system where you have more than one gap. Does that exist? That is a really cool idea! I actually tried implementing that. However I gave up because the code became quite a bit more complex, but it would totally be possible! That being said, multiple gaps would only help the "move gap" latency, they wouldn't help with the resizing latency. The later is both less predictable and much higher then moving the gap. Also when you need to coalesce the text for searching you would loose all your gaps.
    - funcDropShadow 3y ago
      > they wouldn't help with the resizing latency Could'nt you avoid resizing by massively over allocating in the first place? A decent OS, hint Linux, would only map pages to the allocated memory pages once they are touched.
    - IshKebab 3y ago
      You can possible use an array of (heap allocated) ring buffers. I heard about that data structure a while ago and it is clever but I have never seen anyone use it. It means an insertion anywhere just involves M character moves where M is the number of ring buffers. The data layout won't quite be as nice as a gap buffer (2 chunks), instead you get 2*M chunks. But if you make your ring buffers like 10MB it's probably fine.
  - gpderetta 3y ago
    > How often do you edit I file that big? On the other hand, does speed really matter for small files? Handling uncommon scenarios gracefully is important.

loeg 3y ago

Also, the author is quick to dismiss 20-100ms latencies as imperceptible, or nearly so. That is too high.

chongli 3y ago
Yeah. 20ms is more than a full frame at 60hz. This sort of delay is unacceptable in 3D games! And here we’re talking about inserting a character into the data structure used to keep track of edits to a text file! It’s also ignorant of the heavily pipelined nature of input and output on modern computers. If you add up all of the latency from the time you press a key on the keyboard to the time a character appears on the screen — even if you subtract all the time spent inside your text editor — it adds up to many ms of delay. Now the author thinks it’s okay to add another 20-100ms to that just for the basic data structure holding the text? No thank you! Edit: I have to add this link to a classic post by Dan Luu [1]. The Apple IIe leads the pack with 30ms latency from keystroke down to character on the screen. 20ms for a data structure (in the key-to-screen critical path) on a 2023 computer, even if it only occurs 1% of the time, is totally unacceptable. [1] https://danluu.com/input-lag/ https://danluu.com/input-lag/
- kaba0 3y ago
  Maybe reread the relevant part of the article. It’s not average case at all.
- _a_a_a_ 3y ago
  I thought your first para was sarcasm. Now I'm just not sure. It sits on the razor's edge, ready to fall either way in my mind. NB. Elite running on Emacs https://www.salkosuo.net/2015/10/22/elite-for-emacs.html https://www.salkosuo.net/2015/10/22/elite-for-emacs.html
  - intelVISA 3y ago
    The true end goal of all posts here, such craftsmanship.
  - codetrotter 3y ago
    To be sarcastic is human, but to be on the razor's edge is divine
- jenadine 3y ago
  > And here we’re talking about inserting a character We are talking about the worst case when the buffer needs to be resized. This is not for every character. Just once in a while while editing very large texts. Not that it makes it acceptable. But also not as bad as what you're making it sound.
- HerculePoirot 3y ago
  Yeah, I'd have dismissed your comment before I tried running a scheme repl on a raspberry pi over ssh (local) vs a clojure repl running on the jvm on my machine. Day and night.
celeritascelery 3y ago
depends on the context. The rule of thumb I have seen is that anything under 100ms is perceived as instantaneous by a user. So for interactive editing those latencies are acceptable. Though is should be noted those latencies are only for 1 GB file, so they will get worse as the edited file gets larger. But if you are building something like a CRDT where you can have edits coming in from many sources then those will start to compound, and will destroy your responsiveness. Also if you are performing edits while doing something like scrolling you will start to drop frames. Jumprope and Xi-rope were specifically designed for the CRDT use case. As Raph points out, the latencies are what will really bite you. And latency is actually why I picked a gap buffer; the ropes have too high of latency with regex searches. If that was ever fixed I would be tempted to switch to ropes.
- raphlinus 3y ago
  Search is 100% a valid justification to use contiguous storage. It wasn't high in my list of considerations when I was starting out.
- gary_0 3y ago
  An occasional 100ms pause while I'm editing a huge 1GB file wouldn't be a deal-breaker for me, as long as regular-sized files have <10ms latency. It's been a long time since I opened a text file that huge, and I think the editor I was using at the time chugged something awful. VSCode is slightly laggy for me just editing a 10k line text file, so my standards are sadly not that high, even though I find typing latency really annoying.
- vlovich123 3y ago
  I’ve always found that latency number to be suspect. In some contexts, it’s imperceivable. In others it is. For example, dragging an item around a screen with your finger, 100ms is definitely noticeable. Typing seems to be less although I had a coworker claim he could. So it’s hard to say if we don’t notice it vs we’ve just become accustomed to interacting with text with 100ms of latency (or something about the task of typing is more latency insensitive). I would be interested in seeing the the same data driven analysis for human factors as HCI is even less intuitive than computer algorithm performance. Searching is not a particularly latency sensitive task as your next match is probably significantly within 1 gib where you’re paying 250ms at worst. But yeah, if regex searching is the task to optimize around, ropes in Rust won’t work well due to the lack of incremental search at this time.
IshKebab 3y ago
I don't think he's quick to dismiss it. He talks about it several times. Those latencies are when editing files in the hundreds of MB, and only in the worst case non-local edit. How often do you edit I file that big? Also I expect if that was a real problem you could probably implement a system where you have more than one gap. Does that exist?
- celeritascelery 3y ago
  > Also I expect if that was a real problem you could probably implement a system where you have more than one gap. Does that exist? That is a really cool idea! I actually tried implementing that. However I gave up because the code became quite a bit more complex, but it would totally be possible! That being said, multiple gaps would only help the "move gap" latency, they wouldn't help with the resizing latency. The later is both less predictable and much higher then moving the gap. Also when you need to coalesce the text for searching you would loose all your gaps.
  - funcDropShadow 3y ago
    > they wouldn't help with the resizing latency Could'nt you avoid resizing by massively over allocating in the first place? A decent OS, hint Linux, would only map pages to the allocated memory pages once they are touched.
  - IshKebab 3y ago
    You can possible use an array of (heap allocated) ring buffers. I heard about that data structure a while ago and it is clever but I have never seen anyone use it. It means an insertion anywhere just involves M character moves where M is the number of ring buffers. The data layout won't quite be as nice as a gap buffer (2 chunks), instead you get 2*M chunks. But if you make your ring buffers like 10MB it's probably fine.
- gpderetta 3y ago
  > How often do you edit I file that big? On the other hand, does speed really matter for small files? Handling uncommon scenarios gracefully is important.