Item — HN Reader

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.

1 comments

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

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/

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

To be sarcastic is human, but to be on the razor's edge is divine

The true end goal of all posts here, such craftsmanship.

> 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.

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.

Maybe reread the relevant part of the article. It’s not average case at all.

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?

> 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.

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.

> 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.

you can also cut the worst case non local edit case in half by implementing a circular gap buffer as in climacs https://flexichain.common-lisp.dev/download/StrandhVilleneuv...

> 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.

Hundred+ meg JSON files are pretty common these days. A lot data analysis is just "make some JSON and worry about it later" and that I do like to start by pulling into a text editor.

Pulling data in a text editor to look at it has nothing to do with editing it tho. And actuallly wilfully editing hundred+ megs json by hand seems like a near nonexistent use case indeed.

The text editor needs to be able to load large without needing x times more memory than the size of the file.

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.

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.

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.

I would definitely notice 100ms of latency when typing, considering that at my usual speed, the time between characters is around 70ms.

The problem is that your thought is at the level of sentences with your muscle memory being automatic and your visual system mainly scanning for errors. Your “what character do I type next” at speed is less likely to be driven via visual feedback and more by direct proprieception / tactile feedback. Also, it’s not like you have a fixed 100ms delay between each character -the display system is asynchronous and will effectively batch everything up. So that 100ms delay means 100ms after your most recently typed character, not an additive 100ms delay.

Again, I’m not saying you won’t notice it, but I know I’m a very fast typer and when I was working on Oculus AirLink we had a prototype virtual desktop thing and I know I personally didn’t really notice any lag despite our internal metrics saying ~100ms of latency (we’d artificially inject extra latency for studies). It may be people differences, but keep in mind that how you measure is also important and almost no one measures true key stroke to display latency nor do they run human factors studies to accurately characterize if there really is anyone who does notice it (even at Oculus - most studies are very poor quality often with limited sample size, skewed population, and very poor reproduction/analysis because the time allotted for these projects is just enough to try to get guidance on next steps)

I notice 100ms latency when flipping a mechanical light switch (found out while dialling in debounce on ESPHome).

What regex engines do people use for this task generally? Most regex engines I'm aware of don't support stream/incremental searching.

This comment by someone at GitHub mentioned that Atom used PCRE’s partial match functionality, but I have no idea about what is used most commonly.

https://news.ycombinator.com/item?id=15386155

I was just going from the linked issue where I thought I read that Go’s engine supports incremental search. Maybe I misread?

While I have you, how close is the Rust incremental search support? It sounded like regex-automata might make it possible but hard to easily get a sense of high level progress from a GitHub issue.

Go has this: https://pkg.go.dev/regexp#Regexp.MatchReader --- That just tells you whether an io.Reader contains a match anywhere or not. I don't think it tells you anything else, like the position of the match.

> While I have you, how close is the Rust incremental search support? It sounded like regex-automata might make it possible but hard to easily get a sense of high level progress from a GitHub issue.

I'm not working on it. The current status is that other people are working on trying to write it themselves on top of regex-automata in a way that works for their specific use case. That was my high level strategy: release a separately versioned library with the regex internals[1] exposed so that others can experiment and build on top of it.

The regex-automata crate exposes the low level DFA (and lazy DFA) transition function. So you can pretty much do some kind of stream searching out of the box today (certainly at least what Go provides): https://docs.rs/regex-automata/latest/regex_automata/#build-...

Bottom line here is that if you're looking to implement stream searching in Rust, then you should be able to go out and build something to do it today with regex-automata. But you aren't going to get a streamlined experience. (And whether you ever will or not remains unclear to me.)

[1]: https://blog.burntsushi.net/regex-internals/

> Go ... I don't think it tells you anything else, like the position of the match.

The regexp.Regexp.FindReaderIndex and .FindReaderSubmatchIndex methods tell you the position of the match.

> ropes in Rust won’t work well due to the lack of incremental search at this time

Unless you don't mind implementing a couple dozen lines yourself. The regex_automata crate allows you to directly access the DFA, so with iteration through the rope and a bit of state tracking you can already do this, just not as convenient (yet) as a single method call.

It’s not quite that simple, but folks are working on it.

https://github.com/rust-lang/regex/issues/425#issuecomment-1...

https://github.com/helix-editor/helix/pull/211#issuecomment-...

Note that the lazy DFA and its lower level APIs exists now and threads this needle.

Maybe not in the general case for arbitrary abstracted datastructures, but I have done it in a basic test to see if it's viable for my use-case, which is why I made that claim at all.

Our brains are very good at adjusting to latency, but only if it’s a constant.

Search is 100% a valid justification to use contiguous storage. It wasn't high in my list of considerations when I was starting out.

>The rule of thumb I have seen is that anything under 100ms is perceived as instantaneous by a user.

for typing characters into a text box this is not imperceptible. it should happen in a single frame.

And it gets more perceptible when moving the caret (more pixels to track and you're actively tracking).

Users can easily feel one frame of latency at 60hz given enough visual feedback (pixels in this case). It gets harder at 120hz and above. I have a toy editor with Ropey and WGPU, just added a 100ms wait on char insert and it's rubber banding when typing fast.

Instead of the rule of thumb you’ve seen how about the rule of thumb you’ve tried? Make two simple HTML forms: one with an input that instantaneously accepts input and another with 100 ms delay. You can definitely tell the difference.

You are not measuring what you want. You measure 0+~20ms vs 100+~20ms.

Ok, change the experiment to add 80ms artificial delay instead…

I'd say 100ms is perceptible in almost any context, at least if it's on top of the already existing latencies of the hardware & OS (e.g. some laptops already add 150ms latency to every keypress [0], so good luck)

[0] https://danluu.com/input-lag/

100ms is 6 frames of input latency at 60hz! Absolutely noticable.