Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!pt.cs.cmu.edu!rochester!crowl
From: crowl@cs.rochester.edu (Lawrence Crowl)
Newsgroups: comp.arch
Subject: Re: Software modularity vs. instruction locality
Message-ID: <1989Nov9.205356.17585@cs.rochester.edu>
Date: 9 Nov 89 20:53:56 GMT
References: <17707@watdragon.waterloo.edu> <23604@cup.portal.com> <1989Nov2.190900.29144@world.std.com> <1989Nov4.004529.10049@ico.isc.com> <1TMk2X#Qggn6=eric@snark.uu.net>
Reply-To: crowl@cs.rochester.edu (Lawrence Crowl)
Organization: University of Rochester Computer Science Department
Lines: 35

In article <1TMk2X#Qggn6=eric@snark.uu.net>
eric@snark.uu.net (Eric S. Raymond) writes:
>good software modularity practices tend to hurt code locality. If you're
>calling subroutines a lot in generated code the PC jumps all over the shop.

For the purposes of caches and locality, it doesn't matter if the PC jumps all
over the shop.  What matters is if the PC jumps to someplace it has recently
been.  Unrolling loops reduces PC jumping, but also reduces locality and cache
effectiveness.  Replacing several calls to a procedure by the inline code to
achieve the same function produces the same effect.  By leaving the calls in
place, I reduce the number of (static) instructions that the PC visits, and
thereby increase the PC locality.  In short, MODULARITY IMPROVES PC LOCALITY.

There are some tradeoffs involved in modularity that affect performance. 
First, the additional call instructions may increase code size for very small
procedures. (Automatic inlining helps here.)  Second, the PC jumps drain the
instruction pipeline.  If the drain is sufficiently frequent, lower PC
locality may improve performance.  Third, procedures may be spread over many
pages and each occupy only a small portion of its page.  The result is that
while the INSTRUCTION locality increases, the PAGE locality decreases.  This
could reduce performance via translation cache misses and paging.

Suppose we have a highly modular program, and an inlining compiler.  The
compiler may choose to call a procedure, or expand it inline.  For those
procedures where calls are a net performance loss, the compiler will choose to
expand them inline.  Given a modular program, and inlining compiler may emit
either modular code, or non-modular code.  The reverse is not true.  So, given
an inlining compiler, MODULARITY IS ALWAYS GOOD.

(There are also macro-efficiency and software engineering reasons to prefer
modularity.  However, they are outside the scope of this newsgroup.)
-- 
  Lawrence Crowl		716-275-9499	University of Rochester
		      crowl@cs.rochester.edu	Computer Science Department
...!{allegra,decvax,rutgers}!rochester!crowl	Rochester, New York,  14627