6 ms·

Generic Containers in C: Safe Division Using Maybe

114 points by uecker 1y ago

nly 1y ago
GCC generates essentially the same assembly for C++'s std::optional<int> with the exception that the result can't be returned in a register (a problem which will go away if the function is inlined) https://gcc.godbolt.org/z/vfzK9Toz4 https://gcc.godbolt.org/z/vfzK9Toz4
- uecker 1y ago
  Yeah it a amazing a far C++ has come, soon it will be almost as good as C.
  - JonChesterfield 1y ago
    In this instance C++ is far ahead of C, because what you want for maybe<> is typestate, and that's only available in C++ because it's wedded to member functions. See https://awesomekling.github.io/Catching-use-after-move-bugs-with-Clang-consumed-annotations/ https://awesomekling.github.io/Catching-use-after-move-bugs-... or similar
    - uecker 1y ago
      Sure.
  - deleted 1y ago
    [deleted]
  - pjmlp 1y ago
    Except that it is much more safer to use the type system than pre-processor glue based on text replacements, with more interesting error messages than templates.
    - uecker 1y ago
      I don't see how it safer. I think this is just a random claim C++ people like to make without any evidence. In terms of error message, the problem is that C++ often can not produce them because due to overloading it is entirely unclear to the compiler what the intention of the code actually way. A macro-based solution also does not have ideal error message, but I do not think it is worse than C++.
      - pjmlp 1y ago
        It isn't a random claim, is based on years of experience fixing pre-processing code gone wrong, because whoever wrote it in first place forgotten that it is nothing more than text expansion, and then someone else completly unaware that it is a macro, ends up giving a bad set of parameters.
        uecker 1y ago
        I spent also countless amount of hours fixing template code, so no I do not let your anecdotes count. There is certainly a lot of problematic macro code in C, but I do not think it is worse than C++ templates, and one can also write robust macros.
        pjmlp 1y ago
        One can also write robust template code, if that is the reasoning we're going for, enable_if, static_assert and concepts have been available for a couple of years now. At least that is something we can agree on, C and C++ are both languages where developers could write robust code, and the large majority seldom does it.
        uecker 1y ago
        I can agree with this. The difference is that C++ approach is to solve problems with features people need to understand while C solves problems by only providing basic building blocks and expects people to use them correctly. In both cases it needs expertise to do this. But Rust also has this problem.
- wahern 1y ago
  Is this because std::optional isn't trivially constructible?
  - pwdisswordfishz 1y ago
    Destructible. Opportunistically making it trivially destructible does the trick.
- pjmlp 1y ago
  Proving the point that better type system and abstractions don't necessarly produce bad Assembly, and if constexpr is used, there won't be anything on the final executable other than the actual value. https://gcc.godbolt.org/z/31o75W5xx https://gcc.godbolt.org/z/31o75W5xx https://gcc.godbolt.org/z/av6a43WeY https://gcc.godbolt.org/z/av6a43WeY
  - uecker 1y ago
    You do not need constexpr, just remove the "volatile" which I put into my example only to prevent the optimizer from specializing it: https://godbolt.org/z/fs8q3sdxK https://godbolt.org/z/fs8q3sdxK But what matters is run-time behavior for any input. And sorry, C++'s complexity still has the effect that the code is terrible: https://godbolt.org/z/vWfjjf8rP https://godbolt.org/z/vWfjjf8rP In C, the compiler can remove all error paths: https://godbolt.org/z/GGMcc6bxv https://godbolt.org/z/GGMcc6bxv
    - nly 1y ago
      Not sure what you're talking about here. The cruft the assembly is because you enabled UBSAN. If you disable UBSAN then the exception throwing code paths go away.
      - uecker 1y ago
        The point is that the error code paths should go avoid even with UBSAN because they are dead, but the optimizer is not able to see this anymore in C++.
    - aw1621107 1y ago
      > But what matters is run-time behavior for any input. And sorry, C++'s complexity still has the effect that the code is terrible: https://godbolt.org/z/vWfjjf8rP https://godbolt.org/z/vWfjjf8rP > In C, the compiler can remove all error paths: https://godbolt.org/z/GGMcc6bxv https://godbolt.org/z/GGMcc6bxv For what it's worth, if you actually use the same flags for the C++ example (in particular, -fsanitize-trap) the C++ compilers improve quite a bit, with Clang getting fairly close to the GCC C output (https://godbolt.org/z/M3z5EaGKj https://godbolt.org/z/M3z5EaGKj ; note that GCC doesn't seem to eliminate the std::optional::value() check unless you use -O3). But perhaps more interestingly, if you make a simplified std::optional that still uses C++-specific features both Clang and GCC produce output that is very close to that from C/GCC: https://godbolt.org/z/PhEW7eT8x https://godbolt.org/z/PhEW7eT8x Removing I/O-related stuff makes this clearer: C: https://godbolt.org/z/e71s9E63f https://godbolt.org/z/e71s9E63f C++: https://godbolt.org/z/YnhdxYxY4 https://godbolt.org/z/YnhdxYxY4 (Clang seems unable to eliminate the UBSan overflow check for some reason?) Does make me wonder what exactly it is about std::optional that confuses the optimizers, and whether a similarly complex C maybe implementation can suffer from the same issues that std::optional appears to.
- account42 1y ago
  > with the exception that the result can't be returned in a register (a problem which will go away if the function is inlined) It's still a damned shame. Same for not being able to pass optional/unique_ptr/etc in a register. We really need a trivially_relocatable attribute.
nextaccountic 1y ago
> Here, instead of handling the error condition, I create an lvalue that points nowhere in case of an error because it then corresponds to (({ (void)0; })), relying on the null sanitizer to transform it into a run-time trap for safety. Isn't this undefined behavior?
- lmm 1y ago
  In standard C yes. But any decent C compiler will offer stronger guarantees than the minimum that the standard requires, and presumably the "null sanitizer" they're referring to is one of them.
  - pjmlp 1y ago
    As usual, the problem is not what they have been offering for the last decades in tooling, rather what developers actually make use of. Unfortunely many keep needing education on such matters.
  - playforclaude 1y ago
    Any decent C compiler will use loopholes in the standard to optimise your code :)
