what is a stack

[Roedy Green]

Jumps come is 8, 16 and 23 bit signed offsets.

should read

 

[Tony Morris]

A stack is a sort of LIFO (last in first out) queue.

Note that the terminology "LIFO queue" is somewhat of an oxymoron.

A queue is a FIFO data structure (formally referred to as an Abstract Data
Type (ADT)).
A stack is a LIFO data structure (also an ADT).
A LIFO is not a queue.
A FIFO is not a stack.

 

[Liz]

There is also the lload_0 ... lload_3 instructions that are special
shortcuts for pushing the long value of the first four local variable
32-bit slots onto the stack. Local variables I believe are either
parameters or locals.

But I thought it was determined that the stack consists of objects, so
it's pushing references to the first 4 objects? Then it would have
to convert say an int to Integer to make this work?

 

[Roedy Green]

But I thought it was determined that the stack consists of objects, so
it's pushing references to the first 4 objects? Then it would have
to convert say an int to Integer to make this work?

No, the stack at the JVM level contains primitives and references to
objects, not the objects themselves. The objects live on the heap.

The stack is a hodgepodge of different types, in an ever changing
order, verified sane by the byte code verifier before execution
starts.

Each time a method starts, it nails down sufficient space for its
local variables on the tail end of the stack, then does uses the space
past that for computation working storage. When it calls a method it
pushes the params to the top of the stack and then calls the method,
which will leave the return address on the stack so it can get back
when it is done.

When a method returns, it pops its locals off the stack and restores
the instruction pointer to what it used to be in the caller.

I forget who pops the parameters, the caller or the callee. I vaguely
recall the callee.

In real life, things can be more complex. You can have separate
stacks for return addresses, parameters, floating point etc. So long
as the scheme effectively simulates the JVM, it is kosher. The JVM
spec gives plenty of latitude. All that counts is the net effect, not
precisely how it is pulled off.

 

[Sudsy]

Roedy Green wrote:

When a method returns, it pops its locals off the stack and restores
the instruction pointer to what it used to be in the caller.

I forget who pops the parameters, the caller or the callee. I vaguely
recall the callee.

Remember BALR 12,13? And the STM 11,15 which typically proceeded?
Yes, it's normally up to the callee to reset the stack to the
state upon calling, although it can set it up by a fullword in
order to store the return value...
Was that fun or what?!
(most youngsters will find themselves asking WHAT?)

 

[Roedy Green]

Remember BALR 12,13? And the STM 11,15 which typically proceeded?
Yes, it's normally up to the callee to reset the stack to the
state upon calling, although it can set it up by a fullword in
order to store the return value...
Was that fun or what?!
(most youngsters will find themselves asking WHAT?)

He is referring to the IBM 360, a machine without hardware stack
instructions. The calling convention was pretty frightening.

IIRC, the called routine did a call to getmain, to allocate some RAM
on the heap for a save area and for local variables. Then it would
save all the registers in that area. BALR 12,13 would jump to the
address in register 13 and store the return addresess in register 12.
That was the end of hardware support for subroutine calls.

It is not quite as crazy as it sounds. In the BBL forth compiler I
used two different call mechanisms one for branch to branch and one
for branch to leaf. The branch to leaf, instead of pushing the return
address to the stack, I left it in a register. On the old 8086 this
carved quite a few cycles off the call/ret. (A leaf is a method that
does no calls of its own.) In the grand scheme of things the most
common calls are branch to leaf.

A JVM could if it wanted make that same distinction. It does not pay
now since the hardware call/ret to the stack is heavily optimised in
modern machines.

 

[blmblm]

I have seen in various places reference to a 'stack'
But what is a stack? Is it a machine specific
implementation of something, is it a machine hardware
feature/capability? One remark in a book on Java
Performance Tuning*, says that there are special
instructions that make it more efficient to use
the first 4 variables on the stack.

Other people have given good and interesting responses, but the
following point seems to be getting lost from time to time (though
at least one person has I think pointed it out): There is a
difference between "a stack" and "the stack".

"A stack" usually refers to the abstract data type -- the general
idea of a data structure that's "last in, first out". There are
different ways to implement such a data structure, and it can be
used to store different kinds of things (integers, strings,
objects -- though usually all the items on a particular stack
will be of the same type). The common feature is the "LIFO" idea.

"The stack" usually refers to a particular stack -- the stack
the JVM uses to keep track of local variables and parameters, the
stack used by the o/s to keep track of similar information, etc.
There could be hardware support for such stacks.

