Xref: utzoo comp.editors:1218 gnu.emacs.bug:1472 comp.unix.wizards:19982
Path: utzoo!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!uunet!mcsun!ukc!dcl-cs!aber-cs!thor!pcg
From: pcg@thor.cs.aber.ac.uk (Piercarlo Grandi)
Newsgroups: comp.editors,gnu.emacs.bug,comp.unix.wizards
Subject: Re: GNU Emacs, memory usage, releasing
Message-ID: <PCG.90Jan3170738@thor.cs.aber.ac.uk>
Date: 3 Jan 90 17:07:38 GMT
References: <1558@aber-cs.UUCP> <129799@sun.Eng.Sun.COM>
Sender: pcg@aber-cs.UUCP
Organization: Coleg Prifysgol Cymru
Lines: 96
In-reply-to: jpayne%flam@Sun.COM's message of 2 Jan 90 21:45:25 GMT


In article <129799@sun.Eng.Sun.COM> jpayne%flam@Sun.COM (Jonathan
Payne) writes:

   I picked linked list because I knew I could not store the files in
   memory simply because I wrote JOVE for the pdp11/70.

I have been using Jove for many years now. Well, five or six...
On PDPs.  I am now using it instead of GNU, by the way. While it
is coded in a way I disagree with, it has steadily improved, and
the mix of deatures offered/non offered is remarkably balanced.

   But since I moved to bigger machines [... and am going to use
   gap for Jove ... ]

Moving to bigger machines, and all hell breaks loose... Aaaaghhhh.

   I will never use a linked list of lines approach again.  Buffer gap is SO
   much better in lots ways from an implementor's point of view and often
   from the user's point of view.  Here are the reasons that come to mind:

As to that the simplest editor can be built with the two tape model of
buffer management, but I hardly recommend it...

	   o File i/o is blindingly fast.  It's standard to implement
	     read-file the following way: [ .... ]

This is also trivial if you use a log method for updates. You read in the
original, and then you keep a log of changes. It is also true that people
often edit files for long times, and cost of reading them in is not that
important.

	     Writing files is done in two chunks, the data to the left of
	     the gap and then the data to the right.

With the log method this is more complicated, but not dramatically so.

	   o A buffer position is represented as an integer. [ .... ]
	     All are possible with linked list, but the code is harder to
	     write, less reliable, and the implementation will be slower.

But not terribly slow. And with costs being constant, instead of O(n).

	   o Insert and delete operations of ANY kind are trivial to
	     implement. [ ... ]

As you say, just copy everything around... This is a *problem*, not a solution.

	   o No line length hassles.

You have to work a bit harder, On the other hand most lines an editor sees
are short. So you can just have more complicated code for the case where line
length overflows a predetermined limit.

	   o Undo/redo is trivial to implement in this scheme.

Undo/redo is also trivial with a log approach.

   The point is, moving the gap around is not that big a deal.

Oh yeah. Too bad that constant time alternatives exist, instead
of O(n), and that O(n) uses a lot of memory bandwidth and cycles
and paging and...  Of course, as always, if you are the only user
of a 10 MIPS 16 MByte workstation you can afford to waste a lot of
those. To me, however, waste is no good, if it can be easily obviated.

   I thought paging algorithms were geared towards sequential access,

Most paging algorithms implement some approximation of LRU; LRU is *guaranteed*
to trash on sequential access.

   >The better solution, made relatively easy by the reasonably modular and
   >layered structure of GNU emacs, would be to accept The Emacs Cookbook
   >recommendation (adopted by Jove and the MicroEmacs/Gnu family of editors) and
   >implement a linked list system. I would suggest just reading (or map, on the
   >operating systems that allow it) the file to be edited as a large lump of
   >virtual address space, then building a linked list of pointers to lines
   >therein, and then to allocate modified lines from ageneral purpose arena.
   >Informing the OS of the peculiar access patterns would also help, if
   >possible.

   Again, I think this would muck up the rest of the code in the editor.
	[ ... ]

   I'm not saying all this isn't possible.  It's just my belief that it's
   not clearly a win.  In fact, in my eyes, for 99% of the editing that I
   do, a buffer gap solution makes the most sense.

Well, well, there are techniques around that. Also, it pays to invest
more effort in a widely used utility like an editor than otherwise. The idea
that a frequently used, response time critical, tool should be coded quick
and dirty makes me object vehemently.
--
Piercarlo "Peter" Grandi           | ARPA: pcg%cs.aber.ac.uk@nsfnet-relay.ac.uk
Dept of CS, UCW Aberystwyth        | UUCP: ...!mcvax!ukc!aber-cs!pcg
Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk