Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site harvard.UUCP
Path: utzoo!linus!decvax!genrad!panda!talcott!harvard!macrakis
From: macrakis@harvard.UUCP (Stavros Macrakis)
Newsgroups: net.emacs
Subject: Re: gnu design question
Message-ID: <573@harvard.UUCP>
Date: Tue, 31-Dec-85 14:35:52 EST
Article-I.D.: harvard.573
Posted: Tue Dec 31 14:35:52 1985
Date-Received: Wed, 1-Jan-86 05:13:27 EST
References: <21@cornell.UUCP> <22@cornell.UUCP>
Organization: Aiken Comp. Lab., Harvard
Lines: 84
Summary: Simple fast alloca for non-alloca machines

In article <21@cornell.UUCP>, jqj@bullwinkle writes:
> the alloca() routine ... is used heavily by GNU emacs....
> My alternatives seem to be:
>     1/	implement a full alloca() for the Gould.  ...
>     2/	recode entirely in C to eliminate the need for alloca()...
>    3/	Recode GNU emacs to do compile-time maximum-size array allocations... 
>    4/	Hack up the Gould C compiler to use a stack frame....
>    5/	Do something else entirely.  (e.g. use Hemlock?) ....
> 1/, 2/, or 3/ would each take, I estimate, less than a person-week to 
> program and debug.  4/ would take several person-months....

Why not the very simplest solution to alloca: a parallel stack for
alloca'd objects with Mark/Release?  This stack would have to be as
large as the total size of allocas alloc'able at one time.  In a
virtual memory system with large address space, there should be no
problem at all.  Part of the charm of a Mark/Release scheme (as of
regular alloca) is that it is robust: if a Release is `forgotten' via
some coding or timing error, the stack still gets cleaned up
eventually.

    #define Max_Total_Alloca 10000
    char linear_heap[Max_Total_Alloca];
    int linear_heap_pointer = Max_Total_Alloca;

Every routine that used alloca would have to include the Mark macro
among its declarations (of course, it doesn't hurt to have a Mark even
if there is no alloca within the routine):

    #define Mark char *Mark_point = linear_heap_pointer;

...and would release just before returning:

    #define Release linear_heap_pointer = Mark_point;

...for convenience:

    #define Return(x) {Release; return(x);}

Setjmp is slighly more complicated.  Ideally, the setjmp environment
should include the linear_heap_pointer.  If this cannot be
accomplished, then every statement that has a setjmp within it must
become:
    { Mark;
      ...  setjmp ...
      Release; }
Ideally, Setjmp would just be
    #define Setjmp (Mark, setjmp(x) + Release) 
but this won't work for two reasons:
  1. Mark declares a variable, and there can be no declarations within
     C statements; 
  2. the order of evaluation of f()+g() is undefined, and in
     particular on the Vax is the wrong way round.


The function alloca itself is very simple:

#define alloca(x) (Mark_point, _alloca(x))
/* Defined like this to give an error if Mark has not been used. */
char *_alloca(size)
  int size;
{ if ((linear_heap_pointer -= size) < 0) ...error...;
  return(&(linear_heap[linear_heap_pointer]));
}


Note that as a standard precaution the reset-world function should
reset the linear_heap_pointer.  So should the top-level loop.

Since there are only 46 alloca's and 6 setjmp's in all of gnumacs (and
several functions have several allocas), I estimate less than one
man-day to install this type of alloca.  Since I'm working on my
thesis, I am not volunteering (not to mention that my machine has
alloca!).

Note that there is no need to conditionalize the Mark/Return's in
implementations with regular alloca's, since you can just define them
to be null:
    #define Mark
On machines with regular alloca, the alloca macro as above can be
preserved to provide a compile-time error indication in case of
forgetting to use Mark.  Of course, this doesn't guarantee that
Release is used consistently.

	-s