21 ms·
The biggest challenge is figuring out how to store the text document in memory. My first thought was to use an array, but that has horrible performance if the u
by userbinator 7y ago
The biggest challenge is figuring out how to store the text document in memory. My first thought was to use an array, but that has horrible performance if the user inserts text anywhere other than the end of the document.
The counter-argument to that is that processors are ridiculously fast in human timescales --- copying memory at gigabytes per second --- so unless you're focusing your use-case on editing correspondingly huge files, there's no real need to make your implementation more complicated than a single array. Even when DOS machines with <640K of memory and memcpy() speeds in the low MB/s were the norm, people edited text files of similar sizes, with editors that used a single array buffer, and for that purpose they weren't noticeably slower than ones today.
My ideas for challenging projects are a little less open-ended, so they exercise different set of skills: being able to implement a specification correctly and efficiently.
- TTF renderer
- GIF or JPEG en/decoder
- Video decoder (start with H.261)
IMHO being able to consume existing content with code you wrote is very rewarding.
- tgv 7y ago> there's no real need to make your implementation more complicated than a single array Ugh. That's just offensive.
- yaantc 7y agoNot really, it's a commonly used scheme. Read on gap buffers: https://en.wikipedia.org/wiki/Gap_buffer https://en.wikipedia.org/wiki/Gap_buffer It's really an array with a gap at the cursor location. Used by emacs and others for decades.
- pkaye 7y agoHow big can file can a gap buffer be used on until it starts to slow down with current hardware?
- azhenley 7y agoIn the article, I listed a rope, gap buffer, and piece table as potential solutions instead of "just an array".
- smaddox 7y agoBut that's massively better than just an array. It changes the time complexity from O(char_inserts x file_len) to O(cursur_move x file_len), which is likely a couple orders of magnitude better.
- jakear 7y agoVSCode uses a JS piece tree, which allows it to be faster* at manipulating large files than Sublime’s native code implementation. https://code.visualstudio.com/blogs/2018/03/23/text-buffer-reimplementation https://code.visualstudio.com/blogs/2018/03/23/text-buffer-r... *or at least competitive with. I’ve measured it to be faster but I’ve heard others have had different experiences
- ben-schaaf 7y agoFrom a quick read it's actually pretty close to exactly what Sublime Text does. Source: Worked on that code at sublime recently.
- banachtarski 7y agoThat's not a single array though (per the OP's point)
- tgv 7y agoThat's not "just an array".
- symplee 7y agoCheck out: https://en.wikipedia.org/wiki/Rope_(data_structure) https://en.wikipedia.org/wiki/Rope_(data_structure) >> A rope, or cord, is a data structure composed of smaller strings that is used to efficiently store and manipulate a very long string. For example, a text editing program may use a rope to represent the text being edited, so that operations such as insertion, deletion, and random access can be done efficiently.
- markus_zhang 7y agoI just read from somewhere that VSCode uses a "piece tree" for code strings. Damn couldn't find the link...
- appstorelottery 7y agohttps://en.wikipedia.org/wiki/Piece_table https://en.wikipedia.org/wiki/Piece_table
- markus_zhang 7y agoThanks yeah that's the name
- dfox 7y agoIIRC many DOS-era editors used an array/list of line buffers. Which to me seems like good middle ground solution. Certainly for the todays typical usecase when you care about performance, ie. editing >100MB text data file by hand, which is giant pain in emacs because the gap buffer simply is not good structure for doing few simple edits across three places 10MBs away (as you spend most of the time moving the gap around, while touching essentially all of the memory)
- jstimpfle 7y agoDo you know of any reason why the gap buffer couldn't be easily replaced by a proper rope?
- dfox 7y agoas far as how the emacs API works it should not be an issue, but on the other hand there is bunch of elisp code, that realy expects an gap buffer based implementation and in turn is depended by who knows what...
- phkahler 7y agoI dont see any problem with an array. Make it huge so you only have to reallocate every megabyte or so. Keep track of the document length and only move as much as needed. Your processor can do this every character faster than you can type. No need for fancy data structures, and trivial to load and save files. The interesting part then becomes formatting for the display.
- deleted 7y ago[deleted]
- jstimpfle 7y agoTry a 100MB file.
- clarry 7y agoTakes less than 100 ms to read in the file (calling realloc in a loop), insert a byte in the middle (realloc + memmove), and write the modified file out on stdout. The byte insertion amounts to about 4ms. That's hardly fast, yet still a lot snappier than most modern editors' UI or the web, where apparently achieving 60 fps for a few hundred dynamic DOM nodes is some kind of an achievement. https://gist.github.com/hmkemppainen/376b973c568fc122e2d8c843b49e8d0d https://gist.github.com/hmkemppainen/376b973c568fc122e2d8c84... This approach really starts to suck when you implement macros that are going to perform a lot of one-char inserts quickly. Or when you're editing multi-gigabyte files.
- jstimpfle 7y agoI must admit I was surprised, although I shouldn't be. Are we at > 10GB/s memory bandwidth now? > This approach really starts to suck when you implement macros that are going to perform a lot of one-char inserts quickly. Or when you're editing multi-gigabyte files. I'm working on an editor that I've optimized for such cases. In a test it made random edits to a 4GB file in < 50 microseconds. But, it cost a load of sweat and blood to get that rope data structure right. And it loads files only at about 100MB/s (should optimize for bulk inserts). https://github.com/jstimpfle/astedit https://github.com/jstimpfle/astedit
- aliceryhl 7y agoLast I looked into writing a JPEG en/decoder, I ran into the issue that I was unable to find a specification not behind a $800 paywall.
- Jasper_ 7y agoHere you go: https://www.w3.org/Graphics/JPEG/itu-t81.pdf https://www.w3.org/Graphics/JPEG/itu-t81.pdf https://www.w3.org/Graphics/JPEG/jfif3.pdf https://www.w3.org/Graphics/JPEG/jfif3.pdf I'll also link Cristi Cuturicu's "A note about the JPEG decoding algorithm", which is where I started my decoder implementation from, and it was indeed a ton of fun. http://www.opennet.ru/docs/formats/jpeg.txt http://www.opennet.ru/docs/formats/jpeg.txt
- jacquesm 7y agoThe JPEG reference source code is pretty readable.
- caconym_ 7y agoI don't edit really huge files that often (maybe a couple of times a week), but when I do I want to be able to use the same editor I use for everything else. A really great text editor is fast and flexible and powerful regardless of the size of the file you're trying to edit.
- alecmg 7y agoThats one issue I have with these proposed programming tasks. You are not going to write a really great text editor as a learning exercise. It has been done by better programmers who had better overview of the problems and over thousands man hours. This automatically means the task is as useless as a gameboy emulator or basic compiler. The underlying "Things to learn" points are good, but tasks themselves are not.
- caconym_ 7y agoWriting experimental text editors for fun in various programming languages has been one of the most rewarding learning exercises of my life. It's not really clear what your point is. You say the task is "useless"—what does that mean? Personally I can say that you are categorically wrong, because the skills I gained building things that are not completely new ideas fueled my passion for programming and opened up doors for me that otherwise would have remained closed. Even if I didn't still use a lot of these projects myself (because I built them to fit me), the value I derived from them would still be significant in the "grand" scheme of my life. If a programmer is excited about the idea of writing her own text editor, what would you suggest she build instead that will sustain that same excitement and offer exploration into the same diverse subject matter but also satisfy your nebulous criterion of not being "useless"?
- dnautics 7y ago> so unless you're focusing your use-case on editing correspondingly huge files, there's no real need to make your implementation more complicated than a single array. I think the other major corner case is when you need concurrent, distributed editing (although that's not popular or anything these days), in which case an array is a very poor datastructure.
- retrovm 7y ago"no real need to make your implementation more complicated than a single array" That's our industry in a nutshell. Our computers, instead of becoming more capable over time, can barely keep pace with the increasing naivety of our programmers.
- Denzel 7y agoYes, this is engineering in a nutshell: determining a course of action within a set of constraints that meets your objectives. Where constraints can be time, cost, physical limitations (processor speed, memory size, disk space), etc; and objectives can be functional (user can edit files), nonfunctional (user can edit large files in < X seconds, energy usage), personal learning, or any number of other requirements. The GP offered a valid decision point to consider based upon what an engineer is solving for. I don’t think he said that an array was the solution he’d ship in a production text editor to millions of end-users. Engineering is hardly naive. :)
- userbinator 7y agoActually, that's exactly what I was saying --- plenty of existing text editors use the "stupid" single array, yet no one complains about their performance. One example? Notepad.
- deleted 7y ago[deleted]
- ethbro 7y agoNotepad is notepad because someone, god bless their soul, had the sense to put new features into a different app as Wordpad. In some terrible, dark dimension, Notepad has a ribbon interface and supports PDFs.
- tripzilch 7y agoJust because people tend not to edit large files in Notepad doesn't mean they'll complain about it when they do. Actual complaints are of course sparse because hardly anyone uses Notepad for anything serious if they can use an alternative. BUT when they do, oh they will complain. I believe an older version of Notepad even had a (fairly low) limit on file size it would open. I mean that's the reverse argument, computers have gigabytes of memory today, and are super fast, so you should be able to load a multi gigabyte text file and edit it, on a single line, with word wrapping.
- namirez 7y ago> there's no real need to make your implementation more complicated than a single array. I think you are misunderstood about the concept an array. An array has 1) an interface that is easy to use. On the other hand, by definition, an array is 2) contiguous in memory. Property 1 is good but 2 can cause problems. I think you want only 1. The solution is to create a data type that has the interface of an array but a different implementation under the hood. You can have a linked-list of arrays, a tree of strings, etc.
- prox 7y agoI wonder what a text editor made by HN would be like, everyone is already thinking up strategies :)
- deleted 7y ago[deleted]
- onion2k 7y agoWhether an array is contiguous in memory depends on the language (and the specific implementation of that language). JavaScript uses hash tables for its arrays which are really objects.
- namirez 7y agoGood point! Dynamic languages are different in their terminology. AFAIK strongly typed languages have a clear definition of arrays. The OP was talking about arrays having "horrible performance if the user inserts text anywhere other than the end of the document". I think this statement has an implicit assumption that arrays are contiguous which is not true in Javascript.
- calcifer 7y ago> Dynamic languages are different in their terminology By different you mean wrong. PHP calling an ordered hash map an array doesn't make it one.
- bryal 7y ago> there's no real need to make your implementation more complicated than a single array Yeah, good luck enabling line numbers in such an editor. In Emacs, which uses a gap-buffer for storing text, line numbers have had notoriously slow. It's gotten a bit better lately, but suffice to say, a naïve flat array / gap-buffer approach is not good enough for some relatively common scenarios even on modern hardware.
- nine_k 7y agoBut line numbers are trivial to update when a gap buffer needs a move. A list of strings is more elegant, of course, where only the line being edited becomes a gap buffer. It taxes the allocator a bit more, though, which might be a concern on computers of the time when Emacs was born.
- BurningFrog 7y agoThat's a problem to deal with when/if you need to add line numbers. Not a minute before that!
- CuriouslyC 7y agoWhile that is true to an extent, I've made a lot of money cleaning up after people that didn't architect and design their code to cleanly grow into a fairly obvious potential use case, requiring major rewrites. It isn't a premature optimization to avoid walling yourself into a corner..
- BurningFrog 7y agoThis is a complex and nuanced topic. I agree strongly with designing your code so it's easily changeable into whatever new features are needed. This is much easier said than done, and I don't know if anyone has written well about the tricks of that trade. But anyway, if you have that kind of code, swapping out whatever you need to make line numbers happen is no more work later than sooner. Code bases with features implemented that are never used, but you still have to keep working through all changes, because someone imagines it will be a real requirement someday, are what my nightmares are made of.
- xxs 7y agoTIF and GIF are trivial compared to JPEG and H.261, saying that having implemented LZW and GIF (in assembly for 8086) as teenager
- mwfunk 7y agoFor TIFF (and most formats) that's heavily dependent on if you're talking about implementing a reader or a writer for the format. TIFF readers need to handle JPEG streams, so in that sense implementing a general purpose TIFF reader is a superset of implementing a general purpose JPEG reader. On the other hand, TIFF writers can (very conveniently!) be almost as simple as you want, including no compression at all, just blobs of raw pixel values, and a smattering of tags for width, height, pixel format, and that's it. The only thing simpler to output IMO would be uncompressed ASCII formats like XPM. So in that sense you're correct- the simplest possible JPEG writer is much more complicated than the simplest possible TIFF writer, but TIFF in general is extensible to a fault (arguably), in the sense that the number of possible combinations of pixel and metadata encodings you have to prepare yourself for when opening arbitrary .tif files are far greater than when opening arbitrary .jpg files, including JPEGs within TIFFs.
- xxs 7y agoBack in the days TIF was just a large uncompressed file. The initial format is older than GIF87a (no animation which people associate GIF nowadays with). It had header but that pretty much it. Of course the format developed with time and even added LZW once the patent expired. Currently TIF is all kind of things, so writing a fully feature reader is a proper challenge (perhaps not coding-wise, but understand it and implementing the myriads of types/extensions, etc.)
- agumonkey 7y agoSpec implementation is indeed very valuable. But in your cases these are data oriented problems. I'd add some systemic cases: networking, security.. my 2 cents
- audiometry 7y agoNot sure about Gb of throughout makes editor memory representations unimportant. Just this week my friend said he kill emacs with a few-MB text file. I was astonished that a software of that esteem would struggle with that.
- ses1984 7y agoIt's unlikely plain emacs struggled with that file.
- BeetleB 7y agoIn my first job I would routinely open 10-20 MB files in Emacs. It handled it just fine. I mean, it gives a warning that this is considered big, but I ignored it. Now if you open a large text file in something other than text mode, it could bring it to its knees depending on the mode. As an example, opening an XML file in the nXML mode is quite expensive, because nXML mode is powerful and utilizes your XML structure. I just tried a 12 MB XML file and told it to go to the end of the file. It's taking Emacs forever to do it (easily over 30s). But if I switch to text mode for that same file, it handles it just fine. I just tried an 800 MB text file. It handled it fine. The one thing where you can easily get in trouble: Long lines. Emacs cannot handle long lines well. Kinda sad.
- kccqzy 7y agoAre you sure text mode is fine? I usually have to use fundamental mode to edit big files (more than a dozen MBs or so).
- BeetleB 7y agoYup. Text mode is fine. If that's causing problems, perhaps you have things enabled in your config that causes problems? As an example, I have anzu minor mode selected. So if I try to search in the 800MB file, it hangs until I cancel.
- lodi 7y agoTry `emacs -nw -q` for a stock experience. That should have no problem with any reasonable text file.
- froh 7y agoUmm the dos 640k were paged, non contiguous. Additionally, smoothly editing larger texts back then required some clever linked lists of blocks to give a truly instantaneous editing experience for inserting text at the beginning of a large text. Those were the 286/386 days. Today you have fancy rendering, and an instantaneous editing experience for that reason again suggests a more sophisticated data structure for the editor. Which all text editors have, when you look inside vi/emacs/nano/whatever...
- scarface74 7y agoThe counter-argument to that is that processors are ridiculously fast in human timescales Until you actually have to implement your algorithm on a mobile device that is both memory, and power constrained and that doesn’t have a swap file. The OS will either lol your program for being too memory or power inefficient, kill another program running in the background (not a great user experience) and/or force the use of the high power cores using unnecessary battery life when a more efficient algorithm could have used the lower power cores. Attitudes like this also explains why developers don’t think twice about delivering battery consuming Electron apps.
- tripzilch 7y agoBut did you try editing a multi megabyte file with that method? Cause I have seen enough editors struggle with big files (especially if the file is a single line and you're going through it with word-wrap on), that I think the basic straight-forward approach already isn't sufficient on such workloads. from the article: > Luckily, there are some nice data structures to learn to solve this. You could have also learned a new data structure! I mean, it should be obvious that "this thing that the cursor does when moving lines" isn't the big takeaway from this challenge. It's almost cute that the author never noticed it (as a programmer), because I actually use that behaviour to navigate code sometimes. Who hasn't done a quick arrow-left/right to make the cursor lose its memory of which column it used to be on? > Even when DOS machines with <640K of memory and memcpy() speeds in the low MB/s were the norm, people edited text files of similar sizes, with editors that used a single array buffer, and for that purpose they weren't noticeably slower than ones today. No way. Every reasonably performant text editor in those days used special data structures and not just an array. Imagine having to copy the entire buffer on each key press (so, when inserting at the start of the file). Believe me, on a 640K DOS machine you'll feel that. This isn't new stuff, I learned about these data structures in uni -- except I don't remember them because back then I was young and arrogant and didn't think you'd need these fancy data structures for something as simple as an editor :) :) ... but if you never tried to write one, it's hard to see in what ways these editors are not as easy as you think.