[TUHS] Early Unix function calls: expensive?

[TUHS] Early Unix function calls: expensive?

[Warren Toomey]

I just re-found a quote about Unix processes that I'd "lost". It's by
Steve Johnson:

    Dennis Ritchie encouraged modularity by telling all and sundry that
    function calls were really, really cheap in C. Everybody started
    writing small functions and modularizing. Years later we found out
    that function calls were still expensive on the PDP-11, and VAX code
    was often spending 50% of its time in the CALLS instruction. Dennis
    had lied to us! But it was too late; we were all hooked...
    http://www.catb.org/esr/writings/taoup/html/modularitychapter.html

Steve, can you recollect when you said this, was it just a quote for
Eric's book or did it come from elsewhere?

Does anybodu have a measure of the expense of function calls under Unix
on either platform?

Cheers, Warren

[TUHS] Early Unix function calls: expensive?

[Tim Bradshaw]

> On 3 Jan 2016, at 23:35, Warren Toomey <wkt at tuhs.org> wrote:
> 
> Does anybodu have a measure of the expense of function calls under Unix
> on either platform?
> 

I don't have the reference to hand, but one of the things Lisp implementations (probably Franz Lisp in particular) did on the VAX was not to use CALLS: they could do this because they didn't need to interoperate with C except at known points (where they would use the C calling conventions).  This change made a really significant difference to function call performance and meant that on call-heavy code Lisp was often very competitive with C.

I can look up the reference (or, really, ask someone who remembers).

The VAX architecture and its performance horrors must have killed DEC, I guess.

[TUHS] Early Unix function calls: expensive?

[John Cowan]

Warren Toomey scripsit:

>      VAX code was often spending 50% of its time in the CALLS
>      instruction.

From what I understand, the use of CALLS was abandoned on the VAX
at some point in favor of a cheaper calling convention.

-- 
John Cowan          http://www.ccil.org/~cowan        cowan at ccil.org
Where the wombat has walked, it will inevitably walk again.
   (even through brick walls!)

[TUHS] Early Unix function calls: expensive?

[John Cowan]

Tim Bradshaw scripsit:

> The VAX architecture and its performance horrors must have killed DEC,
> I guess.

Like most things, it was overdetermined:  the Rainbow and the lack of
insight it represented was another major cause.

-- 
John Cowan          http://www.ccil.org/~cowan        cowan at ccil.org
The native charset of SMS messages supports English, French, mainland
Scandinavian languages, German, Italian, Spanish with no accents, and
GREEK SHOUTING.  Everything else has to be Unicode, which means you get
only 70 16-bit characters in a text instead of 160 7-bit characters.

[TUHS] Early Unix function calls: expensive?

[scj]

Well, I certainly said this on several occasions, and the fact that it is
recorded more or less exactly as I remember saying it suggests that I may
have even written it somewhere, but if so, I don't recall where...

As part of the PCC work, I wrote a technical report on how to design a C
calling sequence, but that was before the VAX.  Early calling sequences
had both a stack pointer and a frame pointer, but for most machines it
was possible to get by with just one, so calling sequences got better as
time went on.  Also, RISC machines with many more registers than the
PDP-11 also led to more efficient calls by putting some arguments in
registers.  Later standardizations like varargs were painful on some
architectures (especially those which had different registers for pointers
and integers).

The CALLS instruction was indeed a pig -- a space-time tradeoff in the
wrong direction!  For languages like FORTRAN it might have been justified,
but for C it was awful.  It is my memory too that CALLS was abandoned,
perhaps first at UCB.  But I actually had little hands-on experience with
the VAX C compiler...

Steve




> I just re-found a quote about Unix processes that I'd "lost". It's by
> Steve Johnson:
>
>     Dennis Ritchie encouraged modularity by telling all and sundry that
>     function calls were really, really cheap in C. Everybody started
>     writing small functions and modularizing. Years later we found out
>     that function calls were still expensive on the PDP-11, and VAX code
>     was often spending 50% of its time in the CALLS instruction. Dennis
>     had lied to us! But it was too late; we were all hooked...
>     http://www.catb.org/esr/writings/taoup/html/modularitychapter.html
>
> Steve, can you recollect when you said this, was it just a quote for
> Eric's book or did it come from elsewhere?
>
> Does anybodu have a measure of the expense of function calls under Unix
> on either platform?
>
> Cheers, Warren
>

[TUHS] Early Unix function calls: expensive?

[Armando Stettner]

I guess I experienced things a little differently: computer science basis notwithstanding, the VAX was hugely successful for DEC.

   aps.


