From: belal@sco.COM (Bela Lubkin)
Newsgroups: biz.sco.general
Subject: utility of small processor cache
Date: 12 Jan 93 10:09:33 GMT
Organization: [resent by] The SCOGEN gateway and Propagation Society
Resent-From: mmdf@xenitec.on.ca
Submit-To: scogen@xenitec.on.ca
Precedence: bulk

Tom Fitzgerald wrote:

> Bela Lubkin <belal@sco.COM> writes:
> 
> > Any code that ever loops benefits from a cache (unless the
> > loop actually travels through >1K of code).
> 
> .... or unless it contains subroutine calls, in which case things get
> unpredictable.  Given the studies of compiled HLL code [*] that show that
> subroutine-call is the most frequently used machine instruction, this will
> definitely have an impact.  If the routine you're calling is at the same
> address (mod 1024) as the calling loop, it'll push the calling loop out of
> the cache.  A set-associative cache will fix this, but if you call two
> routines from the loop and they're both at the same address, the problem
> comes back.

Things get a bit *less* predictable, but not *un*predictable.  You can
predict that there will be *some* overlap.

Now, I've looked through a lot of compiled code -- I'm always patching
binaries -- and I can't imagine what those studies were looking at.
What you describe sounds much more like a study of high level language
*source code*.  Average C source code probably has close to one function
call per line of executable code (say, between 1/20 and 2 calls per line
depending on coding style, excepting pathological cases).  Even in the
2-calls-per-line case, though, you'd find in the machine code that
push/pop instructions and other sorts of data movement are more common
than call/ret instructions.  This would be different on an architecture
like the VAX, or presumably IBM mainframes (I don't know), in which the
call instruction can inherently specify arguments.  But this is just a
semantic trick of the CPU designer: the call-with-arguments instruction
is just as costly in resources (code space, clock cycles, data
movements) as the push/call/ret/pop sequences it replaces.  The only
resource it conserves is programmer consternation.

All of which is irrelevant to the problem at hand.  I say that a lot of
linear code goes on, and a lot of loops without calls, and yes, a lot of
loops with calls.  Many of the loops with calls (I might even say most,
or almost all) will be small enough to fit within a 1K cache.  Routines
they call will also be that small.  For some significant set of
caller/callee pairs, they will not only both fit in 1K, but also happen
to be aligned so that they don't push each other out of cache.  (Cases
where this is not true are where an associative cache is a *big* win).

I've been ignoring cache contention between code & data.  Basically, I
think that it either doesn't matter much, or if you're doing some sort
of memory scan, then it totally hoses your cache and that's that.  (But
the scan itself benefits from high bandwidth cache line fills).  A
useful CPU optimization would be to *not* cache large(*) string
instructions, in this sense: it would do cache line fills, but not to
the appropriate cache line RAM.  Instead it would keep the current line
in temporary storage until the string instruction passed over it, then
drop it.  It would have two temp cache lines, one for current work, the
other to fetch to while working on the current line.

(*) What's a "large" string instruction?  I was thinking in terms of
some sort of simple heuristic, e.g. "if will wipe out more than 1/2 of
my cache".  Next thought was to give programmer control, perhaps 3
different choices: don't cache this, do cache this, or let the CPU
decide.  Last thought is, I'd bet that for real world use the best
heuristic is to never cache string instructions since they mesh
perfectly with cache fills anyway.  You want to cache other sorts of
data because it would be a waste to do a cache fill, not use all of it,
and not even have the opportunity to use it cheaply later.  You can at
least assume you'll get one full use of your cache fill with a string
instruction, except at the ends.

Does someone out there have a Cyrix 486SLC or DLC processor (which, if I
remember what started all this, have 1K on-chip caches)?  We can test
how much use the 1K cache is, in a crude sense...

> [*] These studies are admittedly from olden days - I'm assuming that
> smarter compiler optimizers and increased use of subroutine libraries have
> not made the situation any better.

Part of being smarter is avoiding as many calls as possible.  Calls are
slow, push a lot of useless bytes through cache, may disturb processor
pipelining etc.  Smart compilers these days are inlining small calls;
and smart library writers are explicitly inlining simple library-internal
calls.

>Bela<