2

One way to optimize code is to minimize the access to arrays and use variables instead, because that way we use registers instead of loading data to cache memory.

For example, if in a loop I'm going to use 3 times a data from an array, say radius[i], I'd better declare a variable tmp, and give it the value of radius[i]. Every time I need to call radius[i] I'll use tmp instead.

The problem is, the number of registers is limited (to 8 in some cases, it depends on the architecture).

What if I have more variables than the number of registers? Will the usage of variables in this case slow down my program more than having access to cache memory?

I am coding in c language.

  • That is not correct, when you use variables in your C methods, the variables' values still reside in memory. The decision to use registers or not to hold the values of those variables are made by the compiler, not by high level language instruction – InformedA Aug 7 '14 at 11:19
  • 6
    If you use radius[i] three times, the compiler is free (and will try) to load from memory only once and keep re-using it. Assuming of course there aren't any semantic roadblocks to that, like radius being volatile or intervening writes to potentially aliasing pointers. Local variables are mostly for reader comprehension, not for optimization. – user7043 Aug 7 '14 at 11:27
  • Thanks all for your answers. How do I know the parts of the code that will be optimized by the compiler, and those that need to be optimized by hand, are there any rules to this? – S.E.K. Aug 7 '14 at 11:56
  • 1
    It will all be optimized, if optimization is enabled. In general, this is controlled not by regions of code, but by types of optimization (although you can use different settings for different translation units). The bits that need to be optimized by hand are exactly the bits that prove to be too slow, when you profile. – Useless Aug 7 '14 at 13:43
  • As @Useless mentions, profiling will tell you where to optimize. Even then, you are often better off leaving the slow parts alone. You may make them less readable/maintainable, for example. Unless the performance really is terrible or it is easy to fix without hurting the code's maintainability, don't bother. – user22815 Aug 7 '14 at 21:42
11

Having more variables than registers isn't necessarily a problem. If a variable's value isn't used after a certain point in the function, the compiler can use that register for another variable. Even when there's more variables in use at a certain point than there are registers, the compiler will probably do a better job of figuring out the order in which they need to be moved in and out of registers than you.

The point of a high level language is to abstract away those details. I know if you program in C you're probably concerned about performance, but C is also an unsafe language, which means a mistake will take execution off the rails and result in undefined behavior. Write code that is simple and easy to follow. Forget about that kind of micro-optimization unless you have a clear performance goal, you've profiled the application, confirmed you're not reaching that goal, and you've identified the specific part of the code that needs optimizing. And in that case, there is no definitive answer we can give you - you'll have to try different variations of the code, profile, and see which one ends up being faster on your particular combination of compiler, OS, and architecture.

| improve this answer | |
  • thank you for your constructive answer.Do you know any good software to profile a c code? – S.E.K. Aug 7 '14 at 11:42
  • @user2651062 No, sorry. I don't do much C programming. Product recommendations are off-topic here, too. Maybe try asking in chat or the Software Recommendations Stack Exchange? – Doval Aug 7 '14 at 11:54
  • 1
    Check out Valgrind – user22815 Aug 7 '14 at 21:43
4

This is called register allocation, and the compiler/optimiser will take care of it for you. Just make sure to turn optimisation on. If you want to see what it does, just compile to assembler ... and then learn to read and understand assembler. The quality of implementation will vary, but in general you don't need to think about this unless you have a specific performance problem.

The only time it might be worth thinking about this up-front, is when you know an array can't be aliased, but it will be hard for the compiler to prove this. Eg,

double radius[3];
double *possible_alias = get_ptr();
...
for (int i=0; i<3; ++i) {
    *possible_alias *= radius[i];
    do_something_else(radius[i]);
}

if you know the pointer assignment won't change radius[i], but the compiler may be unable to rely on it, you could write

    double r = radius[i];
    *possible_alias *= r;
    do_something_else(r);

In general, don't worry about this sort of micro optimisation unless you find a specific performance problem. Reserve your efforts for writing code that's clear, easy to debug and understand, and choosing the right data structures and algorithms.

As for how to profile your code, that's a massive topic, and the support depends on your platform and toolchain. There are compiled-in sampling profilers (like gprof, for the GCC toolchain), post-hoc profilers (like Intel's VTune and the free valgrind), or you can just time whole runs or write your own timing points manually. None of this is likely to be worth the effort unless your program is objectively too slow in the first place.


Note to OP: the discussion in comments below is about the situations in which the CPU may be able to optimise this at run time, even if the compiler couldn't. At least on modern x86 platforms, it just reduces even further the value of thinking about this.

| improve this answer | |
  • Correct me if I am wrong, but a typical CPU like Intel Core i5 has about 1.5K to use as cache for micro-instructions (the instructions that are lower-level than machine/assembly instructions). The cache is about 6Kb in size. So even the case you mentioned above when pointer alias is hard to prove, the CPU will still be able to figure out the same mem address and optimize to use registers. Of course, if the variables are too far apart in the code, the micro-instruction cache will not be enough. But then I doubt that, human can see a potential optimization that is more than 300 lines apart. – InformedA Aug 7 '14 at 13:52
  • I suspect it will turn into a successful load from cache in that case, which still isn't the same as direct access to the register file. And a function call which is semantically guaranteed not to write to an argument (which probably should be marked const, but isn't) can easily be both too big for that icache, and trivial for a programmer to reason about. – Useless Aug 7 '14 at 13:57
  • You might be right, this might be loaded only from cache. I am reading more into this, it has been a while. Wikipage seems to contain lot of info that I have misread. – InformedA Aug 7 '14 at 19:16
0

Yes, this is true of any language, within a function or some confined code space you have more things in flight than registers to hold them you have to spill over into memory, and you will fall off of a performance cliff at that point.

When you hit that point how far the performance falls off, etc varies widely.

There is value in understanding this and it is very easy to understand this by creating simple functions, compiling and disassembling them to see what is really going on. You will want to use the optimizer in general to avoid just really slow code all the time, but that amplifies the problem, as little as one operation in one line of code can greatly affect performance. Because as you are asking, you will hit that Nth operation that causes the number of registers needed to exceed the number if free registers you have and now you have to spill over into memory. Likewise you hit other performance cliffs when your caches fill up or striping of your data causes cache thrashing, etc.

At the end of the day though this is the nature of using high level languages, if you plan on porting this code at all you can do a little tuning to avoid blatant performance hits on all platforms, but you are not going to get too much benefit trying to overoptimize for one platform and possibly hurting others. If you truly have a performance problem you need to first prove you have a performance problem related to the code in question and then solve that using assembly for that or any target where that code is causing a performance problem. And yes that creates a readability and maintainability problem.

In general readability, maintainability, performance, choose two.

| improve this answer | |
0

There are good answers to the question you asked, but it's important to keep in mind that as software gets bigger and more serious, this kind of optimization gets less and less relevant. The reason is that the program traces out a call tree, and time is mainly spent in the leaves, and the leaves are less and less likely to be in code that the compiler sees.

Instead, time becomes more and more likely to be spent in library functions the compiler doesn't see, and some of which do I/O, which no compiler can optimize.

Such a program can certainly be optimized, by a large amount, but only by the programmer. To do that, you need a way to tell what the program is doing that might not strictly need to be done, like a lot of memory allocation. Here's an example.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.