7 ms·
Maximal min() and max()
- baggy_trough 2y ago47MB of code from a min/max macro is simply hilarious!
- dfox 2y agoThe effects of preprocessor in C are quite significant. Old DOS Turbo C had shown amount of lines compiled and the speed in the compilation progress window in the IDE. IIRC straight #include <stdio.h> #include <stdlib.h> int main(int argc, char**argv){ puts("hello, world"); return EXIT_SUCCESS; } came to something ridiculous on the order of 100k lines.
- CGamesPlay 2y agoWell, the #includes are hiding quite a few lines underneath them. While probably not 100k, I wouldn’t be surprised if it was, say, 20k.
- 1718627440 2y agoOn my computer this only results in 1828 lines. (tested with `gcc -E - | wc -l`)
- jonathrg 2y agoThat series of macros is a nice demonstration of the incredible effort it takes to attempt the most basic generic programming in C. Perhaps it would be more productive to just accept the limitations of the language and define a version of `min` and `max` for each type.
- lifthrasiir 2y agoThat will make `typedef` much less useful, though. C is the real problem; not the attempt to do generic programming in C. (And `_Generic` won't solve this problem anyway. Only a GCC extension of statement expressions will.)
- asplake 2y agoAlso a demonstration of how much work other compilers do for you behind the scenes.
- Groxx 2y agoEhhh... not much more so than how much `npm install` hides. These macros are part of a gigantic tower of absurdity that costs many, many times more than they need to, but we use them because dev time is more valuable than CPU time.
- rerdavies 2y agoDev time spent waiting for compiles is way more expensive than CPU time.
- jonathrg 2y agoA compiler for a language with generic types will definitely do less work to implement generic min/max than the C preprocessor has to do in order to perform all the text substitutions generated by these macros.
- asplake 2y agoOh totally! It has the information to do it both properly and efficiently.
- usr1106 2y ago
- peheje 2y agoWhy don't they define a min/max for each primitive type? How many are there, 15?
- kzrdude 2y agoEven use a macro to define all typed min max macros
- wahern 2y agoThe reason the current macro is so complex is because it supports mixed types while avoiding (failing on) integer promotion bugs. A version supporting arguments of all the same type would be just as trivial as in C++ (albeit relying on GCC extensions like statement expressions).
- tempfile 2y agoThis is addressed if you chase down the original kernel mailing list thread (the "flamewar" linked in the article). It was important to Linus that the macro was actually min/max and not min_slong max_uint etc, so that people couldn't "accidentally" use the untyped version. In other words he was trying quite hard to "force" people to use these macros. If you would then say "why doesn't min/max just implement a switch on each primitive type", I think on some level it does just do that.
- colonwqbang 2y agoGenericity is not really the issue as I see it. The basic K&R macro using ?: is fully generic. The problem is that C has implicit conversion between essentially any numeric types. The main point of the kernel macro was to prevent such conversions. I think implicit type conversion is a mistake, perhaps one of the few true design flaws in C. Languages like haskell and rust went with explicit conversions which is probably a better idea overall, even if it does increase the code verbosity a bit. C++ instead doubled down and added many more ways for implicit conversions to happen.
- PaulDavisThe1st 2y ago> C++ instead doubled down and added many more ways for implicit conversions to happen. but also allows you to turn them off for objects, thankfully.
- wakamoleguy 2y agoWhy are these defined as macros at all? A function call would come with overhead, of course, but wouldn't compilers be able to inline that anyways?
- lifthrasiir 2y agoC doesn't have any type-generic function declaration. So any viable solution had to be at least partially powered by a macro and resulting (one-directional) type inference.
- kevin_thibedeau 2y agoC11 does with _Generic but it is limited in ways that make min/max implementations flaky.
- pyth0 2y agoEven with _Generic you can't declare generic functions. You'd still need a macro call that uses _Generic to dispatch different implementations depending on the parameter types.
- dwattttt 2y agoGeneric dispatching all the type combinations (or warning or erroring) wouldn't be a problem in a project the scale of the Linux kernel. I'm unfamiliar with the incantations needed to try preserve constant expressions though, that might be too much for them.
- lifthrasiir 2y agoThe concrete problem that the kernel is facing is an exponential growth of macro expansion. Any current solution, safe or not in terms of re-evaluation, needs at least two copies of both arguments to be expanded [1], so expressions like `min(min(a, b), c)` will expand some arguments four times. The growth factor would be much larger than two if the definition wasn't carefully designed to avoid such cases. [1] `_Generic` also requires at least two because you need one copy to select the generic implementation and another to call it. C23 `typeof` (or the equivalent GNU extension) allows for a compact type tuple matching: inline static int max_int(int x, int y) { return x > y ? x : y; } inline static unsigned max_uint(unsigned x, unsigned y) { return x > y ? x : y; } /* ... */ #define MAX(a, b) (_Generic( \ (void (*)(typeof(a), typeof(b))) NULL, \ void (*)(int, int): max_int, \ void (*)(unsigned, unsigned): max_uint, \ /* ... */ \ default: max_type_error \ ) (a, b))
- account42 2y agoWhat C programmers will do to avoid using even a little bit of C++.
- pjmlp 2y agoEver since CFront was born on the same UNIX building at Bell Labs.
- Sharlin 2y agoTo be fair, it's not like you can just add a "little bit of C++" to the kernel.
- jonathrg 2y agoC codebases can often be updated with minor changes to compile with a C++ compiler, after which C++ features can be gradually introduced. Is the Linux kernel different in this regard?
- creeble 2y agoRead the LWN comments.
- Groxx 2y agoFrom a moderate skim, I'm not seeing much in there that really addresses this beyond FUD and over-simplification. Which, I mean... it's the Internet. That's kinda expected. But if there's something specific you're seeing, could you link to it? I'm curious as well what the "stick to C" crowd's reasons are. "C plus this one feature of C++" seems rather defensible at a glance (ignoring the social difficulty in choosing which feature), but I'm sure it's much more complicated than that in practice.
- dzaima 2y agoEven if a project can choose some specific feature(s) to switch to C++ for, it'd severely reduce the barrier for adding reliance on more features; why did feature X get a pass, but not this other one? And C++ has a lot of such potential features that are harmless and easy to justify at their best, but can become headaches when used more broadly, requiring everyone and everything to deal with them.
- up2isomorphism 2y agoEvery time when such thing happens, then it becomes a language suggestion opportunity. But for those who suggest another language, are you going to replace a 50M line code base because of you want have a fancy min / max? I don’t think this is a responsible suggestion.
- orf 2y agoThat’s a strawman argument: nobody seriously considers a different language because of a “fancy min/max”. However, hygienic macros that fix entire classes of issues (including this) is a more compelling argument. Not to say that it makes the case, only that the strawman you wrote is not good.
- tuveson 2y agoHow would hygienic macros fix this? It seems like the macros were working fine, but the amount of generated code increased compile time significantly. Wouldn’t a more sophisticated macro system still generate a bunch of extra code and result in slow compile times? It even seems like the solution was to fall back to “dumb” macros when feasible for compile-time performance reasons.
- tetha 2y ago> Wouldn’t a more sophisticated macro system still generate a bunch of extra code and result in slow compile times? Not necessarily. The preprocessor code here picks up the original source, and blows up the initial code (which is about "min3(long_a, long_b, long_c)") to 47 MB of code. no fancy stuff, just 47MB of C-Code on the disk. That's a lot of code the compiler then has to parse and handle. If hygienic macros are a first-class citizen in the compiler, the compiler parses the original macro code once and then just modifies it in-memory. There is no reason to write 47MB of code somewhere and read it back, this would just happen as an AST modification in memory. But that is also a much smaller reason. First-class macros allow the compiler to reason based off of the types and structure of the macro inputs. You don't have to guess if something is constant, bounded, unbounded and such. Strong types can enforce this safely and macros and optimization can use these strong guarantees. And sufficiently strong type information can open doors for far, far more powerful optimizations overall. Just for the record - I'm fully aware why the kernel is where it is, and why it will stay there, but there is far improved compiler and language theory from there.
- Borg3 2y agoThis also shows how programmers sometimes use far too fancy stuff for what they do. If you are doing some intense computation, split it, or do it and later slap sanity check inside. It will be even more readable. If you just play with bunch of vars, sure.. min/max macros can be easier to read.
- wood_spirit 2y agoCould not the main compilers get involved and add builtins so an ifdef makes the common path on the main compilers like gcc use builtins and the slowdown only hurts those using the less mainstream compilers? If it takes off the other compilers would quickly add the feature.
- sapiogram 2y agoWhat you're suggesting is basically a worse version of adding built-in min() and max() to the C spec. Which, to be fair, would be quite nice, but I guess the working group didn't want it in the standard.
- nullc 2y agoAdding a compiler specific builtin is one path for things to get into the language.
- layer8 2y agoThis reminds me of how ~25 years ago I wrote little C macro library to perform safe (non-overflowing, and/or saturating) integer arithmetics and comparisons, however the small application I wanted to use it in had the compiler crash after 2-3 hours due to insufficient RAM+swap when compiling a single source file using those macros. It turned out the macro expansions made the translation unit grow to GB size, which must have been 4-5 orders of magnitude over its original size.
- sapiogram 2y agoHow did that end up happening? Did you define addition recursively or something?
- layer8 2y agoThe macros automatically derived the signedness and the minimum and maximum value of the integral types involved, in a way that didn’t made platform-specific assumptions like two’s complement or no padding bits. Cases like comparing signed long to unsigned long also needed extra logic, due to there being no larger type that encompasses both. I don’t remember the details, but it did have a significant number of nested macro invocations.
- usefulcat 2y ago> some of the changes to the macros made some developers (including Bergmann) nervous These macros are now so complex that they're reluctant to touch them. Seems like there is a clear need for some thorough tests here? This is exactly the sort of thing that is eminently testable.
- Vecr 2y agoMaybe. Most C code of non-trivial length is UB or at least implementation defined, you really don't want to "tickle" something in a low-level highly used macro.
- Joker_vD 2y ago(void) (&_x == &_y); Is this... a check for type-compatibility? I don't think actually produces a compilation error if the types are incompatible.
- cmovq 2y agoIt produces a warning for incompatible pointer types.
- Joker_vD 2y agoOkay, it's better than nothing.
- lokar 2y agoWhich you can make an error
- mananaysiempre 2y agoFWIW, (&_x - &_y) will give you an error instead.
- deleted 2y ago[deleted]
- kibwen 2y agoThe most pleasant C codebases that I have read essentially banned macros outside of includes, conditional compilation, and named constants. Please just stop trying to use macros to metaprogram in C.
- deleted 2y ago[deleted]
- seanhunter 2y agoFor everyone with a “why don’t they just…?”-type suggestion, it’s worth carefully rereading TFA and considering what the macros do now and the problem they are trying to solve. The macros now do type-safe comparisons that work correctly with combinations of different argument types where this is possible, work in a constant context (eg defining array bounds), work correctly in the face of implicit type coercion and include a 3-way min and max that have these same desirable properties (same as the two way min and max). The problem(s) are it’s a bit slow to compile and the preprocessor expansion (although not necessarily the final generated assembly - didn’t see anyone saying that) is a bit bloated. So when you make a “why don’t they just…. ?”-suggestion, make sure your suggestion is at least as good as what they have now in terms of the desirable functionality and correctness and then tackles the actual problems in some way. I’m not sure all of the suggestions I have seen here and in the lwn comments succeed at meeting those two criteria.
- deleted 2y ago[deleted]
- dataflow 2y agoI have a "why don’t they just" question: if they're going to rely on compiler intrinsics anyway, why don't they just implement the whole darn thing in the compiler and do whatever they want there? If you're going to marry your code to the compiler, at least take full advantage of it?
- seanhunter 2y agoI think that’s an excellent suggestion tbh (and could meetmy two criteria as well) and someone may well do that. The thing they want seems perfectly reasonable to me and wouldn’t only benefit the kernel.
- starspangled 2y agoAssuming good faith, they don't do that because they are kernel developers not compiler developers, and they want it to build on the compilers that real systems have at hand. If somebody proposed a new extension and got llvm and gcc to both implement it today, they would still need something to work on old compilers. The oldest GCC supported by Linux is 10 years old nearly.
- metrognome 2y agoThere are plenty of projects smaller than the Linux kernel that have developed and employed DSLs (to varying degrees of success, I'll grant). I wonder, are there any languages out there designed specifically for kernel programming? Given the number of preprocessor hacks used in the kernel, and the amount of GCC-specific behavior that the codebase depends on, it seems like they are already halfway there.
- jakobson14 2y agoHonestly, they'd probably be better off if they ditched all the sed/awk/macro BS and just went back to bash scripts (or perl/TCL, if you don't like weird syntax issues) that spat out C code. Rust saw the writing on the wall and implemented proc macros. Stop using tiny hammers and get a big one.
- 38 2y agowhat a pathetic language. modern languages have a fully generic max function, thats also type safe https://godocs.io/builtin#max https://godocs.io/builtin#max
- mastax 2y agoMy question is, why isn't there a `min() and `max()` in the standard library? Even accepting C's philosophy of a minimalist stdlib, these feel like uncontroversial functionality to me. TFA shows there's enough complexity involved in doing it correctly that it makes sense to provide an implementation rather than have everyone write the same often-subtly-incorrect macros. They could use a `__builtin_cmp(type, a, b)` which can use the correct type-casts and prevent double-evaluation without needing any macro weirdness.