Re: Data Structure Reorganizing Optimizations

glew@ichips.intel.com (Andy Glew) wrote in favour of having the compiler
rearrange the order of fields in a struct. He was kind enough to send me
some information about the kinds of rearrangements he has found useful.
I note that
(1) A common kind of rearrangement is to sort fields by their alignment
        requirements. As these requirements may vary from machine to machine,
        the good rearrangements may vary too, so even if you arrange your
        fields well by hand (as I generally do), you can't be _sure_ that the
        same arrangement will work well on other machines. (I'm not sure how
        many of my records would need rearrangement on 64-bit machines.)


        I note that for this kind of rearrangement the compiler has full
        information. It shouldn't be hard to modify lcc or gcc to do it.


(2) Another kind of rearrangement he mentions is rearrangthing fields so
        that fields that _are_ needed in the same critical loop will be in the
        same cache line (or small set of cache lines) and fields that are not
        needed in the same critical loop will not interfere with them.


        A compiler _can_ make intelligent guesses about which loops matter
        most and could do this rearrangement, _provided_ it has access to all
        of the parts of the program using this record. But it is NOT a _local_
        decision. And this kind of rearrangement may conflict with the first
        kind.


(3) From my own experience, there have been machines which provided
        particularly cheap reference to fields near the beginning of a struct
        (which is why old Franz Lisp for the VAX put the 'cdr' field of a cons
        cell first, and why all my list-like structs always put the 'next'
        field first though not the only reason; think also of the transputer).
        Thus the most frequently referenced fields "should" go early. This,
        like (2), is a non-local criterion based on how the struct is _used_.


A particularly noteworthy point is that two different structs with the
same declared fields might be _used_ in different ways, thus warranting
different arrangements according to (2) and (3). That makes separate
compilation tricky. I could quite happily sacrifices the existing ordering
rules of C structs, but I could not sacrifice separate compilation.
That means that any rearrangements the compiler did *unprompted* should be
confined to strictly local ones based on the declared types and order of
the fields, such as type (1).
--
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.