75 Limits, and when not to — macros, SOLID, and back to the start

75.1 Macros — the useful, the cost, the ones to avoid#

Macros come with C object systems. They are useful for cutting down what is repetitive to write by hand and for bringing type checks back, and for the same reasons they are overused.

/* Macros that help an object system, and one that hurts.
   (1) container_of that refuses a pointer of the wrong type
   (2) a checked down-cast in the spirit of GObject's GTK_WIDGET(x)
   (3) a call-through-the-table macro that evaluates its argument twice --- and its fix */
#include <stddef.h>
#include <stdio.h>

/* (1) The comparison inside sizeof is never evaluated, but it must type-check:
   comparing pointers to different types is a constraint violation, so the compiler must
   say so --- and with -Werror a wrong `ptr` stops the build. */
#define container_of(ptr, type, member)                                   \
    ((void)sizeof((ptr) == &((type *)nullptr)->member),                   \
     (type *)((char *)(ptr) - offsetof(type, member)))

enum kind { KIND_CIRCLE = 0xC1, KIND_RECT = 0x4E };
struct shape;
struct shape_ops { enum kind kind; double (*area)(const struct shape *); };
struct shape  { const struct shape_ops *ops; };
/* base not first: container_of still works */
struct circle { double r; struct shape base; };

static double circle_area(const struct shape *s)
{
    const struct circle *c = container_of(s, const struct circle, base);
    return 3.0 * c->r * c->r;
}
static const struct shape_ops circle_ops = { KIND_CIRCLE, circle_area };
static const struct shape_ops rect_ops   = { KIND_RECT, nullptr };

/* (2) check the kind before trusting the cast; a wrong cast yields nullptr, not garbage.
   (It names `s` three times, so it too must be given a plain variable, never s++.) */
#define AS_CIRCLE(s) ((s) && (s)->ops->kind == KIND_CIRCLE                  \
                      ? container_of((s), struct circle, base) : (struct circle *)nullptr)

/* (3) looks harmless... */
#define SHAPE_AREA(s) ((s)->ops->area(s))
/* ...is safer as a function: the argument is evaluated once, and it type-checks */
static inline double shape_area(const struct shape *s) { return s->ops->area(s); }

static int evaluations;
static struct shape *next_shape(struct shape *s) { evaluations++; return s; }

int main(void)
{
    struct circle c = { .r = 2.0, .base.ops = &circle_ops };
    struct shape *s = &c.base;
    struct shape rect = { &rect_ops }, *other = &rect;

    printf("container_of: back to the circle, r = %g\n",
           container_of(s, struct circle, base)->r);
    /* container_of(&c.r, struct circle, base) would not compile: &c.r is a double *. */

    struct circle *ok = AS_CIRCLE(s), *no = AS_CIRCLE(other);
    printf("AS_CIRCLE(circle)    : %s\n", ok ? "a circle" : "nullptr");
    printf("AS_CIRCLE(rectangle) : %s\n", no ? "a circle" : "nullptr");

    evaluations = 0;
    double a = SHAPE_AREA(next_shape(s));
    printf("SHAPE_AREA(next_shape(s)) = %g, next_shape ran %d times\n", a, evaluations);
    evaluations = 0;
    a = shape_area(next_shape(s));
    printf("shape_area(next_shape(s)) = %g, next_shape ran %d time\n", a, evaluations);
    return 0;
}

container_of: back to the circle, r = 2
AS_CIRCLE(circle)    : a circle
AS_CIRCLE(rectangle) : nullptr
SHAPE_AREA(next_shape(s)) = 12, next_shape ran 2 times
shape_area(next_shape(s)) = 12, next_shape ran 1 time

75.1.1 Useful macros#

The example’s container_of checks the type with a comparison inside sizeof. The operand of sizeof is not evaluated, so there is no run-time cost, but it is type-checked — comparing pointers to different types is a constraint violation, so the compiler must issue a diagnostic, and with -Werror on, the build stops.

75.1.2 The cost of macros#

• Error messages point at the expanded code. A type error three macros deep shows an expression nobody ever wrote.
• Debuggers do not know macros. You cannot step into a one-line macro call.
• Arguments are evaluated more than once. That is (3) in the example. SHAPE_AREA(next_shape(s)) calls next_shape twice — with an argument that has side effects, the result is wrong. A static inline function doing the same evaluates its argument once, checks types and shows in the debugger.
• They hide control flow. A macro with a return or goto inside makes an exit that cannot be seen where it is called.

75.1.3 Macros to avoid#

CLASS(Circle, EXTENDS(Shape),
    FIELD(double, r)
    METHOD(double, area)
    OVERRIDE(Shape, draw))