It is good to know what "a stack" in general is, but that alone
won't help you understand the sentence from the book on performance
tuning -- for that you also need to know about the specific stack
in question (here, presumably the one used by the JVM ...).

 

[Gary Labowitz]

Roedy Green wrote:


Remember BALR 12,13? And the STM 11,15 which typically proceeded?

Yes, I remember. When we first were teaching people OS/360 someone decided
to write a "perfect" program which would have no bugs.
He ended up with a program that just returned. But, of course, it had a bug.
He forgot to clear the condition register. What days they were!
(Poughkeepsie, 1962).

 

[=?ISO-8859-1?Q?Daniel_Sj=F6blom?=]

Hi Liz,
A stack is a very basic data structure that is implemented in Java
with the type Stack. In Java (and in most other languages that
implement a stack type data structure), you use the method
push(Object) to "add" an item to the stack and the method pop() to get
items off of it. If you've ever been to a school cafeteria or an
all-you-can-eat buffet, a stack is like the thing you get your plate
out of before going down the line, or buffet. It is called a
last-in-first-out structure in that the last thing you "push()"ed onto
it will be the first thing that "pop()"s off. It can be very useful
at times but the main gist of it can be seen below:

int forwardArray[] = {1, 2, 3};
Stack reversingStack = new Stack(); //stacks are created empty

for (int i=0; i < forwardArray.length; i++) {
reversingStack.push(new Integer(forwardArray));
}

int reverseArray = new int[forwardArray.length];

for (int i=0; i < reverseArray.length; i++) {
reverseArray = reversingStack.pop().getIntValue();
}

reverseArray will now be: {3, 2, 1}

This code is not guaranteed to compile as I haven't tested it. It's
here to give you a feel for how a stack works. For more information,
check out the Java API at http://java.sun.com

Hope this helps!

-Patrick

OP => "... there are special instructions that make it more
efficient to use the first 4 variables on the stack."

So what are these instructions and what is so special
about the first 4 variables on the stack?

There are 5 versions of every load/store instruction + a special wide
load/store instruction. Four of the instructions are one byte long and
they access the first four local vars. The general load/store
instruction requires that a one byte local variable index is supplied
with it, and as such requires two bytes. To access local variable
indices greater than 255, you will need the wide instruction, which is 4
bytes long.

Anyhow, in a JIT-ed environment, the only difference you'll see is that
the bytecode is slightly smaller when accessing the first four local
variables.

 

[Liz]

Roedy Green wrote:


Remember BALR 12,13? And the STM 11,15 which typically proceeded?
Yes, it's normally up to the callee to reset the stack to the
state upon calling, although it can set it up by a fullword in
order to store the return value...
Was that fun or what?!
(most youngsters will find themselves asking WHAT?)

Finally, someone is making some sense. It takes me back a few years.

 

[Liz]

He is referring to the IBM 360, a machine without hardware stack
instructions. The calling convention was pretty frightening.

IIRC, the called routine did a call to getmain, to allocate some RAM
on the heap for a save area and for local variables. Then it would
save all the registers in that area. BALR 12,13 would jump to the
address in register 13 and store the return addresess in register 12.
That was the end of hardware support for subroutine calls.

It is not quite as crazy as it sounds. In the BBL forth compiler I
used two different call mechanisms one for branch to branch and one
for branch to leaf. The branch to leaf, instead of pushing the return
address to the stack, I left it in a register. On the old 8086 this
carved quite a few cycles off the call/ret. (A leaf is a method that
does no calls of its own.) In the grand scheme of things the most
common calls are branch to leaf.

If you want to remember early microprocessors, I started with the 8008.
Boss almost thought it was overkill to use 8008 instead of 4004 or 4040.
The 8008 has 14 bits of addressing and a hardware stack that was only
8 or so levels deep and could not be accessed via software.

 

[Dave Neary]

Hi Liz,

I have seen in various places reference to a 'stack'
But what is a stack?

A stack is a generic data structure, and is nothing Java
specific. In general a stack supports two operations, push
and pull. So if I have a stack S, and I want to store
numbers in it, the use of a stack looks like this (the top
of the stack is to the right, the bottom is to the left):

Instruction S
s.push(1) 1
s.push(3) 1 3
s.push(-1) 1 3 -1
s.pop() 1 3 (returns -1)
s.push(7) 1 3 7
s.push(4) 1 3 7 4
s.pop() 1 3 7 (returns 4)
s.pop() 1 3 (returns 7)
s.pop() 1 (returns 3)
s.pop() (returns 1)

