decoration decoration
Stories

GROKLAW
When you want to know more...
decoration
For layout only
Home
Archives
Site Map
Search
About Groklaw
Awards
Legal Research
Timelines
ApplevSamsung
ApplevSamsung p.2
ArchiveExplorer
Autozone
Bilski
Cases
Cast: Lawyers
Comes v. MS
Contracts/Documents
Courts
DRM
Gordon v MS
GPL
Grokdoc
HTML How To
IPI v RH
IV v. Google
Legal Docs
Lodsys
MS Litigations
MSvB&N
News Picks
Novell v. MS
Novell-MS Deal
ODF/OOXML
OOXML Appeals
OraclevGoogle
Patents
ProjectMonterey
Psystar
Quote Database
Red Hat v SCO
Salus Book
SCEA v Hotz
SCO Appeals
SCO Bankruptcy
SCO Financials
SCO Overview
SCO v IBM
SCO v Novell
SCO:Soup2Nuts
SCOsource
Sean Daly
Software Patents
Switch to Linux
Transcripts
Unix Books

Gear

Groklaw Gear

Click here to send an email to the editor of this weblog.


You won't find me on Facebook


Donate

Donate Paypal


No Legal Advice

The information on Groklaw is not intended to constitute legal advice. While Mark is a lawyer and he has asked other lawyers and law students to contribute articles, all of these articles are offered to help educate, not to provide specific legal advice. They are not your lawyers.

Here's Groklaw's comments policy.


What's New

STORIES
No new stories

COMMENTS last 48 hrs
No new comments


Sponsors

Hosting:
hosted by ibiblio

On servers donated to ibiblio by AMD.

Webmaster
stack architecture | 225 comments | Create New Account
Comments belong to whoever posts them. Please notify us of inappropriate comments.
stack architecture
Authored by: complex_number on Thursday, May 10 2012 @ 04:23 PM EDT
After a few years of bit twiddling in the depths of PDP-11 Unibus systems and
their operating systems I changed jobs and started working on a project that
used Coral-66.

Everything was put on the stack. Performance was abysmal.
Memory usage was horrid.

I re-wrote a number of the most commonly used functions in PDP-11 Assembler and
made full use of the CPU registers. Everything ran a whole lot faster and the
memory footprint was reduced.
The same applied to the basic Fortran Compiler. It was all RPN structures on the
stack. The Fortran 4-Plus compiler cost a lot more but used the CPU registers
and the code was very nicely optimised.

Stacks have their uses but they can have a dramtatic effect on performance when
compared to Register Addressing and Arithmetic.


---
Ubuntu & 'apt-get' are not the answer to Life, The Universe & Everything which
is of course, "42" or is it 1.618?

[ Reply to This | Parent | # ]

Burroughs mainframes, stack architecture
Authored by: Anonymous on Thursday, May 10 2012 @ 09:52 PM EDT
C is not a high-level language. C is a portable assembler for register-based
machines with a linear byte-based addressing space.

It offers the smallest set of "high-level" capabilities of about
anything that was available back in the '70s. Additional stuff was plastered on
it (C++) to make it more like an HLL.

Its major positive contribution to Progress was portability. Much better than
anything before. Small enough to write compilers for. Standard enough for basic
interoperation. Byte addressing wasn't the only way back then; it now is (many
minicomputers used word (16-bit) addressing; try to port a C program to there).
And multibyte machine structures are a problem. But it kinda works and it was a
sea change.

Large Systems do not have a linear address space available to the programmer.
You talk about entities (with references on the stack) that are defined at some
lexical level (another language construct that C killed - PL/1 and Pascal have
it). And at the machine level, entities are 48 bits wide (plus a few tags). No,
there is no assembly language for the beast. Never was.

Talk about a mismatch! Trying to force C in that environment is a nightmare.
But it was done, and if presented with "well-written" C, it would
generate a pretty efficient program.

However, C programmers usually write things that can be expressed in that
language and would run efficiently on some specific machine (yep, it's an
assembler, after all). Even between two instruction sets, or two OSes, C would
give some compatibility, not much. That's why Java's "write once run
anywhere" became a successful mantra.

And so, the program you mention, which was conceived with a machine where
"malloc" is efficient in mind, did horrors on Large Systems C.

I once (1982?) was given a program for the IBM PC and asked to see if it would
run on a machine we were working on. The PC program was supposedly written in
BASIC. We had a full-language BASIC interpreter.

Problem was, the PC program started with a POKE instruction, copied a large set
of machine code at some address, then EXECed it.



YMMV


Bck not logged in

[ Reply to This | Parent | # ]

Burroughs mainframes, stack architecture
Authored by: bprice on Thursday, May 10 2012 @ 10:55 PM EDT
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 | # ]

Groklaw © Copyright 2003-2013 Pamela Jones.
All trademarks and copyrights on this page are owned by their respective owners.
Comments are owned by the individual posters.

PJ's articles are licensed under a Creative Commons License. ( Details )