9 ms·

Will it optimize?

357 points by mark_h 16y ago

wooster 16y ago
ridiculousfish is the smartest programmer I've ever met. I hired him at Apple years ago, and while I could regale you with tales of how awesome he is, Apple would probably sue me. That said, if you've ever played World of Warcraft on the Mac, you should worship him as a god. :-)
- mark_h 16y ago
  If you ever find a way to regale us without being sued, I am all ears :) His blog is that perfect combination of really meaty articles that are published infrequently enough to really be savoured.
- zackattack 16y ago
  This dude is pretty much my dream cofounder. Math background, aesthetically intuitive, intellectually curious, specifically interested in psychology, and clearly a talented programmer. http://upload.wikimedia.org/wikipedia/commons/thumb/4/4f/Corydoras_semiaquilus_1.jpg/800px-Corydoras_semiaquilus_1.jpg http://upload.wikimedia.org/wikipedia/commons/thumb/4/4f/Cor...
  - messel 16y ago
    Wooster would never let him go. Better to offer woost an irresistable offer, then go after this fellow. Seriously beautiful post layout
    - pbhjpbhj 16y ago
      >Seriously beautiful post layout Shame about the blog chrome. Seriously all I had above the fold was the fish picture and until I looked at the scrollbar I'd nothing to indicate that the page had any content, I assumed it was some sort of flash game. Also within the post the code overflows the code boxes for me (I'm 2 clicks up on font size). Looks to be some problem on the all-posts page too - http://ridiculousfish.com/blog/all-posts/ http://ridiculousfish.com/blog/all-posts/ FWIW.
      - messel 16y ago
        I'm using the latest chromium daily build and it looked fine.
- wheaties 16y ago
  Sounds like the kind of guy I want to work with on a daily basis even if half the time he spent yelling at me for doing something stupid. After a few months I'd be such a better programmer.
pquerna 16y ago
great post with a nice quiz format!
- gwern 16y ago
  I wish more posts used quizzes; they make it that much harder to lie to yourself.
praptak 16y ago
Gcc surprised me once. I had put some effort into replacing something like (x << 12) | (x>>20) with the appropriate roll instruction at the assembly level. Only after seeing that the "optimized" code ran no faster than plain GCC, I looked at the GCC output and of course the roll was there. I believe it was GCC 3.*, so even older than the one mentioned in the article.
chipsy 16y ago
I got almost all of it wrong. I'm not very familiar with gcc's workings and usually just figure that the compiler is going to be dumb and fail at everything but the simplest optimizations. But then, when I actually go to do the tedious and source-obfuscating micro stuff I usually check my assumptions first - you kind of have to anyway, once you go that deep.
- JoachimSchipper 16y ago
  The point of most of the optimizations mentioned in the article is not to make programs run faster; e.g. any competent programmer can hoist constant functions out of a for loop himself, but knowing that the compiler will do this allows you to write cleaner code. (This does not apply to e.g. auto-vectorization, which replaces 'x[0] = y[0] * z[0]; x[1] = y[1] * z[1]; ...' by a single (SSE?) instructions which calculates all of that at once. Such instructions are much faster and would require dropping down to assembly without a good optimizer.)
- dkarl 16y ago
  when I actually go to do the tedious and source-obfuscating micro stuff I usually check my assumptions first - you kind of have to anyway, once you go that deep. Absolutely. Fun to read, made me smarter, but half of it could be different in any other version of gcc. And frankly, if these are your problems, you're doing pretty well. I worked on a product that had some numerical parts, which were sometimes the limiting factor in performance, though usually not. So one day I was talking to a guy who wrote the numerical code about why regression testing was difficult and subtle, and it was revealed that our numerical results could differ from build to build. I.e., a single build of the product always produced the same results, but if you changed the floating point code, the new build might produce different (though equally accurate) results, even if semantically the program was supposed to perform the same C math operations on the same data. Which makes perfect sense if you're using the old stack-based x87-style floating point instructions. We couldn't be... not in the 21st century on Opterons... check Makefile and gcc man page... biggest facepalm of my career. We were able to announce a nice speedup on some workloads in the next release.
losethos 16y ago
help, I'm being held by someone.
deleted 16y ago
[deleted]
robryan 16y ago
Great article, only really have a basic knowledge of C from uni, but easy to follow along and learn something.
tumult 16y ago
Got me on the first and last ones. Cool post! I think the fact that I got the first one wrong made me err too far into thinking GCC was smarter than I had first assumed. And it is, but only for certain things.
smcl 16y ago
Ha, I really like this guy. I started reading another one of his blog entries (a description of how compilers often optimise a divide by a constant where, instead of issuing an expensive divide, it multiplies by a "magic" number and then right shifts the result). After hitting lots of complex (for me anyway) mathematical proofs, my brain tuned out slightly until I saw "Did you skip ahead? It's OK. Here's the summary" I like to think he deliberately did that for hungover-yet-still-interested devs like myself.
- sprout 16y ago
  Well, I never read proofs on the first pass. I mean, I read each expression, but I don't bother trying to assimilate them into a coherent thought until I've finished any plain-English associated text. And even that I'll sometimes wait to properly comprehend for a second pass.
jakevoytko 16y ago
I avoid these types of optimizations, say, 97% of the time This reminded me of Linus' blog post on optimizing SHA1 routines in Git [0]. FTA: "Some people seem to think that C is a real programming language, but they are sadly mistaken. It really is about writing almost-portable assembly language, and it turns out that getting good results from SHA1 really is mostly about trying to fight the compilers tendency to try to be clever." [0] http://torvalds-family.blogspot.com/2009/08/programming.html http://torvalds-family.blogspot.com/2009/08/programming.html
- stcredzero 16y ago
  A long, long time ago, I recall that someone did a study of code generated by C compilers and found that, on average, 1 C statement = 2.5 lines of assembly. (for CISC)
- briansmith 16y ago
  "Improving the Performance of the Secure Hash Algorithm" (by transforming the algorithm mathematically and then using hand-written assembler with SIMD instructions): http://software.intel.com/en-us/articles/improving-the-performance-of-the-secure-hash-algorithm-1/ http://software.intel.com/en-us/articles/improving-the-perfo...
- igorgue 16y ago
  SHA1 is still pretty damn fast in Git, I couldn't be able to get an even close speed with my own implementation.
- grogers 16y ago
  There is a self tuning linear algebra library called ATLAS. When building, probes various things about your computer, things like L1/L2 cache, if you have fused multiply/add, etc. It uses these to output very highly tuned matrix kernels in standard C. Ironically, when compiling this C code, you have to use -O, higher optimization levels make the compiler try to be too smart for its own good and actually perform worse.
albertzeyer 16y ago
`x+x` is faster than `x*2`? Really? Why? And how about `x<<1`?
- _delirium 16y ago
  Addition and bitshifting are easier to implement in hardware than multiplication is, with less complicated circuits that can return results in fewer clock cycles (though the difference is much less than it used to be).
- mian2zi3 16y ago
  In a modern CPU, instruction selection is much more complicated than, "Oh, addl (or sll) is faster than umul," and depends on the micro-architecture/pipeline, surrounding code, etc. Addition usually takes one cycle, while multiplication might take several cycles (although, by pipelining, you can generally execute a multiply per cycle per multiplier) But, if all the other adders are full and the result isn't needed for a few cycles, it might be fastest to use the multiplier. (I'm thinking of a statically scheduled pipeline. Things get harder when the CPU does dynamic instruction reordering.)
  - _delirium 16y ago
    Do any compilers attempt to take those sorts of concerns into account? It seems like it'd be an interesting experiment, but it breaks some of the nice abstractions--- afaik, strength-reduction is usually done before scheduling, with the only architecture dependency being a table of costs assigned to each operation. Letting scheduling constraints have input on those decisions seems ideal but tricky, unless I'm missing something.
    - wwalker3 16y ago
      It would be very hard to accurately account for a microprocessor's out-of-order instruction issue in a compiler. A modern desktop-class microprocessor can have scores of instructions "in flight" at once. Each new instruction that's decoded gets reordered or stalled differently depending on the status of all of those previous instructions and their hardware requirements. A compiler could try to model the processor's microarchitecture and simulate how it would execute the program, but that simulation would be inaccurate because of data-dependent branching, interrupts, and other unpredictable behaviors. Plus, the microarchitectural details you'd need to create such a simulation are usually not available. That said, compilers can still tailor code to the microarchitecture in a general way. For example, if you know a processor can only decode one branch instruction per cycle, you can try to reorder the compiled code to avoid back-to-back branches in the instruction stream.
mian2zi3 16y ago
Nice post. This is how the Nullstone compiler optimization benchmark suite is organized: two functionally equivalent versions of a C program, one cleaner/suboptimal, the other optimized by hand. The goal is to have the generated code perform the same in either case.
stcredzero 16y ago
> And lastly, this isn’t meant to be a prescriptive post, > but we all know why micro-optimizing is usually a > mistake: it wastes your time, it’s easy to screw up > (see question 5), and it *typically* produces no > measurable speedup. I emphasized the typically because this is a key idea: you are fallible -- deal with it! I visited a local hacker-space with a friend of mine to talk about a project of ours. A bunch of those guys are NASA and they know quite a bit about how to engineer for reliability. Since our project involved a lot of soldering, he suggested that we estimate our average solder join failure rate and use that as the number of expected failures to look for. That's what he does in his personal projects. I exclaimed that was brilliant, then was a little embarrassed. Of course! Duh! I know I'm not perfect and I'm smart enough to have deduced that I have something like an average failure rate for solder joins. So why have I been proceeding for years and years as if I could just do everything perfectly if I just tried hard enough? Every new function you write is a risk. Minimize your risks. Maximize the cost/benefit. Every routine you optimize is a risk. Minimize your risks. Maximize cost/benefit. One's problems as a programmer are more likely the result of excess hubris and not insufficient smarts. EDIT: Fear is as big a problem as hubris. Walk the middle path. You are your own optimization problem, and the optimal solution is almost never a no-brainer shove of a lever all the way in some direction.
- flogic 16y ago
  That's awesome. I'm always impressed by the reliability work that comes out of NASA. I don't regret a single penny of my tax dollars which goes to them just for this sort of thing alone.
drblast 16y ago
Interesting article. By any chance, does this sort of information exist at all for Java bytecode compilers? Whenever I write Java code I try to do things the Java way but it usually makes me cringe to think that things like accessing a boolean field requires a function call. I console myself by thinking that this all gets optimized away by the JIT compiler, but I'd really like to know for sure.
viraptor 16y ago
Question number 2 really surprised me. What if the layout of memory is: (s)(s+1)(s+2)...(result) If `s` has no null bytes until `result`, then `strlen(s)` will terminate on `result`. However, if you change `result` while iterating over `s`, then `result` will be not null and the `strlen()` result will change. Or is there some rule in C standard that says local variables are not in the same memory range as external pointers?
- notaddicted 16y ago
  Since "result" is on the stack it will only be allocated at the time of the function call. Also note that the stack grows downwards in memory. To get the memory layout you've shown you'd have to be summing up the bytes in the unallocated memory between the heap and the top of the stack. Probably this is explained somehow in the standard but I don't personally know.
  - ramchip 16y ago
    "result" is not necessarily on the stack, and stack growth direction is implementation-specific: http://stackoverflow.com/questions/664744/what-is-the-direction-of-stack-growth-in-most-modern-systems http://stackoverflow.com/questions/664744/what-is-the-direct...
