mark@navtech.uucp (Mark Stevans) (06/25/88)
Due to the alignment requirements of various processor architectures, the
declared order of fields within a C structure can significantly effect the
space required to store the structure. The easy way to save space on almost
all C implementations is to sort your structure fields in order of descending
size of the field type. For arrays, just use the base type.
A brief example. The following program:
typedef struct {
char buf[5];
short s;
char c;
long l;
} Biggie;
typedef struct {
short s;
long l;
char buf[5];
char c;
} Smallie;
main()
{
printf("Biggie is %d bytes long, but Smallie is only %d bytes long.\n",
sizeof (Biggie), sizeof (Smallie));
}
When compiled and run on a Sun-3/50 produces the output:
Biggie is 14 bytes long, but Smallie is only 12 bytes long.
Mark "Speedy" Stevans
spar!navtech!marksmryan@garth.UUCP (Steven Ryan) (06/26/88)
In article <163@navtech.uucp> mark@navtech.uucp (Mark Stevans) writes: > The easy way to save space on almost >all C implementations is to sort your structure fields in order of descending >size of the field type. (Not being a C expert, I don't know if this true.) A nice language definition will say you can define fields but doesn't say what order they are allocated. It would be better if the compiler can sort the fields to optimise access and balance space/time. In this way you can write the structures as it makes sense and not worry about dinking it for a particular machine.
levy@ttrdc.UUCP (Daniel R. Levy) (06/27/88)
In article <163@navtech.uucp>, mark@navtech.uucp (Mark Stevans) writes: # Due to the alignment requirements of various processor architectures, the # declared order of fields within a C structure can significantly effect the # space required to store the structure. The easy way to save space on almost # all C implementations is to sort your structure fields in order of descending # size of the field type. For arrays, just use the base type. # A brief example. The following program: # typedef struct { char buf[5]; short s; char c; long l; } Biggie; # typedef struct { short s; long l; char buf[5]; char c; } Smallie; # main() # { # printf("Biggie is %d bytes long, but Smallie is only %d bytes long.\n", # sizeof (Biggie), sizeof (Smallie)); # } # When compiled and run on a Sun-3/50 produces the output: # Biggie is 14 bytes long, but Smallie is only 12 bytes long. I think you have your Smallie misordered for maximum "portability". On a 3B20 the program prints: Biggie is 16 bytes long, but Smallie is only 16 bytes long. I get better results with: typedef struct { long l; short s; char buf[5]; char c; } Smallie; which gives me: Biggie is 16 bytes long, but Smallie is only 12 bytes long. Your good result on the Sun-3 is because structs and longs only need be halfword aligned there. -- |------------Dan Levy------------| THE OPINIONS EXPRESSED HEREIN ARE MINE ONLY | AT&T Data Systems Group | AND ARE NOT TO BE IMPUTED TO AT&T. | Skokie, Illinois | |-----Path: att!ttbcad!levy-----|
mark@navtech.uucp (Mark Stevans) (06/27/88)
In article <2775@ttrdc.UUCP> levy@ttrdc.UUCP (Daniel R. Levy) writes: <In article <163@navtech.uucp>, mark@navtech.uucp (Mark Stevans) writes: <# Due to the alignment requirements of various processor architectures, the <# declared order of fields within a C structure can significantly effect the <# space required to store the structure. The easy way to save space on almost <# all C implementations is to sort your structure fields in order of descending <# size of the field type. For arrays, just use the base type. <# A brief example. The following program: <# typedef struct { char buf[5]; short s; char c; long l; } Biggie; <# typedef struct { short s; long l; char buf[5]; char c; } Smallie; <# main() <# { <# printf("Biggie is %d bytes long, but Smallie is only %d bytes long.\n", <# sizeof (Biggie), sizeof (Smallie)); <# } <# When compiled and run on a Sun-3/50 produces the output: <# Biggie is 14 bytes long, but Smallie is only 12 bytes long. <I get better results with: <typedef struct { long l; short s; char buf[5]; char c; } Smallie; How goofy can I get? My example doesn't properly follow my proposed rule! Just goes to prove the old adage: avoid comments, since they might conflict with your code. Thanks for the correction, DRL. But anyhows, what do y'all think of the rule itself: "The space requirement of any given C structure may be easily optimized by reorganizing the structure fields in order of decreasing base type size." Some responder pointed out correctly that there is no guarantee in the C language that the compiler will preserve your field ordering -- but I wouldn't worry about that. I have yet to see a C compiler that did any reordering of structure fields. It would make it a challenge to examine structures through "adb"! Perhaps some compilers put the elements in reverse order, but that's about as strange as reality currently gets. Mark "Shorty" Stevans
leo@philmds.UUCP (Leo de Wit) (06/27/88)
In article <806@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: >In article <163@navtech.uucp> mark@navtech.uucp (Mark Stevans) writes: >> The easy way to save space on almost >>all C implementations is to sort your structure fields in order of descending >>size of the field type. > >(Not being a C expert, I don't know if this true.) A nice language definition >will say you can define fields but doesn't say what order they are allocated. It >would be better if the compiler can sort the fields to optimise access and >balance space/time. In this way you can write the structures as it makes sense >and not worry about dinking it for a particular machine. K&R, page 196, section 8.5, Structure and union declarations: Within a structure, the objects declared have addresses which increase as their declarations are read left-to-right. Each non-field member of a structure begins on a addressing boundary appropriate to its type; therefore, there may be unnamed holes in a structure. which explains everything, and frustrates any hope on optimization (only the left-to-right puzzles me, most program text being written top-to-bottom; B.T.W. what do Chinese program texts look like ? 8-). As far as the field size is conceirned, this is compiler/O.S. dependent, as Steven pointed out; so this may be not portable. B.T.W. lets call it member size; a field in K&R denotes a bit field. Leo.
blandy@awamore.cs.cornell.edu (Jim Blandy) (06/27/88)
In article <164@navtech.uucp> mark@navtech.UUCP (Mark Stevans) writes: >Some responder pointed out correctly that there is no guarantee in the C >language that the compiler will preserve your field ordering ... Hmm. K&R v1, p. 196 (section 8.5 in the reference manual) (ooh, quote K&R, baby! It's SO SEXY!) "Within a structure, the objects declared have addresses which increase as their declarations are read left-to-right." (ooh, that was so good! Now be wishy-washy!) Now I could be wrong, but that looks like a pretty clear statement on how C orders structures... I like the fact that C won't mess with your arrangement - 1) If you want to pack for space, you can. 2) If you need to conform to somebody else's format (in files or system calls or functions written in other languages), you can. I think letting the language decide for you which one was important would be a mistake. Using any high-level language will take some control out of your hands, but C does very little of this; I like that. -- Jim Blandy - blandy@crnlcs.bitnet "insects were insects when man was just a burbling whatsit." - archie
gwyn@brl-smoke.ARPA (Doug Gwyn ) (06/27/88)
In article <164@navtech.uucp> mark@navtech.UUCP (Mark Stevans) writes: >Some responder pointed out correctly that there is no guarantee in the C >language that the compiler will preserve your field ordering Oh, yes there is.
blandy@awamore.cs.cornell.edu (Jim Blandy) (06/27/88)
Sorry - should have done this the first time.
The ordering of members in a structure (excluding bit fields) is
also specified in the NEW K&R (v2), section A2.8 (Appendix A, the reference
manual). Page 213, in my edition:
"The members of a structure have addresses increasing in the
order of their declarations."
--
Jim Blandy - blandy@crnlcs.bitnet
"insects were insects when man was just a burbling whatisit." - archiesmryan@garth.UUCP (Steven Ryan) (06/28/88)
> "The space requirement of any given C structure may be easily > optimized by reorganizing the structure fields in order of decreasing > base type size." Some machines provide an item offset, base address+n chars or words or ..., where the hardware shifts the offset before adding to the base, and some of these same machines handle small offsets or a small range of offsets. In these cases, it is more efficient to put all the small fields first. For example, Cyber 205 provides bit, byte, halfword, and word loads with item offsets of the form LODx [base-address-register,offset-register],destination. If elements are arranged 1 bit, 1 byte, 1 halfword, 1 word, the item offsets are (halfword=32 bits, word=64 bits): small to large large to small +0 bit +0 word +1 byte +2 halfword +1 halfword +12 byte +1 word +104 bit In one case, the program only needs two constant registers and the other needs 4. It is very difficult to find a general rule to best pack a structure. One of the easiest is to throw whole mess at the compiler and say gimme your best shot.
wes@obie.UUCP (Barnacle Wes) (06/28/88)
In article <806@garth.UUCP>, smryan@garth.UUCP (Steven Ryan) writes: > (Not being a C expert, I don't know if this true.) A nice language > definition will say you can define fields but doesn't say what order > they are allocated. It would be better if the compiler can sort the > fields to optimise access and balance space/time. In this way you > can write the structures as it makes sense and not worry about > dinking it for a particular machine. A little further though might show this idea to have some far-reaching bad karma. It would be very difficult to write a file system portable across machines of varying architecture (i.e. Idris) if the compiler on each machine can arbitrarily re-arrange structures to suit its own whim. This might start another `volatile' war :-) but it ain't good for those who use C for what it was intended - systems programming :-). -- {uwmcsd1, hpda}!sp7040!obie!wes | "If I could just be sick, I'd be fine." +1 801 825 3468 | -- Joe Housely --
walter@hpcllz2.HP.COM (Walter Murray) (06/29/88)
Doug Gwyn writes: >In article <164@navtech.uucp> mark@navtech.UUCP (Mark Stevans) writes: >>Some responder pointed out correctly that there is no guarantee in the C >>language that the compiler will preserve your field ordering >Oh, yes there is. >---------- Or, to quote the proposed standard (January, 1988, draft): "Within a structure object, the non-bit-field members and the units in which bit-fields reside have addresses that increase in the order in which they are declared."
gwyn@brl-smoke.ARPA (Doug Gwyn ) (06/30/88)
In article <254@obie.UUCP> wes@obie.UUCP (Barnacle Wes) writes: >It would be very difficult to write a file system portable >across machines of varying architecture (i.e. Idris) if the compiler >on each machine can arbitrarily re-arrange structures to suit its own >whim. Although the original poster was mistaken about the order in which struct members are assigned addresses, it is nonetheless impossible to achieve binary file transportability simply by (acceptable) constraints on C struct format. There is a LOT more to binary data transportability than byte padding, alignment, and sequencing.
smryan@garth.UUCP (07/01/88)
> This might start another `volatile' war :-) but it ain't good >for those who use C for what it was intended - systems programming :-). Hopefully the volatile war is resolved by both sides leaving their moral high ground and meeting in the valley of compromise (by the stream of standarisation on the lawn of progress which feeds the cattle of prosperity which leave the piles of.....). My point not being what C should or should not do, but that overspecifying a problem solution is as bad as underspecifying. The question of optimal field orderring and packing is difficult and a good solution on one system can be a terrible solution on another.
iverson@cory.Berkeley.EDU (Tim Iverson) (07/01/88)
Many of you have mentioned that allowing the compiler to reorder the structure would go contrary to the K&R gospel, some even pointed out a few problems this would cause. What I would like to point out is the problem caused already by following the K&R dictum that fields shall be aligned according to type. Forced alignment is fine when you're creating your own data, but when you have to interface directly with hardware or massage foreign binary data into local format, it can force the programmer to abandon the nice bit field and structure abilities of C and resort to bit masks and character arrays to properly address the data. Fortunately, some C compilers have an option to compile with "packed" structures. A new "packed" keyword would be even better, as this would allow the speed of word aligned structs in all but the instances where it is necesary to hand-align the data. As it stands, if you want to pack one struct, then you must pack them all, or none of the "non-packed" modules will be able to properly access the structs in the "packed" module. Hopefully, this feature will be added in the next generation of C, if there ever will be such a beast. - Tim Iverson iverson@cory.Berkeley.EDU ucbvax!cory!iverson
nevin1@ihlpf.ATT.COM (00704a-Liber) (07/01/88)
In article <164@navtech.uucp> mark@navtech.UUCP (Mark Stevans) writes: > "The space requirement of any given C structure may be easily > optimized by reorganizing the structure fields in order of decreasing > base type size." This is not (necessarily) true! For iinstance: sizeof(long) === 8 sizeof(short) === 5 sizeof(char) === 1 Also suppose that alignment for shorts and longs occurs on even addresses (two byte boundaries), while chars can align on single byte boundaries. With your method, a structure containing 1 long, 2 short, and 2 char would be decalred in the following way: struct mark { long long1; short short1; short short2; char char1; char char2; }; would take up 8 (long) + 5 (short) + 1 (fill) + 5 (short) + 1 (char) + 1 (char) = 21 bytes. If it is declared as: struct nevin { long long1; short short1; char char1; short short2; char char2; } would only take up 20 bytes, since no fill byte is needed. -- _ __ NEVIN J. LIBER ..!ihnp4!ihlpf!nevin1 (312) 510-6194 ' ) ) You are in a little twisting maze of / / _ , __o ____ email paths, all different. / (_</_\/ <__/ / <_ These are solely MY opinions, not AT&T's, blah blah blah
bts@sas.UUCP (Brian T. Schellenberger) (07/02/88)
So put the *most commonly used* fields early to optimize access and sort large-to-small to optimize space. Tradeoffs between these two considerations vary widely. But especially if you have one field you use a lot, try to put it first regardless of size; the first field has an offset of zero, ans this is more efficiently accessed on (to put in mildly) a wide variety of machines. -- --Brian, __________________________________________________ the man from |Brian T. Schellenberger ...!mcnc!rti!sas!bts Babble-On |104 Willoughby Lane work: (919) 467-8000 x7783 ____________________________|Cary, NC 27513 home: (919) 469-9389
carlp@iscuva.ISCS.COM (Carl Paukstis) (07/02/88)
In article <531@philmds.UUCP> leo@philmds.UUCP (L.J.M. de Wit) writes: [...] >therefore, there may be unnamed holes in a structure. > >which explains everything, and frustrates any hope on optimization >(only the left-to-right puzzles me, most program text being written >top-to-bottom; B.T.W. what do Chinese program texts look like ? 8-). All the ones I've seen look pretty much like yours and mine, since they are of course written in English. On U.S.- (and Japan)- built equipment. The Chinese programmers who were unfortunate enough to have me as their C instructor were quite good at programming and logic. However, they were very poor at constructing meaningful data names and meaningful comments in the code. (Naturally, I would be much worse trying to write comments in Chinese. But I got REAL good at using chopsticks.) I guess I've debugged worse code than they wrote, but 'wdate', 'wwdate', 'wwwdate', and 'www' all appeared in several functions, for example. (I now return you to your regularly-scheduled debate about NULL FORTRAN.) -- Carl Paukstis +1 509 927 5600 x5321 |"I met a girl who sang the blues | and asked her for some happy news UUCP: carlp@iscuvc.ISCS.COM | but she just smiled and turned away" ...uunet!iscuvc!carlp | - Don MacLean
jfh@rpp386.UUCP (John F. Haugh II) (07/02/88)
In article <254@obie.UUCP> wes@obie.UUCP (Barnacle Wes) writes: >A little further though might show this idea to have some far-reaching >bad karma. It would be very difficult to write a file system portable >across machines of varying architecture (i.e. Idris) if the compiler >on each machine can arbitrarily re-arrange structures to suit its own >whim. it could be serious for any language to not specify how it rearranges structures. it could make it impossible for separate compilation to work, period. imagine if part of the strategy was that large sized code files had their structures packed one way, while small sized code files went a different way. imagine worse still that the implementation didn't have to tell you which one it picked! - john. -- John F. Haugh II +--------- Cute Chocolate Quote --------- HASA, "S" Division | "USENET should not be confused with UUCP: killer!rpp386!jfh | something that matters, like CHOCOLATE" DOMAIN: jfh@rpp386.uucp | -- with my apologizes
wes@obie.UUCP (Barnacle Wes) (07/05/88)
In article <254@obie.UUCP> I wrote: % It would be very difficult to write a file system portable % across machines of varying architecture (i.e. Idris) if the compiler % on each machine can arbitrarily re-arrange structures to suit its own % whim. In article <8192@brl-smoke.ARPA>, gwyn@brl-smoke.ARPA (Doug Gwyn ) replied: > Although the original poster was mistaken about the order in which > struct members are assigned addresses, it is nonetheless impossible to > achieve binary file transportability simply by (acceptable) constraints > on C struct format. There is a LOT more to binary data transportability > than byte padding, alignment, and sequencing. True. I was just pointing out that if the compiler was able to re-order the structure, you could obtain this portability at the source level at all. You would have to write code to read in the structure from the mass storage and then assign it to the individual elements of the in- memory structure. I believe Idris assures that all disk reads and writes are done in a common format, and the structure elements fall into place as the bytes and/or words are swapped as they are read and written. Structure ordering does not result in portability, but lack of structure ordering (nearly) precludes portability. Perhaps the compiler could be signalled when not to `optimize' the structure ordering - a `volatile' structure?!?!?!? ;-O -- {hpda, uwmcsd1}!sp7040!obie!wes "Happiness lies in being priviledged to work hard for long hours in doing whatever you think is worth doing." -- Robert A. Heinlein --
flaps@csri.toronto.edu (Alan J Rosenthal) (07/06/88)
On optimizing space by ordering the struct fields by the sizes of the elements, nevin1@ihlpf.UUCP (00704a-Liber,N.J.) writes: >This is not (necessarily) true! For instance: > >sizeof(long) === 8 >sizeof(short) === 5 >sizeof(char) === 1 > >Also suppose that alignment for shorts and longs occurs on even addresses >(two byte boundaries), while chars can align on single byte boundaries. Aha! This is inconsistent. If shorts must be even-aligned, sizeof(short) would have to report 6, not 5. Consider an array 5 of short, which must have size 29 or 30 to allow alignment, and which also must have sizeof(array) == 5 * sizeof(short). Going through your example again, you will see that, if sizeof(short) is 6 and thus a wasted byte follows all shorts, it is still most space-efficient to put the chars after the shorts. ajr -- - Any questions? - Well, I thought I had some questions, but they turned out to be a trigraph.
nevin1@ihlpf.ATT.COM (00704a-Liber) (07/08/88)
In article <3459@rpp386.UUCP> jfh@rpp386.UUCP (The Beach Bum) writes: >it could be serious for any language to not specify how it rearranges >structures. it could make it impossible for separate compilation to >work, period. Not quite true. As long as the compiler internally arranges the fields in a structure the same way, no problems occur. There is no need for you, the user of a compiler, to know what order fields are stored in, as long as the compiler is self-consistent (unless you are doing something like a block move into a structure). -- _ __ NEVIN J. LIBER ..!ihnp4!ihlpf!nevin1 (312) 510-6194 ' ) ) You are in a little twisting maze of / / _ , __o ____ email paths, all different. / (_</_\/ <__/ / <_ These are solely MY opinions, not AT&T's, blah blah blah
faustus@ic.Berkeley.EDU (Wayne A. Christopher) (07/08/88)
In article <5233@ihlpf.ATT.COM>, nevin1@ihlpf.ATT.COM (00704a-Liber) writes: > >it could be serious for any language to not specify how it rearranges > >structures. it could make it impossible for separate compilation to > >work, period. > > Not quite true. As long as the compiler internally arranges the fields in > a structure the same way, no problems occur. (1) What if I write a binary data file (with structures), re-compile my program (not having realized that somebody installed the new compiler with structure optimization) and then try to read it back in? (2) The system libraries have been compiled with stupid pcc, which doesn't do structure re-ordering. My compiler does re-ordering, so when I call a library function that returns a standard structure (like struct passwd), I'm screwed. (3) For that matter, what if I want to compile half my code with one compiler and half with another? (This isn't silly -- I've written libraries that other people use, and want to use saber with. Saber doesn't understand gcc's symbol tables, but I would rather give up saber than gcc. So I compile my library with pcc and the rest of my program with gcc, so I can get good quality code for part of the program and the other people can get saber.) Wayne
rob@raksha.eng.ohio-state.edu (Rob Carriere) (07/08/88)
In article <4347@pasteur.Berkeley.Edu> faustus@ic.Berkeley.EDU (Wayne A. Christopher) writes: >In article <5233@ihlpf.ATT.COM>, nevin1@ihlpf.ATT.COM (00704a-Liber) writes: >> > [separate compilation is impossible with structure optimization >> > that is not pre-arranged] >> [not true, as long as the compiler is self-consistent] > [various counterexamples] Not to mention, what if you're debugging, and part of your program is compiled *with* and part *without* optimization? I've lost count of how many times I've had to do that, but each every one of them I sure was glad when the compiler turned out not to be outsmarting itself. No, you say, either you optimize, or you don't; half-half is asking for trouble! Sure is, but when the optimized half is some commercial library your site doesn't even have the sources for, there isn't much you can do but ask for trouble and hope it's going to be out of stock. Rob Carriere "I like HLL's, but when push comes to shove, I want to know what the compiler is doing behind my back."
gwyn@brl-smoke.ARPA (Doug Gwyn ) (07/08/88)
In article <4347@pasteur.Berkeley.Edu> faustus@ic.Berkeley.EDU (Wayne A. Christopher) writes: >(1) What if I write a binary data file (with structures), re-compile my >program (not having realized that somebody installed the new compiler >with structure optimization) and then try to read it back in? This sort of change does occasionally occur. Gould changed their calling sequence between two releases of UTX/32. At least one VAX C compiler packs struct members more tightly than the original UNIX 32V PCC. And so on. Mixing output from different compilers has always been hazardous. This and related issues fall into what X3J11 terms the "quality of implementation" bin. The only constraint on such behavior lies in its acceptability to customers. It really isn't proper for the language standard to try to nail down such implementation-specific details; in fact it's extremely hard to write such specifications in a way that applies reasonably to all implementations. Thus it is considered overspecification and is not done.
jfh@rpp386.UUCP (John F. Haugh II) (07/09/88)
In article <5233@ihlpf.ATT.COM> nevin1@ihlpf.UUCP (00704a-Liber,N.J.) writes: >In article <3459@rpp386.UUCP> jfh@rpp386.UUCP (The Beach Bum) writes: >>it could be serious for any language to not specify how it rearranges >>structures. it could make it impossible for separate compilation to >>work, period. > >Not quite true. As long as the compiler internally arranges the fields in >a structure the same way, no problems occur. There is no need for you, the >user of a compiler, to know what order fields are stored in, as long as the >compiler is self-consistent (unless you are doing something like a block >move into a structure). provided there exists exactly one compiler in the entire universe. for without the assurance, via an agreed upon or written standard, that the structures are arranged in a common fashion, no two ``self consistent'' compilers are neccessarily going to produce the same structure ordering. and therein lies the beauty of a standard. while separate compilation may not be such a huge issue, using multiple compilers on a single machine, is. - john. -- John F. Haugh II +--------- Cute Chocolate Quote --------- HASA, "S" Division | "USENET should not be confused with UUCP: killer!rpp386!jfh | something that matters, like CHOCOLATE" DOMAIN: jfh@rpp386.uucp | -- with my apologizes
smryan@garth.UUCP (Steven Ryan) (07/11/88)
>>>it could be serious for any language to not specify how it rearranges >>>structures. it could make it impossible for separate compilation to >>>work, period. >> >>Not quite true. As long as the compiler internally arranges the fields in >>a structure the same way, no problems occur. There is no need for you, the I guess I'm just paranoid--I only write out structures if I reread them with some program. Otherwise I flatten them into a format I know I can control.