> On Jan 3, 2016, at 4:01 PM, John Cowan <cowan at mercury.ccil.org> wrote:
> 
> Tim Bradshaw scripsit:
> 
>> The VAX architecture and its performance horrors must have killed DEC,
>> I guess.
> 
> Like most things, it was overdetermined:  the Rainbow and the lack of
> insight it represented was another major cause.
> 
> -- 
> John Cowan          http://www.ccil.org/~cowan        cowan at ccil.org
> The native charset of SMS messages supports English, French, mainland
> Scandinavian languages, German, Italian, Spanish with no accents, and
> GREEK SHOUTING.  Everything else has to be Unicode, which means you get
> only 70 16-bit characters in a text instead of 160 7-bit characters.
> 

[TUHS] Early Unix function calls: expensive?

[Tim Bradshaw]

On 4 Jan 2016, at 04:40, Armando Stettner <aps at ieee.org> wrote:

> I guess I experienced things a little differently: computer science basis notwithstanding, the VAX was hugely successful for DEC.

I think it was, too.  What I meant, though, was that, although x86 demonstrates that it's possible to make almost anything fast by the application of sufficient money, the VAX was something which was expensive to keep performance-competitive, especially in the era when RISC could make really easy wins, and the cost of doing that hurt DEC pretty badly, I would expect (and made VAXes increasingly expensive compared to the competition, which I remember them being in the late 80s).  And I guess Alpha was too late.

--tim

[TUHS] Early Unix function calls: expensive?

[Tony Finch]

scj at yaccman.com <scj at yaccman.com> wrote:
>
> As part of the PCC work, I wrote a technical report on how to design a C
> calling sequence, but that was before the VAX.  Early calling sequences
> had both a stack pointer and a frame pointer, but for most machines it
> was possible to get by with just one, so calling sequences got better as
> time went on.  Also, RISC machines with many more registers than the
> PDP-11 also led to more efficient calls by putting some arguments in
> registers.  Later standardizations like varargs were painful on some
> architectures (especially those which had different registers for pointers
> and integers).

I had a look for your technical report online but my searches failed me.
Do you have a link to a copy?

Doesn't alloca() get interesting if you have a stack pointer but no frame
pointer? :-)

http://minnie.tuhs.org/cgi-bin/utree.pl?file=4BSD/usr/src/libc/sys/alloca.s

Nowadays it's usually implemented as a builtin, and given that the
compiler ought to be able to cope in most cases, but if you alloca() a
variable amount things soon get too difficult...

Tony.
-- 
f.anthony.n.finch  <dot at dotat.at>  http://dotat.at/
Northeast Viking, North Utsire: Southeasterly 5 to 7, occasionally gale 8 in
south. Rough or very rough, occasionally moderate later. Fair. Good.

[TUHS] Early Unix function calls: expensive?

[Clem Cole]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 401 bytes --]

On Sun, Jan 3, 2016 at 11:40 PM, Armando Stettner <aps at ieee.org> wrote:

> I guess I experienced things a little differently: computer science basis
> notwithstanding, the VAX was hugely successful for DEC.
>
>    aps.
>

​+1​
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20160104/8dc7e093/attachment.html>

[TUHS] Early Unix function calls: expensive?

[Larry McVoy]

On Mon, Jan 04, 2016 at 08:52:51AM +0000, Tim Bradshaw wrote:
> On 4 Jan 2016, at 04:40, Armando Stettner <aps at ieee.org> wrote:
> 
> > I guess I experienced things a little differently: computer science basis notwithstanding, the VAX was hugely successful for DEC.
> 
> I think it was, too.  What I meant, though, was that, although x86
> demonstrates that it's possible to make almost anything fast by the
> application of sufficient money, the VAX was something which was expensive
> to keep performance-competitive, especially in the era when RISC could
> make really easy wins, and the cost of doing that hurt DEC pretty badly,
> I would expect (and made VAXes increasingly expensive compared to the
> competition, which I remember them being in the late 80s).  And I guess
> Alpha was too late.

Yeah, the 750 was OK [*], the 780 was nice, the 8600 (which UW-Madison
named "speedy.rsch.wisc.edu", such a bad name) was expensive.  They threw
a lot of hardware at the perf problem and it seems, to me at least, they
made a pretty good case for the RISC tradeoffs.  But those tradeoffs made
sense when transistors were expensive; these days x86 has shown you can
get some sweet perf out of that CISCy design (though I believe it's sort
of a RISC under the covers).

And as for Alpha, I never warmed up to it.  It was never fast for the 
workloads I cared about (build, test, file serving, integer stuff).
To me, it was over hyped and it under delivered.  Too bad, I liked 
DEC as a company.

[*] the 750 at the UW CS department was where they kept the BSD sources,
it was called slovax.  It was slow but I had so much fun reading that
code that I've always had a machine named slovax ever since, the current
one is mcvoy.com.

[TUHS] Early Unix function calls: expensive?

[Ronald Natalie]

Just never figured out how to make good use of the MARK instruction on the PDP-11.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2284 bytes
Desc: not available
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20160104/993423d5/attachment.bin>

