How to eliminate unused elements in structures?

Question

Background

I am working on a modular architecture for embedded devices where different abstraction layers have to communicate with each others. The current approach is to have plenty of functions, variables and defines mangled with the module name they belong to.

This approach is a bit painful and I would like to define some kind of common interfaces for the API. The key idea is to get a better understanding of what modules share the same HAL interface.

Proposal

I would like to use a OOP inspired architecture where I use structures as interfaces. All these structures are populated statically.

This solution looks nice but I might waste a lot of memory because the compiler doesn't know how to chop off structures and only keep what it really needs to.

The following example can be built with or without -DDIRECT and the behavior should be exactly the same.

Example

Source (test.c)

#include <stdlib.h>

int do_foo(int a) {
    return 42 * a;
}

#ifdef DIRECT
int (*foo)(int) = do_foo;
int (*bar)(int);
int storage;
#else
struct foo_ts {
    int (*do_foo)(int);
    int (*do_bar)(int);
    int storage;
} foo = {.do_foo = do_foo};
#endif

int main(char argc) {
    #ifdef DIRECT
    return foo(argc);
    #else
    return foo.do_foo(argc);
    #endif
}

Makefile

CFLAGS=-O2 -mthumb -mcpu=cortex-m3 -g --specs=nosys.specs
CC=arm-none-eabi-gcc

upper=$(shell echo $(1) | tr a-z A-Z)

EXEC=direct.out with_struct.out

all: $(EXEC)

%.out:test.c
    $(CC) $(CFLAGS) -D$(call upper,$(basename $@)) -o $@ test.c
    size $@

Output

One can notice that the memory footprint used with the struct variant is bigger because the compiler doesn't allow itself to remove the unused members.

arm-none-eabi-gcc -O2 -mthumb -mcpu=cortex-m3 -g \
                  --specs=nosys.specs -DDIRECT -o direct.out test.c
size direct.out
   text    data     bss     dec     hex filename
    992    1092      36    2120     848 direct.out
arm-none-eabi-gcc -O2 -mthumb -mcpu=cortex-m3 -g \
                  --specs=nosys.specs -DWITH_STRUCT -o with_struct.out test.c
size with_struct.out
   text    data     bss     dec     hex filename
    992    1100      28    2120     848 with_struct.out

Question

With this example I demonstrate that using a structure is good for readability and modularity, but it could decrease efficiency and it increases the memory usage.

Is there a way to get the advantages of both solutions? Said differently, is there a way to tell the compiler to be smarter?

OOP?

Following the comments on this question, one suggestion is to use C++ instead. Unfortunately, the same issue would occur because a Class with unused members will never be simplified by the compiler. So I am falling in the same trap with both languages.

Another raised point was the reason for unused members in structures. To address this question we can imagine a generic 3-axes accelerometer used in an application where only 1 axis is used. The HAL for this accelerometer could have the methods read_x_acc, read_y_acc and read_z_acc while only read_x_acc is used by the application.

If I declare a class in C++ or a structure in C the function pointers for unused methods/functions will still consume memory for nothing.

Answer 1

Let me first show you a possible approach regarding your edit, where your current interface has three functions, but sometimes you would need only one of them. You could define two interfaces:

typedef struct I1DAccel
{
    double (*read)(void);
} I1DAccel;

typedef struct I3DAccel
{
    union
    {
        I1DAccel x;
        struct
        {
            double (*read_x)(void);
        };
    };

    union
    {
        I1DAccel y;
        struct
        {
            double (*read_y)(void);
        };
    };

    union
    {
        I1DAccel z;
        struct
        {
            double (*read_z)(void);
        };
    };
} I3DAccel;

Then you can make the implementation of the Accelerometer do this:

I1DAccel accel_x = { read_x_acc };
I1DAccel accel_y = { read_y_acc };
I1DAccel accel_z = { read_z_acc };
I3DAccel accel =
{
    .read_x = read_x_acc,
    .read_y = read_y_acc,
    .read_z = read_z_acc,
};

With proper link-time optimizations, the compiler could then throw away any of these global structs that isn't used by application code.

Of course, you will consume more memory if one part of your code requires only accel_x while another part requires the whole accel. You would have to hunt down these cases manually.

---

Of course, using "interface" structs, you will always consume more memory than without them, the pointers have to be stored somewhere. Therefore, the typical approach is indeed to just prepend the module name to the functions and call them directly, like e.g. in case of such an accelerometer:

typedef int acchndl; // if you need more than one accelerometer

double Accel_read_x(acchndl accel);
double Accel_read_y(acchndl accel);
double Accel_read_z(acchndl accel);

This is conceptually similar to what you would do in e.g. C++:

class Accel
{
    double read_x();
    double read_y();
    double read_z();
};

double Accel::read_x()
{
    // implementation here
}

With the plain C above, instead of an instance pointer, you can use any other type of "object handle", like demonstrated with the typedef to int, which is often an advantage for embedded code.

Answer 2

This solution looks nice but I might waste a lot of memory because the compiler doesn't know how to chop off structures and only keep what it really needs to.
...
Is there a way to get the advantages of both solutions? Said differently, is there a way to tell the compiler to be smarter?

One problem is 'C' compiles things as a module (compilation unit) and there is often no easy way to know what will and will not be used in a structure. Consider the structure can be passed from module to module as you propose. When compiling one module, there is no context/information to know that some other module will use the structure or not.

Okay, so that leads to some possible solutions. gcc has the option -fwhole-program ^{See: -fipa-struct-reorg} as well as gold and LTO. Here you must structure your makefile so that the compiler (code generator) has all of the information available to know if it may remove structure members. This is not to say that these options will do what you want with a current gcc, just that they are a requirement to get things to work.

---

C++

You can do most anything in 'C' that you can in C++; just not as programmer efficiently. See: Operator overloading in 'C'. So how might a 'C' compiler implement your virtual functions? Your C++ virtuals might look like this underneath,

struct foo_ts_virtual_table {
    int my_type /* RTTI value for polymorphism. */
    int (*do_foo)(int);
    int (*do_bar)(int);
} foo_vtable = {.my_type = ENUM_FOO_TS; .do_foo = foo};

struct foo_ts {
    void * vtable; /* a foo_ts_virtual_table pointer */
    int storage;
} foo = {.vtable = foo_vtable};

This is a win memory wise if you have multiple foo_ts structures. A down side of this is that a function pointer is difficult to in-line. Often a simple functions body maybe less than the call overhead on an ARM CPU. This results in more code memory and slower execution.

C++ compilers will be geared to eliminate these extraneous functions, just because this is a common issue in C++. A 'C' compilers analysis is confounded by your custom code/notation and the language definition of structure and compilation units.

---

Other possibilities are to wrap the function calls in macros and emit data to a non-linked section. You can examine the non-linked section to see whether or not to include a function (and pointer) in the final link. What is a win or not depends on lots of different design objectives. It is certainly going to complicate the build process and confound other developers.

As well, the ARM Linux MULTI_CPU maybe of interest. This is only to eliminate function pointers if only one 'type' is needed at run time.

If you insist on function pointers, there will be occasions where this actually generates more code. C++ compilers will do book keeping to see when a virtual might be in-lined as well as possibly not emitting unused member functions in a virtual table (and the implementation of the function). These issues maybe more pronounced than the extra structure overhead.