Generics in C without void* or macros – enabled by psychec | Hacker News Reader

Generics in C without void* or macros – enabled by psychec

github.com

90 pointsunusualcool70 comments

I don't really understand what the point of all this is, and why anyone would consider using this in a real-world application they're developing. There's already a C-like language which lets you write type-safe generic programs: it's called C++! And if for some reason you really want or need to restrict yourself to using C language features (almost) exclusively, you can disable RTTI, exceptions, and use a technique to avoid linking to libstdc++ (or equivalent). It really seems to me that the point of all this is just to reinvent the wheel, but maybe I'm missing something, I only skimmed the paper.

I also think it is rather strange for many projects to continue with C, esp for large projects, where c++ offers much conveniences to the programmer. IIRC gcc only recently started allowing c++ in it's source, and I wonder if emacs allows it still in it's source.

SQLite kicks ass. Don't hate.

Exceptions are a major point of contention. Most of the conveniences C++ offers to the programmer are not possible without exceptions, and non-local transfer of control is not just a huge departure from C, it's one that is hard to gradually transition to.

> Most of the conveniences C++ offers to the programmer are not possible without exceptions

Like what?

Pretty much anything involving constructors that fail.

It's easy to not write constructors that can fail. The major conveniences like templates, RAII, overloading, algorithms, lambdas, virtual functions, etc. work fine without exceptions.

While the "major conveniences" are orthogonal to exceptions, constructors are not, and in many non-trivial cases constructors should be expected to fail.

It's doable to write constructors that don't throw exceptions; writing constructors that can't fail is not possible for a large fraction of the useful space of constructors.

If your constructors fail without throwing an exception, much of the usefulness of RAII goes away.

The traditional approach would be to have an empty state that the object can be put into, ie. classic two-step initialization. This isn't usually too hard since you often need an empty state you can put that kind of object into when it's moved from anyway. Another one is to have a private constructor called from a static function returning a std::expected<your_class, error>.

How would that make the usefulness of RAII go away?

The whole point of RAII is that the scope of the variable is identical to the liveness of the resource. Two step initialization makes that no longer true.

That's not quite right since (1) it's about object lifetime, not variable scope (think of the elements of a vector), and (2) the liveness of a resource is not generally identical to the lifetime of any object because of things like two-step initialization or moves.

    std::vector<int> v; // v's lifetime begins
    // currently owns nothing, exactly as in two-step initialization
    v = other_vector; // resource #1 becomes live
    v = std::move(another_vector); // resource #1 dies, resource #2 becomes live
    return std::move(v); // resource #2 now owned by returned object, will outlive v
    // v's lifetime ends

I'd say RAII is more about making sure every resource always has an owner and that when an object dies, all the resources it owned are cleaned-up. And that works fine with two-step initialization.

It seems to be aimed at quick prototyping of small programs, relieving you from declaring any structs or datatypes at all. The fields and layout of structs are inferred from the usage. With their frontend, you would be able to implement a type-generic list or a tree only with a few function definitions.

Looking at their example:

    _Generic void prepend(_Forall(node_t)** head,
                          _Forall(value_t) value)
    {
        node_t* n = malloc(sizeof(node_t));
        n->value = value;
        n->next = *head;
        *head = n;
    }

For each use of `prepend()`, their frontend defines an appropriate struct with fields `value` then `next` (in that order) whose types are inferred from the assignments in the body of the function.

The problem with C++ is that in addition to generic functionality, it also brings a ton of other baggage that even if you do not use, you still pay for (e.g. personally i really dislike how slow C++ compilers are).

Though TBH i wouldn't use OP's preprocessor either as i think that void* and macros are perfectly fine.

Exceptions being one of the notable pieces of baggage...

Yeah, though i'm not sure if exceptions really slow down compilation and in some compilers you can disable them anyway. Also you can redefine new to return null on failure, though if you are going to use new, delete, etc might as well bite the bullet and use the entire language anyway (and instead of redefining new, use a template that does the allocation and initialization based on some common convention and a macro that causes an error whenever new is used since you can ensure no exceptions will be thrown... at least from new - but IMO a better way is to just stick with C and avoid the tarpit that is C++).

...my compile times rarely take more than a minute, so I can't really relate to that, but exceptions will slow down execution and add an overhead to the binary's file-size.

Exceptions don't generally slow down execution -- they usually have zero runtime cost if they're not thrown making them better than error returns for performance. However, the exchange is, as you said, that they do add a lot of overhead to the file-size.