- ramchip 16y ago
  Attempting to read s[i] when i is outside the bounds of the array is undefined behaviour, so the compiler is free to ignore this case. See example at http://en.wikipedia.org/wiki/Undefined_behavior#Examples_in_C.2FC.2B.2B http://en.wikipedia.org/wiki/Undefined_behavior#Examples_in_... Certain pointer operations may result in undefined behavior: int main() { int arr[4] = {0, 1, 2, 3}; int * p = arr + 5; // undefined behavior } In short, you can't assume that result will be placed after the array. What if result is optimized to a register? It actually sounds quite likely to me given the tight loop.
  - afhof 16y ago
    With C comes the pedantry int main(int argc, char ** argv) { int arr[4] = {0, 1, 2, 3}; int * p = arr + 5; // valid *p; // undefined behavior return 0; }
afhof 16y ago
Concerning #2: Does 'const' mean that the function is not allowed to change the contents of the string, or does it mean that the contents of the string will never change? Suppose the 'sum' function was running in one thread, while in another the string that was passed in as 's' is being continuously written to. While this may not make much sense to do, and the output would not have a reliable value, this optimization would be the wrong thing to do.
- okmjuhb 16y ago
  const only means that the function is not allowed to change memory through that reference. It says nothing about aliases to the same memory. But the "what if another thread changes the string" issue is a red herring. The question to keep in mind when optimizing in a multi-threaded context is "does the output of the compiler generated code correspond to at least one possible interleaving of threads". Since this thread doesn't do any synchronization, it's possible that all the function executes without being interrupted by another thread, so this is a sound optimization.
- murrayh 16y ago
  You can prevent caching optimisations by declaring a variable 'volatile' (http://en.wikipedia.org/wiki/Volatile_variable http://en.wikipedia.org/wiki/Volatile_variable).
igorgue 16y ago
#2 was an error I had, and a co-worker told me screaming that I was a crappy programmer because I did it, now that I know it's optimized I feel like he owns me an apology or maybe not :-)
- yuvi 16y ago
  Were you using gcc? I wouldn't be surprised if e.g. MSVC didn't perform that optimization since it doesn't have the pure function attribute.
grogers 16y ago
"2. Loop-invariant strlen() GCC does this optimization, because strlen is a "built-in function:" one that gcc recognizes and optimizes specially. Disabling built-ins with -fno-builtin defeats this optimization." No, it does it because strlen is declared to be a pure function, and it is smart enough to realize you are not modifying anything in s. -fno-builtin does not change the generated code, it still calls the strlen function (at least on my gcc), but it is hoisted out of the loop.
- gfodor 16y ago
  If this is true it makes me happy because this is surely less of a hack.
- astrange 16y ago
  strlen() is not declared pure in the OS X headers.
nitrogen 16y ago
Wouldn't it be possible to optimize floating point multiplication by 2.0f (or any power of two) to an addition or subtraction on the exponent?
- astrange 16y ago
  Only on architectures with such instructions. x86 doesn't have anything like that (well, maybe in x87), and I don't know of any others that do.
  - nitrogen 16y ago
    So would moving the floating point value into an integer register, shifting, incrementing, ORing, etc. ever be faster than a full FP addition? I imagine that modern desktop CPUs have effectively-single-cycle multiply, but what about something like ARM with VFP but no Neon?
    - astrange 16y ago
      Only in architectures where FP and integer values are kept in the same registers. This is true in SSE2 and Altivec, so you can do integer operations there - but since SIMD integer operations are limited too, it's pretty much only useful for flipping the sign bit. Moving values between different register sets is INCREDIBLY slow since it involves at least two memory operations. And faking FP operations with specialized integer code on something with soft-float like ARM might be worth it. I've never done it so I can't really say.
Aegean 16y ago
He could have added the switch statement optimization. That's my favorite. GCC 4 can optimize switch statements with sequential keys e.g. (1,2,3,4 ...) into a jump table. This was AFAIK introduced in GCC 4
- ramchip 16y ago
  But he did: The switch statement was optimized to a jump table, while the if statements became a long sequence of compares.

357 points by mark_h 16y ago

ridiculousfish is the smartest programmer I've ever met. I hired him at Apple years ago, and while I could regale you with tales of how awesome he is, Apple would probably sue me. That said, if you've ever played World of Warcraft on the Mac, you should worship him as a god. :-)

mark_h 16y ago
If you ever find a way to regale us without being sued, I am all ears :) His blog is that perfect combination of really meaty articles that are published infrequently enough to really be savoured.
zackattack 16y ago
This dude is pretty much my dream cofounder. Math background, aesthetically intuitive, intellectually curious, specifically interested in psychology, and clearly a talented programmer. http://upload.wikimedia.org/wikipedia/commons/thumb/4/4f/Corydoras_semiaquilus_1.jpg/800px-Corydoras_semiaquilus_1.jpg http://upload.wikimedia.org/wikipedia/commons/thumb/4/4f/Cor...
- messel 16y ago
  Wooster would never let him go. Better to offer woost an irresistable offer, then go after this fellow. Seriously beautiful post layout
  - pbhjpbhj 16y ago
    >Seriously beautiful post layout Shame about the blog chrome. Seriously all I had above the fold was the fish picture and until I looked at the scrollbar I'd nothing to indicate that the page had any content, I assumed it was some sort of flash game. Also within the post the code overflows the code boxes for me (I'm 2 clicks up on font size). Looks to be some problem on the all-posts page too - http://ridiculousfish.com/blog/all-posts/ http://ridiculousfish.com/blog/all-posts/ FWIW.
    - messel 16y ago
      I'm using the latest chromium daily build and it looked fine.
