5 ms·

C is Lower Level Than You Think

45 points by prajjwal 13y ago

goldenkey 13y ago
There's no reason that the compiler should even optimize strlen out of the loop. Here's the proper way to iterate a string if order doesn't matter, take notice: for (int i = strlen(str); i--;) ...loopContents... There's a right way to handle values that are repeatedly used, and a wrong way, ie. relying on the compiler to optimize. Many dynamic languages store the length of a string buffer, as part of a String object. ie str.length, and it's very cheap to query, just an accessor/property/getter. What is misguided in this rant, is the attack against strlen which operates on pointers to zero-terminated strings. The length isn't stored, the only storage is for the string's bytes. If you want to have fast access to strlen, and you find yourself being pained by the extra variable to cache the value, then use std::string. This blog post needs a refactor.
- rcfox 13y ago
  The author isn't saying that there's anything wrong with strlen; he's just saying that it's not trivially optimizable like it might seem to be. Also, std::string is C++, not C.
  - goldenkey 13y ago
    Sorry, that was a slipup. What I meant is a string object library. std::string would be fine in the case of C++ or bstring for C http://bstring.sourceforge.net/ http://bstring.sourceforge.net/
- icodestuff 13y ago
  Did we read the same article? I read no rant against `strlen`, but rather against naive programmers incorrectly assuming that it could/should be hoisted out by an optimizing compiler. There was not one word about being pained by an extra variable, rather that it's a clunky-but-correct solution. And other languages have nothing to do with it; this is strictly a post about C, not a dynamic language, and not C++.
  - goldenkey 13y ago
    Just seems silly to rant against strings in C when they aren't really strings at all. char* is explicity a pointer to a sequence of chars. If a developer wants more things, like a cached length, invalidated by changes, then a lib should be used. A string lib like bstring[0]. I think we get to this precarious place by even considering that char* somehow brings what we could call 'common string functions' to the forefront in an easy way. And of course, assuming the compiler will optimize away code like strlen where it cannot possibly deduce constant memory conditions for the null byte, very silly indeed. [0] http://bstring.sourceforge.net/ http://bstring.sourceforge.net/ C is low level, but the same mistake could be said for any other language where a function is repeatedly called in a loop. The compiler can only do so much, garbage code is still garbage code. Cache your function calls less they const restricted, and extremely simple, and even then, the compiler might still fail to optimize.
    - icodestuff 13y ago
      Where do you get the idea that the author is ranting against strings in C? I don't see it.
      - goldenkey 13y ago
        He's ranting against repeated function calls. Same could be said for any other language. The only interesting thing here is that strlen is the main way to get the length of a string in C, unlike OOP languages that will have a .length accessor that usually keeps the last validated length for o(1) access. That doesn't mean C is subterranean leveled.. it just means the language isn't OOP .. use a lib/struct/functions and the problem is solved. I see this as a baseless attack on C's lack of OOP through some clever bashing.
        mbel 13y ago
        Storing length with pointer to array has nothing to do with OOP, strings can be defined as simple records (aka structs, product types) you don't need OOP for that: struct string_t { const char * buffer; int lenght }; And really, I fail to see any attack on C in this article, it only mentions what a naive programmer might do, and why he/she shouldn't.
- unwind 13y ago
  No beginner programmer (the premise of the article) will loop over a string backwards. No beginner programmer will put the decrement in the test slot like you did, in order to make i have valid values in the loop body. I think it's somewhat scary to rely on post-decrement; I tend to favor pre-decrement in for loops as a general pattern, but of course in your code it must be post or it will break on an empty string. I still think the original article's suggestion to manually pre-compute the length (storing it in a const size_t variable, of course) is the better option, overall.
  - goldenkey 13y ago
    This is the fastest way to write a loop in pretty much any language _if_ order is not imperative and is very well understood by any developer worth their salt. > I tend to favor pre-decrement in for loops as a general pattern, but of course in your code it must be post or it will break on an empty string. That makes absolutely no sense. It's post-increment so it runs for i=0, could have easily been: for (int i = strlen(str); --i >= 0;) http://codepad.org/kd3oOBAb http://codepad.org/kd3oOBAb <-- fiddle around beginner ;-)
    - unwind 13y ago
      Huh? I'm aware that there can be benefits to looping backwards. There can also be (cache-related) drawbacks. "It's post-increment so it runs for i=0" is probably exactly what I meant, you needed to use post-decrement (not increment) since otherwise it would break. Of course it can be re-written like you did now, but then you added the >= 0 part which was implicit in your first comment. Its omission made it important to pick post-decrement or it would break on an empty string just as I said. My entire point was that it's beyond most beginners to rely on fairly subtle things like that. Not sure why you're so condescending, I certainly didn't try to call you a beginner, it was the other way around: your code was not very beginner-esque, but the original article was about how a C beginner might write a simple loop and be surprised.
      - goldenkey 13y ago
        I see what you mean now, I was quick to judge, wrongly albeit. Sorry about that.