There are three rules for macros.

1. One macro, one mechanical job. “Recover the outer struct from a member”, “make one set of boilerplate”.
2. A person must be able to write the expansion by hand. Do not use a macro whose expansion you cannot explain.
3. Do not erase type checks. A macro that hides a (T *) cast quietly accepts the wrong type too. Use macros to add checks.

What a function can do, do with a function. static inline functions have been there since C99, and they replace most “small, fast macros”.

75.2 Design principles — reading SOLID in C#

The name most often invoked in talk of object-oriented design is SOLID. It is the initials of five design principles that Robert C. Martin set out in articles in the 1990s and in “Design Principles and Design Patterns” (2000); the collective name SOLID was coined by Michael Feathers around 2004. Two of the five are older — the open–closed principle comes from Bertrand Meyer’s 1988 book Object-Oriented Software Construction, and the substitution principle from Liskov (1987), seen in chapter 71.

As the right-hand column shows, the five principles sit directly on techniques this part has already covered. None of them needs new syntax in C. Their use is plain too — a named principle shortens the talk in code review. “This table breaks interface segregation” stands in for a long explanation.

But SOLID gives principles, not laws. Four of the five (all but S) lean towards adding a layer of indirection — a table, a pointer, an abstraction. The price of that layer is exactly the subject of the next two sections (memory and caches, and flow). Erect open–closed and dependency inversion where nothing is going to change, and all you gain is more places to read. It is not too late to build the abstraction when a second implementation actually appears. And remember once more that in C what keeps these principles is not the compiler but documentation and review — the same story as the warning against “just do it well” in chapter 70.

75.3 The limits of object orientation — memory and caches#

So far this has been about imitating well in C. Now for the limits of the thing imitated — object orientation itself. They come along whether you imitate it in C or write it in C++.

The basic shape of object orientation is “one object = one separately allocated struct, pointed to by a pointer”. Count what that shape leaves in memory and the cache, with the eyes of chapter 51:

• A scattered heap. malloc each object and the objects land here and there in the heap. Walking a list of objects becomes pointer chasing.
• Object headers. A table pointer, a reference count, a kind number — the header attached to each object is sometimes bigger than the real data. Make a point (8 bytes) into an object and a header of that size comes with it.
• An array of objects is AoS. An object keeps its own state together — a layout that hurts work sweeping one field of many objects.
• Indirect calls and blocked inlining. The “Polymorphism” section of chapter 71, and chapter 73, which measures the cost.

The same job measured in three shapes — the total area of a million shapes, ① with objects and tables ② with an array of tagged structs and a switch ③ with one array per kind:

/* The total area of a million shapes, computed three ways.
   (1) objects: each shape allocated on its own, called through its method table
   (2) tagged structs in one array, a switch on the tag
   (3) one array per kind of shape, a plain loop per array
   ★ This program measures time and prints ratios only. */
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N      (1u << 20)
#define ROUNDS 5

/* (1) the object way */
struct shape;
struct shape_ops { double (*area)(const struct shape *); };
struct shape { const struct shape_ops *ops; };
struct circle { struct shape base; double r; };
struct rect   { struct shape base; double w, h; };
static double circle_area(const struct shape *s)
{ const struct circle *c = (const struct circle *)s; return 3.14159 * c->r * c->r; }
static double rect_area(const struct shape *s)
{ const struct rect *r = (const struct rect *)s; return r->w * r->h; }
static const struct shape_ops circle_ops = { circle_area }, rect_ops = { rect_area };

/* (2) the tagged way */
enum kind { CIRCLE, RECT };
struct tagged { enum kind kind; double a, b; };

/* (3) the per-kind way */
static double *radius, *width, *height;
static uint32_t n_circles, n_rects;

static struct shape **objs;
static struct tagged *tags;
static volatile double sink;

static double now(void) { return (double)clock() / CLOCKS_PER_SEC; }
static double by_table(void)
{
    double t = now(), s = 0;
    for (uint32_t i = 0; i < N; i++) s += objs[i]->ops->area(objs[i]);
    sink = s; return now() - t;
}
static double by_switch(void)
{
    double t = now(), s = 0;
    for (uint32_t i = 0; i < N; i++)
        switch (tags[i].kind) {
        case CIRCLE: s += 3.14159 * tags[i].a * tags[i].a; break;
        case RECT:   s += tags[i].a * tags[i].b; break;
        }
    sink = s; return now() - t;
}
static double by_kind(void)
{
    double t = now(), s = 0;
    for (uint32_t i = 0; i < n_circles; i++) s += 3.14159 * radius[i] * radius[i];
    for (uint32_t i = 0; i < n_rects; i++)   s += width[i] * height[i];
    sink = s; return now() - t;
}