wheaties 16y ago
Sounds like the kind of guy I want to work with on a daily basis even if half the time he spent yelling at me for doing something stupid. After a few months I'd be such a better programmer.

pquerna 16y ago

great post with a nice quiz format!

gwern 16y ago
I wish more posts used quizzes; they make it that much harder to lie to yourself.

praptak 16y ago

Gcc surprised me once. I had put some effort into replacing something like (x << 12) | (x>>20) with the appropriate roll instruction at the assembly level. Only after seeing that the "optimized" code ran no faster than plain GCC, I looked at the GCC output and of course the roll was there. I believe it was GCC 3.*, so even older than the one mentioned in the article.

chipsy 16y ago

I got almost all of it wrong. I'm not very familiar with gcc's workings and usually just figure that the compiler is going to be dumb and fail at everything but the simplest optimizations. But then, when I actually go to do the tedious and source-obfuscating micro stuff I usually check my assumptions first - you kind of have to anyway, once you go that deep.

JoachimSchipper 16y ago
The point of most of the optimizations mentioned in the article is not to make programs run faster; e.g. any competent programmer can hoist constant functions out of a for loop himself, but knowing that the compiler will do this allows you to write cleaner code. (This does not apply to e.g. auto-vectorization, which replaces 'x[0] = y[0] * z[0]; x[1] = y[1] * z[1]; ...' by a single (SSE?) instructions which calculates all of that at once. Such instructions are much faster and would require dropping down to assembly without a good optimizer.)
dkarl 16y ago
when I actually go to do the tedious and source-obfuscating micro stuff I usually check my assumptions first - you kind of have to anyway, once you go that deep. Absolutely. Fun to read, made me smarter, but half of it could be different in any other version of gcc. And frankly, if these are your problems, you're doing pretty well. I worked on a product that had some numerical parts, which were sometimes the limiting factor in performance, though usually not. So one day I was talking to a guy who wrote the numerical code about why regression testing was difficult and subtle, and it was revealed that our numerical results could differ from build to build. I.e., a single build of the product always produced the same results, but if you changed the floating point code, the new build might produce different (though equally accurate) results, even if semantically the program was supposed to perform the same C math operations on the same data. Which makes perfect sense if you're using the old stack-based x87-style floating point instructions. We couldn't be... not in the 21st century on Opterons... check Makefile and gcc man page... biggest facepalm of my career. We were able to announce a nice speedup on some workloads in the next release.

