hardmath:
Here's a recollection about stack vs.
register
architectures.
Either someone was pulling your leg, or
your recall is imperfect. As the original B6500/B6700 architect, I would like
to correct some things.
In the mid-80s I worked at a mainframe shop
where my boss was one of the original Burroughs MCP
programmers.
(If you care to identify your ex-boss to me, you may
use the email address carefully encoded in my registration info: just click on
my user-id in the header of this comment.)
Burroughs used 'MCP' to denote
several different operating systems, or several architectures having radically
different architectures. The Small Systems, (B1700, etc) were bit-addressable,
variable-word-length, dynamically microprogrammed register-oriented machines.
The Medium Systems (B2500 thru B4800) were digit (4-bit) addressed,
COBOL-oriented, storage-to-storage, with both digit- and byte-oriented
instructions (later augmented with Fortran-oriented features, like an
accumulator). The 'Algol-based' architectures were the B5000 thru B7900 lines,
designed primarily to support the needs of Algol and Cobol, with threatening
gestures towards Simula I and PL/I (we never did a Simula I, since it was
superfluous as far as marketing was concerned). The B5000 thru B5900 were one
architecture; the B6500-B7900 were another, but designed for upward
compatibility from the B5000 line. I presume that your boss was speaking of one
or the other of the 'Large Systems' architectures.
The MCP
(Master
Control Program for you Tron fans) was written in a
dialect/extension of Algol,
and Algol is famous as a
programming language for having recursive
function
definitions, something we take for granted today.
After
the original B5000 MCP, written in an assembly language named OSIL, and the
B2500/B3500 MCP, written in its own assembly language, each MCP implementation
had its own Algolish language, named SPL, BPL, or Espol. Except for Espol, the
Algolishness was limited to notation: compound statements were delimited by
'BEGIN' and 'END', for instance.
The stack architecture of
Burroughs mainframes was a reflection of the stack architecture of the Algol
language.
No. The stack architecture was a choice, primarily to
support multiple processes and multiple processors, and secondarily to make the
MCP's and compilers' jobs easier.
Elegant stuff, but not the best
fit for the allocation of
random access memory/arrays. In Algol everything was
stack-
based, and if you wanted to allocate memory in a program,
into the stack
it went.
This is where you were misled.
I admit that one time,
in a bare-metal program, I tried that technique. I got away with it that time,
but would never do it again. (A later version of ESPOL, called NEWP, did have
the option of optimising some cases into stack allocation, but that was in the
late 1980s).
Because of Algol's dynamic array allocation requirements, from
the B5000 on, an array (memory area) was represented in the stack by a
single-word 'data area' token. Upon first access, the token was fondled by the
MCP in response to a 'Presence Bit' interrupt: it was changed from 'unaccessed'
to 'allocated', and filled in with the out-of-stack memory address of the
allocation. (Another interesting state of a data token is 'on-backing-store':
this causes another kind of Presence Bit interrupt, causing the data to be
retrieved into a freshly allocated area.).
The area could be resized or
deallocated in the expected way, by manipulating the token to match.
My
little bare-metal program did not need any resizing or reallocation: if it had,
I would not have used that technique. In the NEWP stack-allocated array case,
the compiler fudges a token, in the stack, that initially shows the data in the
stack area; if it is ever resized to outgrow the assigned space, the data is
moved into an off-stack memory space, with appropriate token
fudging.
In testing it out in our shop we found that C programs
compiled on for the mainframe ran orders of magnitude slower than they would on
a PC (say compiled with Borland's Turbo C). The reason is that almost all C
programs want to allocate memory for stuff at runtime, even simple stuff (I
recall a Towers of Hanoi demo or similar).
The real reason for the
poor performance of the original C releases had nothing to do with memory
allocation per se. The C language was optimized for a PDP-8 (for some
small integer value of 8): it makes heavy use of the characteristics of its
targeted architecture, like byte addressing, assuming adjacency of bytes, using
address values as data, and pre- and post-incrementing of memory-address
registers. The architecture it supports is a poor match for the Burroughs
Large-Systems architecture. The c-compiler folks did a reasonable job of
matching the flat-memory PDP model onto the highly solution-oriented, structured
model of the LSs.
The stack allocation proved to be the Achilles'
heel of the
C compiler, perhaps because "free" would involve some
stack
reshuffling operations which the Burroughs instruction set
was never meant
to "address".
Except that the c-compiler folks knew not to do it
that way, and they didn't. The stack reshuffling of which you speak was always
deemed to be too tough — too much work and too little reliability. The
big issues were the tokens in the stacks: tokens (many kinds, not just
data-area tokens) have absolute and/or stack-relative addresses in them, and
could exist in this stack (of course), in other stacks, and perhaps in
pseudostacks. Too many kinds, too many places to look, too hard to find
reliably.
Thus, the c-compiler folks used a heap: a data area with its token
in the stack, but the memory off the stack, with the standard complement of
alloc()s, realloc()s and suchlike functions in the support
library. The first cuts of the compiler showed that a lot of development was
still needed in faking PDP-8 characteristics in a structured architecture. I
understand that, by using a lot of cleverness, they were eventually able to get
acceptable performance. --- --Bill. NAL: question the answers,
especially mine. [ Reply to This | Parent | # ]
|