- shakna 1y ago
  Maybe, but it is defined for GCC: > You can store a null pointer in any lvalue whose data type is a pointer type. [0] Though, I would expect a complaint from clang, and clang-tidy. [0] https://www.gnu.org/software/c-intro-and-ref/manual/html_node/Null-Pointers.html https://www.gnu.org/software/c-intro-and-ref/manual/html_nod...
- uecker 1y ago
  It is only undefined behavior if it is dereferenced, in which case the null sanitizer can be used to define it to trap, so safely terminate the program. But the example then also shows how you can make sure that this case is not even possible in the final program.
  - 1y ago
rowanG077 1y ago
At this point I always wonder why people who write stuff like this don't just move to a different language. You are introducing insane amounts of hidden complexity(see also the other posts on that blog). For something that just exists in other languages. Or maybe this is just a fun puzzle for the author, in which case it's totally fine.
- throw-qqqqq 1y ago
  You don’t always get to choose your language. Especially in the embedded/firmware area of software development, C is the most widely available option, if not the only option besides ASM shrugs
  - rowanG077 1y ago
    Definitely. I still don't think you should swim against the stream. Just bite the bullet and write idiomatic C. The people who will have to debug your code in the future will thank you.
    - throw-qqqqq 1y ago
      I agree 100%
  - windward 1y ago
    It is, but the bar of what's considered too 'clever' in embedded/firmware is usually lower than this. In fact, even the ternary conditional operator is too much.
  - fuhsnn 1y ago
    The said library is a bit farther away from the C that is widely available. It relies on C23 features, GNU statement expression, GNU nested function, sanitizer runtimes, VLA types and a very niche pattern of sizeof executing its statement-expression argument; only platforms that provide latest GCC/Clang would be able to use this.
    - 1y ago
yobbo 1y ago
It might be more useful with a signature like maybe_divide -> maybe(int) -> maybe(int) -> maybe(int) ... and then a set of operations over maybe, and functions/macros for and_then(), or_else(), etc. It would be interesting to see how ergonomic it could get.
- munchler 1y ago
  I await the first “Monads in C” tutorial with mixed feelings.
  - uecker 1y ago
    Good idea. This is very easy, here is a preview. https://godbolt.org/z/dME1MMr19 https://godbolt.org/z/dME1MMr19
BiraIgnacio 1y ago
I love seeing the creative ways people implement these types of, if I can say, high level abstractions in C. Thanks for sharing
- uecker 1y ago
  Thank you!
teo_zero 1y ago
Clever, but it misses the very goal of option/maybe types: forcing the user to check the result. In this implementation nothing stops the user from omitting the "if (p.ok)" part and directly using "p.value". It could work if "maybe(T)" is completely opaque to the user; both checking and accessing its payload must happen through helper macros; the checking macro ticks an invisible flag if ok; the accessing macro returns the payload only if the invisible flag is ticked, otherwise it triggers a runtime error/exception. Not impossible. However, you would need to replace all "p.ok" with "maybe_check(p)", which is not unreasonable, and all "p.value" with "maybe_value(p)", which might be too much for the final user...