[TUHS] Early Unix function calls: expensive?

[Clem Cole]

If I understand it correctly, few if anyone did.

Clem

On Mon, Jan 4, 2016 at 9:00 PM, Ronald Natalie <ron at ronnatalie.com> wrote:

> Just never figured out how to make good use of the MARK instruction on the
> PDP-11.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20160105/bd58b3e7/attachment.html>

[TUHS] Early Unix function calls: expensive?

[John Cowan]

Clem Cole scripsit:

> On Mon, Jan 4, 2016 at 9:00 PM, Ronald Natalie <ron at ronnatalie.com> wrote:
> 
> > Just never figured out how to make good use of the MARK instruction on the
> > PDP-11.
> 
> If I understand it correctly, few if anyone did.

My guess would be that it was intended to support the antiquated Fortran
feature of "multiple returns", whereby a caller could pass one or more
labels (defined in the caller) to the callee, which could then choose to
return directly to one of them rather than through the return address.
In gcc this is implemented by wrapping the call in a switch which
does a (local) goto based on the integer returned by the callee.
(Only subroutines, i.e. subprograms that do not return a user-visible
value, supported multiple returns.)

A PDP-11 Fortran compiler could have followed such a subroutine call by
a series of branch instructions and had the callee use MARK rather than
RTS to return to the correct point in the jump table.

This doesn't explain why some sources of instruction-set information
say that MARK "facilitates stack clean-up procedures", though.

-- 
John Cowan          http://www.ccil.org/~cowan        cowan at ccil.org
How they ever reached any conclusion at all is starkly unknowable
to the human mind.        --"Backstage Lensman", Randall Garrett

[TUHS] Early Unix function calls: expensive?

[Ronald Natalie]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 812 bytes --]


> On Jan 5, 2016, at 10:13 AM, Clem Cole <clemc at ccc.com> wrote:
> 
> If I understand it correctly, few if anyone did.
> 
> Clem

I remember going to the T11 (PDP-11 on a single chip) announcement and having them say the complete instruction set was supported with the exception of MARK.
There was me and one other geek going “What?  No MARK Instruction?” in the back of the hall.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20160105/a6aff3b5/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2284 bytes
Desc: not available
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20160105/a6aff3b5/attachment.bin>

[TUHS] Early Unix function calls: expensive?

[Diomidis Spinellis]

On 05/01/2016 18:46, John Cowan wrote:
> Clem Cole scripsit:
> 
>> On Mon, Jan 4, 2016 at 9:00 PM, Ronald Natalie <ron at ronnatalie.com> wrote:
>>
>>> Just never figured out how to make good use of the MARK instruction on the
>>> PDP-11.
>>
>> If I understand it correctly, few if anyone did.
> 
> My guess would be that it was intended to support the antiquated Fortran
> feature of "multiple returns"

Digital's handbook presents a reasonable (if unusual for Unix) calling
convention that uses MARK.  It terms the convention "the standard PDP-11
subroutine return convention".

https://pdos.csail.mit.edu/6.828/2005/readings/pdp11-40.pdf#page=107

This convention pushes a tailored MARK instruction onto the stack, and
then has the called routine return to the address of the pushed MARK
instruction.  MARK will in turn clean up the stack and restore R5.  If I
understand things correctly, this saves one instruction over doing the
same things through other explicit instructions.

Interestingly, many years before the invention of stack smashing
attacks, we had a calling convention that was based on executing code
placed on the stack.

[TUHS] Early Unix function calls: expensive?

[Clem Cole]

On Tue, Jan 5, 2016 at 11:46 AM, John Cowan <cowan at mercury.ccil.org> wrote:

> A PDP-11 Fortran compiler could have followed such a subroutine call by
> a series of branch instructions and had the callee use MARK rather than
> RTS to return to the correct point in the jump table.
>

Could be - I was not there for that one but, I'll have to try to ask one or
two of the designers of the the 11 FTN compiler back end when I see them
next who was. Rich or Dave might know/remember.   That said, some of the
folks on the simh mailing list might also remember like Tim or Bob.

That said, IIRC the PDP-11 on chip did not support it, so I suspect the FTN
compiler did not use it.  I also know that in the past, when we had talked
about some of the silly instructions that were created in different ISPs
during lunch conversations, I have specific memories of some of the
compiler folks saying they could never figure out PDP-11's MARK either -
hence my comment about few did know how to put it to good use.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20160105/df4ae7e9/attachment.html>

[TUHS] Early Unix function calls: expensive?

[Clem Cole]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 531 bytes --]

On Tue, Jan 5, 2016 at 12:28 PM, Ronald Natalie <ron at ronnatalie.com> wrote:

> I remember going to the T11 (PDP-11 on a single chip) announcement and
> having them say the complete instruction set was supported with the
> exception of MARK.


​right... which is why I don't think FTN use it, or the HW folks would have
been forced to put it in.