losethos 16y ago

help, I'm being held by someone.

deleted 16y ago

[deleted]

robryan 16y ago

Great article, only really have a basic knowledge of C from uni, but easy to follow along and learn something.

tumult 16y ago

Got me on the first and last ones. Cool post! I think the fact that I got the first one wrong made me err too far into thinking GCC was smarter than I had first assumed. And it is, but only for certain things.

smcl 16y ago

Ha, I really like this guy. I started reading another one of his blog entries (a description of how compilers often optimise a divide by a constant where, instead of issuing an expensive divide, it multiplies by a "magic" number and then right shifts the result). After hitting lots of complex (for me anyway) mathematical proofs, my brain tuned out slightly until I saw "Did you skip ahead? It's OK. Here's the summary" I like to think he deliberately did that for hungover-yet-still-interested devs like myself.

sprout 16y ago
Well, I never read proofs on the first pass. I mean, I read each expression, but I don't bother trying to assimilate them into a coherent thought until I've finished any plain-English associated text. And even that I'll sometimes wait to properly comprehend for a second pass.

jakevoytko 16y ago

I avoid these types of optimizations, say, 97% of the time This reminded me of Linus' blog post on optimizing SHA1 routines in Git [0]. FTA: "Some people seem to think that C is a real programming language, but they are sadly mistaken. It really is about writing almost-portable assembly language, and it turns out that getting good results from SHA1 really is mostly about trying to fight the compilers tendency to try to be clever." [0] http://torvalds-family.blogspot.com/2009/08/programming.html http://torvalds-family.blogspot.com/2009/08/programming.html

stcredzero 16y ago
A long, long time ago, I recall that someone did a study of code generated by C compilers and found that, on average, 1 C statement = 2.5 lines of assembly. (for CISC)
briansmith 16y ago
"Improving the Performance of the Secure Hash Algorithm" (by transforming the algorithm mathematically and then using hand-written assembler with SIMD instructions): http://software.intel.com/en-us/articles/improving-the-performance-of-the-secure-hash-algorithm-1/ http://software.intel.com/en-us/articles/improving-the-perfo...
igorgue 16y ago
SHA1 is still pretty damn fast in Git, I couldn't be able to get an even close speed with my own implementation.
grogers 16y ago
There is a self tuning linear algebra library called ATLAS. When building, probes various things about your computer, things like L1/L2 cache, if you have fused multiply/add, etc. It uses these to output very highly tuned matrix kernels in standard C. Ironically, when compiling this C code, you have to use -O, higher optimization levels make the compiler try to be too smart for its own good and actually perform worse.

albertzeyer 16y ago

`x+x` is faster than `x*2`? Really? Why? And how about `x<<1`?

_delirium 16y ago
Addition and bitshifting are easier to implement in hardware than multiplication is, with less complicated circuits that can return results in fewer clock cycles (though the difference is much less than it used to be).
mian2zi3 16y ago
In a modern CPU, instruction selection is much more complicated than, "Oh, addl (or sll) is faster than umul," and depends on the micro-architecture/pipeline, surrounding code, etc. Addition usually takes one cycle, while multiplication might take several cycles (although, by pipelining, you can generally execute a multiply per cycle per multiplier) But, if all the other adders are full and the result isn't needed for a few cycles, it might be fastest to use the multiplier. (I'm thinking of a statically scheduled pipeline. Things get harder when the CPU does dynamic instruction reordering.)
- _delirium 16y ago
  Do any compilers attempt to take those sorts of concerns into account? It seems like it'd be an interesting experiment, but it breaks some of the nice abstractions--- afaik, strength-reduction is usually done before scheduling, with the only architecture dependency being a table of costs assigned to each operation. Letting scheduling constraints have input on those decisions seems ideal but tricky, unless I'm missing something.
  - wwalker3 16y ago
    It would be very hard to accurately account for a microprocessor's out-of-order instruction issue in a compiler. A modern desktop-class microprocessor can have scores of instructions "in flight" at once. Each new instruction that's decoded gets reordered or stalled differently depending on the status of all of those previous instructions and their hardware requirements. A compiler could try to model the processor's microarchitecture and simulate how it would execute the program, but that simulation would be inaccurate because of data-dependent branching, interrupts, and other unpredictable behaviors. Plus, the microarchitectural details you'd need to create such a simulation are usually not available. That said, compilers can still tailor code to the microarchitecture in a general way. For example, if you know a processor can only decode one branch instruction per cycle, you can try to reorder the compiled code to avoid back-to-back branches in the instruction stream.

