CS 4: Lecture 16
Wednesday, March 15, 2006
THE STACK AND THE HEAP
======================
Java stores stuff in two separate pools of memory: the stack and the heap.
The _heap_ stores all objects, including all arrays, and all class variables
(i.e. those declared "static").
The _stack_ stores all local variables, including all parameters.
When a method is called, Java creates a _stack_frame_ (also known as an
_activation_record_) that stores the parameters and local variables for that
method. One method can call another, which can call another, and so on, so the
JVM maintains an internal _stack_ of stack frames, with the most recent method
call on top, and "main" at the bottom. When a method finishes executing, its
stack frame is erased from the top of the stack, and its local variables are
erased forever.
Here's a snapshot of memory while Java is executing the "Test.main" method
below. The stack frames are on the left. Everything on the right half of the
page is in the heap. Read the stack from bottom to top, because that's the
order in which the stack frames were created.
STACK | HEAP
|
method call parameters & local variables |
----------------------------------------------|
---- ---- |
Fraction.gcd a |30| b |45| |
---- ---- |
----------------------------------------------|
--- --- |
Fraction.reduce divisor |0| this |.+-------------------\
--- --- | |
----------------------------------------------| |
--- | |
f |.+------------------------------+---------------\
Fraction.divide --- | | |
--- | | |
this |.+--------------------------\ | |
--- | | | |
----------------------------------------------| v v |
--- | --------------------- |
result |.+----------------------->|num | 30| den | 45| |
--- --- | --------------------- |
Fraction.quotient f |.+-------------------\ |
--- --- | | |
this |.+------------------------\ | |
--- | | | |
----------------------------------------------| | v v
--- --- | | ---------------------
f3 |X| f2 |.+---------------+->|num | 9 | den | 10|
--- --- | v ---------------------
--- --- | ---------------------
Test.main args |.| f1 |.+------------->|num | 3 | den | 5 |
-+- --- | ---------------------
| | --------- -----------
\------------------------->| . | .-+-->| "words" |
| --+------ -----------
----------------------------------------------| | -----------
\--->| "input" |
-----------
public class Test {
public static void main(String[] args) {
Fraction f1 = new Fraction(3, 5);
Fraction f2 = new Fraction(9, 10);
Fraction f3 = f1.quotient(f2);
}
}
The stack is called a "stack" because it acts like a stack of trays at a
cafeteria. You can only (conveniently) add a tray to the top of the stack or
remove a tray from the top of the stack. A method call _pushes_ a new stack
frame onto the top of the stack. When a method finishes executing, its stack
frame is _popped_ from the top of the stack.
The method that is currently executing (at any given point in time) is the one
whose stack frame is on top. All the other stack frames represent methods that
are waiting for the methods above them to return before they can continue
executing.
Each stack frame also contains a "program counter" that tells Java what line of
code is currently executing in that method. Ever wonder how Java knows where
to continue executing when it returns from a method? The stack frame for
Fraction.reduce (pictured above) contains a program counter that points to the
spot in the "reduce" method where Java should continue execution after the
"gcd" method is done. (Your Java code cannot examine the program counters
directly, though.)
You'll notice that three of the methods have "this" as a local variable, but
"main" and "gcd" do not. That's because "main" and "gcd" are static methods,
and the other methods are not.
Remember the "scope" of a variable? Observe that there are two local variables
named "f", and three named "this", all in existence at the same time. If you
write "f" or "this" in a method, how do you know which "f" or "this" you're
referring to? Answer: at any given time, only the local variables in the TOP
stack frame are in scope. So a method can only access its own local variables.
(This will be important to understand when we learn about _recursion_ a few
lectures from now.)
The java.lang library has a method "Thread.dumpStack" that prints a list of the
methods on the stack (but it doesn't print their local variables). This method
can be convenient for debugging--for instance, when you're trying to figure out
which method called another method with illegal parameters that made it crash.
Parameter Passing
-----------------
Let's reprise parameter passing, using stack frames. Recall that parameters
are "passed by value"--they are copied. The copies reside in the stack frame
for the method. A method can change its parameters (in its stack frame), but
the changes are not visible outside the method call. The original values are
not changed.
However, you saw in lab that when a parameter is a reference to an object, the
reference is copied, but the object is not; the original object is shared. A
method can modify an object that one of its parameters points to, and the
change will be visible everywhere.
In this example, the method doNothing sets its parameter to 2, but it has no
effect on the value of the calling method's variable a:
method: | STACK (just before the method returns)
|
static void doNothing(int x) { | -----
x = 2; | x | 2 |
} | ----- stack frame for doNothing
|-----------------------------------------
method call: |
| -----
int a = 1; | a | 1 |
doNothing(a); | ----- stack frame for main
This example shows what the stack and heap look like while constructing an
object:
method: | STACK | HEAP
| IntBox|
class IntBox { | ----- |
int i; | n | 2 | |
IntBox(int n) { | ----- | IntBox object
i = n; | ----- | ------
} | this | .-+------------>|i |2|
} | ----- | ------
|--------------------| ^
method call: | ----- | |
| b | .-+----------------/
IntBox b = new IntBox(2); | ----- main|
Note that the figure above actually shows fields at two different points in
time, because b isn't made to point to the IntBox object until the constructor
terminates, at which point its stack frame is erased.
Here's an example that shows how a method can change an object so that the
change is visible to the calling method:
method: | STACK | HEAP
| set3|
class IntBox { | ----- |
static void set3(IntBox ib) { | ib | .-+----------------\
ib.i = 3; | ----- | |
} | | |
|--------------------| v
method call: | ----- | ------
| b | .-+------------->|i |3|
set3(b); | ----- main| ------
Here's an example of a common programming error, where a method tries and fails
to make a change that is visible to the calling method:
method: | STACK | HEAP
| badSet4|
class IntBox { | ----- | ------
static void badSet4(IntBox ib) { | ib | .-+------------->|i |4|
ib = new IntBox(4); | ----- | ------
} | |
|--------------------|
method call: | ----- | ------
| b | .-+------------->|i |3|
badSet4(b); | ----- main| ------