Comment by userbinator | Hacker News Reader

Comment by userbinator | Hacker News Reader

The worst way to store and manipulate text is to use an array. Firstly, the entire file must be loaded into the array first, which raises issues with time and memory. Even worse still, every insertion and deletion requires each element in the array to be moved. There are more downsides, but already this method is clearly not practical. The array can be dismissed as an option rather quickly.

The authors of the dozens of tiny editors using this "structure", which were quite popular on the PC in the late 80s through early 90s, would disagree. A memcpy/memove() runs at many GB/s on a typical machine today, so you would have to be editing absolutely huge files to notice. Even back then, memory bandwidth was a few MB/s --- still plenty fast, considering that the typical files of the time were also much smaller.

I can remember a time when I was attempting to write my own editor and at first spending a lot of time obsessing over the data structures (it was harder to find such information at the time) --- only to realise that a lot of the editors I'd tried, including the one I was using the most at the time --- were working perfectly well with just one big buffer.

I've opened files of a few hundred MB in Windows' Notepad, which also belongs to this family of editors; and on a machine a few years old, opening the file takes the longest because it has to be read into memory --- once it's opened, moving around and editing lines doesn't show much lag at all. "Worse is better", indeed.

Emphatically: Yes! KISS.

Moby Dick, at its slender 752 pages, is 1.2MB of text. You can save the entire text to disk on every keystroke on just about any system today and keep up with typing just fine.

Assuming you are actually dealing with text in a text editor, you should be fine.

If you have 100MB+ files, chances are they aren't actually text.

Log files..

Yes. Occasionally I'll open a 100MB+, or even a GB, log file without realizing it, and it will take vim many seconds to give me control.

Fair point, but do you actually edit log files in a text editor?

Because if you're just viewing, the "array of characters" representation is going to beat just about any other hands down, especially if you just mmap() the whole thing.

True. Generally no, but sometimes I will insert several empty lines around a particular line of interest..

I've used vi where I meant the pager quite often. I was late at making the use of head, tail, grep, wc, du, stat, etc. to peak into data to become muscle memory.

I am dealing with gigabyte sized log files almost every day.

Why not send them into a log aggregator for search and long term storage and logrotate on the server so you don't get this problem? Hell, why not logrotate anyway and keep multiple smaller files?

Sur4e. My response was to the comment that 100MB+ files are most likely not text. Like others I just tried to express that there are plenty of use cases for a text editor that can handle very large files. It's just a very practical thing.

I was consulting on a project the other day; turned out they never rotated their main Apache log file, and after 5 years it's now 32GB.

Textual dumps of SQL databases also fall in this category. I remember having downloaded a huge sql dump. I couldn't open it in most editors because they all buffered into RAM. The file was about 13G in size and did not fit into the RAM of any machine I own. But in this case using ropes wouldn't have helped either, I guess.

Text editors should also take huge files into account and provide sequential reading from the disk to memory. Even on Emacs, I couldn't work with the file. I ended up fixing it and importing it to Postgresql. And then I spent hours on indexing the necessary fields :).

