optimizing c structs layouts

Let's consider a simple c struct:

struct foo {
    const char * str;
    unsigned char flag;
    uint64_t len;
};

Suppose that this code is being run as a part of a program executing on a 64-bit machine: what would you expect the result of sizeof(struct foo) to be?

Most people that never had to mess with struct sizes and optimizations would guess that it should be 17...

... but it's 24! Why is that?

The reason for this behavior is that compilers optimize struct layouts for speed, and it's the modern norm that aligned memory accesses are the fastest way to access data.

This means that, depending on the type of field and cpu, your data will have some alignment and will be positioned such that that alignment is respected (or, such that field-address % field-alignment == 0).

size, alignment, padding

In the case of the previous example, pointers and 64-bit fields are 8B aligned on 64-bit machines, and this means that, in order to force a layout where everything in the struct is aligned, the compiler will generate some padding between the flag and len fields:

Now let's consider another example, where a struct like this is defined, on the same machine as before:

struct bar {
    const char * str;
    short s1;
    int i1;
    short s2;
    int i2;
};

How do we go about computing its size?

There are three rules:

• Struct fields want to be aligned with their own natural alignment.
• The overall struct alignment is equal to the alignment of its widest field
• If you had to put two structs of the same type side by side, the second one should be aligned to its alignment -- this means that structs must have trailing padding up to their alignment

Quick recap on basic types alignment and size for 64-bit machines:

Also remember that:

• Arrays have the alignment of their value type, and size that is sizeof(type) * elements number.
• Unions have the alignment and size of their widest member.

And you can use the super useful sizeof and _Alignof operators to get this information for your custom types. Note that _Alignof is available from C11 onward, and is called alignof starting with C23. It was always alignof from what I understand in C++, since C++11.

For more information, the bible on this topic is The Lost Art of Structure Packing, from which I learned almost everything I know about this, together with a lot of practice and hands-on experience.

optimizing your structs: stropt

This topic here is something that comes up rather frequently at work, where saving bytes here and there is super important when sending huge loads of data continuously in queues and whatnot.

In order to make my life easier, I wrote a tool that produces some statistics on a type you pass as input, with reference to a source file or code snippet, it's called stropt (struct optimizer).

Abathargh/stropt on GitHub

build & install

If you have a local go installation you can go right ahead and build or install the application directly:

git clone https://github.com/Abathargh/stropt
go build

// or, if you want to install this directly
go install github.com/Abathargh/stropt

Already compiled binaries for a list of os/archs combinations are also provided in the github release page:

stropt binaries

using the tool

You can either use stropt by passing the source to analyze as a string:

stropt "struct meta" "struct meta { int a; double d; float f[100];};"

Or you can pass a file in which the definition is contained:

// test.c
struct test {
  const char * str;
  unsigned char flag;
  const int * const iptr;
  char c;
};

stropt -file test.c "struct test" 

The tool can also provide a possible optimization for your types by using the -optimize flag, and it's aware of fields that are structs themselves:

Note that the verbose flag is used to show inner structs (and unions) along with their fields alignment and size.

what's next

This tool was written in go using the great modernc.org/cc C compiler front-end for parsing C code, and lipgloss from charmbracelet for the UI.

I'm writing this for myself but I'm happy to share it publicly; I'd like to make this a webapp for easier use directly in a browser, so probably that's the next thing I'm going to be working on!