newbiecpp said:
My confusion is from here: C++ says that static allocation, such as
static int i;
is binding at compile-time, while dynamic allocation, such as
int* pi = new int;
is binding at run-time.
Actually there are three types of storage in C and C++: static, dynamic,
and automatic. Following are examples of all three:
// The integer g has static storage duration, like all global variables.
int g;
int main()
{
// The integer s has static duration because of the 'static' keyword.
static int s = 0;
// The integer a has automatic duration, which is the default for
// local variables.
int a = 0;
// The pointer p has automatic duration, but the integer it points
// to has dynamic duration.
int* p = new int(0);
// The following statement frees the integer that p points to, which
// means the integer no longer exists and the memory it occupied can
// be reclaimed for other purposes. The pointer p still exists, but
// it is now an invalid pointer, which means you're not allowed to
// do anything with it except assign to it.
delete p;
return 0;
}
The amount of static storage, and the number of static variables, in a
program is known "in advance" (specifically, at link time) and does not
change over the life of the program -- hence the name "static". In other
words, the lifetime of a static variable is the lifetime of the program.
Automatic variables are created and destroyed "automatically" based on
the flow of control. An automatic variable is created when the control
reaches the point where it is declared, and is destroyed when the flow
of control leaves the block where it is declared. Thus, unlike static
variables, automatic variables may be bound to different addresses at
different times.
Dynamic objects are allocated on the free store (informally known as the
heap) and are allocated and freed explicitly by the programmer -- though
perhaps indirectly, e.g., via objects with constructors and destructors.
As with automatic objects, the number of dynamic objects changes over
time. A reference variable may be bound to different dynamic objects at
different times, and a pointer may point to different dynamic objects at
different times.
I understand now that for i, compiler can put an
offset related to some location (like stack base) somewhere.
In your example, i is static so the stack is not involved. The actual
address of a static variable may not be known until the program is
loaded, but from that point forward it does not change. The way this
works on some common platforms (e.g., Windows) is that the linker
includes "relocation information" in an executable file, which the
operating system them uses to fix up all references to static variables
when it loads the program. Function calls work in a similar manner.
Automatic variables work quite differently. The C++ standard does not
require it, but most implementations for common hardware platforms
allocate automatic variables on the stack. This takes advantage of
the fact that automatic variables are always destroyed in the reverse
order they are created (i.e., LIFO, last-in, first-out). Stacks are
well suited to this. A function can reserve space for its local
variables by simply moving the stack pointer (usually a register)
when it is called, and restoring the previous stack pointer when it
returns.
Following is a more detailed description of how the stack might be
managed in a typical x86 implementation.
Two special registers are used to manage the stack: the stack pointer
(ESP), which points to the top of the stack; and the base pointer (EBP),
which points to the current "stack frame", i.e., the part of the stack
reserved for a particular function invocation. A typical function call
sequence might work like this:
1. The caller pushes parameters onto the stack.
2. The caller pushes the return address (i.e., the address of
the next instruction) into the stack, and transfers control
to the entry point of the function.
3. The function (i.e., the callee) saves the old value of the
base pointer by pushing it into the stack, and stores the
current stack pointer in the base pointer; it then adjusts
the stack pointer to make room for its local variables.
4. Local variables, parameters, and the old base pointer all
now have known offsets from the current base pointer.
5. Before the function returns it restores the old stack and
base pointers (reversing step 3). It then "returns", i.e.,
pops the return address off the stack and transfers control
there (reversing step 2).
6. The caller then fixes the stack pointer (reversing step 1).
There are many variations on this idea. For example, parameters may
be passed in registers instead of on the stack; step 6 may be carried
out by the callee instead of the caller; etc. The specific protocol
used is known as a calling convention, but the basic idea is usually
fairly close to what I described above.
Note that each function invocation has its own stack frame. This
explains how recursion is possible. Consider the following example:
#include <iostream>
int factorial(int n)
{
return (n > 2) ?
n * factorial(n - 1) :
n;
}
int main()
{
std::cout << factorial(3) << std::endl;
return 0;
}
In the above program, main calls factorial with n=3. This first
invocation of factorial calls factorial again with n=2. The second
invocation then returns control to the first invocation, which in
turn returns control to main. Assuming the compiler translates the
program quite literally and uses the calling convention I described
above, here's what the stack looks like during the second
invocation of the factorial function:
(Note: ASCII art best viewed in a monospaced font; the
diagram assumes the stack growns downward.)
+------------------------------------------+
| params to main | stack
| | frame for
| return address (to startup code?) | main
| |
? <--- old base pointer |
| |
+--> | local vars for main |
| | |
| +------------------------------------------+
| | n=3 |
| | | stack
| | return address (somewhere in main) | frame for
| | | factorial
+----- old base pointer | (1st call)
| |
+--> | (local vars if there were any) |
| +------------------------------------------+
| | n=2 |
| | | stack
| | return address (somewhere in factorial) | frame for
| | | factorial
+----- old base pointer | (2nd call)
| |
EBP -> | (local vars if there were any) |
+------------------------------------------+
ESP -> (top of the stack)
Mind you, things are less clear cut in practice. For example,
the recursive call in the factorial function is what's know as
a tail call, and the compiler may just turn it into a jump
instead of an actual function call, in effect replacing recursion
with a loop.
But I still
have some confusion about dynamic binding. To me, the compiler may put an
offset from heap to pi.
It is important to distinguish between the pointer itself (pi) and the
object it points to (*pi). If pi is a local variable it is allocated in
the manner of all automatic variables (e.g., on the stack as described
above).
The memory for the pointee (i.e., *pi) is allocated by a function
called operator new. How that works is quite complex and implementation
dependant, but basically memory management functions like operator new,
operator delete, malloc, and free must maintain some sort of data
structures to keep track of which chunks of memory are in use and which
are free. Something more complex than a stack is required because
(unlike automatic objects) objects on the free store may be freed in
any order. Some cooperation with the operating system is usually often
involved.
In any case, pi can't just point to some static offset from the heap
because pi may point to different objects at different times. Consider
the following example:
struct Node {
Node* next;
};
int main()
{
Node* first = 0;
for (int i = 0; i < 1000; ++i)
{
Node* p = new Node;
p->next = first;
first = p;
}
while (first != 0)
{
p = first->next;
delete first;
first = p;
}
return 0;
}
In the above program, the local variable first points, at different times,
to 1000 different objects. Obviously, then, its value (i.e., the address
of the node it points to) cannot be determined at compile time -- even as
an offset from the beginning of the heap.
But why we call it run-time binding? To me, they
all decide at compile-time, that is, compiler record an offset from stack or
heap.
A static variable is always bound to a single object at a fixed memory
address. The address may be determined at program load time (or in some
other way) rather than compile time; however, it does not change during
the execution of the program.
In contrast, the location of an automatic variable is relative to a
particular stack frame (assuming a stack is even used, which is not
required). Parameters work like automatic variables so consider the
parameter n in the example above. At one point n is bound to a memory
address in one stack frame (containing the value 2). Later it is bound
to another memory address in a different stack frame (containing the
value 3). In fact, both stack frames exist at the same time, although
only the top-most stack frame is active.
In the case of the free store, see the example above. The same pointer
many point to many different objects at different times during a
program's execution.
Well, I think I've gone on long enough. I hope this helps.
--Nick
