5 ms·
The source is very straightforward and readable. I suspect part of the reason why is because live-coding forces you to eschew additional complexity/abstraction
by userbinator 7y ago
The source is very straightforward and readable. I suspect part of the reason why is because live-coding forces you to eschew additional complexity/abstraction in favour of the simplest solution.
That said, I'm not sure if the additional complexity of a gap buffer is worth it --- a lot of editors in the early days of DOS used a single buffer, effectively memmove()'ing the tail part when you inserted characters, and there was no real noticeable lag even when entering characters at the beginning of a "large" (i.e. >100KB) file. On a CP/M system with 64K of total address space at most, it just doesn't take all that long to go through all of memory. As an advantage, cursor movement code is greatly simplified and doesn't involve modifying the buffers.
- david-given 7y agoThe 8086 could move memory _way_ faster than the 8080 could! Also the ACK's memmove/memcpy is truly dreadful. I need to replace it with hand-tooled assembler ASAP. It's tougher than it looks, though; the 8080 only has two register pairs once you've allocated one for the frame pointer... It also doesn't help cursor movement as much as you'd think; editors don't address characters very much, instead preferring to address lines. For that you still need to scan forwards or backwards looking for line breaks. It would let you use memchr and memrchr to find them, though.
- teddyh 7y agoA description and discussion of different implementation strategies can be found here: https://www.finseth.com/craft/#c6.4 https://www.finseth.com/craft/#c6.4
- ncmncm 7y agoAs he says, TECO used a gap buffer in the early 60s, and he would like to know why authors of later editors made such bad choices. My guess is that they took CS classes, and actually thought things taught there were good ideas and not desperate dodges for when the simple thing won't work.
- kragen 7y agoI don't know the 8080 instruction set, but the memcpy in https://en.m.wikipedia.org/wiki/Intel_8080#Example_code https://en.m.wikipedia.org/wiki/Intel_8080#Example_code has 7 instructions in its inner loop and copies 2 bytes per iteration, which is probably about 20 microseconds at 2MHz and thus 640 milliseconds to copy 64K. That's a really long time to handle a keystroke, since they may be coming in every 100 ms or less. You can probably unroll the loop productively to some extent but you probably can't speed it up by the necessary order of magnitude. Gap buffers, by contrast, should keep everything under a millisecond except search and moving the gap a long distance. Many gap-buffer editors don't move the gap whenever the cursor moves; they wait until you modify something. But that does seem like it would be more complicated. I'm not sure how much simpler it can get than the gap-buffer case.
- tom_ 7y agoEven a Z80 would struggle to keep up: you're looking at something like 17-18 T-states/byte for a useful memcpy, which is ~215 KBytes/sec at 4 MHz. Suppose your document is 32 KBytes, and you're inserting chars at the start. It's going to take 0.2 seconds per keypress! You'd notice. (0.2 seconds per keypress = 300 keypresses per second. Assume 6 keypresses per word (5 letters and a space), and that's 50 wpm. You probably type faster than that.)
- kragen 7y agoThanks! I don't know much about 8080-family performance, but I remember sometimes WordStar would fall behind reasonably fast typing on a 4MHz Z80, even 50 or 60 wpm. But it was doing word wrap, too. I think you mean 300 keypresses per minute.
- deleted 7y ago[deleted]
- Someone 7y ago”Suppose your document is 32 KBytes, and you're inserting chars at the start.” Who has such enormous documents, and who inserts chars at the start :-) ? Given the 64kB limit for (program+data), you’ll soon need some way to keep things on disk (most likely by having a master document that lists the names of the files storing each ‘chapter’ in the complete document, and requiring the user to manually switch from file to file) Therefore, I would implement that, search/replace and a yank buffer before I started worrying about such relatively edgy performance issues. For comparison, the original MacWrite on a 128k Macintosh handled only 2 to 3 pages of text, and also soon got slower than that 0.2s per key press. It was smart enough to skip updates if typing was relatively fast, though. that is a feature you might want to add (e.g. by peeking into the keyboard buffer before refreshing the screen), as the best way to speed up code is by doing less.