11 ms·
When static makes your C code 10 times faster
- peter_d_sherman 5y ago>"When modulus is static, gcc / clang know that it is private to the current compilation unit, and therefore they can inline the value itself. Then, they turn the expensive div into a much cheaper and – since mod’ing by a power of two -- is equal to bitwise and of that number minus one! All you need to do is keep the bits lower than that power of two, which is what the and will do."
- kahlonel 5y agoI think a simple “const” would have also done the trick. Sometimes -O3 is clever enough to figure out that the value is never written, so it makes it an asm constant.
- painchoc 5y agoIt is mostly about the fact that if the variable is not static, then it's non-local to the translation unit and can be modified from everywhere else. So its value needs to be loaded and a plain and slow division is applied. Having it local or const makes the compiler able to inline it and do a simple bitwise and with a constant. So yes, make your variables static const by default (if you really need global).
- jheriko 5y agoconst_cast and linkage make const weaker than static on a variable that doesn't change.
- ddulaney 5y agoThis can be accomplished more simply and reliably by marking modulus as const. The compiler currently has to reason about the whole compilation unit to determine that modulus is not modified, which works. However, if future code modifies modulus (either on purpose or accidentally) or something changes that prevents the compiler from performing global reasoning, the optimization will be lost. By marking the actual intention, any modifications of modulus turn into compiler errors. Plus, if it becomes important to expose modulus to another compilation unit, now that's possible. This is a common issue with C code (including lots of code I've written). It's really easy to forget to const something, which forces the compiler to do global reasoning or to generate worse code. I've gotten into the habit of making things const unless I know I plan on mutating them, but I wish there was tooling that encouraged it. (BTW, this is something Rust does well by making things constant by default and requiring "mut" if it's mutable.)
- wyldfire 5y agoIf there were any expressions that took the address of the variable, then even both `static const` qualifiers wouldn't work for a sufficiently paranoid compiler.
- giomasce 5y agoAre you sure? Isn't it UB to modify a const object? It will probably end up in a non-writable memory page. EDIT: gcc seems to agree with me: you can see the optimized version here[1] and the unoptimzed version if you remove "const". [1] https://godbolt.org/z/KWrW45rK8 https://godbolt.org/z/KWrW45rK8
- not2b 5y agoThis is why language standards specify what the compiler can assume and call out some behavior as undefined, exactly so compilers don't have to be paranoid and produce code that sucks. If an underlying object is const, the compiler is allowed to assume that it does not change (it is valid to cast away const on a pointer or reference, but not if the object itself was declared const).
- toast0 5y ago> (it is valid to cast away const on a pointer or reference, but not if the object itself was declared const). Isn't it valid to cast to non-const for a const, but only invalid to modify the const through the casted pointer?
- deleted 5y ago[deleted]
- why_only_15 5y agoInterestingly GCC will still optimize the loop function even if you have code that modifies the modulus. https://godbolt.org/z/EE9PnrY7s https://godbolt.org/z/EE9PnrY7s
- fallingfrog 5y agoWouldn’t making that const or using #define be a bit cleaner? Honestly if I as the programmer knew that I was really trying to select bits from a number I’d just use a binary and directly. In that specific situation I think the intent is more clear that way. Like: //select the bottom 8 bits unsigned bottom8 = val & 0xff;
- wyldfire 5y agoWe have learned so much over the decades of using C. Lowest-visibility-by-default is just one of the many good choices of Rust and other C successors. The example here is for codegen benefits but reducing visibility benefits encapsulation too.
- IvanK_net 5y agoI think every programmer should know, that logical AND is many times faster than Modulus (which is at least as hard as a division), and use & instead of % right in his code for powers of two (and not expect it to be done by a compiler).
- Rompect 5y agoThis is like the easiest thing for a compiler to detect and optimize.
- codeflo 5y agoTrue, but something to be aware of: If the compiler uses bitwise operations to implement %, it emits special handling of negative values (it's really more of a remainder operator than a modulus). You can avoid that either by using unsigned numbers, or & as suggested: https://godbolt.org/z/vdz59q994 https://godbolt.org/z/vdz59q994
- toast0 5y agoThat's bitwise AND.
- simias 5y agoIf I could travel back in time I'd tell Dennis to make "static" the implicit default, and have a special keyword like "public" or "export" for items that are meant to be accessible from outside the compilation unit. I'd also ask him to make "switch" break by default. Then I'd go kill Hitler or something.
- andi999 5y agoBut then you would need 'unbreak' or just 'goto' to the next case. No duffs device no cigar. Probably a module/namespace system would be the biggest improvement.
- jimsmart 5y agoFWIW: Go's switch statements are break by default, with an explicit 'fallthrough' keyword if one wishes to override that behaviour.
- cpeterso 5y agoclang and gcc have a -Wimplicit-fallthrough warning flag that will warn about switch cases that fall through without either C++17's [[fallthrough]] attribute or a /* fallthrough */ comment. I made Firefox's code base able to compile with -Wimplicit-fallthrough. About one hundred fall through cases needed to be annotated and about 2-3 were actual bugs (though minor).
- jcranmer 5y agoThe only real case I use switch fallthrough for is when you have two cases with the same code, e.g.: switch (foo) { case 1: case 2: /* common body */ break; case 3: /* body 3 */ break; } It's not cognitively hard to make an empty case body fallthrough to the next run, but include an implicit break at the end of every nontrivial body. Supporting Duff's Device is not a compelling feature to support--irreducible loops are basically going to destroy any hope of optimization you might accrue.
- 5y ago
- codeflo 5y agoI agree with many of the sibling comments, static vs. non-static is almost a complete red-herring. Static only means that the variable is local to the translation unit (the C file). The relevant difference in the example is actually the const-ness of the variable, which you may put explicitly, but which a powerful compiler can also infer here in the static case. Other than this optimization possibility, const and static are orthogonal concepts. I'm not sure to what extent the article author is aware of this. So the lesson should be: use const (or #define) if you mean to have a constant. It's still a good idea to also make things static, but the real reason for that is to avoid name collisions with variables in other C files.
- jheriko 5y agothis is totally wrong in my experience, although some of the understanding is right. by using static to limit to the compilation unit the compiler can workout the value is constant. const doesn't do this thanks to const_cast etc. maybe things have changed, but const on a file level variable doesn't do this reliably, or at least hasn't for considerable lengths of time. of course 'static const' is the better answer. :)
- codeflo 5y agoI hope your comment wasn't intended to be as hostile as it reads to me, but I do wonder what your experience was exactly, because there might be a misinterpretation. From a technical standpoint, using const_cast to modify a constant is Undefined Behavior. This was explicitly specified that way to make constants inlineable by the compiler. Every compiler that I've ever used does this, it's a trivial but very effective optimization. Proof by Godbolt: https://godbolt.org/z/djEdvee4s https://godbolt.org/z/djEdvee4s Observe how GCC completely eliminates the contents of undefined_mutate_modulus (which it's allowed to -- UB means it can do anything with that function, and it chooses the simplest possible thing) rather than de-optimizing mod4_const like you suggested. Compilers are smart.
- rostayob 5y agoAuthor here -- just to be clear, I agree that marking the variable as const is the "right" thing to do here. I reported the investigation as-is because removing a static declaration made the code slower, which I then narrowed down to the isolated bit of code.
- api 5y agoDivision is slow, which is something most programmers don't know. If you can binary AND instead of MOD this can be a huge win. Multiplication is also very fast, usually one or two cycles on larger chips.
- jeffbee 5y agoIf your compiler doesn't do this for divisors known at compile time, get your money back.
- perl4ever 5y ago>Division is slow I wondered if that's really still true, since I haven't done much assembly language programming since PowerPC was new. Here, it says the M1 has 7-9 cycles latency for division instructions, but throughput of 2 cycles per. https://dougallj.github.io/applecpu/firestorm-int.html https://dougallj.github.io/applecpu/firestorm-int.html "The M1 is 10x faster than the Xeon at 64 bit divides. It’s…just wow." So, given all of the other things that can slow you up, I wonder if it really makes sense to avoid division any more? (I guess the energy efficient "Icestorm" cores have throughput equal to latency, so it's only the "Firestorm" ones where it's super fast)
- astrange 5y agoYou shouldn't assume you're running on the performance cores. Not everyone is writing an app, and even if you are, most of your code will be better off on the efficiency cores.
- jokoon 5y agoSo the compiler cannot always optimize...
- EdSchouten 5y agoBack in 2012 I observed exactly the same thing. I actually managed to get a warning for this added to Clang, called -Wmissing-variable-declarations. When set, warnings are generated in case a non-static global variable is defined without an external declaration that precedes it. I worked on this as part of FreeBSD, which is why their base system is nowadays built with that flag enabled.
- rostayob 5y agoThanks, that's good to know!
- lr4444lr 5y agoGreat write up: a precise problem that digs into the internals pointedly to teach a simple concept. This is exactly how I tell the junior devs where I work to do lunch talks that give people some concrete, memorable piece of learning that makes them better in their practical work.
- daneel_w 5y agoUse a const instead. It's the right tool for the job.
- GlitchMr 5y agoWithout `static`, compiler exports a symbol. $ cat value.c int value = 42; int get_value() { return value; } $ make value.o gcc -c -o value.o value.c $ nm value.o 0000000000000000 T get_value U _GLOBAL_OFFSET_TABLE_ 0000000000000000 D value This symbol, not being `const` can be modified by any other compilation unit. $ cat main.c #include <stdio.h> int value; int get_value(); int main() { value = 123456789; printf("%d\n", get_value()); } $ make main.o gcc -c -o main.o main.c $ cc value.o main.o $ ./a.out 123456789 Compiler when generating an object file has to assume the value of exported non-const symbol can change. It's necessary to tell the compiler that the value cannot change, either by not exporting the symbol by using `static` or making the value of it `const`. In example provided in your article `static` makes sense (or even `static const`) as I don't think there is a reason to export this global.
- rostayob 5y agoYes, see last few paragraphs of the post, in which I also speculate why GCC doesn't infer that there is only one compilation unit.
- pjmlp 5y agoHow could it ever infer it, given C's compilation model? The only option is when all TU are given at the same time to the compiler, or when LTO is used (in which case it is actually the linker doing the work). Even then, this won't apply to libraries.
- rostayob 5y ago> The only option is when all TU are given at the same time to the compiler Exactly -- which is the case here. But implementing such a cross cutting implementation would probably be annoying, which is what I wanted to convey with > I think they could concievably assume that the value of modulus won’t be changed in this case, since we’re producing an executable directly, but it’s probably annoying to have an optimization looking so far into the future of the compiler pipeline.
- synergy20 5y agouse const is a better choice, I changed static to const, the result is the same here.
- malkia 5y agoIn ideal world const, constexpr, explicit (for constructors), and no default implicit conversions (and others that I'v missed) should've been the default...
- nicetryguy 5y agoConst / static allows for "immediate" ASM instruction generation: which means the value is known at compile time so it can compare it directly inline as opposed to the overhead of comparing it to a labeled memory address. It's generally good practice whenever possible.
- arthur2e5 5y agoLink time optimization would enable a similar change even without a code edit. Using static is good, but it’s a good idea to figure out how to just let other people’s code run fast too.
- astrange 5y agoOnly if the value isn't visible outside the final image. This will still happen if it has "default"/dllexport visibility or its address is taken.
- Hello71 5y agostatic can also make your code 10 times smaller: note that in the linked godbolt, there are actually two copies of both loop functions: one regular, and one inlined. this is because the compiler wants to inline the function, but is required to generate an additional one in case someone else will be calling it. what's more, at least on Linux, this copy cannot be removed from the final executable even if nobody calls it, unless a) the compilation is done with -ffunction-sections and the linking is done with --gc-sections, or b) LTO is enabled. adding static to the function declaration resolves this issue. the situation is even worse with ELF dynamic libraries due to the interaction of two rules: a) by default, all functions are exported, and b) by default, all functions can be interposed, e.g. by LD_PRELOAD. here, if you specify -fPIC in the compilation arguments (as is required to produce a modern dynamic library), inlining is totally disabled. for small functions, the call overhead can be substantial.
- sdfdf4434r34r 5y agoAs an embedded programmer working on small micros I make every single function static (including third party code, which I modify and bring into the source tree and curate myself), gives you global/link time optimizations and dead code elimination for free, leads to better code even at -O0, -Og and -O1, static const configuration structs/values gets optimized away, and so on. Really wish it was the default.
- deleted 5y ago[deleted]
- kevin_thibedeau 5y agoIt also gives you a nice private namespace for the translation unit so you can confidently modify any of the static objects without concern for impacting external code. I once had a gray beard chew me out over changing a function signature when revising things. I had to point out politely that it was static and that anyone who managed to link to the function had to be breaking a lot of rules to do so.
- jheriko 5y agoreally? people mentioned const? you can tell how much low-level optimisation they have done if they think its gonna change codegen reliably, or at ll.
- einpoklum 5y agoSee my other comment here regarding const.
- jheriko 5y agothe biggest win here is informing the compiler sufficiently to swap out div for and. the use of static is just a tool to inform the compiler that the value is a constant (which const /might/)
- einpoklum 5y agoTitle rephrase: When the compiler can assume your values don't change magically, it can optimize their use. This is true for restricted pointers, for global-scope variables which can only be accessed in the same translation unit, for stuff in inlined functions (often), etc. -------------------------------------------- const is a bit shifty. const makes the compiler restrict what it allows you to write, but it can still not really assume other functions don't break constness via casting: void i_can_change_x_yeah_i_can_just_watch_me(const int* x) { *(int*) x = x + 1; } now, if the compiler sees the code, then fine (maybe), but when all you see is: void sly(const int* x); You can't assume the value pointed to by x can change. See this on GodBolt: https://godbolt.org/z/fGEMj9Meo https://godbolt.org/z/fGEMj9Meo and it could well be the same for constants too. But somehow it isn't: https://godbolt.org/z/fqGzh7o8z https://godbolt.org/z/fqGzh7o8z
- missblit 5y agoSpecifically it's well-defined behavior to mutate an object after const_cast-ing away constness if the object wasn't const to begin with (const references or const pointers can refer to non-const objects). In your first example you have `int x = 1;` which isn't const, so the compiler has to assume that `f` may mutate it after const casting. In your second example you have `const int x = 1;` which is const so the compiler can assume the value will never change.
- einpoklum 5y agoYou must be right. But - it's so easy to forget that! Or - never to be told that in the first place.
- pjmlp 5y agoExcept that on embedded const objects might land on read only memory and cast-ing away constness will give hours of debugging pleasure.
- MaxBarraclough 5y agoThey covered that with if the object wasn't const to begin with.
- alok-g 5y agoI think this is beyond simply making the variable static/constant. It is the specific value of the constant that is allowing the division to be substituted with bitwise AND, which then makes it so much faster. I wonder how much the speedup would be if some other near-random value is there for the constant (which is likely beyond the purpose at hand).
- sgerenser 5y agoSpeed up would be less but not zero, almost any div or modulo can be replaced by a multiply by a magic constant plus a bit shift.
- nyc_pizzadev 5y agoMy first C intuition would be defining this value as a macro. If I was in C++, then a const would make sense.
- deleted 5y ago[deleted]
- bcrl 5y agoMore programmers really should have a look at what sort of assembly the compiler generates for their code. Compilers aren't magic, and seeing what sort of code it generates does give authors more insight into how concise their code truly is.
- midjji 5y agoIts better to make it constexpr.