114 points by uecker 1y ago

nly 1y ago

GCC generates essentially the same assembly for C++'s std::optional<int> with the exception that the result can't be returned in a register (a problem which will go away if the function is inlined) https://gcc.godbolt.org/z/vfzK9Toz4 https://gcc.godbolt.org/z/vfzK9Toz4

uecker 1y ago
Yeah it a amazing a far C++ has come, soon it will be almost as good as C.
- JonChesterfield 1y ago
  In this instance C++ is far ahead of C, because what you want for maybe<> is typestate, and that's only available in C++ because it's wedded to member functions. See https://awesomekling.github.io/Catching-use-after-move-bugs-with-Clang-consumed-annotations/ https://awesomekling.github.io/Catching-use-after-move-bugs-... or similar
  - uecker 1y ago
    Sure.
- deleted 1y ago
  [deleted]
- pjmlp 1y ago
  Except that it is much more safer to use the type system than pre-processor glue based on text replacements, with more interesting error messages than templates.
  - uecker 1y ago
    I don't see how it safer. I think this is just a random claim C++ people like to make without any evidence. In terms of error message, the problem is that C++ often can not produce them because due to overloading it is entirely unclear to the compiler what the intention of the code actually way. A macro-based solution also does not have ideal error message, but I do not think it is worse than C++.
    - pjmlp 1y ago
      It isn't a random claim, is based on years of experience fixing pre-processing code gone wrong, because whoever wrote it in first place forgotten that it is nothing more than text expansion, and then someone else completly unaware that it is a macro, ends up giving a bad set of parameters.
      - uecker 1y ago
        I spent also countless amount of hours fixing template code, so no I do not let your anecdotes count. There is certainly a lot of problematic macro code in C, but I do not think it is worse than C++ templates, and one can also write robust macros.
        pjmlp 1y ago
        One can also write robust template code, if that is the reasoning we're going for, enable_if, static_assert and concepts have been available for a couple of years now. At least that is something we can agree on, C and C++ are both languages where developers could write robust code, and the large majority seldom does it.
        uecker 1y ago
        I can agree with this. The difference is that C++ approach is to solve problems with features people need to understand while C solves problems by only providing basic building blocks and expects people to use them correctly. In both cases it needs expertise to do this. But Rust also has this problem.
wahern 1y ago
Is this because std::optional isn't trivially constructible?
- pwdisswordfishz 1y ago
  Destructible. Opportunistically making it trivially destructible does the trick.
pjmlp 1y ago
Proving the point that better type system and abstractions don't necessarly produce bad Assembly, and if constexpr is used, there won't be anything on the final executable other than the actual value. https://gcc.godbolt.org/z/31o75W5xx https://gcc.godbolt.org/z/31o75W5xx https://gcc.godbolt.org/z/av6a43WeY https://gcc.godbolt.org/z/av6a43WeY
- uecker 1y ago
  You do not need constexpr, just remove the "volatile" which I put into my example only to prevent the optimizer from specializing it: https://godbolt.org/z/fs8q3sdxK https://godbolt.org/z/fs8q3sdxK But what matters is run-time behavior for any input. And sorry, C++'s complexity still has the effect that the code is terrible: https://godbolt.org/z/vWfjjf8rP https://godbolt.org/z/vWfjjf8rP In C, the compiler can remove all error paths: https://godbolt.org/z/GGMcc6bxv https://godbolt.org/z/GGMcc6bxv
  - nly 1y ago
    Not sure what you're talking about here. The cruft the assembly is because you enabled UBSAN. If you disable UBSAN then the exception throwing code paths go away.
    - uecker 1y ago
      The point is that the error code paths should go avoid even with UBSAN because they are dead, but the optimizer is not able to see this anymore in C++.
  - aw1621107 1y ago
    > But what matters is run-time behavior for any input. And sorry, C++'s complexity still has the effect that the code is terrible: https://godbolt.org/z/vWfjjf8rP https://godbolt.org/z/vWfjjf8rP > In C, the compiler can remove all error paths: https://godbolt.org/z/GGMcc6bxv https://godbolt.org/z/GGMcc6bxv For what it's worth, if you actually use the same flags for the C++ example (in particular, -fsanitize-trap) the C++ compilers improve quite a bit, with Clang getting fairly close to the GCC C output (https://godbolt.org/z/M3z5EaGKj https://godbolt.org/z/M3z5EaGKj ; note that GCC doesn't seem to eliminate the std::optional::value() check unless you use -O3). But perhaps more interestingly, if you make a simplified std::optional that still uses C++-specific features both Clang and GCC produce output that is very close to that from C/GCC: https://godbolt.org/z/PhEW7eT8x https://godbolt.org/z/PhEW7eT8x Removing I/O-related stuff makes this clearer: C: https://godbolt.org/z/e71s9E63f https://godbolt.org/z/e71s9E63f C++: https://godbolt.org/z/YnhdxYxY4 https://godbolt.org/z/YnhdxYxY4 (Clang seems unable to eliminate the UBSan overflow check for some reason?) Does make me wonder what exactly it is about std::optional that confuses the optimizers, and whether a similarly complex C maybe implementation can suffer from the same issues that std::optional appears to.
account42 1y ago
> with the exception that the result can't be returned in a register (a problem which will go away if the function is inlined) It's still a damned shame. Same for not being able to pass optional/unique_ptr/etc in a register. We really need a trivially_relocatable attribute.

nextaccountic 1y ago

> Here, instead of handling the error condition, I create an lvalue that points nowhere in case of an error because it then corresponds to (({ (void)0; })), relying on the null sanitizer to transform it into a run-time trap for safety. Isn't this undefined behavior?

lmm 1y ago
In standard C yes. But any decent C compiler will offer stronger guarantees than the minimum that the standard requires, and presumably the "null sanitizer" they're referring to is one of them.
- pjmlp 1y ago
  As usual, the problem is not what they have been offering for the last decades in tooling, rather what developers actually make use of. Unfortunely many keep needing education on such matters.
- playforclaude 1y ago
  Any decent C compiler will use loopholes in the standard to optimise your code :)