static int cmp(const void *a, const void *b)
{ double x = *(const double *)a, y = *(const double *)b; return (x > y) - (x < y); }
static double median(double (*job)(void))
{
    double r[ROUNDS];
    job();
    for (int i = 0; i < ROUNDS; i++) r[i] = job();
    qsort(r, ROUNDS, sizeof *r, cmp);
    return r[ROUNDS / 2];
}

int main(void)
{
    objs = malloc(N * sizeof *objs); tags = malloc(N * sizeof *tags);
    radius = malloc(N * sizeof *radius);
    width = malloc(N * sizeof *width);
    height = malloc(N * sizeof *height);
    if (!objs || !tags || !radius || !width || !height)
        { puts("out of memory"); return 1; }

    uint64_t rng = 0x9E3779B97F4A7C15u;
    for (uint32_t i = 0; i < N; i++) {
        rng ^= rng << 13; rng ^= rng >> 7; rng ^= rng << 17;
        double x = (double)(i % 100) / 10.0;
        if (rng >> 63) {                     /* kinds come in random order */
            struct circle *c = malloc(sizeof *c);
            if (!c) { puts("out of memory"); return 1; }
            *c = (struct circle){ { &circle_ops }, x };
            objs[i] = &c->base;
            tags[i] = (struct tagged){ CIRCLE, x, 0 };
            radius[n_circles++] = x;
        } else {
            struct rect *r = malloc(sizeof *r);
            if (!r) { puts("out of memory"); return 1; }
            *r = (struct rect){ { &rect_ops }, x, 2 };
            objs[i] = &r->base;
            tags[i] = (struct tagged){ RECT, x, 2 };
            width[n_rects] = x; height[n_rects++] = 2;
        }
    }

    double t = median(by_table), s = median(by_switch), k = median(by_kind);
    printf("%u shapes, circles and rectangles in random order\n", N);
    if (k > 0) {
        printf("  method table : %5.1f times as long as per-kind arrays\n", t / k);
        printf("  tag + switch : %5.1f times as long as per-kind arrays\n", s / k);
    } else puts("  the clock is too coarse on this machine to tell them apart");

    for (uint32_t i = 0; i < N; i++) free(objs[i]);
    free(objs); free(tags); free(radius); free(width); free(height);
    return 0;
}

== -O0
1048576 shapes, circles and rectangles in random order
  method table :   4.3 times as long as per-kind arrays
  tag + switch :   3.1 times as long as per-kind arrays
== -O2
1048576 shapes, circles and rectangles in random order
  method table :   5.9 times as long as per-kind arrays
  tag + switch :   3.5 times as long as per-kind arrays

The result has to be read honestly. ① is slow not only “because virtual calls are slow”. The objects are allocated separately and pointers have to be followed; the kinds are mixed at random, so the indirect branch is often mispredicted; and the compiler cannot unroll the loop or vectorise it (compute several values with one instruction). ② is slowed by the same random branching. ③ does the same operation per kind on dense arrays, with no branches and no indirect calls. There are several causes, and all of them come from the shape “one object at a time”.

75.4 The limits of object orientation — the flow of a program#

Object orientation has another cost: it makes the flow of a program harder to read.

• The yo-yo problem. With deep inheritance, finding out what one method does means going up and down between derived and base — here the derived one, there the base one, and inside that a call to the derived override again. Taenzer, Ganti and Podar gave the phenomenon its name in 1989.
• The fragile base class. Only the inside of the base was changed, and the derived kind breaks, because it was relying on the base’s implementation (such as which of the base’s methods calls which). Inheritance hands down implementation, so the heir is tied to the insides of what it inherited.
• Inverted flow. In a system built from callbacks and overrides, “who calls me, and when?” cannot be known from my own code. The framework calls. The flow shows only when followed in a debugger.
• Hidden state. Objects hide their state. That is how they keep invariants, but why the same method called twice gives different results cannot be seen from outside. It makes testing hard, and harder still when several threads touch it.

Many of these problems come from inheritance. So Design Patterns (Gamma, Helm, Johnson and Vlissides, 1994) set down the principle “favour object composition over class inheritance”. Composition holds another object as a member and uses only its public behaviour — it is not tied to the insides. The same goes for the C imitation: “composition”, holding the parts needed as members and calling their functions, is usually simpler than “inheritance” by making the base struct the first member.

75.5 Where things are going now — object orientation is not a cure-all#

In the 1990s object orientation was taken as the right answer in programming. Today’s languages treat it as one tool among others.

75.5.1 The expression problem — what changes more often?#

