Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!wuarchive!uwm.edu!ux1.cso.uiuc.edu!ux1.cso.uiuc.edu!m.cs.uiuc.edu!p.cs.uiuc.edu!gillies
From: gillies@p.cs.uiuc.edu
Newsgroups: gnu.emacs
Subject: Re: GNU Emacs, memory usage, releasing
Message-ID: <110700010@p.cs.uiuc.edu>
Date: 9 Jan 90 01:39:02 GMT
References: <1558@aber-cs.UUCP>
Lines: 45
Nf-ID: #R:aber-cs.UUCP:1558:p.cs.uiuc.edu:110700010:000:2011
Nf-From: p.cs.uiuc.edu!gillies    Jan  7 21:44:00 1990


The Interlisp-D text editor is probably based upon the "pieces" data
structure developed for Bravo and subsequent WYSWYG editors at Xerox
PARC.  It was not used in STAR because the editor-writers were not
informed (this is a long, sad story).

A "pieces" editor stores the file as a linked list of (ptr, lth) text
stretches.  I imagine it works like this --

To insert, find the appropriate piece in the list, split it into 2
pieces, add a 3rd in between, allocate an empty buffer and start
entering text into the 3rd piece.

To search forward and backwards efficiently you'd probably need a
doubly-linked list.

To delete, unlink a stretch of pieces (maybe zero), and also a
fraction of a piece at the beginning and end of the deletion.

The pieces data structure is fantastically efficient for large files.
I believe that you never have to copy memory blocks once the file is
loaded into memory.  If the user inserts a 6K piece of text into the
file, then duplicates it 20 times, the memory usage is still ~6K,
since different pieces reference the same 6K block several times.

The only drawback is that 
  (a) The user should save the file occasionally to restore it to
      a single piece, or
  (b) The program should do this automatically.

My impression is that pieces can be inefficient for large global
replaces (they "chop up" the file into small pieces), so you'd
want to save the file immediately after a global replace.

MS-Word (macintosh version) probably uses the pieces data structure.
It has "fast save" (write out all pieces) and "full save" (compact to
1 piece).  I edit 2 megabyte files all the time, with an editor
constrained to 220K (no VM), however, saves can be slow.  I think this
demonstrates that pieces work well for files larger than physical
memory.  I recommend that you check out this editor sometime.


Don Gillies, Dept. of Computer Science, University of Illinois
1304 W. Springfield, Urbana, Ill 61801      
ARPA: gillies@cs.uiuc.edu   UUCP: {uunet,harvard}!uiucdcs!gillies