I have a fuction that is called many times:

... fuction(...)
{
    for (int i=0; ...)
        array = ...
    for (int i=0; ...)
        ...
}

Can i speed up this code by making i static?

... fuction(...)
{
    static int i;
    for (i=0; ...)
        array = ...
    for (i=0; ...)
        ...
}

I thought "int i;" means that new memory must be allocated for a new variable.
When the variable goes out of scope, memory must be deallocated.
Memory allocation/deallocation takes time.
Is this not right then?

If you declare a local variable it will be allocated on the stack. Allocation on the stack is very cheap, only heap allocation is expensive. In any case, don't worry about it! Your first function more clearly shows the intent of the code. Only declare variables as static if you actually need that property.

Even if we assume that allocating a variable on the stack is slow (which it isnt)...

You save time by pre-allocating the one variable, and reusing it every call, instead of allocating one every call, BUT

The one you pre-allocated is either somewhere down the bottom of the stack, or somewhere on the heap, anyway, the point is that it probably wont be on the same 'page' of memory as the rest of the function code is, so when you go to use that variable at the start of the function, the CPU requests the memory address, but cant find it in the cache, so it asks the OS memory manager, which might have to load the page from virtual memory..

Point being, overzealous optimisations can actually cause slow-downs by making the low-level implementation too large.

Variables allocated from the stack are more efficent than static variables, since they're more cache friendly.

Ok, its clear that making the vars static isn't such a good idea.
Thanks for the quick replies.

Now consider complex user-defined variables like binary trees, and perhaps even a good old vector with 1GB worth of function-local non-volatile array data.

That would make for a highly unreasonable stack size, and re-allocating that memory on the heap every time the function runs would be just too costly.

Moving the vector up a level into some class seems to be both logical and programmatic over-complication.

Example of a function-local static vector:


[Edited by - taby on June 27, 2006 8:02:31 PM]

On all modern CPUs/compilers (at least with any amount of optimization turned on)

void foo(void)
{
int i;

for (i = 0; i < N; ++i)
// ... whatever
}

the auto variable 'i' is going to be in a register for most or all of its life. This is even more efficient than using a stack-local memory address, which is, as pointed out, generally more efficient than a variable allocated as static.

That said, you really shouldn't be worrying about this. Unless you have intimate knowledge about the details of your specific CPU, under a very specific computational load, it's very difficult to get any significant degree of efficiency improvements at this level, even for experts. 95%+ of the time, worrying about the algorithmic complexity of what you're doing makes far more sense than the smaller details of implementation efficiency within the context of a given algorithm.

Cheers,
Jason

p.s. A static std::vector<> with 1Gb of data allocated would almost certainly have that 1Gb of data living in the allocated heap, not in static storage. The std::vector<> class member variables would live in the static storage, but (at least in every implementation I've seen) the data that's stored in the vector is allocated from the heap. Not that having a std::vector<> with 1Gb of data static is generally a good idea, or anything.