Re: Data Structure Reorganizing Optimizations

        Does anyone have any actual results for the potential spaced saved from
        automatic reorganization of structures? Unless the gains are large, it
        doesn't strike me as worth thinking about--particularly not for C or
        C++, since so much code would break.


My post started out as a reply to a post by Alvin LeBeck at Wisconsin,
whose paper on cache profiling reports obscene performance
improvements - sometimes 3-4X, if memory serves me correctly - for
various of the SPEC benchmarks.


Certainly in the range of 2X.


I've been meaning to post a summary of the discussion to this group.
Will still go into more detail. But the short of it is:


Problems with reorganization mainly lie in people making assumptions
about the *consistency* of data structure layout.


a) People who pass structures between separately compiled modules
        - don't really care about order of fields, just want compatibility.


        RESPONSE: fine, only do reorganization within a compilation module (or, at
      least
        the scope necessary to do interprocedural optimizations). If the compiler
        can prove that the structure isn't accessed from other modules (e.g. it's
        compiling and linking main() and all dependencies) let it have free rein.


b) People who pass structures around on disk, persistent data structures.


        Same response as above, although I must admit that I have little
        sympathy for these folk since their code is guaranteed to break when
        porting between different machines.


c) Networking code ... almost the same reaction as above, except that some of
        the people writing the non-portable code are some of the leading lights
        of the networking community.


d) Device drivers.


e) Arrays at the end of a structure, e.g. struct { int size; int array[0]; }


        RESPONSE: easy enough to special case this.


>From this, I conclude that there are valid reasons to not arbitrarily
reorder BUT ALL OF THESE REASONS ARE BROKEN OR NONPORTABLE C PROGRAMS IN
THE FIRST PLACE!!! (except for class a, passing between separately
compiled modules)


It therefore seems to me that a compiler doing data structure
reorganization is implementing legal C, except for the rule about
addresses of structure e;ements being monotonically increasing.


There does seem to be an implicit rule that structure of the same shape
shall be similarly ordered and packed, to permit bcopy() between
structures, but again, this does not seem to be defined by the standard.
--
Andy "Krazy" Glew, glew@ichips.intel.com, Intel,
M/S JF1-19, 5200 NE Elam Young Pkwy, Hillsboro, Oregon 97124-6497.
Place URGENT in email subject line for mail filter prioritization.
--

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