Regarding error handling, I agree with this author[0], and find the C-based approach much better than C++'s try/throw/catch methods.

Regarding execution times, I don't know from first-hand experience, I did some research and found this[1]. The third sentence in that reply ("The error code is not sensitive to the percentage of occurrence") is AFAIK wrong (because of speculative execution, I believe?), but the rest seems quite solid.

[0]: http://250bpm.com/blog:4

[1]: https://stackoverflow.com/a/52513707

Something that generates extra code that ends up in the instruction cache during execution is not zero cost.

There's cost to transfer it through memory and cache hierarchies and there's cost when it causes the CPU to drop some other L1C cache line.

Well, if the exception is not thrown, no code related to the exceptional path goes into the instruction cache (not even checking for exception propagation). Assuming of course a non-completely dumb compiler that puts exceptional path code and unwinds tables in separate pages than hot code.

True.

I think I'll test whether use of exceptions can affect optimizations concerning register allocation and spilling, like function prologues and epilogues. Unwinding will also need to call destructors, and for that you'll need to have the object pointer somewhere in (stack frame) memory. But it might be in just a register. Unless, of course, the unwinding engine can look into registers as well.

I guess it's not a huge deal either way, especially in 32-bit x86 code. For large register file systems it might be a different story, forcing otherwise unnecessary spills. Regardless, I'll find out when I got some time.

Anyways, my point was more generic. So-called zero-cost abstractions are my pet peeve, because they're often not zero cost precisely because of larger generated code size. Typical microbenchmarks don't capture this, because their hot path can usually fit comfortably in L1 code and data caches.

In theory the optimizer can optimize exactly as if the exceptions where not there, in practice some code motion optimizations might be restricted across exception boundaries simply because it might be too much work to make it work correctly. So it is possible on some tests cases to measure a difference.

Regarding spilling and register allocation, IIRC[1] the unwind tables contain a simple bytecode that is interpreted by the undwinder to fixup stack and restore registers (indexed by the current ip address), so no actual registration of object to destroy need to be done, nor does the frame pointer need to exist at all: the unwinder interprets the bytecode to recursively adjust each stack frame and registers to the expected values.

[1] At some point I had actually learned to write unwind tables by hand, of course I completely forgot everything about that: look at trampoline_thunk at https://github.com/gpderetta/delimited/blob/master/delimited... even with extensive comments is still write-only code. It doesn't help that there aren't a lot of DWARF CFI tutorials around.

Exceptions store the data to unwind the stack and run the handlers "out of band". Actually triggering the exception itself is expensive but that's an acceptable trade off as exceptions should only be used for exceptional situations.

I'm no compiler expert, but I would expect that compilers would put exception-handling code on a separate 64-byte cache line.

You only use up "cache" if you actually hit the cache. If you're on a different L1 cache line (and never execute), you'll never be in L1 instruction cache, maybe never even in L2 or even L3 cache lines.

Not that I'm an expert on compilers... but whenever I look at assembly, there are lots of "NOPs" across the code. I've always assumed it was for some kind of boundary alignment, probably cache.

> I'm no compiler expert, but I would expect that compilers would put exception-handling code on a separate 64-byte cache line.

I'd sure hope they're on an entirely different page, not just cache line!

Concerning compiler code alignment: they seem to place my code on 16-byte boundaries - for a good reason too, the smallest code size while keeping optimal 16-byte aligned branch targets.

In past I actually had to drop to assembler to get 64-byte (cache line) alignment for functions (MSVC).

GCC does have optimize pragma, like:

  #pragma GCC optimize ("align-functions=64")

Although I want to point out one shouldn't usually worry about low level details like function alignment. Use profile guided optimization, etc. instead. Also remember due to L1 set associativity limitations excessive alignment can even cause pathological L1 churn in the worst case.

Heh, this reminds me of the Abrash quote about optimization mentioned a few days ago (from his black book):

> We're so used to slow software that when a compile-and-link sequence that took two minutes on a PC takes just ten seconds on a 486 computer, we're ecstatic—when in truth we should be settling for nothing less than instantaneous response.