- Rangi42 13y ago
  "The proper way"? Not only is it less familiar than the usual "i = 0; i < n; i++" idiom, requiring the reader to examine exactly what it's doing, but now i goes from n to 1 instead of 0 to n-1. What's so bad about caching the strlen result in a variable beforehand?
  - tedunangst 13y ago
    You have read his loop wrong. It has the same bounds.
  - nitrogen 13y ago
    i goes from n-1 to 0 in the example because for loops execute the condition before the first iteration.
  - goldenkey 13y ago
    You're wrong. Maybe I should hire my next team based on loop analysis ;-) http://codepad.org/kd3oOBAb http://codepad.org/kd3oOBAb
    - vidarh 13y ago
      And I think this perfectly demonstrates why it is a stupid approach to take in the first place. In fact, personally I have a tendency to avoid for-loops in C because of the awful syntax; I much prefer using while-loops as I find them far clearer. In 25+ years of C, I've seen plenty of people getting for-loops wrong (making broken assumptions about what's evaluated where, and countless off by one bugs), but everyone gets while-loops. If you are going to do for-loops in C, stick with the most obvious, simplest variants possible - the moment you try to be smart, you've substantially increased the odds that a maintenance programmer will introduce a bug at one point or another.
      - nitrogen 13y ago
        For the sake of job security, I propose using the comma operator to put the entire loop body within the for() parentheses, and replace the block with a semicolon: // Pure C99 (prints an invalid character at the end) for( FILE *f = fopen("/etc/fstab", "r"); !feof(f) || (fclose(f), 0); putchar(fgetc(f)) ) ; // C99+POSIX for( int fd = open("/etc/fstab", O_RDONLY), c = 0; read(fd, &c, 1) || (close(fd), 0); write(1, &c, 1) ) ;
- coldtea 13y ago
  >What is misguided in this rant, is the attack against strlen which operates on pointers to zero-terminated strings. The length isn't stored, the only storage is for the string's bytes. No attack at strlen at all. Perhaps you didn't read it correctly? Not to mention the author already knows all of this (trivial) information. The only attack is at the naive assumption of some newbie programmers (which the blog post targets) that "the compiler should take care of that".
- p1esk 13y ago
  Wow, this "for (int i = strlen(str); i--;) printf("%c", str[i]);" trick to reverse a string is really cool! Thanks!
  - vidarh 13y ago
    I realise this is illustrating something, but just in case: For the love of all that is good, please don't actually printf() for every character... Depending on your platform that may or may not result in a ridiculous number of system calls, but no matter what, it will be slow if you do it a lot. If you insist on calling a function for every character (which is still silly), please at least putchar()/putc()/fputc() (putc()/putchar() can expand inline, but even they have substantial overhead to lock the stream) I've seen systems spend the majority of their time in IO functions because of stuff like that. Always, always, always batch up IO unless you have real reasons not to (and almost always avoid syscalls when you can)
    - p1esk 13y ago
      Is there a good resource or book on how to write high performance C code? I just started learning programming, and I will need to write C for simulations (well, it will be CUDA version of C or C++).
      - vidarh 13y ago
        I can't think of any good books of the top of my head - I've picked this up largely from starting out with assembly, and spending years picking apart compiler output (initially because the C compilers I had access to were junk, and I more than once would compile something, disassemble it and then hand-optimise the result...) One approach is to learn to read assembly (being able to write it from scratch is optional), and understand what affects clock cycle count. On modern architectures that also means understanding cache effects, and particularly looking out for memory access patterns. Then look at lots of disassembly and learn to understand what kind of code typically gets generated from your C. Often it will be plain obvious why things are slow when you see the amount of generated code (though here be dragons - sometimes modern compilers will actually do a good job optimising, and as a result produce code that no sane human would ever write manually). You can quickly get a good feel for patterns that are good and bad. But in general: - Profile. Profile some more, to make sure you're actually spending your time on the code that matters. - A useful rule of thumb is that for any given algorithm, the fewer function calls and memory accesses, the better it is likely to to be. Functions calls are expensive, and often (not always) reduce locality of code, and so increase the amount of time spent accessing memory that is not in cache (== expensive). But don't start hand-unrolling/removing abstractions until you know by profiling that the code in question is performance critical, or you may just end up creating a maintenance nightmare. - System calls are particularly nasty on any memory protected modern OS. The context switch overhead tends to be absolutely brutal. Which means it's very often worth quickly breaking out strace (on Linux) or equivalents to quickly eyeball the system call behaviour of applications before spending much time on other stuff. E.g. one particular pet peeve of mine is the amount of time you see read() or write() with small byte counts - if that occurs often, you can sometimes get truly massive speedups simply by changing the code to do non-blocking read/writes to/from a buffer and do smaller read/write's in user space from those buffers. (Always be suspicious of code that does read/write/recv/send or similar unless you can see it uses large-ish buffers... but profile). My experience is that odds are shockingly high that people will severely underestimate the cost of system calls. - Keep data that is accessed together close in memory. E.g. cluster values by access patterns when you can, to avoid thrashing cache when you access the data. This can be tricky, and the solutions can be non-obvious because the actual access patterns may not be that easy to spot.