Clem​
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20160105/e6400ffa/attachment-0001.html>

[TUHS] Early Unix function calls: expensive?

[Ronald Natalie]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1314 bytes --]

No, to my knowledge NO compiler I ever came across (I worked on the dark side DOS BATCH, RT-11, RSX-11, and RSTS-11 in various languages though primarily MACRO-11 and FORTRAN) ever used this linkage.    Certainly, none of the UNIX products did.   It was goofy.    We played around with it and it just didn’t do anything you couldn’t do better with JSR/RET and some clever stack manipulation with MOV instructions.



> On Jan 5, 2016, at 12:43 PM, Clem Cole <clemc at ccc.com> wrote:
> 
> 
> On Tue, Jan 5, 2016 at 12:28 PM, Ronald Natalie <ron at ronnatalie.com <mailto:ron at ronnatalie.com>> wrote:
> I remember going to the T11 (PDP-11 on a single chip) announcement and having them say the complete instruction set was supported with the exception of MARK.
> 
> ​right... which is why I don't think FTN use it, or the HW folks would have been forced to put it in.
> 
> Clem​
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20160105/b84651c3/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2284 bytes
Desc: not available
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20160105/b84651c3/attachment.bin>

[TUHS] Early Unix function calls: expensive?

[Warner Losh]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1771 bytes --]

Back in the early days of my career, I saw MARK used once in
MACRO-11 to implement a switch statement. It was horrific and super
long compared to the code that replaced it a few months later. It was a
horrible abuse of the instruction, and the person who wrote the code
(not me) was just learning PDP-11 ropes at the time. The replacement
code was also faster. I doubt I'd ever have noticed if this code didn't
wind up in the hot path and attract the attention of the senior engineer
on the project. He was so horrified, he called us all together to go over
what the instruction actually did, and why it was such a bad idea.

Warner


On Tue, Jan 5, 2016 at 10:46 AM, Ronald Natalie <ron at ronnatalie.com> wrote:

> No, to my knowledge NO compiler I ever came across (I worked on the dark
> side DOS BATCH, RT-11, RSX-11, and RSTS-11 in various languages though
> primarily MACRO-11 and FORTRAN) ever used this linkage.    Certainly, none
> of the UNIX products did.   It was goofy.    We played around with it and
> it just didn’t do anything you couldn’t do better with JSR/RET and some
> clever stack manipulation with MOV instructions.
>
>
>
> On Jan 5, 2016, at 12:43 PM, Clem Cole <clemc at ccc.com> wrote:
>
>
> On Tue, Jan 5, 2016 at 12:28 PM, Ronald Natalie <ron at ronnatalie.com>
> wrote:
>
>> I remember going to the T11 (PDP-11 on a single chip) announcement and
>> having them say the complete instruction set was supported with the
>> exception of MARK.
>
>
> ​right... which is why I don't think FTN use it, or the HW folks would
> have been forced to put it in.
>
> Clem​
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20160105/d3eb11dd/attachment.html>

[TUHS] Early Unix function calls: expensive?

[Ronald Natalie]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1022 bytes --]

Ah, this brings back memories.    We had this MACRO-11 concept called “threaded code” (not threads in the multiprocessing sense).    Essentially we had very small code fragments that were loaded into a table and we’d run them to process data with very light JSR/RET linkage (minimal register saves).

Getting back to Richie’s idea of lightweight functions, it indeed is a more maintainable style and perhaps ahead of it’s time when modern highly optimized inlining compilers came around it made it efficient without the programmer needing to wrap his head around it too much.

> On Jan 5, 2016, at 1:03 PM, Warner Losh <imp at bsdimp.com> wrote:
> 
> Back in the early days of my career, I saw MARK used once in
> MACRO-11 to implement a switch statement.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2284 bytes
Desc: not available
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20160105/b01175f2/attachment.bin>

[TUHS] Early Unix function calls: expensive?

[scj]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1150 bytes --]

> Ah, this brings back memories.    We had this MACRO-11 concept called
> “threaded code” (not threads in the multiprocessing sense).
> Essentially we had very small code fragments that were loaded into a table
> and we’d run them to process data with very light JSR/RET linkage
> (minimal register saves).
>
> Getting back to Richie’s idea of lightweight functions, it indeed is a
> more maintainable style and perhaps ahead of it’s time when modern
> highly optimized inlining compilers came around it made it efficient
> without the programmer needing to wrap his head around it too much.
>
It brought back memories for me, too.  At Ardent, we had a 4-processor
system with each processor a vector processor.  We wanted to be able to go
between parallel and serial very quickly, and the key to achieving this
was to have all 4 threads share the stack.  So in the parallel sections,
all function calls had to be lightweight (only JSR/RET) and keep their
paws off some of the registers (including the stack pointer).  It worked
beautifully, giving us a 3.99 times speedup with 4 processors when we were
in its sweet spot.

