13 ms·
The joy of max()
- AnssiH 9y agoFor an explanation of __is_constant(), see the thread where it was suggested: https://lkml.org/lkml/2018/3/20/845 https://lkml.org/lkml/2018/3/20/845 (this was also indirectly linked to in the article) tl;dr: If one of the expressions in a ternary operator is a null pointer constant, the result type is that of the other expression.
- nothrabannosir 9y agoI’m surprised this is necessary at all. Wouldn’t a compiler at any reasonable optimisation level optimise __cmp_once into __cmp automatically (and then into the resulting max constant) if used with constants? Seems like very basic constant propagation.
- CJefferson 9y agoThe problem is cmp and cmp_once are actually different if x and y are function calls. In that case cmp calls the functions twice.
- loeg 9y agoI think you've misread the question. Grandparent isn't asking why use cmp_once at all; they're asking, why not always force the single evaluation of x and y (i.e., always use cmp_once and let the compiler optimizer reduce the resulting expression)? A responsive answer is given in https://news.ycombinator.com/item?id=16720118 https://news.ycombinator.com/item?id=16720118 .
- LukeShu 9y agoAs explained in the article linked at the top ("LWN recently looked at the kernel's max() macro"), the issue isn't one of optimization, it's one of syntax. Sure, a decently optimizing compiler can optimize __cmp_once in to a constant value. However, C99 requires that non-VLA arrays have a size that is a constant expression, which is a syntax thing; even though GCC knows that __cmp_once evaluates to a constant value, the resulting C coming out of the preprocessor is of the wrong syntactic shape.
- tbodt 9y agoThe most insane macro in that is this monstrosity: #define __is_constant(x) \ (sizeof(int) == sizeof(*(1 ? ((void*)((long)(x) * 0l)) : (int*)1))) If x is a compile-time constant, (void* )((long)(x) * 0l) is equivalent to NULL, otherwise it's just a regular void* . And if both sides of a ternary are pointers, the rule is: If one side is NULL, the type of the ternary should be the type of the other side (int* in this case). Otherwise, if one side is a void* , the type of the ternary should be void* . So if x is constant, the type of the ternary is int* , and if it's not constant the type is void* . The sizeof(* ()) around it turns that into sizeof(int) or sizeof(void), and in the GNU dialect sizeof(void) is 1, which is different from sizeof(int). Whew. What I want to know is what's wrong with __builtin_constant_p.
- LukeShu 9y ago> What I want to know is what's wrong with __builtin_constant_p. 1. __builtin_constant_p might not return a constant--it might return a magic value that says "I don't know yet, ask me again at a later optimization step". __builtin_choose_expr needs to be evaluated pretty early, so "ask again later" isn't good enough for it. https://lkml.org/lkml/2018/3/18/268 https://lkml.org/lkml/2018/3/18/268 2. It doesn't really care if it is constant in the __builtin_constant_p-sense, it cares if it has side-effects. > ({x++; 0;}) is constant in the eyes of __builtin_constant_p, but not side-effect free. https://lkml.org/lkml/2018/3/18/316 https://lkml.org/lkml/2018/3/18/316
- deleted 9y ago[deleted]
- gerdesj 9y agoI'll also drop in another link - https://lkml.org/lkml/2018/3/20/845 https://lkml.org/lkml/2018/3/20/845 that D Wheeler pointed out in LWN and this quote from Mr T's reaction: >That's not "an idea". >That is either genius, or a seriously diseased mind. >I can't quite tell which.
- halayli 9y agoIt would be nice to credit this explanation to Linus.
- jstanley 9y agoWhat's the advantage of ever using cmp over just always using cmp_once?
- deleted 9y ago[deleted]
- tbodt 9y agoIf foo and bar are functions, foo() > bar() ? foo() : bar() can have a different result than int __x = foo(); int __y = bar(); __x > __y ? __x : __y
- loeg 9y agoI think you've misread the question. Grandparent isn't asking why use cmp_once at all; they're asking, why not always force the single evaluation of x and y (i.e., always use cmp_once)?
- tbodt 9y agoAh, that's because cmp_once doesn't yield a constant even when the inputs are constant. The reason that matters is there are some arrays in the kernel declared like int things[max(size1, size2)]; and there's been recently a push to remove all VLAs (arrays with non constant size) from the kernel. The -Wvla flag was warning about these arrays even though they're actually constant size, so something needed to be done.
- loeg 9y agoYep. https://news.ycombinator.com/item?id=16720118 https://news.ycombinator.com/item?id=16720118 is another good explanation :-).
- loeg 9y agoThere's an answer in another thread: https://news.ycombinator.com/item?id=16720118 https://news.ycombinator.com/item?id=16720118
- RcouF1uZ4gsC 9y agoThis is why C++ is so nice. Constexpr fits the bill perfectly instead of using these non-portable hacks.
- deleted 9y ago[deleted]
- tbodt 9y ago> In fact, in Linux we did try C++ once already, back in 1992. > It sucks. Trust me - writing kernel code in C++ is a BLOODY STUPID IDEA. https://lkml.org/lkml/2004/1/20/20 https://lkml.org/lkml/2004/1/20/20
- AceJohnny2 9y agoA 14-year old opinion based on a 26-year old experiment. C++ has evolved tremendously since. There are better arguments. (and I say this as a C developer who doesn't believe C++ is the right answer)
- rileymat2 9y agoWith no solid ABI it is unlikely.
- anarazel 9y agoIs that a likely problem for the kernel, actually? Given that there's no API stability, and the fact that syscalls are an explicit ABI anyway, I don't see how that'd matter for linux? (not that I'm arguing for C++ in linux or such)
- rileymat2 9y agoSorry, Just my sour grapes. Recently created a third party SDK DLL in c++ and could not pass c++ types natively (unless you coupled to compiler and maybe version of compiler).
- andrepd 9y agoThis in cpp: template<class T> constexpr const T& max(const T& a, const T& b) { return a>b ? a : b; }
- mehrdadn 9y agoEdit: apologies, I'm blind; never mind. I thought I double-checked but the use of > instead of < tripped me up.
- darkmx0z 9y agoStepanov disagrees. You should return the second parameter if a, b are equivalent (and you should use < anyway): template<typename T> inline constexpr const T& max(const T& a, const T& b) { return (b < a ? a : b); }
- loeg 9y agoThe C version works with distinct types for a and b. Does this?
- Jyaif 9y agoThat's not a feature, it's more bug prone.
- krallja 9y agoI’m not up to date on GCC macros, so I’m not familiar with this syntax: #define __cmp_once(x, y, op) ({ \ typeof(x) __x = (x); \ typeof(y) __y = (y); \ __cmp(__x, __y, op); }) Is that a block-expression, or what?
- krallja 9y agoOk, I found the doc for GCC Statement Expressions. Seems very Ruby-like. https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html
- gshrikant 9y agoWhat exactly is the typecheck macro doing here? I get that it compares the sizes of two pointer values but I don't know why and I feel like there is some C standard nuance involved here that I don't understand. Also, is the `sizeof` used to force evaluation at compile time?
- tbodt 9y agoThe type of == is always int, so the sizeof is sizeof(int), and the !! makes the result always be 1 (true). The entire purpose of the macro is to have the compiler warn if the types are incompatible.
- gshrikant 9y agoThanks! However, I still don't understand this completely. So the sizeof is there just to force evaluation of the comparison and because == can only be used among compatible types the compiler would warn? Why is the !! necessary then wouldn't sizeof(int) be enough as a "true" value?
- LukeShu 9y agoIt's to have the compiler produce a warning if the types aren't the same. __cmp_once produces such a warning, and they don't want the warning to go away if it decides to use plain __cmp instead of __cmp_once. It doesn't "do" anything otherwise; it always evaluates to "1".
- gshrikant 9y agoDoesn't the compiler produce a warning by default (on comparing a `char` and `int`, for example) when using -Wall?
- rwmj 9y agoThe lesson here is that if you're designing an operating system, you should also be designing/evolving the programming language to go alongside it. The original authors of Unix did this (developing C in parallel), and so have many more obscure OSes. This could have been written simply as 'max()' with appropriate modifications to the compiler to make it do the right thing.
- brianon99 9y agoThings have changed over the years. Even if the developers have patched gcc, or "own" gcc, linux still have to be built with gcc 4.4 otherwise many distro will have problems, so it does not solve the problem. Moreover, change the semantics of C as you have suggested will break other non-linux-kernele existing programs. There may exists programs depending on the K&R version of max with side effect. Who nows?
- mjw1007 9y agoI think asking the GCC developers for a builtin form of __is_constant would be a sensible step, so that the worst of those macros can eventually be retired.
- psyc 9y agoI'm 100% on board with this. I think big low-level projects, including AAA games (my field) would benefit by treating the compiler exactly like a dependency they have the source for. We might stumble on very good language evolutions as a side effect.
- netheril96 9y agoI often find it amusing how C advocates complain about the complexity of C++, and then proceed to implement the same complex functionality in even more brittle ways. Language features I have seen C developers emulate poorly in C: constepxr (here), virtual functions (with function pointers), templates (with macros), exceptions (with setjmp/longjmp).
- static_noise 9y agoThe only argument for C and against C++ is the slippery slope of wanting to use one useful feature and ending up using a thousand features where noone is really sure what's actually happening in the end. Then again they start re-inventing "C with classes" using unsafe structs and macros. It seems that the problem is not really with the language but the developers who cannot restrain themselves.
- astral303 9y agoIn C++, you don’t pay for features you dont use. Linux kernel has virtual calls for file systems via function pointers. That’s polymorphism. Why not let the compiler handle that?
- beeforpork 9y agoC natively supports type-safe function pointers -- there is no ugly hacking or boilerplate involved in that. I.e., the C compiler handles that. So what's the advantage of wrapping a class around it?
- candiodari 9y agoNo it doesn't. Or yes, it does, but we're talking about virtual method calls, emulated with function pointers. This is an argument people always make here in the kernel C++ debates or the GNOME vs KDE debates (GNOME is C and GTK, KDE is C++ with Qt) What needs to be happening, to avoid crashes and get correct functioning: 1) virtual method tables need to be allocated (otherwise you might be getting a function pointer from unallocated memory and calling it. Good luck surviving that. Bugs like this have happened in both kernel and GNOME). 1b) Pointers to the virtual method tables need to be correctly set upon every allocation of the struct that contains them. So you lose the ability to create an instance without constructing it. (again plenty of bugs) 2) every level of the inheritance hierarchy need to fill in the function pointers in the correct order (You can't count the number of bugs of this type in GNOME). 3) the pointers for same functions need to be at the same memory location for every object (and the corollary. Function pointers for different functions cannot, at any point of the inheritance tree, have the same location). This leads directly to the kernel datastructures, where everybody is utterly terrified of changing anything or even reordering fields. And sadly, that fear is there for good reason. 4) 1, 2 and 3 need to be redone (best from scratch) any time the inheritance hierarchy changes. And of course, need to be done correctly, so you really ought to erase the whole thing in the whole inheritance (and somehow tell out-of-tree developers to do the changes on their end), but in C nobody does this because of the amount of work involved. Then ... bugs happen. 5) May God help you if you modprobe a module across one of these changes without recompiling it. In other words, any change to the inheritance hierarchy risks making out-of-tree modules deathtraps (such changes require modifying the source to the out-of-tree module and recompiling) In C++ a) put "virtual" in front of the function you want to work across the inheritance hierarchy b) (optional) don't remove or reorder virtual functions in versions where you want to maintain binary compatibility (caveat: not in the functions themselves, and of course, not in any data structures they might use) (in short: anything out-of-tree needs to be recompiled) Given that KDE maintains binary compatibility across major versions b) is not optional within that project (with a bit of a cleanup at avery major version). Except for DCOP. But if you recompile from scratch for every deployment like every large C++ shop, you can just outright ignore it. The result of this is that the lookup tables can be compiled into programs. This works ridiculously fast. A virtual function call in C++ is one indirection. Not even one extra instruction (just a much more expensive one than the one you'd ordinarily use). In Java, if I remember the last time I checked it was ~20.000 instructions (but can be compiled out by the JIT compiler ... eventually. Then it's still ~1000). And I assure you Java is a lot more efficient at this than any scripting language. This is the usual difference between C and C++. In C++ you get all the advantages that lots of manual work gets you in C, at the same runtime cost. The criticism is that if you give inexperienced programmers lots of high level tools, they will quickly use it to blindly generate programs that are 20G+ of machine code. And ... well that's true. Fixing it can be pretty hard. The arguments of people like Linus are essentially that it's a good thing that people go through and redo the low-level stuff regularly. It's a lot of work but at times you find problems and inefficiencies. I do agree with that, but sadly, I find it pretty hard to assemble a 2K+ member team that I don't have to pay. So work that programmers don't have to do is a win for me.
- wruza 9y agoI would like to use a language that doesn’t involve sizeof(typeof...) and template(Tmagic...) both. #include “meta.h” @tr max(@ta a, @tb b) if (is_comparable(ta, tb)) tr = common_base(ta, tb, optionshere...) produce_code {...} else compile_error “incompatible types in $(__func__)” I can’t figure out for decades why can’t we just get all ideas from lisp and code in happiness.
- devit 9y agoLisp has hard to read syntax and no static type system, so not really something to imitate.
- dragonwriter 9y ago> Lisp has hard to read syntax and no static type system, The first is subjective, and there are Lisp-family languages with static typing.
- wruza 9y agoI think I should stress out that my hope is not to use lisp instead of our languages of choice, but to simplify metaprogramming tasks in them with at least equally simpler approaches that lisp has. E.g. all C constructs can be described in a set of structs. IfStmt, CallStmt, BinopExpr, etc. Generating or inspecting these on the fly could allow to create hundreds of metaprogramming frameworks, few of which could prove their best fit. But instead we locked in ugly cpp macros and C++ templates that even seasoned haskell monader hardly understands and has no tools to explain. Debugging is hard and manual, metadebugging is not even a thing, cppcheck and other code analysis tools are enormously complex and rare, apple ARC is a propietary language feature for NSObject instead of two pages of metacode available to anyone with an “int rc” in their struct. I hope that snippet above is now more clear.
- _asummers 9y agoThat looks very similar to an Elixir macro (heavily influenced by Lisp macros). If you haven't checked that language out, you might find yourself liking it.
- drngdds 9y agoI'm really confused by the 1s in this macro. What are they, syntactically? The second one looks like it could be being cast to the type "pointer to y" but the first one has the sizeof expression in front of it. #define __typecheck(x, y) \ (!!(sizeof((typeof(x)*)1 == (typeof(y)*)1)))
- ivanbakel 9y agoBoth are being cast - the brackets are a little confusing, but the sizeof expression is for the result of the comparison.