- derefr 13y ago
  It seems that everyone's forgetting the whole genius thing about C-strings, which is that you can iterate through them without advance knowledge of their length: char c; while(c = *(str++)) ... This is, after all, the loop strlen() itself performs.
  - vidarh 13y ago
    Which is great if you're guaranteed to advance one character per loop iteration. Which may or may not hold.
  - goldenkey 13y ago
    True, this is even better in terms of complexity. I'd be curious to know if constantly changing the pointer causes certain cpus to execute this slower than doing a DWORD PTR [EAX + EDX] where EDX is the counter and EAX is the start of the str.
- chacham15 13y ago
  I actually prefer the variation: char c; for (int i = 0; (c = str[i]) != '\0'; i++) ...loopcontents using c... this should be faster than all the rest of the implementations as you might break early and you save a memory dereference of every character. in all honesty though, these optimizations are highly unlikely to be the constraining factor on any loop so the question really is moot.
  - vidarh 13y ago
    If you're going to do that, why are you wasting instructions maintaining an offset and adding it to the string pointer on every iteration, instead of just iterating the pointer (or a copy of it) every iteration instead?
    - chacham15 13y ago
      I was trying to provide a semantically equivalent construct (you might need the current index for some computation). Furthermore, the difference between the two really is negligible. The current solution involves an increment to i, an increment to the pointer, and a dereference whereas the solution you describe only involves an increment to the pointer and a dereference. The difference is an increment to a number, i.e. a single instruction which is probably the fastest instruction in the ISA.
      - vidarh 13y ago
        Providing a semantically equivalent construct is a fair enough reason. > Furthermore, the difference between the two really is negligible. > ... > The difference is an increment to a number, i.e. a single instruction which is probably the fastest instruction in the ISA. Whether or not it matters will depend greatly on how often this loop is executed, and what else it does, and the ISA and available address modes, as well as whether or not the pointer and/or counter can fit in available registers. If the pointer and counter is not in registers, and you don't have a suitable indirect indexed type load/test instruction, you can easily end up with 3+ extra memory reads. Memory access gets expensive if/when those kind of loops are run often enough. I've seen speed improvements of 30%-50% from a couple of hours of work from production systems just from trivial rewrites to reduce memory accesses like these. Some fixes like that have paid my salary for months in reduction in server investments.