I believe you can use the vlf package (https://github.com/m00natic/vlfi) for dealing with large files in Emacs. I haven't used it myself, so I am not sure how stable it is.

Thanks for the pointer. I guess I could also have written a small program or script to go through the file. Regular fopen and fread should work. However the vlf package does exactly what I looked for. Only prerequisite I can see is that one must compile Emacs with bignum support on 32bit systems to read files greater than 512M.

Many times in my career I've had to open very large files (usually CSV data) and inspect/edit them by hand.

Of course there are other ways to do this work, but a text editor that can efficiently open and edit very large files (e.g. Vim) is a great tool for the job. I will put up with otherwise excellent code-specific editors/IDEs that cannot work on such files but my default general-purpose text editor is always going to be something that can.

I appreciate that the design and implementation of text editors is basically an art form (one I've dabbled in myself) in which simplicity has aesthetic value, but efficiency and flexibility are very important for an editor that's going to be used for real work.

Are you sure the editors you're referring to weren't using gap buffers? The logic for a gap buffer is hardly any more complicated, and the performance benefit is significant.

Back when I first (and last) had to write my own text editor, 30 years ago, memory was at a premium, so I did what everybody else in the old Commodore days did: use the screen buffer, a paltry 40*25=1000 bytes, as additional memory.

When you first loaded a file, it would go straight to the screen buffer, B. Well, almost straight: you had to move to a new line when a CR character was seen. The rest of the file would go into buffer C, the region at the end of the free memory space.

As you scrolled down, the first line would go into buffer A, the region at the beginning of the heap, minus trailing whitespace. And so on.

In hindsight, this is a variant of gap buffers. If you edit the first line in a file, changes stay within the current paragraph on screen, until the paragraph needs to take up an extra line. Even then, though, the line at the bottom that scrolls off the screen only needs to be prepended to C, which, again, is at the end of the memory map and thus grows backwards.

The point is that each insertion at the start of the file would memcopy the entire buffer, though. With a few hundred mb file that sounds slow even today.

Are you sure that they don't keep a buffer of 10k lines or a gap buffer?

> With a few hundred mb file that sounds slow even today.

That depends upon how fast one can perform the memcopy of the entire buffer.

It has been said that latency amounts of 100ms are perceived as instantenous (https://www.pubnub.com/blog/2015-02-09-how-fast-is-realtime-...).

So if we take 100ms as our latency budget, then the max file size we can 'edit' with a straightforward memcopy (i.e., no gap buffer) becomes how much data the CPU can move in memory in 100ms.

With a modern CPU, moving on the order of 5-7 GiB/sec (http://jamesslocum.com/post/64209577678) a simplistic memcopy could handle editing the start of a 512MiB to 716MiB file and still feel 'instantaneous'.

With the much smaller file sizes of yesteryear (someone did mention Dos, many of the old Dos editors had a 64KiB max file size limit) in order for editing of a 64KiB file with a max latency of 100 ms required only that the CPU be capable of moving memory at a maximum of 640KiB/sec. On an 8088 IBM PC at 4.77Mhz with a 4 cycle latency per byte (https://trixter.oldskool.org/2013/01/10/optimizing-for-the-8...) the rep movsb instruction should achieve a maximum of 1164KiB/sec memory move speed. More than enough headroom to make editing a 64KiB max file appear to be instant, even using the basic memcopy method. Even if we assume 8 cycles per byte (4 to read, 4 to write) we still get 582KiB/sec of memcopy performance. Enough that editing would appear instant on all files less than 58KiB.

I take issue with the 100ms statement, but perhaps I'm missing something.

My hands automatically tend to play ahead of time when I play on a midi keyboard (piano piece) with anything more than 12ms.

Doesn't matter what I think I perceive, reality is my hands (muscle memory) intuitively perceive lag and begin to (measurably) hit notes just before the beat.

Likewise when I play a multiplayer (pvp) game, 100ms is considered even for the average gamer to be slow and annoying and is very much perceivable.

I like it no more than 25ms, and I have the luxury to get 7ms in best case scenario over fiber and ethernet. I can anticipate for the lag sure, but I feel it, which in this context is perceiving.

I am very confident I do not have to look at a gauge to perceive the lag, and can easily perceive it in a blind test around the 10 - 20ms response times.

I hit just one key and I notice if I lag or not. My ears are finetuned to expect the responding note to sound with at least 10ms accuracy within the resulting timeframe.

> A response time of 100ms is perceived as instantaneous.

please no :( my eyes hurt just from the thought of it. 10ms at most and I'm sure some people can perceive even faster stuff.

your eyeballs have more than 10ms latency iirc

Even if there was a minute latency between our eyes and brain, we would still be able to perceive the same sub-second differences we can now. We would just be too late to react to them.

You're conflating two different things.

A typical screen refreshes at 60Hz, giving 16ms between refreshes. If you take more than 16ms between animation frames, it will appear choppy and "bad".

The 100ms budget is around pressing a button and seeing a response. If you pressed your refresh button and the page loaded in 100ms, you consider that sufficiently "instantaneous". (This breaks down for video game controls where you're continuously giving input. And maybe 100ms is too long to respond to someone typing at 70WPM, but expecting a 10ms response is much too greedy.)

Is it, though? IntelliJ, a fully-blown IDE gets below it: https://pavelfatin.com/typing-with-pleasure/

I don’t see the logic behind having a full 60fps in a 3d game but not in a textarea (even though the linked article explains why it’s difficult).

xxxdarrenxxx's dead comment is long and relevant. If you don't have them turned on, it might be worthwhile.

~5ms is a more realistic budget given the 60-120 Hz refresh rate of most displays.

> It has been said that latency amounts of 100ms are perceived as instantenous (https://www.pubnub.com/blog/2015-02-09-how-fast-is-realtime-...).

Yes, but that was 50 years ago(!!!) and technology + expectations have moved on considerably since then; which that article explores. Thus my take away from that article is that 100ms is very perceivable and thus simply not fast enough for some applications.

For what it's worth, the article correlates with my own personal anecdote as well.

Going back to the original point, 100ms might still be good enough for a text editor, generally speaking. But going back to my own anecdote, I do find it highly frustrating when running into lag on a text editor when I'm banging out quick edits when either in the zone or working to a tight deadline. Frustrating enough that I have stopped using some text editors because of it.

If you are talking about typing, then I agree, 100ms lag after every keystroke, would be noticeable and annoying, but edits?

Surely you are not claiming to be doing 10 edits a second, where you might need to start complaining about 100ms lag?

I'm not really sure how you've interpreted my claim but the context of this discussion was about holding the text as an unbuffered array. This would mean every keystroke is effectively an edit. But even that aside, I'm sure we've all done stuff like:

    type "foobar\n" -> select "foobar\n" -> copy
    ctrl+v
    ctrl+v
    ctrl+v
    ctrl+v
    ctrl+v

...or the equivalent with replacing text within blocks of the same document; or other repetitive textual tasks that could easily be marcoed if it were a job you'd need to repeat again at a future point in time.

The limit probably more to do with typing speed isn't it? 100wpm, 5.1 characters per word is 8.5 characters per second.

Even if 100ms delay wasn’t noticeable, my peak writing speed is over 10 characters per second. Every character which comes less than 100ms after the previous one adds some delay, and I can imagine you end up writing for a bit, then stop and wait as the computer types 10 characters per second trying to catch up with you.

> A memcpy/memove() runs at many GB/s on a typical machine today, so you would have to be editing absolutely huge files to notice.

That's only good if your text happen to be raw text; I guess it won't work so well if it's rich text with needs to be converted to lightweight objects before being processed, where you'll want every object to be memory-aligned. And I wonder how well that approach works if your virtual memory space is paginated, which wasn't common in the 90's, but is practically everywhere nowadays.

I wrote a wysiwyg, memory-based rich text editor from scratch on the Mac back in the 90s called Scorpio. It had support for fonts, colors, styles, inline pictures, etc. It used a single buffer for text and I had no problem with insert/delete into this buffer even back then, even with ginormous amounts of text.

The "trick" (not really a trick, but..) was to use external data structures for the style runs that had offsets into the text array for styles/rich object support. That way I didn't need to worry about object alignment or whatever.

The downside of that approach was that there was bookkeeping to do in these external structures when text was inserted/deleted (indexes would need to be increased/decreased by a fixed amount, etc). The other major downside was that multi-level undo became problematic. It was easy enough to do one level of undo, which I did.

BTW, writing a word processor/text editor from scratch is a blast. I highly recommend it!

In my first attempt at an editor, written in an amazingly ugly (Borland) C/C++ mix, I assumed text was always delimited with some form of newline. I loaded the initial file into memory completely, and then constructed a "line" array structs, which contained a pointer to the start of the line, a length and a pointer to the 'previous' version. If this was NULL, it was the initially loaded buffer.

The editing of a line itself was far from optimal but straight-forward: it involved allocating a new struct, filling it in, when the undo mechanism was enabled pointing the previous version to the currently active version, otherwise pointing to the previous version of the last version (which should be the initial buffer), swapping the line pointer in the line array, and free'ing that old buffer/struct. Inserting a new line involved a memmove of the "line" array and an insert, and worst case a realloc of that array if it was too small.

I never really finished it, but I had a primitive undo mechanism in place that had issues with line inserts, which I never ironed out (project was abandoned at that point). It wasn't very memory-friendly when I enabled this undo mechanism, since this caused the entire history of every line being kept indefinitely, and every single-character insert or delete did a full copy of that line - and caused memory issues creating even relatively small files, certainly when starting from scratch, the memory bloat was incredible ^^

Still it was a fun project for me as a 16-year old kid.

> In my first attempt at an editor, written in an amazingly ugly (Borland) C/C++ mix, I assumed text was always delimited with some form of newline. I loaded the initial file into memory completely, and then constructed a "line" array structs, which contained a pointer to the start of the line, a length and a pointer to the 'previous' version. If this was NULL, it was the initially loaded buffer.

Something like this is how various vi implementations, and even some older (pre-GNU) versions of Emacs, work.

So 16-year-old you was not far off the mark.

Reply on news.ycombinator.com