Hacker News Reader

Comment by john_moscow | Hacker News Reader

Efficiently handling large text files requires extra special care.

~2x memory looks like a naive implementation of just allocating an std::string from heap for each line. Due to heap fragmentation and various overhead it would quickly blow up.

~1x memory looks like just reading the entire file into RAM (that would still be slow).

A truly efficient implementation would never need to load the entire original file in RAM. It would just need to remember the binary offset of each line in a way that combines random access and reasonably fast insertion/deletion (e.g. K-fold trees). You can even keep everything beyond the top-level directory in an temporary on-disk file, so your RAM usage could be less than 1MB with nearly instant performance.

The efficient implementation is tricky, error-prone, and involves handling a solid amount of corner cases, which is beyond the amount of hassle a typical hobbyist developer is willing to go through.

View on HN

> A truly efficient implementation would never need to load the entire original file in RAM. It would just need to remember the binary offset of each line

Except that this would most likely result in unpredictable corruption if another process modified the file while you had it open, which is contrary to the way basically every text editor works.

It would be nice if there was a way to mmap a file in such a way that the OS would give you a snapshot view, but AFAIK that doesn't exist, at least on Linux in a filesystem-agnostic way (not sure about other operating systems).

I think every platform supports FS notifications at least right? The app could listen for changes to the file and reload/discard when it goes out of sync. In fact Notepad++ already does this.

On Windows in particular you also have a ton of other facilities that could help with this (opportunistic locks, transactions, etc.) but notification is usually good enough.

My main editor is vim. It notifies the user when a file you have open in a buffer gets modified on disk by another process. It explicitly gives you the option to load the file from disk at this time. I would not use a text editor which silently reloads a file because this could result in a loss of work.

Yeah Notepad++ asks you too. I don't know of any editors that silently discard changes by default.

While many editors will come and go, vi in some form will always remain. Once you "get" it, using anything else starts to become alien.

This would also be too slow. The user may want to jump from line 1 to line 999999. You can't do a file load fast enough.

> This would also be too slow. The user may want to jump from line 1 to line 999999. You can't do a file load fast enough.

My text editor supports files up to 256 GB in size, unless you have that much memory, you’ll have to wait a little bit to go from the first to the last line.

That's great, which editor is that?

I use UltraEdit, it opens files way beyond hundreds of GB without issues, both text and binary (in hex edit mode). Love that editor for over 10 years (perpetual license) on Windows, Mac and Linux. See the video loading a 35GB text file: https://www.ultraedit.com/support/tutorials-power-tips/ultra...

EmEditor, it’s windows only: https://www.emeditor.com/

Isn't that what having offsets and mmaps are for? With that information, jumping lines becomes constant time.

Not necessarily. It's possible to listen for file updates and respond accordingly on the fly by re-reading the file and updating all your offsets and mmaps. It doesn't even have to be efficient; it's not a common case.

This is why I will always pay for the latest version of Sublime Text. First to support indie developers, but second for the marvelous piece of software that allows me to browse gigabytes of data in a GUI.

Dammm havn't heard that word in awhile - had to look at my calendar to double check what year it was. Great to hear they are still rocking!

Python Crash Course by Eric Mathes is updated up to Python 3.7 and uses Sublime as the editor of choice also.

I thought Sublime's popularity has grown in recent years? Was it even more popular in the past or am I mistaken? It's just that compared to the standard vim vs emacs debate, I now always hear sublime thrown in for good measure when discussing pure text editors.

I last used Sublime Text in early 2014 and the same is true for most of my friends.

It is a lot more performant than VS Code, but VS Code seems to have won on the sheer quantity of “good enough” plugins. Its pair programming features are a big deal as well.

For the most part I use VIM for quick things and VS Code when I need a plugin or to work with others. SBT kinda sits between those two extremes.

The pair programming feature from VSC is the only one I’d really miss from that side if I were to go back to SBT. Not sure about from the VIM side because I’m sure the SBT VIM plugins have improved over the past 8 years.

I think it was a joke about the band.

Everyone I worked with in about 2014 swore by sublime text. A few years later it lost a ton of ground when Atom was released (and then forked to make VSCode).