- jbert 13y ago
  My guess/intuition was that walking backwards might defeat any memory pre-caching at various layers (CPU, OS). I wrote this quick-and-dirty code [http://codepad.org/d9ilykxA http://codepad.org/d9ilykxA] to try and test the effect. To me, it's a little interesting how it various with optimisation level, but I've not picked apart the assembly to see what's going on. Under gcc 4.8.1, 64bit ubuntu): -O0 forwards 4.37s, backwards 4.88s (fowards faster) -O1 forwards 2.67s, backwards 2.66s (same/backwards faster) -O2 forwards 2.67s, backwards 2.66s (same/backwards faster) -Os forwards 3.33s, backwards 3.00s (backwards faster) and the same under clang: -O0 forwards 3.35s, backwards 4.11s -O1 forwards 2.67s, backwards 2.67s -O2 forwards 0.69s, backwards 0.77s -Os forwards 2.67s, backwards 3.00s So...it's not as simple as "forwards or backwards always faster", unless the test code is simple enough to be defeated by the optimiser in some cases which real code wouldn't. Also - what is going on with clang -O2?
  - goldenkey 13y ago
    I don't believe these tests show much. You need to be doing something realistic inside the loop, and not repeating it using num_iterations, that will probably be optimized out into an unrolled memcpy. Too simplistic to be an accurate test. Modern CPUs will precache memory forwards as well as in reverse.
jayferd 13y ago
This is a problem in most imperative-paradigm languages, unfortunately. The issue is in the semantics of the `for` loop, which make everything confusing both for the programmer and the compiler.
- 10098 13y ago
  I think the issue is that you don't know what's going to happen when you call an arbitrary function.
Nursie 13y ago
No, C is lower level than you think. That's perfectly rational behaviour. And yes, the string could change mid iteration, in the loop or in another function that has access to the address, or even in another thread that's just made a guess at a valid memory address. This is the beauty and power of C, everything is a piece of memory and nothing is guaranteed, and no we will not hold your hand or stop you doing something stupid. Someone else has a valid use case for that, even if they don't know it yet.
- sgift 13y ago
  > This is the beauty and power of C, everything is a piece of memory and nothing is guaranteed, and no we will not hold your hand or stop you doing something stupid. Someone else has a valid use case for that, even if they don't know it yet. Just replace C with assembler and we know why we should all go back to it. Or rather not ..? Guarantees provide reliable environments. Reliablity is really helpful. My nitpick aside ... I still want to (finally, really) learn C some time. Yeah, I can read it more or less, but that's not the same. Maybe on my next vacation.
  - goldenkey 13y ago
    I really don't think you have a space to speak here if you don't know C. C is a behemoth, sure but there's no surprises. And assembler is platform specific, so you can't really make the 'bandwagon'/'slippery slope' logical fallacy. Stay in Python/Ruby/TLC world, and leave us hard-core coders alone. We'll continue making the performant libs that your dynamic language runtime requires. Thanks.
    - deleted 13y ago
      [deleted]
    - sgift 13y ago
      Much real world C code is platform specific too. As written: I can read C (more or less) and I can recognize things like code that will only work on your nice little endian platform and will explode in your face on big endian. Code like that is written all the time in C - especially by programmers that "continue making the performant libs" or whatever you think you do. So, the abstraction over assembler is often far smaller than you make it out to be. But that is a completely different point, which has nothing to do with my last post.
deleted 13y ago
[deleted]
10098 13y ago
It's weird to me that a post like this even needs to be written. Isn't it kind of obvious that it's highly problematic for the compiler to do this optimization because the function, generally speaking, may have side effects?
- smsm42 13y ago
  In this particular case it's not even the fact that strlen may have side effects. Suppose we had syntax to tell the compiler strlen is a pure function. It still could not optimize it out because it'd have to know that strlen argument (both itself and memory it points to) is not going to change inside the loop either. By the time you're done checking all the Vs that compiler needs to actually optimize it, it may be much easier to rewrite the loop. At least that way you'd know exactly what's going on and won't have to disassemble binaries to find it out.
- ygra 13y ago
  It might be obvious to people with some experience. Many C programmers never read the standard or understand how the language works exactly, though. And to those people it might not immediately be obvious that for the strlen to be hoisted out of the loop the compiler would have to guarantee that the string's memory cannot change at all during the same loop. And that any function call can already lead to the compiler giving up trying to guarantee that.
- username42 13y ago
  For me, this kind of post means that C language is not any more core basic knowledge. The new generation has selected a new set of core basic knowledge: javascript, html5, python (for teaching of algorithm, not for production), scalability, replication, UX/UI ...
fhd2 13y ago
Here's a gotcha I find more interesting than strlen: Right shifting integers instead of dividing by powers of two, e.g: 1337 / 8; Becomes: 1337 >> 3; Compilers ought to figure that one out, shouldn't they? Well if 1337 is a signed int, they can't. Shifting actually leads to different semantics for negative numbers, so this optimisation is only possible for unsigned ints. You can either do the bit shift or cast to unsigned, but it's a leaky abstraction either way.
- azernik 13y ago
  I'm pretty sure that the different semantics for negative signed ints (sign extension) are there to make sure it works as division. It's right-shifting for regular bit manipulation purposes that's unsafe with signed.
  - icodestuff 13y ago
    Whether right-shift is arithmetic or logical is implementation-defined in C. The compiler (for obvious reasons) knows what hardware is available, and generally optimizes a divide by a power of two to a right-shift if arithmetic is available (as it is in most architectures), plus a check to see if the number is odd and negative (and to add 1 to the numerator if so). All of which is still faster than using the divide hardware.
    - azernik 13y ago
      One more instance where I just assumed that what GCC does was in the standard. Very interesting. For the curious who don't want to duplicate my look-up - right shift is by definition division by two except negative signed numbers, for which it's implementation defined. GCC on every architecture I've checked uses arithmetic shift for signed, probably because that extends the base definition to negatives.
vsbuffalo 13y ago
This seems like surprising behavior because we expect compilers will make wise choices. Beginning programmers do the same: for example I've seen something like: for x in stuff_list: print other_list_of_stuff.count(x) This is intuitive to beginning programmers and uses Python's methods. But there's hidden complexity behind it. C is no worse a language for not moving strlen out of the loop than Python is for not optimizing this. Languages work at their level, and it's essential the programmer understand the precise bounds of this level.
- smsm42 13y ago
  Nobody who tried to write some code compiling something (I'm not even talking about optimizing C compiler, but parsing or processing any sufficiently rich format that humans can touch) wouldn't expect compilers to make too much of the wise choices. Making code that behaves correctly, in a predictable manner according to what people expect and be "wise" too is very hard. It's easy to say "oh, it's clear I meant foo when I wrote bar" but try to make a code that identifies cases where "bar" means "foo" with 100% accuracy and you'll get why compilers aren't as wise as some think they could be.
Theriac25 13y ago
tl;dr if you don't know what you're doing, you don't know what you're doing.
augustk 13y ago
The problem here is that the for loop in C is a direct generalization of the while loop. In a Pascal-like language like Oberon the bound is only calculated once, so FOR i := 0 TO Strings.Length(s) - 1 DO ... END would be equivalent to lim := Strings.Length(s) - 1; WHILE i <= lim DO ... INC(i) END
aneeskA 13y ago
http://prog21.dadgum.com/179.html http://prog21.dadgum.com/179.html This is my favourite article of him :)
DmitryNovikov 13y ago
P.S. We have PVS-Studio rule for this issue: http://www.viva64.com/en/d/0309/ http://www.viva64.com/en/d/0309/
joshguthrie 13y ago
I don't see how the compiler's smartness factors in a language's level.

45 points by prajjwal 13y ago

There's no reason that the compiler should even optimize strlen out of the loop. Here's the proper way to iterate a string if order doesn't matter, take notice: for (int i = strlen(str); i--;) ...loopContents... There's a right way to handle values that are repeatedly used, and a wrong way, ie. relying on the compiler to optimize. Many dynamic languages store the length of a string buffer, as part of a String object. ie str.length, and it's very cheap to query, just an accessor/property/getter. What is misguided in this rant, is the attack against strlen which operates on pointers to zero-terminated strings. The length isn't stored, the only storage is for the string's bytes. If you want to have fast access to strlen, and you find yourself being pained by the extra variable to cache the value, then use std::string. This blog post needs a refactor.

rcfox 13y ago
The author isn't saying that there's anything wrong with strlen; he's just saying that it's not trivially optimizable like it might seem to be. Also, std::string is C++, not C.
- goldenkey 13y ago
  Sorry, that was a slipup. What I meant is a string object library. std::string would be fine in the case of C++ or bstring for C http://bstring.sourceforge.net/ http://bstring.sourceforge.net/
icodestuff 13y ago
Did we read the same article? I read no rant against `strlen`, but rather against naive programmers incorrectly assuming that it could/should be hoisted out by an optimizing compiler. There was not one word about being pained by an extra variable, rather that it's a clunky-but-correct solution. And other languages have nothing to do with it; this is strictly a post about C, not a dynamic language, and not C++.
- goldenkey 13y ago
  Just seems silly to rant against strings in C when they aren't really strings at all. char* is explicity a pointer to a sequence of chars. If a developer wants more things, like a cached length, invalidated by changes, then a lib should be used. A string lib like bstring[0]. I think we get to this precarious place by even considering that char* somehow brings what we could call 'common string functions' to the forefront in an easy way. And of course, assuming the compiler will optimize away code like strlen where it cannot possibly deduce constant memory conditions for the null byte, very silly indeed. [0] http://bstring.sourceforge.net/ http://bstring.sourceforge.net/ C is low level, but the same mistake could be said for any other language where a function is repeatedly called in a loop. The compiler can only do so much, garbage code is still garbage code. Cache your function calls less they const restricted, and extremely simple, and even then, the compiler might still fail to optimize.
  - icodestuff 13y ago
    Where do you get the idea that the author is ranting against strings in C? I don't see it.
    - goldenkey 13y ago
      He's ranting against repeated function calls. Same could be said for any other language. The only interesting thing here is that strlen is the main way to get the length of a string in C, unlike OOP languages that will have a .length accessor that usually keeps the last validated length for o(1) access. That doesn't mean C is subterranean leveled.. it just means the language isn't OOP .. use a lib/struct/functions and the problem is solved. I see this as a baseless attack on C's lack of OOP through some clever bashing.
      - mbel 13y ago
        Storing length with pointer to array has nothing to do with OOP, strings can be defined as simple records (aka structs, product types) you don't need OOP for that: struct string_t { const char * buffer; int lenght }; And really, I fail to see any attack on C in this article, it only mentions what a naive programmer might do, and why he/she shouldn't.
unwind 13y ago
No beginner programmer (the premise of the article) will loop over a string backwards. No beginner programmer will put the decrement in the test slot like you did, in order to make i have valid values in the loop body. I think it's somewhat scary to rely on post-decrement; I tend to favor pre-decrement in for loops as a general pattern, but of course in your code it must be post or it will break on an empty string. I still think the original article's suggestion to manually pre-compute the length (storing it in a const size_t variable, of course) is the better option, overall.
- goldenkey 13y ago
  This is the fastest way to write a loop in pretty much any language _if_ order is not imperative and is very well understood by any developer worth their salt. > I tend to favor pre-decrement in for loops as a general pattern, but of course in your code it must be post or it will break on an empty string. That makes absolutely no sense. It's post-increment so it runs for i=0, could have easily been: for (int i = strlen(str); --i >= 0;) http://codepad.org/kd3oOBAb http://codepad.org/kd3oOBAb <-- fiddle around beginner ;-)
  - unwind 13y ago
    Huh? I'm aware that there can be benefits to looping backwards. There can also be (cache-related) drawbacks. "It's post-increment so it runs for i=0" is probably exactly what I meant, you needed to use post-decrement (not increment) since otherwise it would break. Of course it can be re-written like you did now, but then you added the >= 0 part which was implicit in your first comment. Its omission made it important to pick post-decrement or it would break on an empty string just as I said. My entire point was that it's beyond most beginners to rely on fairly subtle things like that. Not sure why you're so condescending, I certainly didn't try to call you a beginner, it was the other way around: your code was not very beginner-esque, but the original article was about how a C beginner might write a simple loop and be surprised.
    - goldenkey 13y ago
      I see what you mean now, I was quick to judge, wrongly albeit. Sorry about that.
Rangi42 13y ago
"The proper way"? Not only is it less familiar than the usual "i = 0; i < n; i++" idiom, requiring the reader to examine exactly what it's doing, but now i goes from n to 1 instead of 0 to n-1. What's so bad about caching the strlen result in a variable beforehand?
- tedunangst 13y ago
  You have read his loop wrong. It has the same bounds.
- nitrogen 13y ago
  i goes from n-1 to 0 in the example because for loops execute the condition before the first iteration.
- goldenkey 13y ago
  You're wrong. Maybe I should hire my next team based on loop analysis ;-) http://codepad.org/kd3oOBAb http://codepad.org/kd3oOBAb
  - vidarh 13y ago
    And I think this perfectly demonstrates why it is a stupid approach to take in the first place. In fact, personally I have a tendency to avoid for-loops in C because of the awful syntax; I much prefer using while-loops as I find them far clearer. In 25+ years of C, I've seen plenty of people getting for-loops wrong (making broken assumptions about what's evaluated where, and countless off by one bugs), but everyone gets while-loops. If you are going to do for-loops in C, stick with the most obvious, simplest variants possible - the moment you try to be smart, you've substantially increased the odds that a maintenance programmer will introduce a bug at one point or another.
    - nitrogen 13y ago
      For the sake of job security, I propose using the comma operator to put the entire loop body within the for() parentheses, and replace the block with a semicolon: // Pure C99 (prints an invalid character at the end) for( FILE *f = fopen("/etc/fstab", "r"); !feof(f) || (fclose(f), 0); putchar(fgetc(f)) ) ; // C99+POSIX for( int fd = open("/etc/fstab", O_RDONLY), c = 0; read(fd, &c, 1) || (close(fd), 0); write(1, &c, 1) ) ;
coldtea 13y ago
>What is misguided in this rant, is the attack against strlen which operates on pointers to zero-terminated strings. The length isn't stored, the only storage is for the string's bytes. No attack at strlen at all. Perhaps you didn't read it correctly? Not to mention the author already knows all of this (trivial) information. The only attack is at the naive assumption of some newbie programmers (which the blog post targets) that "the compiler should take care of that".
p1esk 13y ago
Wow, this "for (int i = strlen(str); i--;) printf("%c", str[i]);" trick to reverse a string is really cool! Thanks!
- vidarh 13y ago
  I realise this is illustrating something, but just in case: For the love of all that is good, please don't actually printf() for every character... Depending on your platform that may or may not result in a ridiculous number of system calls, but no matter what, it will be slow if you do it a lot. If you insist on calling a function for every character (which is still silly), please at least putchar()/putc()/fputc() (putc()/putchar() can expand inline, but even they have substantial overhead to lock the stream) I've seen systems spend the majority of their time in IO functions because of stuff like that. Always, always, always batch up IO unless you have real reasons not to (and almost always avoid syscalls when you can)
  - p1esk 13y ago
    Is there a good resource or book on how to write high performance C code? I just started learning programming, and I will need to write C for simulations (well, it will be CUDA version of C or C++).
    - vidarh 13y ago
      I can't think of any good books of the top of my head - I've picked this up largely from starting out with assembly, and spending years picking apart compiler output (initially because the C compilers I had access to were junk, and I more than once would compile something, disassemble it and then hand-optimise the result...) One approach is to learn to read assembly (being able to write it from scratch is optional), and understand what affects clock cycle count. On modern architectures that also means understanding cache effects, and particularly looking out for memory access patterns. Then look at lots of disassembly and learn to understand what kind of code typically gets generated from your C. Often it will be plain obvious why things are slow when you see the amount of generated code (though here be dragons - sometimes modern compilers will actually do a good job optimising, and as a result produce code that no sane human would ever write manually). You can quickly get a good feel for patterns that are good and bad. But in general: - Profile. Profile some more, to make sure you're actually spending your time on the code that matters. - A useful rule of thumb is that for any given algorithm, the fewer function calls and memory accesses, the better it is likely to to be. Functions calls are expensive, and often (not always) reduce locality of code, and so increase the amount of time spent accessing memory that is not in cache (== expensive). But don't start hand-unrolling/removing abstractions until you know by profiling that the code in question is performance critical, or you may just end up creating a maintenance nightmare. - System calls are particularly nasty on any memory protected modern OS. The context switch overhead tends to be absolutely brutal. Which means it's very often worth quickly breaking out strace (on Linux) or equivalents to quickly eyeball the system call behaviour of applications before spending much time on other stuff. E.g. one particular pet peeve of mine is the amount of time you see read() or write() with small byte counts - if that occurs often, you can sometimes get truly massive speedups simply by changing the code to do non-blocking read/writes to/from a buffer and do smaller read/write's in user space from those buffers. (Always be suspicious of code that does read/write/recv/send or similar unless you can see it uses large-ish buffers... but profile). My experience is that odds are shockingly high that people will severely underestimate the cost of system calls. - Keep data that is accessed together close in memory. E.g. cluster values by access patterns when you can, to avoid thrashing cache when you access the data. This can be tricky, and the solutions can be non-obvious because the actual access patterns may not be that easy to spot.
derefr 13y ago
It seems that everyone's forgetting the whole genius thing about C-strings, which is that you can iterate through them without advance knowledge of their length: char c; while(c = *(str++)) ... This is, after all, the loop strlen() itself performs.
- vidarh 13y ago
  Which is great if you're guaranteed to advance one character per loop iteration. Which may or may not hold.
- goldenkey 13y ago
  True, this is even better in terms of complexity. I'd be curious to know if constantly changing the pointer causes certain cpus to execute this slower than doing a DWORD PTR [EAX + EDX] where EDX is the counter and EAX is the start of the str.
chacham15 13y ago
I actually prefer the variation: char c; for (int i = 0; (c = str[i]) != '\0'; i++) ...loopcontents using c... this should be faster than all the rest of the implementations as you might break early and you save a memory dereference of every character. in all honesty though, these optimizations are highly unlikely to be the constraining factor on any loop so the question really is moot.
- vidarh 13y ago
  If you're going to do that, why are you wasting instructions maintaining an offset and adding it to the string pointer on every iteration, instead of just iterating the pointer (or a copy of it) every iteration instead?
  - chacham15 13y ago
    I was trying to provide a semantically equivalent construct (you might need the current index for some computation). Furthermore, the difference between the two really is negligible. The current solution involves an increment to i, an increment to the pointer, and a dereference whereas the solution you describe only involves an increment to the pointer and a dereference. The difference is an increment to a number, i.e. a single instruction which is probably the fastest instruction in the ISA.
    - vidarh 13y ago
      Providing a semantically equivalent construct is a fair enough reason. > Furthermore, the difference between the two really is negligible. > ... > The difference is an increment to a number, i.e. a single instruction which is probably the fastest instruction in the ISA. Whether or not it matters will depend greatly on how often this loop is executed, and what else it does, and the ISA and available address modes, as well as whether or not the pointer and/or counter can fit in available registers. If the pointer and counter is not in registers, and you don't have a suitable indirect indexed type load/test instruction, you can easily end up with 3+ extra memory reads. Memory access gets expensive if/when those kind of loops are run often enough. I've seen speed improvements of 30%-50% from a couple of hours of work from production systems just from trivial rewrites to reduce memory accesses like these. Some fixes like that have paid my salary for months in reduction in server investments.
jbert 13y ago
My guess/intuition was that walking backwards might defeat any memory pre-caching at various layers (CPU, OS). I wrote this quick-and-dirty code [http://codepad.org/d9ilykxA http://codepad.org/d9ilykxA] to try and test the effect. To me, it's a little interesting how it various with optimisation level, but I've not picked apart the assembly to see what's going on. Under gcc 4.8.1, 64bit ubuntu): -O0 forwards 4.37s, backwards 4.88s (fowards faster) -O1 forwards 2.67s, backwards 2.66s (same/backwards faster) -O2 forwards 2.67s, backwards 2.66s (same/backwards faster) -Os forwards 3.33s, backwards 3.00s (backwards faster) and the same under clang: -O0 forwards 3.35s, backwards 4.11s -O1 forwards 2.67s, backwards 2.67s -O2 forwards 0.69s, backwards 0.77s -Os forwards 2.67s, backwards 3.00s So...it's not as simple as "forwards or backwards always faster", unless the test code is simple enough to be defeated by the optimiser in some cases which real code wouldn't. Also - what is going on with clang -O2?
- goldenkey 13y ago
  I don't believe these tests show much. You need to be doing something realistic inside the loop, and not repeating it using num_iterations, that will probably be optimized out into an unrolled memcpy. Too simplistic to be an accurate test. Modern CPUs will precache memory forwards as well as in reverse.

jayferd 13y ago

This is a problem in most imperative-paradigm languages, unfortunately. The issue is in the semantics of the `for` loop, which make everything confusing both for the programmer and the compiler.

10098 13y ago
I think the issue is that you don't know what's going to happen when you call an arbitrary function.

Nursie 13y ago

No, C is lower level than you think. That's perfectly rational behaviour. And yes, the string could change mid iteration, in the loop or in another function that has access to the address, or even in another thread that's just made a guess at a valid memory address. This is the beauty and power of C, everything is a piece of memory and nothing is guaranteed, and no we will not hold your hand or stop you doing something stupid. Someone else has a valid use case for that, even if they don't know it yet.

sgift 13y ago
> This is the beauty and power of C, everything is a piece of memory and nothing is guaranteed, and no we will not hold your hand or stop you doing something stupid. Someone else has a valid use case for that, even if they don't know it yet. Just replace C with assembler and we know why we should all go back to it. Or rather not ..? Guarantees provide reliable environments. Reliablity is really helpful. My nitpick aside ... I still want to (finally, really) learn C some time. Yeah, I can read it more or less, but that's not the same. Maybe on my next vacation.
- goldenkey 13y ago
  I really don't think you have a space to speak here if you don't know C. C is a behemoth, sure but there's no surprises. And assembler is platform specific, so you can't really make the 'bandwagon'/'slippery slope' logical fallacy. Stay in Python/Ruby/TLC world, and leave us hard-core coders alone. We'll continue making the performant libs that your dynamic language runtime requires. Thanks.
  - deleted 13y ago
    [deleted]
  - sgift 13y ago
    Much real world C code is platform specific too. As written: I can read C (more or less) and I can recognize things like code that will only work on your nice little endian platform and will explode in your face on big endian. Code like that is written all the time in C - especially by programmers that "continue making the performant libs" or whatever you think you do. So, the abstraction over assembler is often far smaller than you make it out to be. But that is a completely different point, which has nothing to do with my last post.

deleted 13y ago

[deleted]

10098 13y ago

It's weird to me that a post like this even needs to be written. Isn't it kind of obvious that it's highly problematic for the compiler to do this optimization because the function, generally speaking, may have side effects?

smsm42 13y ago
In this particular case it's not even the fact that strlen may have side effects. Suppose we had syntax to tell the compiler strlen is a pure function. It still could not optimize it out because it'd have to know that strlen argument (both itself and memory it points to) is not going to change inside the loop either. By the time you're done checking all the Vs that compiler needs to actually optimize it, it may be much easier to rewrite the loop. At least that way you'd know exactly what's going on and won't have to disassemble binaries to find it out.
ygra 13y ago
It might be obvious to people with some experience. Many C programmers never read the standard or understand how the language works exactly, though. And to those people it might not immediately be obvious that for the strlen to be hoisted out of the loop the compiler would have to guarantee that the string's memory cannot change at all during the same loop. And that any function call can already lead to the compiler giving up trying to guarantee that.
username42 13y ago
For me, this kind of post means that C language is not any more core basic knowledge. The new generation has selected a new set of core basic knowledge: javascript, html5, python (for teaching of algorithm, not for production), scalability, replication, UX/UI ...

fhd2 13y ago

Here's a gotcha I find more interesting than strlen: Right shifting integers instead of dividing by powers of two, e.g: 1337 / 8; Becomes: 1337 >> 3; Compilers ought to figure that one out, shouldn't they? Well if 1337 is a signed int, they can't. Shifting actually leads to different semantics for negative numbers, so this optimisation is only possible for unsigned ints. You can either do the bit shift or cast to unsigned, but it's a leaky abstraction either way.

azernik 13y ago
I'm pretty sure that the different semantics for negative signed ints (sign extension) are there to make sure it works as division. It's right-shifting for regular bit manipulation purposes that's unsafe with signed.
- icodestuff 13y ago
  Whether right-shift is arithmetic or logical is implementation-defined in C. The compiler (for obvious reasons) knows what hardware is available, and generally optimizes a divide by a power of two to a right-shift if arithmetic is available (as it is in most architectures), plus a check to see if the number is odd and negative (and to add 1 to the numerator if so). All of which is still faster than using the divide hardware.
  - azernik 13y ago
    One more instance where I just assumed that what GCC does was in the standard. Very interesting. For the curious who don't want to duplicate my look-up - right shift is by definition division by two except negative signed numbers, for which it's implementation defined. GCC on every architecture I've checked uses arithmetic shift for signed, probably because that extends the base definition to negatives.

vsbuffalo 13y ago

This seems like surprising behavior because we expect compilers will make wise choices. Beginning programmers do the same: for example I've seen something like: for x in stuff_list: print other_list_of_stuff.count(x) This is intuitive to beginning programmers and uses Python's methods. But there's hidden complexity behind it. C is no worse a language for not moving strlen out of the loop than Python is for not optimizing this. Languages work at their level, and it's essential the programmer understand the precise bounds of this level.

smsm42 13y ago
Nobody who tried to write some code compiling something (I'm not even talking about optimizing C compiler, but parsing or processing any sufficiently rich format that humans can touch) wouldn't expect compilers to make too much of the wise choices. Making code that behaves correctly, in a predictable manner according to what people expect and be "wise" too is very hard. It's easy to say "oh, it's clear I meant foo when I wrote bar" but try to make a code that identifies cases where "bar" means "foo" with 100% accuracy and you'll get why compilers aren't as wise as some think they could be.

Theriac25 13y ago

tl;dr if you don't know what you're doing, you don't know what you're doing.

augustk 13y ago

The problem here is that the for loop in C is a direct generalization of the while loop. In a Pascal-like language like Oberon the bound is only calculated once, so FOR i := 0 TO Strings.Length(s) - 1 DO ... END would be equivalent to lim := Strings.Length(s) - 1; WHILE i <= lim DO ... INC(i) END

aneeskA 13y ago

http://prog21.dadgum.com/179.html http://prog21.dadgum.com/179.html This is my favourite article of him :)

DmitryNovikov 13y ago

P.S. We have PVS-Studio rule for this issue: http://www.viva64.com/en/d/0309/ http://www.viva64.com/en/d/0309/

joshguthrie 13y ago

I don't see how the compiler's smartness factors in a language's level.