[TUHS] Early Unix function calls: expensive?

[John Cowan]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1289 bytes --]

Ronald Natalie scripsit:

> Ah, this brings back memories.    We had this MACRO-11 concept called
> “threaded code” (not threads in the multiprocessing sense).
> Essentially we had very small code fragments that were loaded into
> a table and we’d run them to process data with very light JSR/RET
> linkage (minimal register saves).

I wrote an interpreter for a Forth-ish language in Macro-11 for RT-11.
The core dispatch loop was just two instructions:

	JSR PC, @(R5)+
	BR .-1

When entered with R5 equal to the beginning of a series of addresses of
routines to be entered, this invoked the routines at the addresses in turn.
If the routine was in machine language, it terminated with RTS PC
(shorter than JMP-ing back to the dispatch loop).  If it was itself
threaded code, it began with JSR R5,DISPATCH, which pushed R5 on the
stack and loaded it up with the next instruction, and terminated with
the address of an POP R5 instruction conveniently placed just before
the dispatch loop.

-- 
John Cowan          http://www.ccil.org/~cowan        cowan at ccil.org
You annoy me, Rattray!  You disgust me! You irritate me unspeakably!
Thank Heaven, I am a man of equable temper, or I should scarcely be able
to contain myself before your mocking visage.  --Stalky imitating Macrea

[TUHS] Early Unix function calls: expensive?

[Dave Horsfall]

On Mon, 4 Jan 2016, Ronald Natalie wrote:

> Just never figured out how to make good use of the MARK instruction on 
> the PDP-11.

RSX-11 probably used it, though, as could've RSTS...

-- 
Dave Horsfall DTM (VK2KFU)  "Those who don't understand security will suffer."

[TUHS] Early Unix function calls: expensive?

[Ronald Natalie]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1012 bytes --]

The only thing we really used on RSTS was Basic Plus so I wouldn’t know, but I spent a lot of time making cross calls between MACRO-11 and FORTRAN on the RSX-11M and there was no MARK-based linkage in anything I saw.    I had the kind of odd misfortunate to spend one summer in college writing a database system in Fortran and Macro-11 on RT and when I graduated the company saw that and set me down to work on FORTRAN/MACRO-based database on their two processor RSX-11M system.



> On Jan 5, 2016, at 6:24 PM, Dave Horsfall <dave at horsfall.org> wrote:
> 
> On Mon, 4 Jan 2016, Ronald Natalie wrote:
> 
>> Just never figured out how to make good use of the MARK instruction on 
>> the PDP-11.
> 
> RSX-11 probably used it, though, as could've RSTS...
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2284 bytes
Desc: not available
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20160105/af46c347/attachment.bin>

[TUHS] Early Unix function calls: expensive?

[John Cowan]

Norman Wilson scripsit:

> As late as 1990, every UNIX I knew of still used the
> expensive calls/ret instructions for subroutine calls.

Yes, it seems I was thinking of the Lisp calling convention.

> It's possible that current UNIX-descended/cloned systems
> that have VAX ports, like Linux or Open/Free/NetBSD,
> have had a chance to start over and do better on
> subroutine calls and system calls.  Does anyone know?

Easily determined.  The vax.md (machine description) file
uses CALLS, and in any case gcc runs on both Unix and VMS,
so it has to be VMS-compatible, and there is no switch to
use a different calling convention (the VAX port has few
switches at all: there is one to use G-format floats
instead of D-format).

LLVM has no VAX support at all: the llvm-gcc compiler can
compile for the VAX, but only as a cross compiler.

-- 
John Cowan          http://www.ccil.org/~cowan        cowan at ccil.org
It's the old, old story.  Droid meets droid.  Droid becomes chameleon.
Droid loses chameleon, chameleon becomes blob, droid gets blob back
again.  It's a classic tale.  --Kryten, Red Dwarf

[TUHS] Early Unix function calls: expensive?

[Noel Chiappa]

    > that's 28+13 = 41 memory cycles.
    > ...
    > purely in overhead (counting putting the args on the stack as overhead).

Oh, I missed an instruction for de-stacking the arguments, which was typically
something like 'add #N, sp', so another two instruction word fetches, or 43
cycles.

Ironically, if N=4, the compiler used to emit a 'cmp (sp)+, (sp)+', which is
more efficient space-wise (one word instead of two), but less time-wise
(3 cycles instead of 2).

   Noel

[TUHS] Early Unix function calls: expensive?

[Larry McVoy]

> I used to tell people that the time required to make a good optimizing C
> compiler grew as the cube of the size of the instruction manual, 

So this has nothing to do with Unix but it triggered this memory.
My dad, physics prof, rhodes scholar, told me this when we started
backpacking together:

The population density drops like 1/r^2 the distance from the parking lot.