mian2zi3 16y ago

Nice post. This is how the Nullstone compiler optimization benchmark suite is organized: two functionally equivalent versions of a C program, one cleaner/suboptimal, the other optimized by hand. The goal is to have the generated code perform the same in either case.

stcredzero 16y ago

> And lastly, this isn’t meant to be a prescriptive post, > but we all know why micro-optimizing is usually a > mistake: it wastes your time, it’s easy to screw up > (see question 5), and it *typically* produces no > measurable speedup. I emphasized the typically because this is a key idea: you are fallible -- deal with it! I visited a local hacker-space with a friend of mine to talk about a project of ours. A bunch of those guys are NASA and they know quite a bit about how to engineer for reliability. Since our project involved a lot of soldering, he suggested that we estimate our average solder join failure rate and use that as the number of expected failures to look for. That's what he does in his personal projects. I exclaimed that was brilliant, then was a little embarrassed. Of course! Duh! I know I'm not perfect and I'm smart enough to have deduced that I have something like an average failure rate for solder joins. So why have I been proceeding for years and years as if I could just do everything perfectly if I just tried hard enough? Every new function you write is a risk. Minimize your risks. Maximize the cost/benefit. Every routine you optimize is a risk. Minimize your risks. Maximize cost/benefit. One's problems as a programmer are more likely the result of excess hubris and not insufficient smarts. EDIT: Fear is as big a problem as hubris. Walk the middle path. You are your own optimization problem, and the optimal solution is almost never a no-brainer shove of a lever all the way in some direction.

flogic 16y ago
That's awesome. I'm always impressed by the reliability work that comes out of NASA. I don't regret a single penny of my tax dollars which goes to them just for this sort of thing alone.

drblast 16y ago

Interesting article. By any chance, does this sort of information exist at all for Java bytecode compilers? Whenever I write Java code I try to do things the Java way but it usually makes me cringe to think that things like accessing a boolean field requires a function call. I console myself by thinking that this all gets optimized away by the JIT compiler, but I'd really like to know for sure.

viraptor 16y ago

Question number 2 really surprised me. What if the layout of memory is: (s)(s+1)(s+2)...(result) If `s` has no null bytes until `result`, then `strlen(s)` will terminate on `result`. However, if you change `result` while iterating over `s`, then `result` will be not null and the `strlen()` result will change. Or is there some rule in C standard that says local variables are not in the same memory range as external pointers?

notaddicted 16y ago
Since "result" is on the stack it will only be allocated at the time of the function call. Also note that the stack grows downwards in memory. To get the memory layout you've shown you'd have to be summing up the bytes in the unallocated memory between the heap and the top of the stack. Probably this is explained somehow in the standard but I don't personally know.
- ramchip 16y ago
  "result" is not necessarily on the stack, and stack growth direction is implementation-specific: http://stackoverflow.com/questions/664744/what-is-the-direction-of-stack-growth-in-most-modern-systems http://stackoverflow.com/questions/664744/what-is-the-direct...
