x command extremely slow

[rakitzis]

vis view.c
:,x/./c/x

This takes ~30 seconds on my i7-based laptop, vs. instantaneously with plan9's sam.

[martanne]

Thanks for the report. This is a known problem which I plan to address some time next year.

Basically you hit the worst case of the underlying text management data structure which is even more aggravated due to the current implementation details. Each character is replaced individually with a huge overhead, instead all changes within a line should be coalesced.

[rakitzis]

Haven't looked at vis source but simple question: the original sam regexp engine is open sourced. Why not reuse it? A lot of care went into getting it right.

[martanne]

The regex engine isn't the problem here, well at least not for this particular case. See #488 for other reasons for which we might want to reuse sam's / Plan 9's regex library. After all, the sub match capturing technique nicely illustrated by Russ Cox's regex articles originated in sam.

The bottleneck here is the underlying text management data structure. Basically each non-newline character is deleted individually before a x is being inserted, changes aren't properly coalesced.

This can be illustrated with the following sequence which should have the same outcome:

:x/.*
rx

The last line performs the replacement in visual mode. It is still too slow (probably for different reasons), but should be considerably faster.

[aksr]

I agree with OP. x command is extremely slow in general—especially noticeable on bigger files. RegExp engine really needs more work.., and if it's not possible to adjust it properly, maybe the underlying text management data structure should be changed (even though that way vis would lose one distinctive feature).

[erf]

I found :x/something/c/somethingelse to have ok performance, but if i type :x\something and then type s to replace and type in that text manually it was not responding.

[aksr]

AFAIK, s isn't supported, check wiki for more details.

[erf]

@aksr you can type s in visual mode after the search is what i meant ( it's an alias to c )

[ninewise]

@erf editting a lot of selections in insert mode is indeed slow.

[martanne]

As I tried to explain in my previous comment, the core issue is due to the characteristics of the underlying text management data structure.

It is basically a linked list of changes. This design was initially chosen because it is simple, independent of file size, reasonably performant (assuming few and localized changes) and not in widespread use. With the introduction of multiple selections and structural regular expressions these assumptions no longer hold and the core data structure is not the best fit for the current functionality.

As for your observations, with the c/replacement/ command we perform O(selections) operations, while when editing interactively we do O(selections*keypress) operations. Hence, the former is substantially faster.

At some point I should probably write down desirable properties and possible alternative designs. Also as preparation for evaluating different approaches, I wrote some very basic bench marking infrastructure.

[nsajko]

should probably write down desirable properties and possible alternative designs.

I'm looking into the same stuff myself currently, so here's what I found so far, hope it's not too outdated:

https://en.wikipedia.org/wiki/Piece_table

https://en.wikipedia.org/wiki/Rope_(data_structure)

https://en.wikipedia.org/wiki/Gap_buffer

https://www.cs.unm.edu/~crowley/papers/sds.pdf

In case you guys already created such a comparison of alternative editor data structures, I'd be interested in seeing it.