Objects and tables, or tags and switch (sum types)? There is a named criterion for choosing between the two. It is what Philip Wadler called “the expression problem” in 1998 — with data defined by cases, can new cases and new functions be added without recompiling existing code, while keeping static type safety?¹

• Objects and tables (polymorphism) make adding a new case (a new kind of shape) easy — one new table. But adding a new operation (“perimeter” for every shape) means changing every kind.
• Tags and switch (sum types) make adding a new operation easy — one new switch function. But adding a new case means changing every switch.

So the question is not “which is more object-oriented?” but “what gets added more often in this program?”.

75.5.2 C’s enum-match#

C has an imitation of sum types too — tagged unions (chapter 49) and switch. And C compilers catch missing branches as well.

/* The closed-set alternative to a method table: a tag, a union, and a switch.
   No default label, on purpose: then the compiler can tell us when a new kind
   of shape has been added and this function was not taught about it. */
#include <stdio.h>

enum shape_kind {
    SHAPE_CIRCLE,
    SHAPE_RECT,
#ifdef ADD_TRIANGLE
    SHAPE_TRIANGLE,              /* the new kind, added later */
#endif
};

struct shape {
    enum shape_kind kind;
    union {
        struct { double r; } circle;
        struct { double w, h; } rect;
#ifdef ADD_TRIANGLE
        struct { double base, height; } triangle;
#endif
    };
};

static double area(const struct shape *s)
{
    switch (s->kind) {
    case SHAPE_CIRCLE: return 3.0 * s->circle.r * s->circle.r;
    case SHAPE_RECT:   return s->rect.w * s->rect.h;
    }
    return 0.0;                  /* not reached for a valid kind */
}

int main(void)
{
    struct shape a[] = {
        { .kind = SHAPE_CIRCLE, .circle = { 1.0 } },
        { .kind = SHAPE_RECT,   .rect = { 2.0, 3.0 } },
    };
    double total = 0;
    for (size_t i = 0; i < sizeof a / sizeof a[0]; i++) total += area(&a[i]);
    printf("total area %g\n", total);
    return 0;
}

two kinds   : total area 9
three kinds : the build stops ---
  enumeration value ‘SHAPE_TRIANGLE’ not handled in switch [-Werror=switch]

The trick is to give the switch no default. Then, when a new value (the triangle) is added to the enum, -Wswitch, part of -Wall, says “this switch does not handle the triangle”. Add a default and the compiler reads it as “the rest is handled here” and says nothing. It is not as strict as Rust’s match — it cannot stop an out-of-range integer getting into the tag — but for a closed set of kinds it is well worth using.

75.6 Do not get carried away by object orientation#

Object orientation is a tool. Get carried away by a tool and problems start to look like the tool — to someone holding a hammer, everything looks like a nail. Make everything an object, every relation inheritance and every function a table, and every line of code pays for the limits above.

The last row deserves stress. A C struct is an excellent tool in its own right. Not every struct needs to be an object.

75.7 Back to the beginning#

At the start of this part (chapter 70) Alan Kay’s picture was put aside. In 2003, when a reader asked him what object orientation is, Kay answered by e-mail:

“OOP to me means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things.”²

Late binding means deciding which code to call only when the program runs. In the same message he wrote that he had left inheritance out as a built-in feature “until I understood it better”. The object he first pictured was not a class hierarchy but something like a biological cell, wrapped in a membrane, hiding its inside and communicating with the outside only by messages.

Look at this part again with that picture and the plainest imitation, the opaque type, looks different. A C opaque type and its set of functions have no classes and no inheritance — yet they hide their inside (not even the size can be seen), communicate only through fixed functions, and spare the outside a recompile when the version changes (late binding). The plainest of the imitations is the closest to the first idea of object orientation.

The heart of object orientation is not syntax but boundaries: what to keep inside and what to offer outside, and what promise to make across the boundary. That question can be asked perfectly well in C. And when it is asked in C, making structure keep the boundary is part of the programmer’s job.

75.8 Summary#

75.9 Closing Part XI#

The part on imitating object orientation in C is over. We told apart the two meanings of the word “object” and set up the imitation’s bare-handed tools (chapter 70), used them to build polymorphism and inheritance and made them survive versions and lifetimes (chapter 71). We built, sealed and looked up tables at run time (chapter 72), and measured on this machine what one call through a table costs (chapter 73). We toured the object systems others have built in C and the papers that measured them (chapter 74), and decided where to stop (this chapter). One theme runs through the six chapters: every part of the imitation is a promise, and a good imitation makes structure, not people, keep that promise.

The next part reads the largest bundle of promises C has offered from the start — the standard library. Its first chapter lays out the terrain: what toolboxes there are, and why this library looks so thin and so old.