11 ms·
C is, of course, totally up for writing generic functions already. The patten I like most is a struct of const function pointers, instantiated as a const global
by JonChesterfield 2y ago
C is, of course, totally up for writing generic functions already. The patten I like most is a struct of const function pointers, instantiated as a const global, then passed by address to whatever wants to act on that table.
Say you took a C++ virtual class, split the vtable from the object representation, put the vtable in .rodata, passed its address along with the object. Then write that down explicitly instead of the compiler generating it. Or put the pointer to it in the object if you must. Aside from &mod or similar as an extra parameter, codegen is much the same.
If you heed the "const" word above the compiler inlines through that just fine. There's no syntactic support unless you bring your own of course but the semantics are exactly what you'd want them to be.
Minimal example of a stack of uint64_t where you want to override the memory allocator (malloc, mmap, sbrk etc) and decided to use a void* to store the struct itself for reasons I don't remember. It's the smallest example I've got lying around. I appreciate that "generic stack" usually means over different types with a fixed memory allocator so imagine there's a size_t (*const element_width)() pointer in there, qsort style, if that's what you want.
struct stack_module_ty
{
void *(*const create)(void);
void (*const destroy)(void *);
size_t (*const size)(void *);
size_t (*const capacity)(void *);
void *(*const reserve)(void *, size_t);
// This push does not allocate
void (*const push)(void *, uint64_t);
// pop ~= peek then drop
uint64_t (*const peek)(void *);
void (*const drop)(void *);
};
// functions can call the mod->functions or
// be composed out of other ones, e.g. push can be
// mod->reserve followed by mod->push
static inline uint64_t stack_pop(stack_module mod, void *s) {
uint64_t res = stack_peek(mod, s);
stack_drop(mod, s);
return res;
}
I like design by contract so the generic functions tend to look more like the following in practice. That has the nice trick of writing down the semantics that the vtable is supposed to be providing which tends to catch errors when implementing a new vtable.
static inline uint64_t stack_peek(stack_module mod, void *s) {
stack_require(mod);
stack_require(s);
#if STACK_CONTRACT()
size_t size_before = stack_size(mod, s);
size_t capacity_before = stack_capacity(mod, s);
stack_require(size_before > 0);
stack_require(capacity_before >= size_before);
#endif
uint64_t res = mod->peek(s);
#if STACK_CONTRACT()
size_t size_after = stack_size(mod, s);
size_t capacity_after = stack_capacity(mod, s);
stack_require(size_before == size_after);
stack_require(capacity_before == capacity_after);
#endif
return res;
}
- camel-cdr 2y ago> The patten I like most is a struct of const function pointers, instantiated as a const global, then passed by address to whatever wants to act on that table > If you heed the "const" word above the compiler inlines through that just fine. But only when the function it self is inlined, which you quite often don't want. If you sort integers in a bunch of places, you don't really want qsort to be inlined all over the place, but rather that the compiler creates a single specialized copy of qsort just for integers. With something as simple as qsort compilers sometimes do the function specialization, but it's very brittle and you can't rely on it. If it's not specialized nor inlines then performamce is often horible. IMO an additional way to force the compiler to specialize a function based on constant arguments is needed. Something like specifying arguments as "inline". IIRC, this library uses this style of generic programming with a very nice API: https://github.com/JacksonAllan/CC https://github.com/JacksonAllan/CC It's just unfortunate that everything needs to get inlined for good performance.
- JonChesterfield 2y agoSort of. If you want the instantiation model, you can go with forwarding functions (maybe preprocessor instantiated): void malloc_stack_drop(void *s) { stack_drop(&malloc_stack_global, s); } If you inline stack_drop into that and user code has calls into malloc_stack_drop, you get the instantiation model back. Absolutely agreed that this is working around a lack of compiler hook. The interface I want for that is an attribute on a parameter which forces the compiler to specialise with respect to that parameter when it's a compile time constant, apply that attribute to the vtable argument. The really gnarly problem in function specialisation is the cost metric, the actual implementation is fine - so have the programmer mark functions as a good idea while trying to work out the heuristic. Going to add that to my todo list, had forgotten about it.
- eqvinox 2y agoThe entire point of this discussion is to get the compiler to tell you when you're accidentally mixing up things — which you don't get with void pointers. Your example doesn't exhibit this particularly well, try looking at a generic simple linked list or so.