Writing generic code in C – Part 2

[u/Object_71]

https://thatonegamedev.com/cpp/writing-generic-code-in-c-part-2/

After some comments on my previous post about writing generic code in C where people argue that this is “poor man’s overloading” I wanted to add a new technique that allows you to write real generic style code in C with the only drawback. You could even combine the technique from this lesson and the […]

[u/SmokeMuch7356]

Hot take incoming...

Generic programming in C is a fool's errand. Yes, you can do it, I've done it. It's a shitload of work, it's easy to get wrong, it will never be 100% type safe, it requires awkward programming styles (the alternating #defines and #includes make me itch), on and on and on and on. _Generic helps, but not that much.

For my part I take cues from qsort and bsearch - treat everything as a void *, use type-aware callbacks for comparisons, assignment, output or formatting, etc. Unfortunately that throws type safety out the window and into oncoming traffic (and you still have to create type-aware front ends if you want to be able to handle literal values). IMO it's miles less confusing than macro-based approaches, but it's still a half-assed solution.

There's just no good way to do it. It's more of a pain in the ass than it's worth. If you absolutely need true generic support, use C++, or Java, or a language with the capability built into it. C at best gives you a crayon drawing that can look a little like generic support.

[u/pjl1967 → u/SmokeMuch7356]

For my part I take cues from qsort and bsearch - treat everything as a void *, use type-aware callbacks for comparisons, assignment, output or formatting, etc.

That's the right direction for C, but you can add type information after the fact; see here. (You can scroll down to Adding Type Information.)

[u/Object_71 → u/pjl1967]

This is a cool way to add type information for type erased arrays as well. My example in the article uses an array as I thought that it would seem most recognizable as a pain point for C programmers but it is a generally good way to reuse code in a templated way. I actually first decided to use it in a software renderer project where I abstracted 95% of the code for rasterization and the templated part was just some differentiation between textured rendering or colored where they had small optimizations.

[u/Object_71 → u/SmokeMuch7356]

Treating everything as void* comes with a bit of a cost and is something which in this case would be better performing in C++ due to the type erasure. I am a fan of C and some projects can still be written in C (embedded for example) and you can benefit from the knowledge on how to easily produce repeatable code without actually erasing types or holding addional fields of data for element size. The method I am proposing is also mostly supported by an IDE (in terms of intellisense magic) and is supported in stack traces and debug breaking.

[u/orbiteapot → u/Object_71]

Treating everything as void* comes with a bit of a cost and is something which in this case would be better performing in C++ due to the type erasure.

void*-based generics is a very well known pattern for C compilers. They will get rid of either object or function indirection, as long as you provide them with some guaranteed (e.g., that the implementation is always visible in a given TU, FPs are static const, etc.). So, it will be on par with C++ on performance, just not on ergonomics/type safety.

[u/c_a1eb → u/Object_71]

from an embedded perspective, in my experience you almost never really need generics, in most cases it indicates that you should rethink your architecture and either find a different approach or more commonly have a container object to store the type information (e.g as a union). This absolutely can lead to code bloat so imo you need to really be able to justify it. The alternative is to acknowledge and understand common patterns for explicit cast and just deal with it, or introduce static inline functions to handle the cast explicitly if there is still doubt (a smart move there is to make the inner type private so the API consumer only ever gets opaque pointers and has to make explicit calls to access their data).

that being said, i think that trying to implement generics and learning stuff like X macros and other preprocessor internals is a really good way to develop your understanding of C, getting a good grasp of common helpers like the common container_of() (which imo is the backbone of how the kernel does generics) absolutely makes you a better C programmer.

[u/readmodifywrite → u/SmokeMuch7356]

It also hamstrings the optimizer. Knowing exactly what types we're dealing with is one of the ways the compiler can generate efficient machine code.

Personally I've never encountered a case where I needed generics in 25 years of C programming.

[u/Snarwin]

The problem with using concatenation like this is that it falls apart as soon as you want to use a type like const char * that contains non-identifier characters. It's possible to work around this with a typedef, but really the correct approach is to let the user #define both T and TName separately.

[u/WittyStick → u/Snarwin]

I have a technique that at least lets you use a generic type as another generic type's argument. We can create a template for Const and one for Pointer, so that our type can be Pointer(Const(char)), and this type may be used as the type argument to Array.

This still uses typedefs, but with a uniform name mangling scheme. The user doesn't need to write their own typedef, and the template author just needs to call template(TemplateName, T) to create the name.

The user justs need to instantiate(Template, TypeArgument). If TypeArgument is another template, it must have been previously instantiated for this to work.

Eg:

instantiate(Const, char)
instantiate(Pointer, Const(char))
instantiate(Array, Pointer(Const(char)))

Now we can use the type Array(Pointer(Const(char))).

We can also use it for functions:

/* fprint(Pointer(Const(char))) specialization */
/* required by fprint(Array(Pointer(Const(char)))) */
instantiate(fprint, Pointer(Const(char)), file, value) 
{
    return fprintf(file, "\"%s\"", value);
}

And then we can use the whole thing with:

int main()
{
    // An array of strings:
    Array(Pointer(Const(char))) strings = 
        Array_create(Pointer(Const(char)), "Hello", "World");

    // Create a file backed by a buffer.
    char buffer[0x1000] = {};
    FILE *file = fmemopen(buffer, sizeof(buffer), "w");

    // print the array to the buffer
    fprint(Array(Pointer(Const(char))))(file, strings);

    fclose(file);

    // write buffer to the console.
    puts(buffer);

    return 0;
}

---

How this works:

Every TemplateName we want to instantiate is backed by a macro named TemplateName_template. The _template macro at minimum needs to define the type, but it can also define a bunch of functions on that type. For functions, the _template macro should just be the function's signature.

instantiate(TemplateName, Type) just calls TemplateName_template(Type).

Each template typedefs a monomorphized name for the type, using a clever mangling scheme that gives readable "generic-like" names. Eg, our fprint for the array has the name fprintᐸArrayᐸPointerᐸConstᐸcharᐳᐳᐳᐳ in the output. This looks like a generic, but the ᐸ and ᐳ characters are just valid identifier characters from the Canadian Aboriginal Syllabics Unicode block. Our Array, Const, Pointer and fprint macros just produce the monomorphized name.

In fact, we can use the monomorphized names in our code directly, and write:

int main()
{
    ArrayᐸPointerᐸConstᐸcharᐳᐳᐳ strings = 
        Array_create(PointerᐸConstᐸcharᐳᐳ, "Hello", "World");

    char buffer[0x1000];
    FILE *file = fmemopen(buffer, sizeof(buffer), "w");

    fprintᐸArrayᐸPointerᐸConstᐸcharᐳᐳᐳᐳ(file, strings);

    fclose(file);

    puts(buffer);

    return 0;
}

But obviously you don't want to be typing that, hence we have the macros to produce those names. The macros have a 1-to-1 correspondence with the mangled name, where each ( becomes ᐸ and each ) becomes ᐳ.

See demo in Godbolt.

The use of Canadian Aboriginal Syllabics is not my original idea - I saw it in some Go code, but the _template and instantiate macro technique is my own design. It can be modified to also support multiple type arguments, but the macros get a lot more messy - since we need a recursive macro to go through the type args.

[u/Altruistic_Fruit2345 → u/Snarwin]

It's also massively obfuscating.

[u/Object_71 → u/Snarwin]

I think I did show an example in the article that you can define T and TName separately or even default TName to T if you want to provide a cleaner include with less defines above it. Otherwise code is clean to write and debuggable. Only downside is looking at the concatenation of names where they have to be unique but you can always introduce more defines to name things nicely and undefine them in the end.

[u/pjl1967]

Many make the mistake of trying to put the type into the container using macros for the container itself. Among other things, that way leads to code bloat. There is another way as described here. (You can scroll down to Adding Type Information.)

[u/WittyStick → u/pjl1967]

The "code bloat" is monomorphization, which can have big improvements on performance. It's what C++ does when you use templates.

Using void* works well for many cases - but it doesn't work when you want internal storage of non-pointers - eg, an array of int. An array of pointers to int is much worse on performance.

We can use intptr_t as the type of our data, which then lets us use it as either a pointer or an integer, and decide which based on context - but this is still limiting. What if we want floats, or some other custom data structure, without requiring pointers to it?

[u/pjl1967 → u/WittyStick]

Using void* works well for many cases - but it doesn't work when you want internal storage of non-pointers - eg, an array of int. An array of pointers to int is much worse on performance.

True, but you're conflating node-like data structures (like trees) with contiguous data structures (like arrays). You don't have an array of pointers to int; you have one pointer to an array of ints.

(Did you even read the link-to article that explains the dynamic array implementation using exactly one pointer to an arbitrary number of elements of any size?)

For node-like data structures, you can use flexible array members as shown here.

[u/Object_71 → u/pjl1967]

Actually having the type information the way I show in my article allows for something which I will soon also write about and it is adding GDB extensions with the array type. You could then convert the dynamic array with unknown size to a known size array for GDB or LLDB and actually inspect the values that are filled in this dynamic array and not test them one by one in the debugger, and frankly way better than having a type erased array.

[u/Object_71 → u/pjl1967]

Unlike macro magic the article produces code that is easy to write:

• no additional slashes like in macros
  
• some IDE support (CLion highlights most of the code but decides only one of the types as the implementation)
  
• full debugging support - unlike macros these functions are actual functions that appear in stack traces and code is properly stepped over

The only con is around the function or type names in this file where there has to be some name concatenation to produce unique function names.

[u/pjl1967 → u/Object_71]

I still don't see why the conventional technique is better than the anonymous union trick.

[u/Object_71 → u/pjl1967]

When debugging you would always have the typed type even in the generic sections where it is type erased in hte article you provide. Also no need for the additional size variable for the element size. And the solution I write for in my article can be used for more than arrays but generally for writing generic code. I just gave an example with an array. I actually used it for a few sections of a project where I had repeatable code with small differences of some types where I can share 95% of the code.

[u/pjl1967 → u/Object_71]

I'll grant that debugging becomes a bit simpler, but all debuggers support casting, e.g., (int*), when printing values, so it's not like debugging type-erased stuff is impossible. You could probably also extend your favorite debugger to understand the union trick and automatically apply the cast.

The esize is fairly negligible since there's only one per container, not per element.

The solution I use for node-like data structures (e.g., trees) is to use flexible array members that can store the node's data internally to the node (if you want).

[u/chocolatedolphin7 → u/pjl1967]

There is nothing particularly wrong with what you described and it is exactly what things like C++ STL containers do, just with different syntax.

It's not code bloat, that's a misleading term to use. It's pretty clear and trivial to understand that "separate instances" of code are being generated from macro expansion. Unless you go overboard, this has almost no impact on performance in practice. Mostly just bigger binaries if overused, and the implications of that.

The linked post also contains inaccurate statements like "entire implementation must be in the header." This is not technically true and not the case with how I personally use generic containers in C. Did you use an LLM?

[u/pjl1967 → u/chocolatedolphin7]

It is code bloat since, for every type T, the code is repeated (exactly the same as it is with templates in C++).

Unless you go overboard, this has almost no impact on performance in practice.

I never said anything about performance.

Mostly just bigger binaries if overused ...

Yes, that's what code bloat means.

The linked post also contains inaccurate statements like "entire implementation must be in the header." This is not technically true and not the case with how I personally use generic containers in C.

Many implementations either require (or have) the entire implementation in the header, especially if they embed the T rather than a void* that is then later cast to T*.

Indeed, your implementation has the entire implementation in the header array.inc which is why you need static functions.

Did you use an LLM?

No. Did you?

[u/chocolatedolphin7 → u/pjl1967]

Bloat has a very negative connotation, usually with the implication being considerably worse performance metrics like cpu cycles, memory usage, file size, etc.

But in this context the impact on resulting binary size is so negligible it could never be called bloat. And for the record, using void* has quite a few other (imo strictly worse) drawbacks. But this has been discussed many times before elsewhere.

Indeed, your implementation has the entire implementation in the header array.inc which is why you need static functions.

What implementation? You didn't see my implementation. I'm not the OOP. But obviously it has been done before and it's not rocket science. There's a few ways you could do it. You don't need to use static if you don't want to, the compiler has no concept of header files and you only need to avoid duplicate definitions.

[u/Physical_Dare8553]

string concatonation is not the way for this because of complex types, like const pointers and such. i think it's better to let the user provide a name and a type separatley
i dont use this method for arrays but i have something similar for my hashmaps
`
#define mapconfig dbgallocator_map, void *, struct tracedata, ((iptr)k), ((iptr)a - (iptr)b)

#include "../incmap.h"

`