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/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/Liquid_Magic → u/WittyStick]

Okay but… why? Like what’s the advantage of using glyphs from Canadian Aboriginal Syllabics in this context?

[u/WittyStick → u/Liquid_Magic]

Readability (of the object code).

The output is perfectly legible. It reads as if it were written like C++ templates. Contrast this to C++ name mangling schemes and you'll see they're completely unreadable.

It also normalizes names in a way that prevents ambiguous interpretation compared with typical concatenation schemes. For example, it's common to just do Array##T, which for a type like Int would produce ArrayInt. But what if we have some ArrayListInt in our output? It's non-obvious here whether that is some Array(List(Int)), or whether it was ArrayList(Int).

We can use an underscore prevent this ambiguous reading. Eg, Array_##T and List_##T. Then ArrayList(Int) would produce ArrayList_Int and Array(List(Int)) would produce Array_List_Int. Assuming the programmer does not use underscores in their type names. That resolves the problem for templates with one type argument, but where we have multiple (potentially variable) arguments and nesting, one delimiter isn't sufficient. We really want two delimiters - one to mark the start of a templates arguments and one to mark the end.

Ideally we want something that the programmer is very unlikely to type. Other than _ we don't really have any ASCII punctuation characters that can be used in identifiers (except maybe $, supported by GCC and Clang, but not all compilers). C compilers that support Unicode allow any XID_continue characters in identifier names - but most of these are just letters from other alphabets - punctuation and delimiters are typically still not permitted. The Canadian Aboriginal Syllabics is one exception - they're all valid XID_continue characters, but many look like punctuation characters. In this case the characters are perfect because they look almost the same as how generics are written in many languages.

There's none that look like a comma, so for eg, Map(String, Obj), we can use some other delimiter, such as ᙮ - giving MapᐸString᙮Objᐳ which is just a single identifier, and very readable.

[u/Liquid_Magic → u/WittyStick]

Okay cool. I get it now. Thanks! That was a great response! I think if it were me working alone I would only use glyphs that look similar to, but clearly distinct from, any character you can press on a US based keyboard. I would want it to me clear to me that a certain glyph isn’t a hyphen or greater-than character types on my keyboard but is instead a special character being used in a special way. This is because I would write the code, forget that used special characters, come back and make changes and then wonder why using a regular character in my changes breaks everything and loose my mind.

This reminds me of my original first year university C programming course in the 90’s. Most people used the VT-220 terminals connecting to a VAX/VMS system to work on their projects. I, however, bought a boxed copy of Borland Turbo C for MS-DOS. I wrote a “hello world” program and it wouldn’t compile. I lost my absolute shit for what felt like hours until I realized that somehow, someway, a weird white-space character was in my source code. It was a space or tab or line break - I forget what it was - but it was like something that the compiler didn’t like and freaked out about without being helpful.

So that’s why having any character I can’t type on my North American keyboard inside a source file freaks me out. It’s early-childhood-programmer trauma.

Thank you for coming to my TEDTalk.

[u/WittyStick → u/Liquid_Magic]

You wouldn't really type these (though you can) - you'd still typically call the macros that generate the names.

In the previous example, it only worked for a single type argument, but you can have it working for many arguments. Eg, we could define some Tuple template taking a variable number of arguments, and you would really want a mangling scheme that shows where the list ends.

Example of multiple argument name mangling. The macro foo is quite horrendous which is why I omitted it from the previous post - but it basically uses a known recursive macro trick to cycle through the varargs, and joins them all with ᙮.

Obviously to generate the tuple structure you'd need a recursive macro to fill out the fields of a struct. Ideally we'd want to name these fields _1, _2, _3, etc for uniformity, but I haven't figured out how to do this with a macro yet (for an arbitrary number of arguments). It's not too difficult if we cap the number of arguments.

[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/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/aalmkainzi → u/orbiteapot]

From benchmarks ive seen this isnt true. It calls an external function.

[u/orbiteapot → u/aalmkainzi]

Can I ask for a counterexample, then?

[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/aalmkainzi → u/SmokeMuch7356]

I've used a library named STC, which provide generic containers. Works pretty well

[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/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/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/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"

`

[u/theNbomr]

I cannot envision producing by hand, code that reads like what you're describing, ever.

However... I can easily imagine some kind of C source code generator that is the back end of some kind of tool leveraging it. I'm thinking of GUI producing tools or perhaps code to produce an implementation of network protocols a la ASN.1

There is a good bit of merit to your project in getting a lively discussion going between people who have some advanced knowledge and skills.

[u/massive_cerebrum]

A link to part 1 would be nice