Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!ub!csn!ccncsu!debussy!rro
From: rro@debussy.cs.colostate.edu (Rod Oldehoeft)
Newsgroups: comp.arch
Subject: Re: Page size and linkers (was: Re: SunMMU history)
Message-ID: <12237@ccncsu.ColoState.EDU>
Date: 24 Jan 91 15:53:59 GMT
References: <PCG.91Jan20191955@teacho.cs.aber.ac.uk> <3981@skye.ed.ac.uk> <9840@frame.UUCP>
Sender: news@ccncsu.ColoState.EDU
Organization: Colorado State Computer Science Department
Lines: 87

In article <9840@frame.UUCP> sbs@ciara.Frame.COM (Steven Sargent) writes:

>In article <3981@skye.ed.ac.uk>, richard@aiai.ed.ac.uk (Richard Tobin) writes:

>|> In article <PCG.91Jan20191955@teacho.cs.aber.ac.uk> pcg@cs.aber.ac.uk (Piercarlo Grandi) writes:

    [A little deleted here.]

>|> 
>|> Large page sizes seem likely to interact badly with programs
>|> containing a large number of small procedures, such as X clients.  An
>|> obvious improvement would be to have the linker order procedures so that
>|> procedures commonly used together were adjacent, and separate from
>|> rarely used procedures.
>|> 
>|> Has this been done in any real systems?
>|> 
>
>NeXT's 2.0 linker provides a scheme for ordering procedures.
>I've used it to separate out startup code from the rest of the
>program and gotten good results (naturally, the numbers aren't
>handy.)  Special flags to gprof cause it to present output in a
>form useful to the linker.

Before we all get out chisels and find a roundish rock, here are some
references to the idea of restructuring programs for virtual memory:

   Brawn and Gustavson, Program behavior in a paging environment, Proc.
   AFIPS FJCC 33, 1968: 1019-1032.
   
   Comeau, L., A study fo the effect of user program optimization in a
   paging system, Proc. 1st ACM Symp.  OS Principles, 1967.
   
   Ferrari, D. and M. Kobayashi, Program restructuring algorithms for
   global LRU environments, Proc. Int. Comp. Symp., 1977: 277-283.
   
   Hatfield, D. J. and J. Gerald, Program restructuring for virtual
   memory, IBM Sys. J. 10, 3, 1971: 168-192.
   
   Johnson, J. W., Program restructuring for virtual memory systems,
   Project MAC TR-148, MIT, 1975.
   
   McKellar, A. and E. G. Coffman, The organization of matrices and
   matrix operations in a paged multiprogramming environment, CACM 12, 3,
   1969: 153-165.

Notice how old these references are.  There was great concern that
automatic memory management via paging would not be as efficient as
its predecessor, manually designed and explicitly executed overlaying.

This research fell off because it was suggested that the advent of
electronic auxiliary memory would cause page sizes to decrease and
therefore working sets would more closely approximate the actually
needed portions of the program in real memory, so thinking about this
was unnecessary.  And of course, memory was getting to be nearly
free, wasn't it?

Of course this didn't happen.  Disks with rotational latency delays
didn't go away, so large page sizes continued.  Disk technology
continued to improve dramatically and unexpectedly, so the price/
performance advantage over electronic backing store continued.
Also, applications got bigger much faster than memory prices dropped.

When I co-authored "Operating Systems--Advanced Concepts" I included
a section covering Johnson's work (reference above), partly because
no one else seemed to think it was important any more, but I did.
In general, automatic restructuring based on execution trace data
can reduce page faults by 50% over a "bad" virtual memory ordering,
for a broad range of available real memory sizes.  Since orderings
are now random, how do you know yours aren't bad?

{{{   No need for you to rush out and buy this book, published by
Benjamin-Cummings, 1987.  Really.  First author is Maekawa.  Really
no need to buy it.   :->   }}}

On a more recent note than the references above, the MIPS f77
compiler, which has only the name in common with the original
ATT f77, allows profiling of the execution (via pixie) and subsequent
recompilation which uses profile data to reorganize the text
segment for better I-cache performance.  Same concept, maybe
pixie output could be input for Johnson's algorithms.


Rod Oldehoeft                    Email: rro@cs.colostate.edu
Computer Science Department      Voice: 303/491-5792
Colorado State University        Fax:   303/491-2293
Fort Collins, CO  80523