shakna 1y ago
Maybe, but it is defined for GCC: > You can store a null pointer in any lvalue whose data type is a pointer type. [0] Though, I would expect a complaint from clang, and clang-tidy. [0] https://www.gnu.org/software/c-intro-and-ref/manual/html_node/Null-Pointers.html https://www.gnu.org/software/c-intro-and-ref/manual/html_nod...
uecker 1y ago
It is only undefined behavior if it is dereferenced, in which case the null sanitizer can be used to define it to trap, so safely terminate the program. But the example then also shows how you can make sure that this case is not even possible in the final program.
- 1y ago

rowanG077 1y ago

At this point I always wonder why people who write stuff like this don't just move to a different language. You are introducing insane amounts of hidden complexity(see also the other posts on that blog). For something that just exists in other languages. Or maybe this is just a fun puzzle for the author, in which case it's totally fine.

throw-qqqqq 1y ago
You don’t always get to choose your language. Especially in the embedded/firmware area of software development, C is the most widely available option, if not the only option besides ASM shrugs
- rowanG077 1y ago
  Definitely. I still don't think you should swim against the stream. Just bite the bullet and write idiomatic C. The people who will have to debug your code in the future will thank you.
  - throw-qqqqq 1y ago
    I agree 100%
- windward 1y ago
  It is, but the bar of what's considered too 'clever' in embedded/firmware is usually lower than this. In fact, even the ternary conditional operator is too much.
- fuhsnn 1y ago
  The said library is a bit farther away from the C that is widely available. It relies on C23 features, GNU statement expression, GNU nested function, sanitizer runtimes, VLA types and a very niche pattern of sizeof executing its statement-expression argument; only platforms that provide latest GCC/Clang would be able to use this.
  - 1y ago

yobbo 1y ago

It might be more useful with a signature like maybe_divide -> maybe(int) -> maybe(int) -> maybe(int) ... and then a set of operations over maybe, and functions/macros for and_then(), or_else(), etc. It would be interesting to see how ergonomic it could get.

munchler 1y ago
I await the first “Monads in C” tutorial with mixed feelings.
- uecker 1y ago
  Good idea. This is very easy, here is a preview. https://godbolt.org/z/dME1MMr19 https://godbolt.org/z/dME1MMr19

BiraIgnacio 1y ago

I love seeing the creative ways people implement these types of, if I can say, high level abstractions in C. Thanks for sharing

uecker 1y ago
Thank you!

teo_zero 1y ago

Clever, but it misses the very goal of option/maybe types: forcing the user to check the result. In this implementation nothing stops the user from omitting the "if (p.ok)" part and directly using "p.value". It could work if "maybe(T)" is completely opaque to the user; both checking and accessing its payload must happen through helper macros; the checking macro ticks an invisible flag if ok; the accessing macro returns the payload only if the invisible flag is ticked, otherwise it triggers a runtime error/exception. Not impossible. However, you would need to replace all "p.ok" with "maybe_check(p)", which is not unreasonable, and all "p.value" with "maybe_value(p)", which might be too much for the final user...