[TUHS] Early Unix function calls: expensive?

[scj]

> A routine had to be pretty lengthy before it was worth paying the
> overhead, in
> order to amortize the calling cost across a fair amount of work (although
> of
> course, getting access to another three register variables could make the
> compiled output for the routine somewhat shorter).
>
>         Noel
>

I remember Dennis Ritchie telling me that the C compiler itself got
smaller and faster when he added register variables (and used them...)

I used to tell people that the time required to make a good optimizing C
compiler grew as the cube of the size of the instruction manual, including
the appendix on instruction execution timing.   These days they don't even
bother to have such an appendix, because timing depends on so many arcane
internal pipe stalls, memory refreshes, cache misses, etc. that it is
effectively uncomputible.  And then people wonder why
compiled code isn't very "good"...

At UC Berkeley, not long after they got their VAX, Prof. Susan Graham
gave a year-long class on optimization.  The first semester, the  students
learned all the relevant algorithms, etc.  The second semester,
they each implemented an optimization and integrated them into the Unix
F77 compiler.  As I recall, they got a 15% speedup on a set of benchmarks.

Then, over the summer, a student who had studied the VAX hardware
realized that the typical FORTRAN expression ( A = B op C ) was dealing
with three 32-bit addresses, and the resulting instruction was too big
to fit into the instruction lookahead buffer.  Allocating a register to
point to the internal (static) variables for each routine and using a
16-bit offset made these instructions fit, and the performance
improvement (for what was a 2-day fix) was 20%.

The moral of the story is that overhead kills you, and unknown or
uncharacterized overhead is especially fatal...

[TUHS] Early Unix function calls: expensive?

[Clem Cole]

Folks remember, VAX was not designed with UNIX in mind.  It had two primary
influences, assembly programmers (Cutler et al) and FORTRAN compiler
writers.  The truth is, the Vax was incredibly successful in both UNIX and
its intended OS (VMS) sites, even if a number of the instructions it has
were ignored by the C compiler writers.  The fact the C did not map to it
as well as it would for other architectures later is not surprising given
the design constraints - C and UNIX were not part of the design. But it was
good enough (actually pretty darned good for the time) and was very, very
successful - I certainly stopped running a PDP11 when Vaxen were generally
available.  I would not stop doing that until the 68000 based workstations
came along.

From my own experience, when Dave (Patterson) was writing the RISC papers
in the early 1980s, a number of us ex-industry grad student types @ USB
were taking his architecture course having just come off some very
successful systems from the Vax, DG Eagle, Pr1me 750, etc.. [I'll leave the
names of said parties off to protect the innocent].  But what I will say is
that the four of used sit in the back of his calls and chuckle.  We used to
remind Dave that a lot of the choices that were made on those machines, we
not for "CS" style reasons.  IMO: Dave really did not "get it" -- all of
those system designers did make architectural choices, but the drivers were
the code base from the customer sites not how how well spell or grep
worked.   And those commercial systems generally did mapped well at what
the designers considered and >>why<< those engineers considered what they
did  [years later a HBS professor Clay Christensen's book explained why].

I've said this in other forums, but I contend that when we used pure CS to
design world's greatest pure computer architecture (Alpha) we ultimately
failed in the market.  The computer architecture was extremely successful
and many of miss it.   Hey, I now work for a company with one of the worst
instruction sets/ISA from a  Computer Science standpoint - INTEL*64 (C),
and like the Vax, it's easy to throw darts at the architecture from a
purity standpoint.   Alpha was great, C and other languages map to it well,
and the designers followed all of the CS knowledge at the time.   But as a
>>system<< it could not compete with the disruption caused by the 386 and
later it's child, INTEL*64.   And like Vaxen, INTEL*64 is ugly, but it
continues to win because of the economics.

At Intel we look at very specific codes and how they map and the choices of
what new things to add, how the system morphs are directly defined by what
we see from customers and in the case of scientific codes, how well the
FORTRAN compiler can exploit it -- because it is the same places (the
national labs and very large end users like weather, automotive, oil/gas or
life sciences) that have the same Fortran code that still need to run ;-)
 This is just want DEC did years ago with the VAX (and Alpha).


As an interesting footnote, the DNA from the old DEC Fortran compiler lives
on "ifort" (and icc).   Some of the same folks are still working on the
code generator, although they are leaving us fairly rapidly as they
approach and pass their 70s.  But that's a different story ;-)

So the question is not a particular calling sequence or set of instructions
is good, you need to look at the entire economics of the system - which to
me begs the question of if the smartphone/tablet and ARM be the disruptor
to INTEL*64 - time will tell.

Clem


On Sun, Jan 3, 2016 at 7:42 PM, <scj at yaccman.com
<https://mail.google.com/mail/?view=cm&fs=1&tf=1&to=scj at yaccman.com>> wrote:

> Well, I certainly said this on several occasions, and the fact that it is
> recorded more or less exactly as I remember saying it suggests that I may
> have even written it somewhere, but if so, I don't recall where...
>
> As part of the PCC work, I wrote a technical report on how to design a C
> calling sequence, but that was before the VAX.  Early calling sequences
> had both a stack pointer and a frame pointer, but for most machines it
> was possible to get by with just one, so calling sequences got better as
> time went on.  Also, RISC machines with many more registers than the
> PDP-11 also led to more efficient calls by putting some arguments in
> registers.  Later standardizations like varargs were painful on some
> architectures (especially those which had different registers for pointers
> and integers).
>
> The CALLS instruction was indeed a pig -- a space-time tradeoff in the
> wrong direction!  For languages like FORTRAN it might have been justified,
> but for C it was awful.  It is my memory too that CALLS was abandoned,
> perhaps first at UCB.  But I actually had little hands-on experience with
> the VAX C compiler...
>
> Steve
>
>
>
>
> > I just re-found a quote about Unix processes that I'd "lost". It's by
> > Steve Johnson:
> >
> >     Dennis Ritchie encouraged modularity by telling all and sundry that
> >     function calls were really, really cheap in C. Everybody started
> >     writing small functions and modularizing. Years later we found out
> >     that function calls were still expensive on the PDP-11, and VAX code
> >     was often spending 50% of its time in the CALLS instruction. Dennis
> >     had lied to us! But it was too late; we were all hooked...
> >     http://www.catb.org/esr/writings/taoup/html/modularitychapter.html
> >
> > Steve, can you recollect when you said this, was it just a quote for
> > Eric's book or did it come from elsewhere?
> >
> > Does anybodu have a measure of the expense of function calls under Unix
> > on either platform?
> >
> > Cheers, Warren
> >
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20160103/875cf921/attachment.html>

[TUHS] Early Unix function calls: expensive?

[Norman Wilson]

As late as 1990, every UNIX I knew of still used the
expensive calls/ret instructions for subroutine calls.
I vaguely remember a consensus (and I certainly shared
the feeling) that in hindsight it would have been better
to use jsb/rsb, but changing everything would have been
so much work that nobody wanted to do it.

1990 was already past peak VAX in the UNIX world, so
I can't imagine anyone bothering to make such a change
to an existing system after then.  Especially a system
that already had many existing installations who would
have to deal with the resulting compatibility problem.

During the latter part of the 1990s, I was actively
supporting a private UNIX system just for myself on
a few MicroVAXes at home.  One of the things I did
was to write a VAX code generator for the then-current
version of lcc (the one around which the book was
written), so as to have an ISO-compatible compiler
and convert all of /usr/src (not so big even in those
days) to ISO.  It was an interesting exercise and I
learned a lot, but even then, I wasn't brave enough to
adopt an incompatible subroutine-calling convention.

Another big time waste in the original VAX UNIX was
the system-call interface: arguments were left on the
stack (where they had been put before calling the
syscall stub routine in libc); the kernel then had
to do a full-fledged copyin to get them.  It occurred
to me more than once to change the convention and have
the syscall stubs copy the arguments into registers
before executing the chmk (syscall) instruction.
That instruction didn't touch the registers; the
kernel saved them early in the chmk trap routine,
in its own address space, so no copying or access
checking would have been required to fetch their
call-time contents.

That would still have been a messy change to make,
because I'd have to be sure every program had been
relinked with the new-style libc before changing the
kernel.  (This was a system without shared libraries.)
But on a personal system it would have been doable.
I never did.

It's possible that current UNIX-descended/cloned systems
that have VAX ports, like Linux or Open/Free/NetBSD,
have had a chance to start over and do better on
subroutine calls and system calls.  Does anyone know?

Norman Wilson
Toronto ON

[TUHS] Early Unix function calls: expensive?

[Noel Chiappa]

    > From: Warren Toomey

    > I just re-found a quote about Unix processes
    > ..
    >  Years later we found out that function calls were still expensive
    >  on the PDP-11
    > ..
    > Does anybodu have a measure of the expense of function calls under Unix
    > on either platform?

Procedure calls were not cheap on the PDP-11 with the V6/V6 C compiler (which
admittedly was not the most efficient with small routines, since it always
saved all three non-temporary registers, no matter whether the called routine
used them or not).

This was especially true when compared to the code produced by the compiler
with the optimizer turned on, if the programmer was careful about allocating
'register' variables, which was pretty good.

On most PDP-11's, the speed was basically linearly related to the number of
memory references (both instruction fetch, and data), since most -11 CPU's
were memory-bound for most instructions. So for that compiler, a subroutine
call had a fair amount of overhead:

	inst	data

call	4	1
	2	0	if any automatic variables
	1	1	minimum per single-word argument

csv	9	5

cret	9	5

