Are yacc parsers portable ?
Naim Abdullah
question has been beaten to death here].
Is the C parser produced by yacc, portable ? I was looking at it and it had
stuff like:
yyparse() {
short yys[YYMAXDEPTH];
register short yystate, *yyps, yyn;
...
yyps= &yys[-1];
...
}
It seems to me that negative indices on arrays are probably not portable.
Is it really necessary for yacc to do these tricks, or can it produce
portable code that is just as efficient ? Is bison any better in this respect ?
Thank you.
Naim Abdullah
Dept. of EECS,
Northwestern University
Internet: na...@eecs.nwu.edu
Uucp: {oddjob, chinet, att}!nucsrl!naim
Scott Wilson
> Is Bison any better ...
My main complaint with Bison was that both the source for Bison (last I
looked) and the parser it produces rely on alloca - a method for allocating
space on the stack that is automatically reclaimed when the function
that calls it exits. Alloca is found on BSD derived systems and
I am told on other UNIX's. It, however, is less than universally
available (the manual page states: "alloca() is both machine- and
compiler-dependent; its use is discouraged"). I had a rather protected
mail war with several people associated with Bison and/or FSF regarding
this. My opinion was that FSF would be doing computer users a greater
service by writing more portable code when possible. The gist of the
replies I recieved was that it is "impossible" to write code that is worth
anything without taking advantage of nifty features like alloca. I
completely disagree.
Writing portable code is not easy. I would venture to suggest that
unportable code is much more often the result of laziness than lack
of efficiency of portable means. Even if efficiency is of paramount
importance it is still possible to structure the code for easy porting
in the future. As an example, in a recent piece of code I wrote I had
#ifdef vax, #ifdef sun, etc, with efficiency-minded machine-dependent
code and then for other machines I had machine-independent code.
Sure it makes the code look uglier, but it also meant the code ran
without change (albeit at less than greatest efficiency) on a Macintosh.
Scott Wilson
Jim Blandy
>Is the C parser produced by yacc, portable ? I was looking at it and it had
>stuff like:
> short yys[YYMAXDEPTH];
...
> yyps= &yys[-1];
>It seems to me that negative indices on arrays are probably not portable.
Yacc doesn't actually dereference this pointer; it only uses it to
initialize the stack pointer for its inc-push, pop-decr stack. yyps
will get used in a phrase like *++yyps = uhlrich to push uhlrich
onto the stack, and zwingli = *yyps-- to pop zwingli off.
Portable? ANSI says that that pointer is undefined, but I can't
imagine it ever causing any problems. Unless there is an architecture
where one can decriment a pointer, increment it, and not get the
original value back (I'd be surprised, but not terribly surprised),
it's plenty portable, since yacc never dereferences it.
They could use a push-inc decr-pop stack, for which the equivalent
initialization would be
yyps = yys;
which looks cleaner and <ahem> portabler. But the advantage to using
their approach is that yyps points AT the top item, not at the top
free space; this makes it easier to look at the top of the stack
without popping, which yacc does quite often.
Since the advent of LALR, parsing is cheap enough that it doesn't take
up much of the compiler's time anyway; I'd bet this doesn't make much
of a difference...
David DiGiacomo
>My main complaint with Bison was that both the source for Bison (last I
>looked) and the parser it produces rely on alloca - a method for allocating
>space on the stack that is automatically reclaimed when the function
>that calls it exits. Alloca is found on BSD derived systems and
>I am told on other UNIX's. It, however, is less than universally
>available (the manual page states: "alloca() is both machine- and
>compiler-dependent; its use is discouraged"). I had a rather protected
>mail war with several people associated with Bison and/or FSF regarding
>this. My opinion was that FSF would be doing computer users a greater
>service by writing more portable code when possible.
The FSF people aren't evil (?), they just disagree with the author of that
man page blurb about the usefulness and implementation difficulty of
alloca. By distributing excellent software which makes good use of
alloca, they are ensuring that all self-respecting C compiler/library
vendors will provide an efficient implementation of it. They even help
out the alloca-deprived by providing Doug Gwyn's malloc based alloca.
Seems reasonable to me!
--
David DiGiacomo, Sun Microsystems, Mt. View, CA sun!david da...@sun.com
Doug Gwyn
>The FSF people aren't evil (?), they just disagree with the author of that
>man page blurb about the usefulness and implementation difficulty of
>alloca. By distributing excellent software which makes good use of
>alloca, they are ensuring that all self-respecting C compiler/library
>vendors will provide an efficient implementation of it.
The C vendors aren't evil (?) either; requiring support for alloca()
does impose an undue burden on implementations on some architectures.
>They even help out the alloca-deprived by providing Doug Gwyn's malloc
>based alloca.
I provided that with the intention of helping people who had to import
existing code that relied on alloca(), not to encourage its use in new
code. In fact my emulation of alloca() can fail to reclaim free memory
under some unusal circumstances.
Please don't use alloca() in new code. Thanks.
Scott Wilson
>alloca, they are ensuring that all self-respecting C compiler/library
>vendors will provide an efficient implementation of it.
If alloca is such a wonderful function (and I'm NOT saying it isn't)
then why isn't it part of the ANSI draft proposed standard libraries
for C? Are you saying that a "self-respecting" C compiler/library
vendor will be doing users a disservice by providing only ANSI memory
routines (malloc, calloc, realloc, and free)? I would argue that it
is better to conform to a standard even with its shortcomings than
attempt to make something universal by "forcing" it on everyone.
--
Scott Wilson arpa: swi...@sun.com
Sun Microsystems uucp: ...!sun!swilson
Mt. View, CA
William Aitken
>
>The C vendors aren't evil (?) either; requiring support for alloca()
>does impose an undue burden on implementations on some architectures.
>
difficult to implement, and explain what it is that makes automatic
arrays possible, but alloca difficult? If C were to provide a means
to declare an automatic array with size that depended on an integer valued
argument, many of the uses of alloca would disappear; would this be any
easier to implement than alloca? Why?
---- Bill.
William E. Aitken <ait...@svax.cs.cornell.edu> (607)257-2542(h)
{uw-beaver,ihnp4,vax135,decvax}!cornell!aitken (607)255-4222(o)
ait...@crnlcs.BITNET 700 Warren Rd. #20-2A, Ithaca, NY
42 26'30" N 76 29'00" W 4148 Upson Hall
Paul Gluckauf Haahr
ait...@svax.cs.cornell.edu (William Aitken) writes:
> Could someone give a concrete example of an architecture on which alloca is
> difficult to implement, and explain what it is that makes automatic
> arrays possible, but alloca difficult?
in general, a compiler (rather, a run-time calling convention) that
does not use a register for the frame pointer (as opposed to a virtual
frame pointer) makes alloca() next to impossible.
alloca() counts on being able to munge the stack frame (by adding space
to it) without confusing the calling function. functions
index off their frame pointers to refer to local variables, parameters,
and the function return address. if the frame pointer is a real
register, there is no problem: alloca() can decrement (or, rarely,
increment) the stack pointer appropriately and the calling function
probably won't notice. but, as is more common with newer (RISC
influenced) compilers, the frame pointer is a virtual entity, really
just the stack pointer plus some offset: munging the stack pointer
confuses the calling function about where its locals, etc, are.
Gould machines (i've heard) make it difficult to do alloca(). the MIPS
R2000 normally uses a virtual frame pointer. various 68000 family
compilers (at least the GreenHills compiler and Ken Thompson's 2c) do
not use a register for a frame pointer, so they too probably have
trouble with alloca() in the general case. many of these compilers
have compile time options to force using a register as a real frame
pointer, in order to allow alloca() and other stack munging.
> If C were to provide a means
> to declare an automatic array with size that depended on an integer valued
> argument, many of the uses of alloca would disappear; would this be any
> easier to implement than alloca? Why?
yes, because that provides a way of telling the compiler that either it
needs a real frame pointer for some particular function, or at least that
some part of the stack frame is of variable length. the gnu c compiler
provides this functionality. not only is easier, but notationally it
is nicer, though not as general as alloca().
paul haahr
princeton!haahr or ha...@princeton.edu
David Keppel
The fast (compiler-supported) alloca may turn off other optmizations.
It need only turn them off in the function using alloca and (given
that memory management is often expensive) you aren't likely to lose a
whole lot by using alloca.
The slower (library-supported) alloca will break whenever you have a
multi-thread (e.g., lightweight process) program (at least in every
"reasonable" implementation that I've thought of). This may be a
problem for shared-memory multiprocessors.
During the last alloca war somebody suggested having alloca require
explicit "free" semantics, so that malloc-based (library) allocations
would be reasonable to write and work on shared-memory multiprocesors.
This would probably also hose fewer compilers/architectures. If I
understand, code would look like:
:
foo = alloca( size );
:
afree( size );
return( value );
This complicates the code slightly, but (I believe) would give
everybody "the best of both worlds". Does anybody object to these
semantics?
Note that GNU products are *not* designed to work on every machine.
The documentation for gcc (as I remember) says that it is designed to
work with 32-bit machines with a flat (non-segment-register) address
space. Alloca could be seen as a constraint on this. Finally, gcc
makes some extensions that can destroy alloca semantics; garbage
collection can (silently) take place before the end of the function,
so even their use is broke (and is documented as such).
[ Please, he said following up, try to keep down your
followup-rate. We just got done with this war a few weeks ago ]
;-D on ( What, me deallocate? ) Pardo
pa...@cs.washington.edu
{rutgers,cornell,ucsd,ubc-cs,tektronix}!uw-beaver!june!pardo
Karl Heuer
>In <82...@smoke.ARPA> gw...@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes:
>>The C vendors aren't evil (?) either; requiring support for alloca()
>>does impose an undue burden on implementations on some architectures.
>>
>Could someone give a concrete example of an architecture on which alloca is
>difficult to implement, and explain what it is that makes automatic
>arrays possible, but alloca difficult?
The AIX compiler on the IBM RT/PC. A single register is used for the stack
pointer, frame pointer, and arg pointer; the compiler generates appropriate
offsets based on its knowledge of the frame size%. If (as in the usual
implementation of alloca) you tried to change the frame pointer on the fly,
all hell would break lose.
My conclusion (I analyzed this problem when porting GNU Emacs&, which makes
heavy use of alloca) was that a proper alloca would have to be written as a
compiler builtin$. In this case the cost would be one extra register, in only
those functions that happen to use alloca. This doesn't seem like an undue
burden. I agree with the FSF on this one.
Karl W. Z. Heuer (ima!haddock!karl or ka...@haddock.isc.com), The Walking Lint
________
% The frame size depends on the number of registers used by the current
routine, the number of automatic variables, and the number of arguments
passed to subroutines, but is independent of the number of arguments passed
to the routine itself. Thus variadic functions work too.
& Sorry, I'm no longer providing the Emacs diffs. They're outdated.
$ I could almost have done it by postprocessing the .s file, but I couldn't
find a way to get the compiler to not use all the registers.
Robert Firth
>Could someone give a concrete example of an architecture on which alloca is
>difficult to implement, and explain what it is that makes automatic
>arrays possible, but alloca difficult? If C were to provide a means
>to declare an automatic array with size that depended on an integer valued
>argument, many of the uses of alloca would disappear; would this be any
>easier to implement than alloca? Why?
First, recall that "alloca" claims a chunk of local stack space, of size
unknown at compile time. It is therefore almost the same as being able
to declare a local array
int myarray[expression()]
whose size is likewise dynamic. The implementation difficulty is almost
the same. C local arrays, by contrast, have a size known at compile time,
and so are a lot easier to deal with.
There are two problems. Neither is really major, but they're there.
First, what happens if you have an inner declaration after the allocation:
int myarray[...]; /* array of dynamic size */
...
{
int i,j;
}
If you observe strict stack allocation (LIFO) semantics, then I and J are
at an offset from the start of the stack frame that you can't compute. So
you have to "float" inner declarations above the dynamic declaration, which
makes life tough for one-pass guys. (If you declare an inner variable
after calling alloca you'll probably discover another reason why it's a
bad idea to use alloca!)
The second problem is that, if the size of a local stack frame is dynamic,
you cannot get away with having just a frame pointer; you MUST have a stack
front pointer. That can add substantially to the cost of a procedure call;
moreover, it probably adds to the cost of ALL procedure calls. That means
you probably can't have the caller adjust the stack, which blows away the
optimisation of eliding stack adjustments between successive calls, and
so compounds the inefficiency.
On the majority of machines I've written codegenerators for, there is a
cost in going from a stack regime where all sizes are known at compile
time, to one where they aren't. It seems to me pretty silly to force
every C user to pay that price for the sake of the few who regard writing
portable code as beneath their dignity.
So, do I have an alternative? The only serious reason for allocating
dynamic objects on the local stack is to ensure their automatic deallocation
on scope exit; most C dynamic storage libraries are pretty efficient. This
seems to me largely a matter of programmer convenience, which could
perhaps be served almost as well by an auxiliary stack managed explicitly.
We initialize this by something like
createaux(size)
which does a malloc() to get the stack and sets up a stack pointer.
We claim by allocaux(size), which grabs a chunk. We manage scopes
explicitly by
{
m = markaux(); /* grab current aux stack pointer */
... /* code that does a lot of allocaux() calls */
resetaux(m); /* reset aux stack pointer */
}
So the programmer has to remember to set a Mark at the beginning of the
scope and to do a Reset at the end of the scope. And, of course, not to
jump out of the scope!
Finally, there is an ALMOST safe way to do without the Mark/Reset
discipline. Give each allocated chunk a header and store in it the
value of the caller's stack pointer. On an allocate, first deallocate
all chunks whose stored stack pointer is "below" the stack pointer of
the current caller - those chunks must have passed out of scope.
(I used this technique to implement Algol-60 local arrays; this was
completely safe rather than "almost" safe, since the compiler could pass
down to the allocator enough contextual information)
Finally, the old BCPL library had a strange function that was a lot
easier than alloca and allowed you to claim one (or at most a very
few) chunks of stack space. It is called aptovec, and is rather like
this:
int aptovec( f, s )
/* whatever says f takes (*int,int) and returns int */
int s;
{
int myarray[s];
return f(&a[0],s);
}
The body is a hairy piece of machine code that achieves the above effect,
including allocation and deallocation of the dynamic array.
Hope this helps.
Doug Gwyn
- foo = alloca( size );
- :
- afree( size );
- return( value );
-Does anybody object to these semantics?
Yes, I object very much. If you're going to do that, just use
malloc()/free(), which are universally available.
Jeff Barr
Correct me if I'm wrong. The benefits of alloca() over malloc() are:
(1) There is no need for the program to explicitly free the storage
allocated via alloca(), as the free() is implicit at the end of the
scope which encloses the alloca call. (Actually implemented by
adjusting the frame pointer at the end of the scope in a true
alloca implementation.)
(2) The memory arena used by malloc() is not referenced by alloca (),
bypassing any possible fragmentation problems.
--
Jeff
+---------------------------------------------------------+
| Jeff Barr AMS-DSG uunet!amsdsg!jeff 800-832-8668 |
+---------------------------------------------------------+
David Dyer-Bennet
$ During the last alloca war somebody suggested having alloca require
$ explicit "free" semantics, so that malloc-based (library) allocations
$ would be reasonable to write and work on shared-memory multiprocesors.
$ This would probably also hose fewer compilers/architectures. If I
$ understand, code would look like:
$ :
$ foo = alloca( size );
$ :
$ afree( size );
$ return( value );
$ This complicates the code slightly, but (I believe) would give
$ everybody "the best of both worlds". Does anybody object to these
$ semantics?
Well, the reasons why alloca is difficult to implement seem convincing.
However, the only point I ever saw to alloca was the automatic deallocation
on exit. If you don't have that, what advantage is there over malloc or
any of the standard allocation routines?
--
-- David Dyer-Bennet
...!{rutgers!dayton | amdahl!ems | uunet!rosevax}!umn-cs!ns!ddb
d...@Lynx.MN.Org, ...{amdahl,hpda}!bungia!viper!ddb
Fidonet 1:282/341.0, (612) 721-8967 hst/2400/1200/300
David Keppel
> foo = alloc(); ... afree(foo);
Karl Haddock pointed out that afree's will not be called for any
frames whose scope is left by longjmp() of a dynamically included
(child) function. Oh well, it seemed like a good idea at the time.
Sorry for the bandwidth.
;-D on ( Memory obfuscation/deallafreeing ) Pardo
Rahul Dhesi
vendors will provide an efficient implementation of it.
The original Rationale for the design of Ada implied that the usual
mechanism for deallocating dynamically-allocated memory for a given
pointer type would be the following: All allocated memory would be
recovered when the block containing the definition of the pointer was
exited. To help this, there was a pragma that allowed the programmer
to specify how many units of memory would be needed for that pointer
type.
This sounds like exactly the type of thing alloca is good for. So I
don't think the FSF people are doing something that nobody else thought
was a good idea.
--
Rahul Dhesi UUCP: <backbones>!{iuvax,pur-ee,uunet}!bsu-cs!dhesi
Scott Wilson
was in response to the portability issue, so let me see if we
agree on this:
1.) Code that, in general, makes use of features that are less available
than others is, in general, less portable.
2.) Alloca is less available than malloc/free.
3.) Therefore, all other things equal, code that uses alloca is less
portable than code that doesn't.
Does this make sense?
--
Scott Wilson arpa: swi...@sun.com "Why do dogs lick
Sun Microsystems uucp: ...!sun!swilson their balls? Because
Mt. View, CA they can!"
hjm
Two points about alloca:
- not knowing the size of the stack frames is a big pain on a non-virtual
memory machine. If a program is non-recursive, then it possible to
calculate at compile time the maximum stack usage and allocate just that
space for the stack in a multi-tasking system, minimising memory usage
and avoiding the need for stack relocation or extension.
- why have two mechanisms for memory allocation when one will do? malloc()
is perfectly adequate in that it gives you the memory you require when
you require it (if it's available) and free() lets you give it back when
you want to. Simple to implement portably, and easy to understand. If
you find it difficult to remember to give back memory at the end of a
function then why not have a function which does the following:
alloc_and_call (func, size) void (*func)(); int size;
{
char *p;
p = malloc(size);
func(p);
free(p);
}
OK, so that's not perfect. Parameter passing is a problem, but just a
small part to add on. Portable code for those people who can't remember
to deallocate stuff they asked for.
When physical memory gets tight, how do you propose that malloc and
alloca should talk to each other so that they don't tread on each other's
toes?
As a general principle, I would advocate one method for doing something rather
than two if there is any choice at all. Uniformity is something that aids
thinking and allows people to solve the real problems of writing the code to
do the job, and not to waste time wondering "should I use malloc or alloca".
Hubert Matthews
Walter Bright
1. Automatic variables must be implemented using a frame pointer
register rather than offsets from the stack register.
2. Functions containing alloca() must have a stack frame (this is
a problem because many compilers generate a stack frame only
if there are non-register automatics).
3. Evaluation of arguments becomes a problem if the code generator
uses the stack, as in:
func(1,2,3,4,5,p=alloca(10),6,7,8,9,10);
(On some implementations of alloca() that I've seen, the above
will cause a program crash.)
4. If the code generator uses the stack to store temporary results
when it runs out of registers, alloca() can cause it to lose
it's place.
Of course, alloca() could be implemented by having the compiler recognize
it and then modify the behavior of the code generator. This seems like a
lot of implementation effort for a minor return, however.
Dave Jones
>
> Well, the reasons why alloca is difficult to implement seem convincing.
> However, the only point I ever saw to alloca was the automatic deallocation
> on exit. If you don't have that, what advantage is there over malloc or
> any of the standard allocation routines?
>
Speed. The malloc() on in Sun3 OS, for example, is incredibly slow
after a few thousand blocks have been allocated. As has been pointed
out, a memory allocation package built on a separate stack could
be used. (But then you miss the automatic deallocation, of course.)
-- djones
Charles Marslett
> >
> >The C vendors aren't evil (?) either; requiring support for alloca()
> >does impose an undue burden on implementations on some architectures.
> >
> Could someone give a concrete example of an architecture on which alloca is
> difficult to implement, and explain what it is that makes automatic
> arrays possible, but alloca difficult?
The only reasonable way to allocate a variable amount of space from the
stack is to maintain a register (or local memory cell) containing the
size or end of the allocated space -- on some computers this is provided
"free of charge" by the architecture (so we use it) and on others it
imposes overhead on subroutine call/return linkage, usually serious only
for very short routines (and we do not use it).
A second and much more serious problem is that many of us are forced to
use Intel based boxes with 64K stacks and code using alloca() often
allocates too much local memory. Malloc() on the other hand can always
allocate 64K per chunk and often (MSC under DOS for example) can allocate
any size up to the hardware available. Of course, sloppy programmers then
have to remember to free what they allocated -- I find this can help document
the routine as well (named braces would help even more, oh well . . .).
> ... If C were to provide a means
> to declare an automatic array with size that depended on an integer valued
> argument, many of the uses of alloca would disappear; would this be any
> easier to implement than alloca? Why?
See comments above: both problems would remain (except that a mechanism
could probably be built into Intel C compilers to allcoate arrays off a
second "software" stack -- compilers for the 6502 often do this).
Does anyone know of an alloca() implementation that works this way -- other
than Doug Gwen's (and I would like to see it as well).
> ---- Bill.
> William E. Aitken <ait...@svax.cs.cornell.edu> (607)257-2542(h)
> {uw-beaver,ihnp4,vax135,decvax}!cornell!aitken (607)255-4222(o)
> ait...@crnlcs.BITNET 700 Warren Rd. #20-2A, Ithaca, NY
> 42 26'30" N 76 29'00" W 4148 Upson Hall
Charles Marslett
ch...@killer.dallas.tx.us
STB Systems, Inc.
(2140 234-8750
Michael
>
>
>My main complaint with Bison was that both the source for Bison (last I
>looked) and the parser it produces rely on alloca - a method for allocating
>
>compiler-dependent; its use is discouraged"). I had a rather protected
>
>anything without taking advantage of nifty features like alloca. I
>completely disagree.
Actually, alloca() isn't that big of a problem. Annoyance, yes, but you
can get a PD version of alloca that is nearly identical and 98%+ portable,
and I've seen completely compatible subroutines for ibm's, 68K's, pdp's, etc.
What really gets me in all the FSF software I've looked at is...
"Memory is cheap, and always will be. If they don't have at least 8 megs
of virtual space with reasonable performace times, they don't count".
The C compiler takes 500K+
====
The C preprocessor takes up rediculous amounts of memory (200K+) for something
the standard preprocessor does in 50K. Why?
They want to keep everything in memory.
They want to keep everything in memory.
And, they want to keep everything in memory.
(As in: Well, we need 2 more bytes of memory, so call realloc(). Realloc()
cant get it from free space, so call sbrk() for the full amount, then
copy it there. Repeat as needed.).
Of course, it does have some benefits. You can preprocess the recursion
winner of the C contest in finite time.
: ---
: Michael Gersten uunet.uu.net!denwa!stb!michael
: sdcsvax!crash!gryphon!denwa!stb!michael
: What would have happened if we had lost World War 2. Well, the west coast
: would be owned by Japan, we would all be driving foreign cars, hmm...
Greg Onufer
> 1.) Code that, in general, makes use of features that are less available
> than others is, in general, less portable.
code. Makes extensive use of alloca. Works on quite a few machines too,
I'd say.
> 2.) Alloca is less available than malloc/free.
On a M68k with a decent OS, alloca is not more than a few lines of assembly
code, correct? (Judging by the size of the GNU assembly alloca)...
If one needs alloca and it is not available, why not write a quick alloca?
If the machine architecture or OS is braindamaged, then one would have
to program around it. GNU does that also.
> 3.) Therefore, all other things equal, code that uses alloca is less
> portable than code that doesn't.
Not if the programmer cares that extra little bit.
> Does this make sense?
Does it?
-Greg
--
Greg Onufer GEnie: G.ONUFER University of the Pacific
UUCP: -= Focus Semiconductor =-
exodus@mfgfoc ...!sun!daver!mfgfoc!exodus (and postmaster/exo...@uop.edu)
AT&T: 415-965-0604 USMAIL: #901 1929 Crisanto Ave, Mtn View, CA 94040
Scott Wilson
>On a M68k with a decent OS, alloca is not more than a few lines of assembly
>code, correct? (Judging by the size of the GNU assembly alloca)...
>If one needs alloca and it is not available, why not write a quick alloca?
This makes about as much sense as saying: If your in Tokyo and need
to get to the airport just ask directions. It's only one sentence, how
hard can that be? Well if you don't know the language it's probably
pretty damn hard. I would guess the same is true about writing m68k
code, if you don't know how it doesn't matter if it is just a few lines.
Ok, so I need to write alloca, so let's see I brush up on m68k, buy the
book if necessary, understand the calling convention and stack frame
stuff for my compiler, figure out if my programming environment has
an easy way to get assembler in, understand the particular enviroment's
assembler syntax, etc. Gee that should only take 10-15 minutes. We're
talking about C here, I think it's unreasonable to expect a programmer
to have any knowledge of assembly code to port a program. What may
seem like a simple exercise to you and others may be a major chore
for me and others. And after all the debate on here about alloca
implementation difficulties, I would be hesitant to try it on a cpu that
it hasn't already been done for in fear that it be impossible. And what
if I'm not running on a 68k? C runs under many OS's and many cpu's some
you've never heard of. I've written C code for a TP1 running MOST, how
do I do alloca there? The best assembler manual for it is in Japanese.
It took me quite a while to write setjmp/longjmp for this beast, it would
be just as much of a hassle to write alloca. Isn't that what languages like
C are all about, so I don't have to know assembly language?
Again let me say that this whole discussion started with regard to
portability. Your solution is to add machine dependent code to a
program to make it work. So how does that help future portability?
It doesn't of course.
--
Scott Wilson arpa: swi...@sun.com
Gordon Burditt
> On a M68k with a decent OS, alloca is not more than a few lines of assembly
> code, correct? (Judging by the size of the GNU assembly alloca)...
> If one needs alloca and it is not available, why not write a quick alloca?
> If the machine architecture or OS is braindamaged, then one would have
> to program around it. GNU does that also.
If the compiler knows about alloca [Read: recognizes the name as special
and refrains from doing certain things because of it, OR recognizes the name
as special and implements it as a built-in], , it could be made to work
nicely. If the compiler doesn't know about alloca you can have a real
headache trying to implement it as it was intended (memory on the stack
frame), even with a "nice" CPU.
Further, even with the ultimate alloca implementation, GNU GCC with
alloca built into the compiler, it still gets it wrong.
Take, for example, the following 68000 linkage conventions:
d0-d1, a0-a1 are clobbered across calls. d2-d7, a2-a5 are preserved across
calls. a6 is the frame pointer. a7 is the stack pointer. Args are
on the stack, first arg at the lowest address. CALLER POPS ARGS FROM THE
STACK. Function return value is in d0 or d0/d1 (for doubles).
These are not negotiable, unless I scrap all my libraries and the compiler
that came with the system, and actually seem fairly reasonable. These are
used on Tandy's 68k Xenix compiler, and some other systems, like the sun
(2 and/or 3) version of the GNU compiler, which I have adapted to also
work on a Tandy 6000.
Ok, so alloca should be simple, right?
- Leave a2-a6 and d2-d7 alone, so you don't have to save them.
- Pop the return address into a register (a0 probably). [1 instruction]
- Pick up the requested amount of memory and round it up to
a multiple of 2. [2-3 instructions]
- Subtract the rounded amount of memory from the stack pointer.
[1 instruction]
- Put the stack pointer + the size of the argument ( = 4) in d0
(because the caller is going to adjust the stack to remove
that argument). [1-2 instructions]
- Return to the saved return address. [1 instruction]
[Nitpickers: I really don't care if I'm one or two instructions off in the
above estimates]
Simple, huh? So how come bison infinite loops?
Typical function entry/exit code for Tandy's compiler:
.globl _foo
_foo:
link a6,#-<stack frame size>
moveml #<<bunch of registers>>,-(a7)
...
moveml (a7)+,#<<bunch of registers>> | AARRRGGGGHHHH!!!!
unlk a6
rts
The "bunch of registers" is determined from what is actually used. There
are variations of this code if 0 or 1 registers need to be saved.
Notice the instruction marked "AARRRGGGGHHHH". If alloca moves the stack
pointer, then it has to allocate some extra memory and leave a copy of the
saved registers in them, so this instruction can pop them off. (Why didn't
the compiler writer use "moveml <offset>(a6),#<bunch of registers>" instead?
I don't care, really, but it might be because the code it actually generates
is 2 bytes shorter (and 1 clock cycle faster on a 68020).) So, my first shot
at alloca trashes all of the registers in the caller of the caller of alloca.
Ok, how much memory? 40 bytes (d2-d7 and a2-a5), regardless of whether the
function actually saves them or not. Why not find out what's actually saved?
To do this, you'd need to find the entry point of the function and disassemble
a few instructions. The frame pointer points to the return point in the
caller of the caller of alloca. However, in 68000 code, given the address
of the end of an instruction and the contents of memory, you cannot always
uniquely find the address of the beginning of it. (Ok, maybe 99% of the time
you can, but having any need for a "panic: alloca can't find it's caller -
program aborted" message is unacceptable). Besides, if the caller of alloca
was called through a function pointer (I DID NOT say alloca was called through
a function pointer! although that wouldn't matter much anyway), the address
might be and usually is in a0, and has been destroyed before alloca is called.
Now, on to another issue: function calls and arguments. Assume that the
compiler has a maximum of N temporary locations in registers to store
computed arguments that haven't been pushed on the stack yet. (Suppose for
this example that N = 2). Assume that the compiler pushes its arguments onto
the stack in an endian order (I did NOT say which end!). The arguments and
return types of foo and bar are (char *), and bar returns its first argument.
How does the compiler evaluate this (foo is presumed to have 2N+3 arguments):
foo(bar(alloca(20)), bar(alloca(20)), bar(alloca(20)), alloca(40),
bar(alloca(20)), bar(alloca(20)), bar(alloca(20)) );
Can anyone find ANY compiler on a system with caller-pops-args linkage
conventions that gets this right? Or for that matter, any compiler on
ANY system where alloca really allocates memory on the stack?
To correctly evaluate this, the compiler would have to evaluate
"bar(alloca(20))" 3 times, store the results somewhere other than pushing
on the stack, and since it has only 2 registers, one of them has to be
elsewhere (stack frame relative temporary seems to be the only place left),
evaluate alloca(40), at which point it had better not have pushed anything on
the stack, and then evaluate "bar(alloca(20))" 3 more times. THEN it fetches
the 7 values from assorted storage and pushes them on the stack.
Now, consider a compiler that doesn't know alloca is special. Can you
imagine the laughter if it always generated the above sequence for
every function, alloca or not? Storing stuff on the stack frame, then
copying it with a push-contents-of-memory-on-stack instruction? Inefficient
code in the extreme ... .
What it's really going to do is evaluate "bar(alloca(20))", push the result on
the stack, repeat 2 more times, evaluate "alloca(40)", push the result on
the stack, and repeat evaluating and pushing "bar(alloca(20))" 3 times.
foo() will then be called with all but the last-pushed argument in the wrong
place. This is, in fact, how gcc 1.24 evaluates it, WITH AND WITHOUT
using the builtin alloca. With the builtin and without the optimizer, the
alloca() becomes 2 instructions (fix stack and move return value to d0).
The round-up-to-multiple-of-2 gets done at compile time since the arguments
to the alloca calls were constant.
Consider the GNU compiler feature "defer-pop". If a compiler defers
taking arguments off the stack after a function call, and doesn't recognize
alloca as a clue to turn off this behavior, and there is no flag to
control it, then I have to throw up my hands and abandon any attempt to
write alloca. Supposedly GCC does recognize alloca as special for this
purpose, and in any case, it has flags to control it.
Back to my Tandy 68k machine. To accomodate the args-on-the-stack problem,
I have to make alloca copy more of the stack frame to handle the worst-case
of args pushed on the stack when it's called. There is no worst-case, but 5
args ( = 20 more bytes) might be good enough.
I got lucky. Tandy's compiler references auto variables relative to the
stack frame pointer. If it referenced them relative to the stack pointer,
I'd be out of luck.
So now it works like this:
- Leave a2-a6 and d2-d7 alone, so you don't have to save them.
- Pop the return address into a register (a0 probably). [1 instruction]
- Pick up the requested amount of memory and round it up to
a multiple of 2, and add 60. [2-3 instructions]
- Subtract the rounded amount of memory from the stack pointer.
[1 instruction]
- Copy 60 bytes from the old stack pointer + 4 to the new stack
pointer + 4 for length 60. [15 instructions, straightline.
Could be less but slower with a loop]
- Put the stack pointer + the size of the argument plus the
copied stack ( = 64) in d0 (because the caller is going to adjust
the stack to remove that argument). [1-2 instructions]
- Return to the saved return address. [1 instruction]
So I have a version of alloca that allocates its memory on the stack frame
and wastes 60 bytes per call. If a compiler uses defer-pop, it's
going to screw up. If there are more than 5 arguments on the stack when
it's called, it's going to screw up. But bison doesn't infinite loop
any more.
Why don't I post it? Several reasons:
- It's too compiler- and system- specific to be of much use to many people.
- The waste of memory per call is embarrasing.
- It was debugged using bison, and according to discussions going on in
gnu.gcc, it is probably subject to the GNU Public License, and I'd have to
post the source to everything I used it in. I don't have that much disk
space, and neither does the net.
- It still doesn't work right, in ways I indicated.
Gordon L. Burditt
killer!ninja!sneaky!gordon
Henry Spencer
>Speed. The malloc() on in Sun3 OS, for example, is incredibly slow
This just says that whoever wrote Sun's malloc was incompetent. There is
nothing inherently hard about writing a fast malloc, although it's not
simple, especially for widely-diversified needs.
--
MSDOS is not dead, it just | Henry Spencer at U of Toronto Zoology
smells that way. | uunet!attcan!utzoo!henry he...@zoo.toronto.edu
Rob McMahon
>Actually, alloca() isn't that big of a problem. Annoyance, yes, but you
>can get a PD version of alloca that is nearly identical and 98%+ portable,
>and I've seen completely compatible subroutines for ibm's, 68K's, pdp's, etc.
If this is the same alloca() that Gould supply with their Unix, UTX-32, it has
big problems with the GNU software. When you call this version, it frees any
memory that was allocated from further up the stack. Quite often, though, it
is called repeatedly at the same level, and the memory is never freed, as in:
for (long loop) {
...
func ();
}
func ()
{
alloca (much memory);
...
}
Compiling the gcc parser using this alloca, the compiler ran out of swap space
space and died. (We had ~40M swap space, and there was one other large (10M)
job running and not much else.)
Rob
--
UUCP: ...!mcvax!ukc!warwick!cudcv PHONE: +44 203 523037
JANET: cu...@uk.ac.warwick ARPA: cu...@warwick.ac.uk
Rob McMahon, Computing Services, Warwick University, Coventry CV4 7AL, England
Stan Friesen
>> any of the standard allocation routines?
>
>Speed. The malloc() on in Sun3 OS, for example, is incredibly slow
>after a few thousand blocks have been allocated.
Indeed, and not just on Suns either. A similar thing happened to
me on a Convergent. In fact it eventually got sooo slow that our customers
complained! (Luckily the large number of allocations was unnecessary, the
code was not freeing a message block, so it was easy to fix by just adding
a free() after the message was displayed. But still a 10-20 fold increase in
speed *just* by adding one free!!)
--
Sarima Cardolandion sar...@gryphon.CTS.COM
aka Stanley Friesen rutgers!marque!gryphon!sarima
Sherman Oaks, CA
Chris Torek
>>The malloc() on in Sun3 OS, for example, is incredibly slow
>>after a few thousand blocks have been allocated...
In article <1988Aug7.0...@utzoo.uucp> he...@utzoo.uucp (Henry Spencer)
answers:
>This just says that whoever wrote Sun's malloc was incompetent. There is
>nothing inherently hard about writing a fast malloc, although it's not
>simple, especially for widely-diversified needs.
To be fair to Sun, consider their environment: They are running large
virtual memory systems (`bloated VAX-spawned code' :-) ) on machines
with small virtual memories (backing stores). If you have only 8MB of
swap space, you will want to conserve it. One way to conserve memory
is to trade speed for space, which is what was done in their malloc().
(Of course, shared libraries and memory could help immensely, given that
part of the reason for the bloat in SunOS programs is the enormous size
of the window system. How much difference it really makes in SunOS 4.x
have yet to see for myself.)
--
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain: ch...@mimsy.umd.edu Path: uunet!mimsy!chris
braner
In several implementations I have seen, and one that I have written
myself, there are two malloc()s. A slow "system-malloc" that is designed
for allocating space for programs about to be run, etc, and a fast
"library-malloc" that is actually called when you say "malloc()" in
your program. The system malloc may be slow because it is built to
be bomb-proof. (Still can be not very slow.) The library malloc
calls the system malloc (actually called SBRK or whatever) only when
necessary, and then allocates a rather large chunk (say 8K minimum).
Then the library function (which is internal to the process, since it
was linked to the program from a library archive!) doles out little pieces
of it for each malloc() call. Upon free(), the little (or big) piece
is returned to the locally-managed pool but NOT to the system. Upon
exit() everything is (or should be) returned to the system. Since the
library malloc does not need to keep tables of who owns which block,
and can keep control info in the blocks, it can be rather fast. One
I wrote (adapted from the example in K&R, with various sanity checks
added and only 6 bytes average overhead per block) takes about 150 microsecs.
(That's on a 15 MHz T414 transputer, roughly equivalent to a 68020.)
(And it's written in C :-)
- Moshe Braner
PS: the only fair way to benchmark a function is to time the complete
"y = f(x)" operation, so it includes the assignment and the function
calling overhead.
Greg Onufer
> In article <3...@mfgfoc.UUCP> exo...@mfgfoc.UUCP I write:
>>On a M68k with a decent OS, alloca is not more than a few lines of assembly
>>code, correct? (Judging by the size of the GNU assembly alloca)...
>>If one needs alloca and it is not available, why not write a quick alloca?
> Again let me say that this whole discussion started with regard to
> portability. Your solution is to add machine dependent code to a
> program to make it work. So how does that help future portability?
> It doesn't of course.
Repeat this ten times:
Good C programmers should always know the output of their compiler!!!
And I tried to emphasize the GNU code.... It does it--- portable too.
And if you look at the GNU code (and I think _everybody_ should have copies
of some of the important C files in both Emacs and Gnu C), there _IS_
a portable implementation that works on machines which could not
reasonably be asked to support proper alloca functionality. It does
require one to call alloca with a argument of zero to clear free up the
allocated memory (making it no better than malloc, essentially).
This is an example where one could learn from someone else's code.
I'd say GnuEmacs and Gnu C are very excellent sources of education on
portable program writing.
> Scott Wilson arpa: swi...@sun.com
Shankar Unni
^^^^^^^^^
> mail war with several people associated with Bison and/or FSF regarding
> this.
Protected? By an asbestos suit, maybe? :-)
("The flames! The flames! Aaaarrgh! (Gasp!)")
--
Shankar.
Dave Brower
>In <6...@goofy.megatest.UUCP> djo...@megatest.UUCP (Dave Jones) writes:
>>Speed. The malloc() on in Sun3 OS, for example, is incredibly slow
>>after a few thousand blocks have been allocated...
>
>This just says that whoever wrote Sun's malloc was incompetent. There is
>nothing inherently hard about writing a fast malloc, although it's not
>simple, especially for widely-diversified needs.
Don't you just love the way the electronic communication helps make
generally reasonable people offensive? It's more than a bit out of line
to say the Sun programmer is incompetant. It isn't simple making the
tradoffs inherent in an allocator. I've never seen a one that would
satisfy all desirable criteria for all clients, because the requirements
are completely program specific.
There are at least four dimensions to the allocator problem:
(1) Time to get a block.
(2) Run size of the program (swap space).
(3) Fragmentation, and what is does to (1) and (2).
(4) Time to release a block, and what that does to (2) and (3).
No one algorithm is ever going to be optimal in all cases. The stack
based alloca is nearly ideal for allocating large numbers of small
easily disposed objects. Malloc and friends are better for smaller
numbers of probably larger objects. Sbrk with +/- increments is more
for getting and releasing small numbers of large objects.
There is no one correct answer. "Incompetence" is a unfairly glib way
of saying that one perfectly valid implementation isn't the one that
would be best for a particular application.
-dB
"Ready when you are Raoul!"
{amdahl, cpsc6a, mtxinu, sun, hoptoad}!rtech!daveb da...@rtech.com <- FINALLY!
Michael Meissner
| If alloca is such a wonderful function (and I'm NOT saying it isn't)
| then why isn't it part of the ANSI draft proposed standard libraries
| for C? Are you saying that a "self-respecting" C compiler/library
| vendor will be doing users a disservice by providing only ANSI memory
| routines (malloc, calloc, realloc, and free)? I would argue that it
| is better to conform to a standard even with its shortcomings than
| attempt to make something universal by "forcing" it on everyone.
It was proposed to the ANSI committee, and it got shot down, for two reasons:
1) it was judged to be too late; 2) the systems don't have frame pointers
on their stacks would have to recognize it as a builtin and support it
through some method.
--
Michael Meissner, Data General.
Uucp: ...!mcnc!rti!xyzzy!meissner
Arpa: meis...@dg-rtp.DG.COM (or) meissner%dg-rtp...@relay.cs.net
Henry Spencer
>Don't you just love the way the electronic communication helps make
>generally reasonable people offensive? It's more than a bit out of line
Who, me, offensive? Nah. :-)
On the contrary, it is quite in line to say that some Sun programmers are
incompetent; this is an established fact. (Some others are highly competent,
but unfortunately they're not the whole story.)
>There is no one correct answer. "Incompetence" is a unfairly glib way
>of saying that one perfectly valid implementation isn't the one that
>would be best for a particular application.
Well, no, actually it was a shorthand way of saying that while this *might*
be a case of implementation-application mismatch, it is much more likely
that it's a case of programmer incompetence, or at least deliberate disregard
of performance issues (which appears to be a widespread disease at Sun).
--
Intel CPUs are not defective, | Henry Spencer at U of Toronto Zoology
they just act that way. | uunet!attcan!utzoo!henry he...@zoo.toronto.edu