🚀 go-pugleaf

On the machine where I receive my e-mail, mail folders (primarily from
the last month or two) occupy 80% or more of the disk space I am using.
Thus, the suggestion that mush support compressed mail folders seemed
highly attractive to me.  The subsequent discussion convinced me that
building in automatic use of compress/uncompress would be both
difficult and inefficient.  Unfortunately, an approach like the zfolder
macro, although easier to do, is even less efficient, so I thought I
would suggest another approach:

From the discussion, it would appear that mush performs the following
low level operations on a mail file:
1. reading the entire file sequentially
2. reading selected sequences of bytes from the file randomly -- the
   size and location of these sequences can apparently be identified
   during the sequential pass
3. appending data (of known size?) to the end of the file
4. creating a new file
5. renaming a new file to replace an old file
6. deleting an old file

What I am suggesting is that it might be possible for mush to recognize
that some classes of mail files require special processing and to fork
an new process to do that special processing.  The process could accept
"commands" and data through stdin and produce status information and
data on stdout.  The specific commands needed to allow efficient
implementation may require some further study, but as a first cut, I
would suggest the operations above plus an operation to identify those
points where subsequent random reads are likely to begin.  Assumining
that both the file containing the process and the conditions under
which it is invoked are made user specifiable, mush can be extended to
handle new mail storage formats to write such a process, without Dan
and Bart's intervention.  To illustrate this, I will suggest how three
such special processes might be constructed:

Example 1: Compressed Folders

Although the existing commands compress and uncompress are ill suited
for this, the underlying LZW algorithm is not so hopeless.  Both the
compress and uncompress algorithms involve the creation of the same
internal dictionary and this creation process is additive, that is,
the dictionary later in the file is normally a superset of the
dictionary early in the process.  Thus, only relatively little
information should be needed to allow uncompression of data in the
middle of the file using the dictionary corresponding to the end of
the file.  The implementation of the "commands" might then be as
follows:
1. sequential read - Do standard zcat/uncompress algorithm, except
   one also creates a list of correspondences between offsets into
   the compressed data and offsets in the resulting uncompressed data.
2. random read - Search the list of correspondences to find the highest
   output offset less than the requested starting point.  Do standard
   zcat/uncompress from that point, discarding output bytes before and
   after the requested range.
3. append - If dictionary is not already built, do uncompress algorithm
   building dictionary without constructing uncompressed text.  Then
   start compress algorithm at the end of the file, augmenting the
   existing dictionary.
4. create file - Initialize dictionary as for standard compress
   algorithm.
5. rename - Do ordinary rename (except for possible "smart" handling
   of .Z extension).
6. delete - Do ordinary delete (except for possible "smart" handling
   of .Z extension).
7. position noting - This could be taken into account in building the
   offset correspondences during sequential read.  I would suggest
   maintaining a circular buffer of temporary correspondences with
   small separation for recently uncompressed data.  When a request is
   received to note a position, the temporary position best covering
   that request can be added to the permanent list and all earlier
   temporary positions discarded.  If the buffer fills up, the oldest
   temporary positions can be discarded.  (The temporary buffer needs
   to be large enough that mush can recognize interesting positions and
   request that they be noted before the appropriate temporary
   correspondence "falls off the end".)

There is one other special case:  Some times the dictionary in LZW is
filled and the algorithm restarts with a fresh dictionary.  For this
processor, I would note the offset at which this occurs and then fork
a copy of the processor to handle requests for reading or writing
beyond that offset.  Thus, there would be a separate copy of the
process for each distinct dictionary.

Note that this implementation _never_ produces the uncompressed file,
only uncompressed portions of it.  This should help to keep down the
peak disk usage!

Example 2: Bart's Variation on Compressed Folders

The above method for implementing append should be significantly faster
than uncompressing the file, appending, and recompressing it, but if
the file becomes large enough, it still might be too slow for some
people.  Bart suggests the variation of using two files to represent
a folder, a compressed base file and and uncompressed extension.
The implementation of the "commands" might then be as follows:
1. sequential read - First apply same algorithm as for example 1 to
   base file.  Note the number of bytes produced.  Then deliver the
   bytes from the extension file.
2. random read - If the bytes are before the breakpoint, use the
   implementation from example 1.  If the bytes follow, subtract
   breakpoint and get corresponding bytes from the extension.  (Since
   mush will be asking for messages, requests should never span the
   breakpoint, but if they did, you just do these two methods one
   after the other.)
3. append - If dictionary already available, do as for example 1.
   Otherwise, append data to extension file.  (Optionally, if extension
   file gets "too large", build dictionary and append all of its
   current contents as for example 1 and truncate the extension file
   back to being a zero length file.
4. create file - initialize base file as for example 1 and create
   zero size extension file.
5. rename - Rename both files.
6. delete - Delete both files.
7. position noting - note positions before the breakpoint as for
   example 1, but don't bother noting positions after the breakpoint.

Example 3 - Directory as Mail File

Someone wanted to modify mush to deal with a scheme where each message
was in a separate file and the directory was the "mail file".

1. sequential read - Reach each file in order, building a list of which
   byte offset are in which file.
2. random read - Use the list to determine which file to read from.
3. append - Write new file in directory.  (If it can be recognized that
   this corresponds to exactly the text in a file in another directory
   (i.e., the copy during the update of a mail file), link the file
   rather than writing a new one.  Additional "commands" may be
   required to give the special process enough hints to recognize
   this case.)
4. create file - Create directory.
5. rename - Rename directory.
6. delete - Recursively delete the directory and its contents.
7. position noting - Ignore.


OK folks - how does this approach sound to you?
-- 
Kurt W. Hirchert     hirchert@ncsa.uiuc.edu
National Center for Supercomputing Applications