aglew@urbsdc.Urbana.Gould.COM (06/10/88)
Two papers that might be of interest to the comp.arch readership, in SIGPLAN Notices, Volume 23, Number 6, June 1988. The thing that attracted me about these papers is that they contain measurements for things that I've wanted to measure in the past. B.P. Miller, "The Frequency of Dynamic Pointer References in C Programs" ------------------------------------------------------------------------ Wonder of wonders, a pure measurement paper, that isn't trying to prove a point at the same time! I think we need far more such papers; unfortunately, measurement papers probably can't make it into refereed journals unless they have something "special". Bart Miller of Wisconsin-Madison presents dynamic counts of pointer references vs. total number of instructions in several UNIX programs on VAX running BSD, obtained by a compiler that inserted counters. I will not type in all the tables, but briefly: Sample % Pointer Refs % Due to Library ========================================================== ls(empty) 1.2% 42.1% ls -tl (empty) 1.9% 47.2% ls (big) 13.0% 8.6% ls -tl (big) 6.9% 12.5% ---------------------------------------------------------- cc 49 lines 1.7% 93% cc 663 lines 1.9% 84% ---------------------------------------------------------- sort 10 lines 12.7% sort 497 lines 31.4% ---------------------------------------------------------- ex startup 0.5% 53.4% ex file create 2.7% 96.9% ex 418 lines 14.5% 99.8% ---------------------------------------------------------- nroff small 1.2% 99% nroff 6 pages 1.6% 99% ---------------------------------------------------------- f77 27 lines 4.9% 94% f77 270 lines 5.5% 93% ---------------------------------------------------------- sh trivial 3.5% 100% sh complex 5.1% 100% % Pointer Refs = percentage of all instructions that are pointer references. % Due to Library = percentage of pointer references that are due to code in standard library routines. This is kind of interesting because of the rather low percentages, although I note that most of the programs used are rather old C programs, several written before the use of pointers and structs became widespread (cc and f77 I know use arrays where people would nowadays use pointers, because of their age (the key to understanding pcc is remembering that it wasn't written in C, but forth :-()). It would be useful to have relative numbers - comparing pointer references to number of array references, and simple variable references by data type and storage class. Also, simple pointer references, and pointer references to fields. Anyway, a paper that contains some interesting numbers without any overloading attempt to prove a point. Like I said above, we need more measurement papers of any type. P.E. Cohen, "An Abundance of Registers" --------------------------------------- A not too unusual paper about register allocation saving the intersection of caller and callee active register set on the NEC V60/V70, with some results for a very small program using a random number generator to select which registers a routine used. 20 registers used (+1 for mask). Number of trials Registers saved 1 189 5 6261-6451 10 12519-12770 4 18809-19030 The point is that this primitive interprocedural register allocation strategy can make has a slight performance gain over a simplistic strategy, on average (average for the random allocation 11710, average simple strategy 12744) without using register window mechanisms - and a profiling type optimizer can search for the dramatically reduced allocation. A simple optimization makes the average 8224.