ramchip 16y ago
Attempting to read s[i] when i is outside the bounds of the array is undefined behaviour, so the compiler is free to ignore this case. See example at http://en.wikipedia.org/wiki/Undefined_behavior#Examples_in_C.2FC.2B.2B http://en.wikipedia.org/wiki/Undefined_behavior#Examples_in_... Certain pointer operations may result in undefined behavior: int main() { int arr[4] = {0, 1, 2, 3}; int * p = arr + 5; // undefined behavior } In short, you can't assume that result will be placed after the array. What if result is optimized to a register? It actually sounds quite likely to me given the tight loop.
- afhof 16y ago
  With C comes the pedantry int main(int argc, char ** argv) { int arr[4] = {0, 1, 2, 3}; int * p = arr + 5; // valid *p; // undefined behavior return 0; }

afhof 16y ago

Concerning #2: Does 'const' mean that the function is not allowed to change the contents of the string, or does it mean that the contents of the string will never change? Suppose the 'sum' function was running in one thread, while in another the string that was passed in as 's' is being continuously written to. While this may not make much sense to do, and the output would not have a reliable value, this optimization would be the wrong thing to do.

okmjuhb 16y ago
const only means that the function is not allowed to change memory through that reference. It says nothing about aliases to the same memory. But the "what if another thread changes the string" issue is a red herring. The question to keep in mind when optimizing in a multi-threaded context is "does the output of the compiler generated code correspond to at least one possible interleaving of threads". Since this thread doesn't do any synchronization, it's possible that all the function executes without being interrupted by another thread, so this is a sound optimization.
murrayh 16y ago
You can prevent caching optimisations by declaring a variable 'volatile' (http://en.wikipedia.org/wiki/Volatile_variable http://en.wikipedia.org/wiki/Volatile_variable).

igorgue 16y ago

#2 was an error I had, and a co-worker told me screaming that I was a crappy programmer because I did it, now that I know it's optimized I feel like he owns me an apology or maybe not :-)

yuvi 16y ago
Were you using gcc? I wouldn't be surprised if e.g. MSVC didn't perform that optimization since it doesn't have the pure function attribute.

grogers 16y ago

"2. Loop-invariant strlen() GCC does this optimization, because strlen is a "built-in function:" one that gcc recognizes and optimizes specially. Disabling built-ins with -fno-builtin defeats this optimization." No, it does it because strlen is declared to be a pure function, and it is smart enough to realize you are not modifying anything in s. -fno-builtin does not change the generated code, it still calls the strlen function (at least on my gcc), but it is hoisted out of the loop.

gfodor 16y ago
If this is true it makes me happy because this is surely less of a hack.
astrange 16y ago
strlen() is not declared pure in the OS X headers.

nitrogen 16y ago

Wouldn't it be possible to optimize floating point multiplication by 2.0f (or any power of two) to an addition or subtraction on the exponent?

astrange 16y ago
Only on architectures with such instructions. x86 doesn't have anything like that (well, maybe in x87), and I don't know of any others that do.
- nitrogen 16y ago
  So would moving the floating point value into an integer register, shifting, incrementing, ORing, etc. ever be faster than a full FP addition? I imagine that modern desktop CPUs have effectively-single-cycle multiply, but what about something like ARM with VFP but no Neon?
  - astrange 16y ago
    Only in architectures where FP and integer values are kept in the same registers. This is true in SSE2 and Altivec, so you can do integer operations there - but since SIMD integer operations are limited too, it's pretty much only useful for flipping the sign bit. Moving values between different register sets is INCREDIBLY slow since it involves at least two memory operations. And faking FP operations with specialized integer code on something with soft-float like ARM might be worth it. I've never done it so I can't really say.

Aegean 16y ago

He could have added the switch statement optimization. That's my favorite. GCC 4 can optimize switch statements with sequential keys e.g. (1,2,3,4 ...) into a jump table. This was AFAIK introduced in GCC 4

ramchip 16y ago
But he did: The switch statement was optimized to a jump table, while the if statements became a long sequence of compares.