(In V7, someone managed to bum one cycle out of csv, taking it down to 8+5.)

So assume a pair of arguments which were not register variables (i.e.
automatics, or in structures pointed to by register variables), and some
automatics in the called routine, and that's 4+2 for the arguments, plus 6+1,
a subtotal of 10+3; add in csv and cret, that's 28+13 = 41 memory cycles.

On a typical machine like an 11/40 or 11/23, which had roughly 1 megacycle
memory throughput, that meant 40 usec (on a 1 MIP machine) to do a procedure
call, purely in overhead (counting putting the args on the stack as overhead).

We found that, even with the limited memory on the -11, it made sense to run
the time/space tradeoff the other way for short things like queue
insertion/removal, and do them as macros.

A routine had to be pretty lengthy before it was worth paying the overhead, in
order to amortize the calling cost across a fair amount of work (although of
course, getting access to another three register variables could make the
compiled output for the routine somewhat shorter).

	Noel

[TUHS] Early Unix function calls: expensive?

[Larry McVoy]

On Mon, Jan 04, 2016 at 02:08:17AM +0100, Johnny Billquist wrote:
> On 2016-01-04 00:53, Tim Bradshaw <tfb at tfeb.org> wrote:
> >>>On 3 Jan 2016, at 23:35, Warren Toomey<wkt at tuhs.org>  wrote:
> >>>
> >>>Does anybodu have a measure of the expense of function calls under Unix
> >>>on either platform?
> >>>
> >I don't have the reference to hand, but one of the things Lisp implementations (probably Franz Lisp in particular) did on the VAX was not to use CALLS: they could do this because they didn't need to interoperate with C except at known points (where they would use the C calling conventions).  This change made a really significant difference to function call performance and meant that on call-heavy code Lisp was often very competitive with C.
> >
> >I can look up the reference (or, really, ask someone who remembers).
> >
> >The VAX architecture and its performance horrors must have killed DEC, I guess.
> 
> I don't know if that is a really honest description of the VAX in
> general, nor DEC. DEC thrived in the age of the VAX.
> However, the CALLS/CALLG and RET instructions were really horrid for
> performance. Any clever programmer started using JSB and RSB
> instead. as they give you the plain straight forward call and return
> semantics without all the extra stuff that the CALL instructions
> give.
> 
> But, for assembler programmers, the architecture was nice. For
> compilers, it's more difficult to do things optimal, and of course,
> it took quite a while before hardware designers had the tools, skill
> and knowledge how to implement complex instruction sets fast in
> hardware. But nowadays, that is definitely not a problem, and it was
> more or less already solved by the time of the NVAX chip as well,
> which was actually really fast compared to a lot of stuff when it
> came out.
> 
> 	Johnny

Yeah, I agree.  The VAX was pretty pleasant.  I never warmed up to it as
much as I warmed up to the PDP-11 (has to be the most pleasant working
CPU I've used - I say working because NS320xx seemed like it would be
pleasant).  I wrote a user level thread library that ran on the VAX and
I had to write the assembler for swtch() and it was pretty easy.

[TUHS] Early Unix function calls: expensive?

[Johnny Billquist]

On 2016-01-04 00:53, Tim Bradshaw <tfb at tfeb.org> wrote:
>> >On 3 Jan 2016, at 23:35, Warren Toomey<wkt at tuhs.org>  wrote:
>> >
>> >Does anybodu have a measure of the expense of function calls under Unix
>> >on either platform?
>> >
> I don't have the reference to hand, but one of the things Lisp implementations (probably Franz Lisp in particular) did on the VAX was not to use CALLS: they could do this because they didn't need to interoperate with C except at known points (where they would use the C calling conventions).  This change made a really significant difference to function call performance and meant that on call-heavy code Lisp was often very competitive with C.
>
> I can look up the reference (or, really, ask someone who remembers).
>
> The VAX architecture and its performance horrors must have killed DEC, I guess.

I don't know if that is a really honest description of the VAX in 
general, nor DEC. DEC thrived in the age of the VAX.
However, the CALLS/CALLG and RET instructions were really horrid for 
performance. Any clever programmer started using JSB and RSB instead. as 
they give you the plain straight forward call and return semantics 
without all the extra stuff that the CALL instructions give.

But, for assembler programmers, the architecture was nice. For 
compilers, it's more difficult to do things optimal, and of course, it 
took quite a while before hardware designers had the tools, skill and 
knowledge how to implement complex instruction sets fast in hardware. 
But nowadays, that is definitely not a problem, and it was more or less 
already solved by the time of the NVAX chip as well, which was actually 
really fast compared to a lot of stuff when it came out.

	Johnny

-- 
Johnny Billquist                  || "I'm on a bus
                                   ||  on a psychedelic trip
email: bqt at softjar.se             ||  Reading murder books
pdp is alive!                     ||  tryin' to stay hip" - B. Idol