4 ms·
> The worst way to store and manipulate text is to use an array. Claim made from theoretical considerations, without any actual reference to real-world editors
by p-e-w 3y ago
> The worst way to store and manipulate text is to use an array.
Claim made from theoretical considerations, without any actual reference to real-world editors. The popular Micro[1] text editor uses a simple line array[2], and performs fantastically well on real-world editing tasks.
Meanwhile, ropes are so complicated that even high-quality implementations have extremely subtle bugs[3] that can lead to state or content corruption.
Which data structure is "best" is not just a function of its asymptotic performance. Practical considerations are equally important (arguably more so).
[1] https://github.com/zyedidia/micro https://github.com/zyedidia/micro
[2] https://github.com/zyedidia/micro/blob/master/internal/buffer/line_array.go https://github.com/zyedidia/micro/blob/master/internal/buffe...
[3] https://github.com/cessen/ropey/pull/67 https://github.com/cessen/ropey/pull/67
- kragen 3y agoit's talking about an array of bytes, and you're talking about an array of lines, which performs acceptably in a much wider range of situations than what's being dismissed ropes can be complicated but they don't have to be. ropey is ten thousand lines of code, and only six years old, so it's not surprising that it's buggy. https://github.com/ivanbgd/Rope-Data-Structure-C https://github.com/ivanbgd/Rope-Data-Structure-C is 339 lines of code, but it's probably not a real-world rope probably the most widely used implementation of ropes is the one from the sgi stl, which is in gcc as libstdc++/ext/rope https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.3/a01984.html https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USER... and libstdc++/ext/ropeimpl.h https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.3/a01985.html https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USER..., which total 1485 lines of code, about halfway in between the two. in a garbage-collected language, like the cedar language where ropes originated, most of that complexity goes away, and production-quality ropes are only a few hundred lines of code. also c++'s verbose syntax isn't doing brevity any favors here http://www.bitsavers.org/pdf/xerox/parc/cedar/Cedar_7.0/09_Cedar_Language_Overview_Version_5.2_Jun1986.pdf http://www.bitsavers.org/pdf/xerox/parc/cedar/Cedar_7.0/09_C...
- deleted 3y ago[deleted]
- gumby 3y ago> > The worst way to store and manipulate text is to use an array. > Claim made from theoretical considerations, without any actual reference to real-world editors. I also found this weird, especially when the author then extols the piece table (an approach going back at least to the early 60s) which itself is nothing but an array! And the author did cite emacs as an example (emacs inherited that approach from TECO).
- gumby 3y agos/piece table/buffer gap/ or else my comment makes absolutely no sense. Note to self: do not comment from bed.