I used it in 2010 for PHP and python related projects, It worked like charm.

I've been using Sublime Text for a decade and never had any reason to leave it. It's been pretty much the most valuable piece of software that I use daily for a big chunk of my career. I've had to buy a new license maybe twice? ST2 and ST3. And another for Sublime Merge. The $100 or whatever it was might as well be _zero_ compared to the amount of value I've gotten out of it. I love this thing.

Is that a direct competitor to something like Notepad++ ? Looking into it myself

It is, in my opinion. It’s quite brilliant as a powerful text editor.

> A truly efficient implementation would never need to load the entire original file in RAM. It would just need to remember the binary offset of each line in a way that combines random access and reasonably fast insertion/deletion (e.g. K-fold trees).

To know the offset of each line, you'll need to load the entire file from disk. So you're talking about loading it, processing it, and throwing it out again. You should qualify calling that "efficient" since you will need to re-load portions of the file, as needed.

Also, an OS's virtual memory systems may work well for you with minor tuning, so it's work looking into that before you spend a lot of time essentially writing your own.

I think unless you have a good reason not to, your best bet for a text editor on a modern OS is to read the entire file into memory and leave it there. (But don't make multiple copies of it or use two bytes to store each character as the current version of NotepadNext is apparently doing.)

> To know the offset of each line, you'll need to load the entire file from disk.

No. You will need to read the file, not load it all at once in memory. And for a sequential scan, you need very little memory at any one time.

And if you are doing that, you can start displaying the file as soon as you have scanned enough to fill the view. The rest could happen in the background.

I didn’t say you had to keep it all in memory to process the line ending. Of course you don’t. You need only two characters of memory (assuming you’re handling windows line breaks).

With a 64-bit address space, you're probably better off just mapping the entire file into memory, not specifically loading it all. Let the OS swap in and out the pieces you need as you access it (and build your index of line offsets or whatever other structures you need).

The big advantage to mapping is that you only read from disk the portions of the file you need, and only when you need them. Disk access is monumentally slow, so this can be a big win: if you don’t need to access all of a large file, or don’t need to access it all at once, mapping saves you very expensive operations or spreads them out over time.

The problem with that for a text editor is that probably the first thing you want to do is process the line endings. So you’re just going to access the entire file, right away, as fast as possible anyway.

So mapping doesn’t really give an advantage in this case.

Or it might be that one is representing the character data as 16-bit wchars in memory, and the other treats them as 8-bit chars.

> Due to heap fragmentation and various overhead it would quickly blow up

I think this is mostly likely the culprit. There almost definitely isn't that much contiguous memory available for a large file like this, so there are a lot of wasted pages (maybe 2-3x) which is causing that footprint to balloon.

For 500MB there should easily be enough contiguous virtual address space, and if there isn’t the allocation would fail. I don’t see how it could take up 2-3x extra pages unless it’s being stored in a really poorly designed segmented memory structure.

Yeah without knowing anything about the implementation when I see "I opened a 500MB file and it's taking 1.3GB of memory" that's just my first guess. Maybe it's wrong.

How it can be nearly instant performance if you have to load data from disk on demand? If users jumps a few pages, or he performs a search or replace, things will get real slow.

We wouldn't use large quantities of RAM today if there were any techniques that could make disk acces "nearly instant".

Seems like anything past a few megabytes would really be better done with dedicated tools for that amount of data.

I think I'd be a bit unhappy if I was regularly loading megabyte blobs of text into editors, and start looking at other representations or tools.

The only files that big that I know of are log files, and very occasionally a CSV or two as some kind of data dump, and there's usually dedicated tools for those cases.

~1x memory looks like just reading the entire file into RAM (that would still be slow).

It's worth keeping in mind that typical CPUs from the past few years to today have memory bandwidths of several GB/s. Disks have sequential read speeds of ~100MB/s; SSDs can easily do 1GB/s and above.

It's amazing to me how slow some stuff is even on modern hardware. Lazy programming abounds.

Does anything implement it like that?

Wouldn't mind betting Sublime does a good job

It does. I loaded a 14GB file in it once.

xi-editor has some reasonably sophisticated handling for large files

It's vaguely reminiscent of Vim's implementation, in the sense that I think, for large files, in it's default config, Vim keeps most of the text in it's swap file and pages it in as needed.

Vim's implementation also feels somewhat line-oriented in that if you load a large JSON file that has everything on 1 line and you try to edit that line, uh... it will be sluggish, but if you do, like %!jq '.' and format it, you can them move around the file a little easier.

Edit - What the heck while I'm at it:

Emacs - Historically used a Gap-Buffer which optimized more for locality of edits than loading large files. It doesn't suffer though as much from heap fragmentation though as the linked-list of strings type approach.

Monaco - The editor in VS Code recently went from a linked-list of strings to a PieceTree buffer. Which basically loads a the whole file into an immutable buffer and then uses the PieceTree to manage the edits.

Others - Lately people keep talking about Ropes, which is another tree type deal with extra-smarts specifically for text editing. I don't know of a game-changing editor like the others mentioned that uses it tho.

Ropes were introduced in this paper in the journal Software, Pracise and Experience: https://doi.org/10.1002/spe.4380251203 (best accessed from a university domain)

An example for an editor that uses them to manage large text files is Xi-Editor: https://github.com/xi-editor/xi-editor (edit: written in Rust).

Cool, I'm really interested in that paper, ty.

https://www.chiark.greenend.org.uk/~sgtatham/tweak/

> 2x memory looks like a naive implementation of just allocating an std::string from heap for each line. Due to heap fragmentation and various overhead it would quickly blow up.

Looks more line Qt's internal UTF-16 encoding in this case.

Such truly efficient implementation sounds really nice, with offsets and mmaps.

Is there any open source text editor doing this?

I’m afraid to ask, but how does emacs do it?

grabs popcorn

Never fear, Emacs approach is pretty great. It uses a gap-buffer, which is conceptually an array with a space that moves around with the insertion point. It's pretty cool approach because, it's simple, there's very little bookkeeping overhead and moving around the gap is gonna generally be cheaper than shifting around the whole array and minimize complete re-allocations. In other words it's good for what we do the vast majority of the time with a text editor which is jump around reasonably size files making small edits.

One downside, relative to this conversation, is it doesn't make working with pathologically large files a lot better. Without further optimization a gap buffer could push your box into swap if you open a large enough file.

I love gap buffers because it was super simple to implement. I struggled with ropes and certain tree based algos when I wrote a terminal based text editor in Nim

Also if the file is 500Mb, probably a text editor isn't the best choice of app to work with it. That said it is often the most convenient. But a 'non loading' text editor would be interesting for this. E.g. it doesn't show the file, but you can still do find in file etc. operations. Maybe basically a thin UI around grep etc.

Why not just use mmap() or the Windows equivalent?

Because then all your edits have to go directly into the file, so you have no real "save" flow unless you make a swap file for every file and then mmap that (which can be an appropriate approach, to a degree). Then all your caching and memory use subject to OS I/O and filesystem concerns, and you can't optimize for specific use. And inserting or deleting the middle of the file means shifting all the bytes after it.

I could think of a reasonable implementation for Linux that would use mmap and fallocate, but it wouldn't "just" be an mmap, as the swap file would still need to represent a rope or a gap buffer or something else of the sort for efficient editing.

Aren't edits of a huge file expected to be comparatively small? If you're editing an mmap'd file, I'd expect the editor to maintain a display combining the original mmap'd file with a list of changes that have been performed so far.

Let me rant for a bit because I've dealt with the following: Another downside is you'll get people complaining about memory usage despite mmap only paging in what's needed.

It's frustrating but users don't understand how to read memory usage at all. There's even guides out there quite wrongly telling users to look at virtual memory usage for each app.

Mmap is a brilliant way to have the os handle which parts of the file actually reside in memory but you'll seriously have to deal with users that know only enough to be dangerous complaining that your app uses gb of ram when it's merely mapping a file into virtual address space to allow the os to page as it sees fit.

In fact I wouldn't at all be surprised if the memory measurements in this thread were judging virtual allocation rather than physical memory used.

Reply on news.ycombinator.com