This is a useful structure for lots of stuff, like token
parsing (consider parsing expresions with parentheses, for
example (1 + (2 * 3)) - (((4 - 2) / ( 6 / 3)) + 3)

there are special
instructions that make it more efficient to use
the first 4 variables on the stack.

Sometimes in a particular context, a stack can refer to one
particular use of the stack structure. For example, when
talking about a process's use of memory, a stack will
typically refer to the function stack, which is the way that
operating systems often organise processes. When a function
is called, a new stack frame is created on top of the existing
stack, and space is allocated for all of the local variables
and instruction code there.

This performance tuning book may be referring to some specific
stack, or it may be referring to a generic stack type structure.
Without more detail, it's difficult to say.

Cheers,
Dave.

 

[Chris Smith]

Other people have given good and interesting responses, but the
following point seems to be getting lost from time to time (though
at least one person has I think pointed it out): There is a
difference between "a stack" and "the stack".

Good point. To complicate things further, "the stack" is not strictly
"a stack". That is, it isn't *always* accessed by push and pop
operations. The Java thread stack is often used as a stack, but there
are also instructions in Java bytecode to reference its contents in
other ways. And, indeed, the comment about the first four variables is
such a usage; it doesn't refer to the top four elements of the stack,
but rather to the top four fixed-location variables, which are
(logically, at least) located directly underneath the actual "stack"
piece.

It's worth noting that a book on Java performance that spends time
pretending that Java is interpreted is probably useless anyway, and this
is a good example. Yes, an interpreter would be faster at accessing the
first four variables... but a JIT compiler probably converts the entire
method to an SSA form before it begins generating code anyway, and the
whole stack-based nature of Java bytecode is lost. The number of
bytecode instructions affects nothing except translation, and that's
only done once per lexical unit of code (i.e., it's worthless to
optimize that stage).

I'm jumping in late, so apologies if this has already been covered.

--
www.designacourse.com
The Easiest Way to Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

 

[Dale King]

The JVM can get at the top four elements of the stack more efficiently
that those deeper. These are typically intermediate results in a
calculation. Java does not use Top of stack relative addressing to
get at the local variables. It uses frame relative addressing. This
makes manually understanding JVM code easier, but I think created
needless overhead.

But that is making assumptions about what the JIT or hotspot compiler will
do. It can do whatever it wants. It might not even put the local variables
on the stack. It could use registers for a local variable and or for
intermediate results. It might use top of stack relative addressing if it
wanted to. That's one of the things that is so great about vitual machines.
It can optimize to the specific architecture that it is running on.

 

[Dale King]

No, the stack at the JVM level contains primitives and references to
objects, not the objects themselves. The objects live on the heap.

The stack is a hodgepodge of different types, in an ever changing
order, verified sane by the byte code verifier before execution
starts.

Each time a method starts, it nails down sufficient space for its
local variables on the tail end of the stack, then does uses the space
past that for computation working storage. When it calls a method it
pushes the params to the top of the stack and then calls the method,
which will leave the return address on the stack so it can get back
when it is done.

When a method returns, it pops its locals off the stack and restores
the instruction pointer to what it used to be in the caller.

I forget who pops the parameters, the caller or the callee. I vaguely
recall the callee.

In real life, things can be more complex. You can have separate
stacks for return addresses, parameters, floating point etc. So long
as the scheme effectively simulates the JVM, it is kosher. The JVM
spec gives plenty of latitude. All that counts is the net effect, not
precisely how it is pulled off.

Once again that is one possible implementation, but not a very likely one.
The JIT compiler will probably shy away from using stack and instead use
registers where it can.

 

[Roedy Green]

But that is making assumptions about what the JIT or hotspot compiler will
do. It can do whatever it wants. It might not even put the local variables
on the stack. It could use registers for a local variable and or for
intermediate results. It might use top of stack relative addressing if it
wanted to. That's one of the things that is so great about vitual machines.
It can optimize to the specific architecture that it is running on.

When you jit or hotspot, the details of the JVM don't matter much.
The advantages comes in making the JVM code more compact or in making
interpreters more efficient.

By using TOS relative addressing, you would have cut down the number
of JVM instructions, and the need for a dedicated local variable base
register. You could have used a PICK instruction (relative to TOS) to
handle parms, locals, and calculation temporaries.

It is too late now.