6 ms·
Type-erased generic functions for C: A modest non-proposal
- kazinator 2y agoC has generic selection via _Generic. You just have to write your generic function as a macro which uses that in its expansion. It has limitations. It's powerful enough though that for example in the current draft C, I believe, functions like strchr are now overloaded such that if the argument is const char *, you get the const-qualified return type, otherwise plain. There's a header of type generic math as well.
- rwmj 2y agoMeh, you just need more macros ... https://gitlab.com/nbdkit/nbdkit/-/blob/296b9dd041fdbcbaa73119db1ff58c5e115cc9b8/common/utils/vector.h#L112 https://gitlab.com/nbdkit/nbdkit/-/blob/296b9dd041fdbcbaa731...
- eqvinox 2y ago<300 lines? Peanuts! ;D https://github.com/FRRouting/frr/blob/master/lib/typesafe.h https://github.com/FRRouting/frr/blob/master/lib/typesafe.h https://docs.frrouting.org/projects/dev-guide/en/latest/lists.html https://docs.frrouting.org/projects/dev-guide/en/latest/list...
- naasking 2y agoThat monomorphizes every definition, and the point of this proposal was to avoid that.
- rwmj 2y agoThat's true, although I wonder if a "sufficiently smart compiler" could combine compatible definitions. Also note it's in a header file and most of these functions are minimal enough they would be inlined.
- eqvinox 2y agoI'd distinguish here and not label one-liner "cast wrappers" as monomorphization. And then you can in fact do a lot with macros. (My definition of a "cast wrapper" is: function body contains exactly one function call, mostly forwarding arguments. Pointer offsets¹ on arguments/retval are allowed, as well as adding sizeof/offsetof/constant integer arguments, but nothing else.) ¹ this may include some conditionals to keep NULL as NULL when applying a pointer offset. I would expect the compiler to be able to optimize these away in 99% of cases, but TBH I don't care if it doesn't and I'm littering a bunch of small wrapper functions.
- variadix 2y agoYou can get better properties by using the include itself to do the macro expansion, e.g. #define VECTOR_TYPE int #include “vector.h” This will let you step into the macro generated functions in GDB and doesn’t require putting the function creation in macros (no backslashes, can write the implementations like normal code) You can also get syntax like this that way Vector_Push(int)(&vec, 1); Which imo does a better job distinguishing the type from the name
- david2ndaccount 2y agoI wrote a blogpost describing this technique. https://www.davidpriver.com/ctemplates.html https://www.davidpriver.com/ctemplates.html
- eqvinox 2y agoI agree that the debugging and maintenance experience is much better that way, but it comes at the cost of very poor "DX". We, discussing this here on this thread, understand what's going on. But sadly at least for the projects I'm involved in, the average developer does not. TBH, rather than fancy high-meta generic support, I'd be much more appreciative of ISO C adding something like "_Include" to the preprocessor, e.g. #define DEFINE_MY_WRAPPER(foo, bar) _Include("wrapper.h") /* "foo", "bar" remain accessible in wrapper.h */ I tried implementing this in GCC but didn't get very far, it runs a bit counter to how includes are handled currently. P.S.: I ended up doing this https://github.com/FRRouting/frr/pull/15876/files#diff-907836b27aed5047e0e2db06b6f235b8f2630e11411c5b857125cd190872da8fR6-R12 https://github.com/FRRouting/frr/pull/15876/files#diff-90783... instead; a tool that can be invoked to expand some DEFINE_FOO if needed for debugging. It's not used particularly often, though.
- choeger 2y agoI really don't see what the problem with the runtime metadata is? In the example, the size of T is also an argument? So why not pass a pointer to the whole set of type information there?
- rwmj 2y agoModern CPUs make following pointers quite slow.
- anacrolix 2y agoJust use Zig?
- pfg_ 2y agoThis proposal is different than how zig handles generic functions because it only emits one symbol and function body for each function. In zig, genericMax([]i32) would emit seperate code to genericMax([]i16). This proposal has both of those functions backed by the same symbol and machine code but it requires a bunch of extra arguments, virtual function calls, and manualy offsetting indices into arrays. You could use zig to do the same with some effort.
- pfg_ 2y agofn genericReduceTypeErased( size: usize, total: [*]u8, list: []const u8, reducer: *const fn(total: [*]u8, current: [*]const u8) callconv(.C) void, ) void { for(0..@divExact(list.len, size)) |i| { const itm = &list[i \* size]; reducer(total, @ptrCast(itm)); } } inline fn genericReduce( comptime T: type, total: *T, list: []const T, reducer: *const fn(total: *T, current: *const T) callconv(.C) void, ) void { genericReduceTypeErased( @sizeOf(T), @ptrCast(total), std.mem.sliceAsBytes(list), @ptrCast(reducer) ); } The proposal is basically syntax sugar for making a typed version of the first function in C
- WhereIsTheTruth 2y agoJust use D? The point is not to use something else, but to improve what they already use
- samatman 2y agoAnd a lot of people will, but we're not taking C out back of the barn and shooting it. It's here to stay and adding some new features which make it a better language is a good idea. I'm not convinced this specific proposal does that, but that's a separate matter. JenHeyd Meneide has a Technical Specification paper for a defer statement in C, which is visibly based on Zig's version, and I applaud that. https://thephd.dev/just-put-raii-in-c-bro-please-bro-just-one-more-destructor-bro-cmon-im-good-for-it https://thephd.dev/just-put-raii-in-c-bro-please-bro-just-on...
- ww520 2y agoZig’s comptime has wonderful support for generic. It’s very powerful and intuitive to use. May be can borrow some ideas from it?
- SubjectToChange 2y agoThe problem with ISO C standardization is dealing with absolutely impoverished implementations. Said implementations either object to anything moderately complex or can't be trusted to do it right.
- t43562 2y agoFor new code you can use any language but we do have a lot of C code out there so it would be nice to have some ways to modernize it in, say 10 years, when those modernizations have made it out to every conceivable platform that runs the software. e.g. GNU make could do very much with some better abstractions (not sure about this one specifically) and yet one cannot use such things until the last VMS user of gmake has got that feature in their C compiler. IMO that probably means the most effective way to modernise C programs might be to transpile the modernisations to e.g. C89. That could be done on any device and the result, one hopes, would work on all the systems out there which might not have the modern compiler on them.
- wolletd 2y agoI wonder how hard it would be to just convert old C code to C++? I mean, most of C just compiles as C++ and does the right thing. There may be some caveats with UB (but less if you don't switch compiler vendor) and minor syntactic differences, but I guess most of them could be statically checked. Or is there any other (performance/size) reason to not do this?
- zabzonk 2y ago> most of C just compiles as C++ um, not unless explicitly written to so.
- jay-barronville 2y ago> I mean, most of C just compiles as C++ and does the right thing. In my experience, unless you’re strictly talking about header files (which I’m assuming you’re not), C code compiling via C++ compilers is usually hit or miss and highly dependent on the author of the C code having put in some effort into making sure the code actually compiles properly via a C++ compiler. In the overwhelming majority of cases, what lots of folks do is just slap that `extern "C"` in between `#ifdef __cplusplus` and call it a day—that may work for most forward declarations in header files, but that’s absolutely not enough for most C source files. By the way, a great example of C code that does this exceptionally well is Daan Leijen’s awesome mimalloc [0]—you can compile it via a C or C++ compiler and it simply just works. It’s been a while since I read the code, but when I did, it was immediately obvious to me that the code was written with that type of compatibility in mind. [0]: https://github.com/microsoft/mimalloc https://github.com/microsoft/mimalloc
- xiphias2 2y agoIt's a cool idea, simple, I like it much more than the _Var and _Type stuff, but I'm not sure if it's 100% backwards compatible: If I pass (int) and (void ) at different places, they will convert to void *, but won't be accepted in the new code. Still, it would be great to have an implementation where it can be an optional error, and see what it finds.
- cherryteastain 2y agoLooks very similar to Go generics, which also don't support monomorphization. Sadly, Go's generics are a bit of a basket case in terms of usefulness since they don't support compile time duck typing like C++ generics, but I imagine it won't be a problem for C since it does not have methods etc like Go. That said, I personally feel like that's precisely why I feel like this proposal adds little value compared to macros, since runtime dispatch is bad for performance (very important for most uses of C) and the convenience added is small because C only supports a few primitive types plus POD structs without embedding/inheritance.
- mseepgood 2y ago> Looks very similar to Go generics, which also don't support monomorphization. That's not true. Go's generics are monomorphized, when it makes sense (different shapes) and not monomorphized when it doesn't (same shapes). It's a hybrid approach to combine the best of both worlds: https://go.googlesource.com/proposal/+/refs/heads/master/design/generics-implementation-gcshape.md https://go.googlesource.com/proposal/+/refs/heads/master/des...
- cherryteastain 2y agoGo does monomorphization in a rather useless manner from a performance perspective because all pointers/interfaces are essentially the same "shape". Hence you still have no inlining and you do not avoid the virtual function when any interfaces are involved as detailed in https://planetscale.com/blog/generics-can-make-your-go-code-slower https://planetscale.com/blog/generics-can-make-your-go-code-... C++ fully monomorphizes class/function templates, and therefore incurs 0 overhead while unlocking a ton of inlining, unlike Go.
- tialaramex 2y agoYup. The most classic example of this is that in both Rust and C++ we can provide a method on some type which takes a callable and instead of a single implementation which runs off a function pointer, the compiler will separately monomorphize individual uses with lambdas to emit the optimised machine code for the specific case you wrote often inline. For example Rust's name.contains(|c| c == 'x' || (c >= '0' && c <= '9')) gets you code which just checks whether there are any ASCII digits or a lowercase latin x in name. If you don't have monomorphisation this ends up with a function call overhead for every single character in name because the "shape" of this callable is the same as that of every callable and a single implementation has to call here. Is Go's choice a valid one? Yes. Is it somehow the "best of all worlds"? Not even close.
- JonChesterfield 2y agoC 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 agoThere is a very simple and small adition to C, that would solve the generics problem, albeit without much typesafety and you'd probably need a bunch of macros to create really nice APIs: Marking function arguments as "inline" such that the argument must always be a constant expression and the compiler is supposed/forced to specialize the function. You can already write generic code that way currently, see qsort, but the performance is often very bad, because compilers don't specialize the functions aggresively enoigh. On the simple level, this would make thigs like qsort always specialize on the comparator and copy operation. But you can use this concept to create quite high level APIs, by passing arround constexpr type descriptor structs that contain functions and parameters operating on the types, somewhat similar to interfaces.
- strlenf 2y agoHere is my not-very-novel proposal for function overriding only. Its backward/forward compatible and free of name-mangling. void qsort_i8 ( i8 *ptr, int num); void qsort_i16(i16 *ptr, int num); void qsort_i32(i32 *ptr, int num); void qsort_i64(i64 *ptr, int num); #if __has_builtin(__builtin_overridable) __builtin_overridable(qsort, qsort_i8, qsort_i16); // qsort resolves to qsort_i8 qsort_i16 // qsort() is forward compatible and upgradable with your own types __builtin_overridable(qsort, qsort_i32, qsort_i64); // qsort resolves to qsort_i8 qsort_i16 qsort_i32 qsort_i64 #endif i8 *ptr0; int num0; i16 *ptr1; int num1; i32 *ptr2; int num2; i64 *ptr3; int num3; qsort(ptr0, num0); // call qsort_i8() qsort(ptr1, num1); // call qsort_i16() qsort(ptr2, num2); // call qsort_i32() qsort(ptr3, num3); // call qsort_i64()
- Someone 2y agoYou can do that since C11 using _Generic. https://en.cppreference.com/w/c/language/generic https://en.cppreference.com/w/c/language/generic: #include <math.h> #include <stdio.h> // Possible implementation of the tgmath.h macro cbrt #define cbrt(X) _Generic((X), \ long double: cbrtl, \ default: cbrt, \ float: cbrtf \ )(X) int main(void) { double x = 8.0; const float y = 3.375; printf("cbrt(8.0) = %f\n", cbrt(x)); // selects the default cbrt printf("cbrtf(3.375) = %f\n", cbrt(y)); // converts const float to float, // then selects cbrtf }
- strlenf 2y agoTrue but its very clumsy for large number of parameters. Even more importantly, its not forward compatible. For example, cbrt() cant reliably expanded to support bigints or any private types.
- fuhsnn 2y agoThis is too close to C++ templated functions, I would prefer just use C++ syntax with stricter rules like C23 did with constexpr and auto. Being able to interop/share code with C++ with extern "C"{ template<T> } wouldn't hurt either. I see the non-proposal and WG14's <Forward Declaration of Parameters> parts of the pursuit to finally standardize passing size info over function calls, with past arts even from Dennis Ritchie himself. While I don't have a strong preference on how it should be done (other than "just use fat pointers already"), I feel some of these too much new syntax for too little improvement. C codebases have established routines for generic types if those were needed, there would be little incentive to adopt a new one. And judging from what Linux[0] and Apple[1] have been doing, if projects are doing annotations at all, they would want a superset of just size or alignment. [0] https://lpc.events/event/17/contributions/1617/attachments/1244/2528/features.pdf https://lpc.events/event/17/contributions/1617/attachments/1... [1] https://llvm.org/devmtg/2023-05/slides/TechnicalTalks-May11/01-Na-fbounds-safety.pdf https://llvm.org/devmtg/2023-05/slides/TechnicalTalks-May11/...