(from https://github.com/jagregory/abrash-black-book/blob/master/s...)

Personally i'm annoyed when my compile times take more than a few seconds :-P

One of the reasons C++ is so complicated is that you don't pay for the features that you don't use. If you wanted generics in C, you can easily use C++ without any of those other features (baggage, if you will) and not pay for it.

Heck, you could define a few macros and make it impossible to use any baggage features you don't like.

I've used C++ in a pretty tight embedded environment and it was great.

You may not pay for them (generally) in terms of execution time, but you pay for them in terms of compilation time and language complexity.

If I don't use them then language complexity doesn't matter. Compilation times might be a factor assuming that turning them off doesn't also decrease that (which it might).

> I've used C++ in a pretty tight embedded environment and it was great.

I'd love to hear some details. I'm always looking for C++ stories that didn't end in disaster and what the people did that worked.

Pretty much any CUDA programmer can talk about how they got 1024 threads working on 64kB "shared memory" with their C++ compiler. That "shared memory" region is exceptionally fast, so its a good idea to hyper-optimize your memory accesses to use that region.

There are some very interesting constraints in GPU-programming. Fitting C++ classes and even some data-structures in the "shared memory" region is pretty nifty.

I've done similar. The Microsoft Band UI was written in C++. No templates or other advanced features, compiler was stuck on 2003 standard. We had templates but used the trick of implementing them in a .cpp file and declaring all the instanciations of them we'd ever use at the bottom of the same file. Had to write our own to guarantee 0 allocs.

It is quite do-able. Lots of static declarations, basically write C with classes. V-tables ended up being non-trivial in size, but what can you do, GUIs and all that. Possibly the best (only?) good use of inheritance hierarchies.

256KB memory, the UI only had 60KB or so available for it IIRC. We also had a scratch pad available over a super slow bus of a couple megs, but it couldn't be used too much or we'd drop frames and we loved our 30fps v-sync'd performance.

No, I’m not going to drag in C++ and all of its baggage if all I need is some form of generics. It’s really not as simple as, “Just use C++!” If I truly need type-safe generics and C11 is an option, I’d rather go with that any day!

One can also use D (now part of GCC). D with its better dialect allows one to not use D run time libraries, or even C++ runtime libraries. A developer can just choose what C libraries they want to link with.

In this mode, no GC is provided, so a developer will be using manual allocation.

With upcoming D's dip1000 feature, it will be able to do rust-like borrows checker at compile time (or at least this is my understanding). And that capability will be available in betterC mode as well (not just for full blown D).

The code in betterC can use generics and other advanced features

https://dlang.org/spec/betterc.html

---

Nearly the full language remains available. Highlights include:

- Unrestricted use of compile-time features

- Full metaprogramming facilities

- Nested functions, nested structs, delegates and lambdas

- Member functions, constructors, destructors, operating overloading, etc.

- The full module system

- Array slicing, and array bounds checking

- RAII (yes, it can work without exceptions) scope(exit)

- Memory safety protections

- Interfacing with C++

- COM classes and C++ classes

- assert failures are directed to the C runtime library

- switch with strings

- final switch

- unittest

dip1000:

https://github.com/dlang/DIPs/blob/master/DIPs/other/DIP1000...

Generics != templates

Templates are a particular implementation of generics.

Good point!

No void* or macros, but requires a special compiler frontend.

Yes, that was confusing. "Look, you don't need to use these C-features if you use another language than C."

C++ 14, Haskell and Python.

One of the reasons I'm actually going for pure C in this modern day and age, is that I can just write a small program, without having any other dependency.

I'm sure the same could be said for C++, too, but for some reason, with my setup (GCC 5.1.0 with MinGW on Windows 7), I'm averaging around 800KB on C++ vs 80KB on C, for the (mostly) same code. EDIT: It appears that exception-handling is one of the reasons the binary is bigger in C++ than C.

I mainly write code for embedded devices, so whatever programs I write on x86 is to interface with those devices, hence I'm quite comfortable staying with C.

Are you sure it isn't debugging information that bloats the executable? Try a strip --strip-all your.exe and see if it is still that big.

> Try a strip and see if it is still that big.

...I guarantee that it is nothing short of humongous xD

Joking aside, maybe, I don't know, it's been a while since I used some C++ code, but I'll have a look into it the next time around.

...though it's probably unlikely, I use Code::Blocks and exclusively use the "Release" candidate, and uncheck the "Debug" version, and I'm quite confident the CB authors know what they are doing.

I do not remember Code::Blocks' configurations, but a Release configuration may still contain debug symbols so you can debug your release executable.

This needs to be made clearer in the readme: C++ and Haskell are requirements for building the type inference engine; Python is necessary for invoking the frontend (or the binaries can be downloaded).

> I mainly write code for embedded devices, so whatever programs I write on x86 is to interface with those devices, hence I'm quite comfortable staying with C

I'm in the same situation and I use C# for windows based tools.

Sorry, it wasn't my intention to be tricky, that's why I added "enabled by psychec" to the subject line. I hope that, once landing at the project page, it should be obvious that such functionality is provided by a tool.

You should never typedef a pointer to an object. That’s common knowledge amongst experienced C developers and an immediate red flag, even for myself normally welcoming of anything built with Haskell.

A red flag implying what, exactly?

While I agree with this, I think it's a ridiculously common thing to see among major software vendors. A lot of Apple's APIs are typedef'd pointers to various structs.

I'm not an expert C developer but can see some semantic benefits of typedefing a pointer.

Is this considered harmful because it hides the fact that you're dealing with a pointer in the first place?

As evidenced by countless examples of somethingPTR-types, it is done regularly. But the main problem is indeed that you hide the pointer.

If you apply qualifiers like const to your type, results might me unexpected.

It might have semantic benefits, but C developers should be trained to ignore all these strange *-symbols anyway.

If it's an opaque pointer I see no reason to typedef it as there is zero way to dereference any struct members.

It's all semantic sugar anyway.

Yeah, true. Although, the problem is lessened if properly abstracted away via opacity. MPFR (GNU multi-precision library) typedefs an array of size 1 holding its basic type, as opposed to just typedefing the struct of the basic type. This is (I think) purely so they don't have to put '&' in front of their "objects" when passing them around.

While I've great respect for the authors of that fantastic library, I only have this to say about the practice: Jeeesh!

I don’t see why not, as long as you make it clear what it is. E.g., if a C API is handing me an opaque handle that I need to pass around to the rest of the API, I don’t need to know that it’s a pointer (I’m not the one dereferencing it) and I’d rather not have to worry about that if I’m using the API properly.

I agree that it's something you shouldn't do, but that's just an opinion. Many C programmers are fine with it.

Yeah it's not like something 'bad' is going to happen.

I typedef function pointers when they get too verbose. Otherwise not. But it's not the mole hill I'd choose to die on either.

You should never hide a pointer to a type with a typedef.

So to program C in this special way I need C++, Haskell, and Python. No thank you. If/when I still work in C, it's with the aim of keeping bloat and dependencies to a dull roar at most.

Type generic expressions [1] already exist in C11. You can do this without a special compiler front-end if you need it, you would just need to define each variant by hand. These are supported in GCC and Clang with the -std=c11 flag.

[1]: http://www.robertgamble.net/2012/01/c11-generic-selections.h...

I developed these ideas a bit further with the use of XX macros, which allow you to make a set of functions generic across some list of types. There can be real performance wins to this over void*: https://abissell.com/2014/01/16/c11s-_generic-keyword-macro-...

That looks handy. I got bored one day and built a fluent interface: http://flukus.github.io/fluent-interfaces-for-c.html

_Generic has been created for a specific use (tgmath.h) and is not very powerful.

I like C for the small set of basic rules and that it does not impose much cognitive overhead of learning too many new things for a given project I have to get to know. Typedefs were already too much and I prefer not to use them...

Typedefs are nice if you do not want to write 'struct' all the time...

Yes! Typedefs are definitely worth the time spent learning them.

Interesting link, but if anybody is interested in making real practical use of generics in a C-style language, then it's best to take a look at Zig.

Zig is not able to output c code that could be consumed by an alternative [optimized|verified/proofed] C compiler like Intel along with other questionable decisions such as "Zig does not support RAII or operator overloading because both make it very difficult to tell where function calls happen just by looking at a function body. Zig tends to avoid syntactic sugar except where it would have a significant effect on the semantics of a program. Zig does not have a C-style for loop, because you can just use the more general-purpose while loop instead with only a little bit of extra code. [1] The compiler is free to inline non-extern functions, change their parameters, and otherwise !!do whatever it wants!!, since they are internal functions." [2]

[1] https://ziglang.org/download/0.1.1/release-notes.html [2] https://andrewkelley.me/post/intro-to-zig.html

Just a note for drive by viewers, there's a link here to 0.1.1 release notes but a lot has changed since 0.1.1:

* [0.2.0 release notes](https://ziglang.org/download/0.2.0/release-notes.html)

* [0.3.0 release notes](https://ziglang.org/download/0.3.0/release-notes.html)

* [0.4.0 release notes](https://ziglang.org/download/0.4.0/release-notes.html)

0.5.0 is scheduled to be released Sept 30.

Can you add existentially-quantified generics? Then OOP with dynamic dispatch would just be syntactic sugar. IMHO this would be way better than C++ since it would completely unify generics with the OO approach.

Reply on news.ycombinator.com