Home arrow static arrow Java Programming [Archive] - Heap vs. Stack
Warning: Creating default object from empty value in /www/htdocs/w008deb8/wiki/components/com_staticxt/staticxt.php on line 51
Java Programming [Archive] - Heap vs. Stack
This topic has 30 replies on 3 pages.    « Previous | 1 | 2 | 3 | Next »

Posts:11,186
Registered: 06.04.04
Re: Heap vs. Stack  
Jun 13, 2004 1:46 PM (reply 15 of 30)



 
I have no intention whatsoever to further discuss this with you because there's nothing to discuss.

Good; good night and

kind regards,

Jos
 

Posts:11,186
Registered: 06.04.04
Re: Heap vs. Stack  
Jun 13, 2004 2:19 PM (reply 16 of 30)



 
Just wanted to jump in the middle here to ask something -

The compile (whether JIT or not) stands with its back against the wall, because no fixed space
can be allocated on any stack anymore to accomodate to different (sized?) objects.

why not?

Because it would introduce 'slicing' of object values and Java is supposed to be 'slicing' free
just because it claims to be a strongly typed language. I apologize for this intimidating reply,
if you want a more friendly, detailed answer: feel free to ask for one; it's Sunday evening overhere
and it takes quite a bit of code generation detail to explain ...

Here's a little thingy --
Object foo= new Foo();Object bar= new Bar();foo= new InheritedFromFooButABitBigger(); 

Where should bar go is both foo and bar were allocated on the stack?

kind regards,

Jos
 

Posts:447
Registered: 3/8/01
Re: Heap vs. Stack  
Jun 13, 2004 3:01 PM (reply 17 of 30)



 
It's been a truth that object creation is slow and you
should avoid it, but that's not valid anymore. The
new/old generation principle of the GC keeps for
example makes object creation on the heap very cheap.
It's not at all obvious anymore that you can speed up
a program by keeping your own memory pools to avoid
using the new keyword.

Object creation with new() is still pretty slow. I know because I've just been working on a Java program to optimize it, and I gained a lot by avoiding it. My program had to print a log of perhaps several million events, and writing some strings and integers to a file was taking by far the most time. I improved logging performance by a factor of 50-100 by creating a custom StringBuffer type class to gain complete control over the string concatenation. Before, I was using BufferedWriter, which should've had the same effect as my custom StringBuffer, but it allocated too many temporary char[]'s and java.nio.HeapCharBuffers. I even created a custom copy of Integer.toString() to prevent it from creating a temporary String for each integer I converted, and this improved that part by a factor of 50 (I think the normal StringBuffer does this too, but I had gained a lot of performance by using my custom one anyway, and this was the only time-consuming method left). Try running a profiler on some Java application that does heavy manipulations with Strings or other objects, and you might be surprised at how much time is spent allocating new objects.
 

Posts:5,965
Registered: 5/17/03
Re: Heap vs. Stack  
Jun 13, 2004 9:46 PM (reply 18 of 30)



 
Here's a little thingy --
Object foo= new Foo();
Object bar= new Bar();
foo= new InheritedFromFooButABitBigger();
Where should bar go is both foo and bar were allocated
on the stack?

Of course not all objects can be allocated on the stack (then they probably already would) but in many situation they can. The most obvious case is when an object is local to the method during runtime (no reference to it ever leaves the method.)

I don't really get the problem with this "sllicing" situation you describe above. The compiler has two choises, either it allocates space for InheritedFromFooButABitBigger from the start and temporarily put the smaller Foo object in it, or it allocates new space for InheritedFromFooButABitBigger in addition to Foo.

As I've already said I won't struggle with you through different situations where this optimization technique can or cannot be used. I have full confidence in the JIT designers to come up with clever schemes to solve more of these "impossibe" cases than you could ever imagine. I'm sure you can find more information about it if you're interested. Start with the link I provided.

kind regards,

Jos

And please stop this silly signing of your posts like they were personal letters.
 

Posts:5,965
Registered: 5/17/03
Re: Heap vs. Stack  
Jun 13, 2004 10:59 PM (reply 19 of 30)



 
Object creation with new() is still pretty slow.

Object instantiation using new is very fast actually. In the situation you describe the problem probably wasn't object creation in itself but the string handling, basically excessive copying of characters. This is often hidden behind the scenes in String, especially the innocent looking '+' operator.

In this situation it's important to get rid of as much unnecessary processing as possible from the innermost loop of the performance bottleneck. No data shuffling back and forth and no object creations either. This can be done in steps but if you take it to the limit you end up with a very thin abstraction layer over the 'bare metal'. Just a few plain byte arrays, for-loops and low-level API calls.

The above tweaking was probably what you (successfully) did, but that doesn't mean object creation was to blame and generally should be avoided.
 

Posts:284
Registered: 5/24/04
Re: Heap vs. Stack  
Jun 14, 2004 12:07 PM (reply 20 of 30)



 
'slicing' of object values and Java is supposed to be 'slicing' free
do you mean by this storing object data in non "continuous" memory blocks?
meaning having some momery blocks on the stack separating between memory blocks of the same object?
Where should bar go is both foo and bar were allocated on the stack?
I Don't know much about memory allocation, so this may be a dumb question, but anyway -
if the Foo, Bar and InheritedFromFooButABitBigger instances are determined local to that method, why not store them one after the other on the stack? what do I care if the InheritedFromFooButABitBigger inherits for Foo and is bigger? why not keep the memory block for Foo even though it is not needed at the point of
foo= new InheritedFromFooButABitBigger(); 
and store InheritedFromFooButABitBigger instance on top? all blocks will be freed anyway when method exits, no?
 

Posts:5,965
Registered: 5/17/03
Re: Heap vs. Stack  
Jun 15, 2004 12:02 AM (reply 21 of 30)



 
all blocks will be freed anyway when
method exits, no?

Yes, and there is no "slicing" problem. The compiler has different choises to fit the objects on the stack (as both you and I have suggested).

The problem here is JosAH. He initially stated that this kind of optimization isn't possible and is now desperately trying to save face. The "hard" cases he puts forward and the "logic" errors he's trying to find in my posts are just attempts to recover from this lapse. I usually don't mind but his behaviour may give the impression that this kind of optimization really isn't possible. Well, it's both possible and highly likely to be introduced in future JIT's.
 

Posts:11,186
Registered: 06.04.04
Re: Heap vs. Stack  
Jun 15, 2004 4:23 AM (reply 22 of 30)



 
I Don't know much about memory allocation, so this may be a dumb question, but anyway -
if the Foo, Bar and InheritedFromFooButABitBigger instances are determined local to that method, why
not store them one after the other on the stack? what do I care if the InheritedFromFooButABitBigger
inherits for Foo and is bigger? why not keep the memory block for Foo even though it is not needed at
the point of
foo= new InheritedFromFooButABitBigger(); 

and store InheritedFromFooButABitBigger instance on top? all blocks will be freed anyway when method
exits, no?

That is not possible, here's an example --
/* 1 */ Foo foo= new Foo();/* 2 */ Bar bar= new Bar();/* 3 */ if (someCondition()) foo= new new InheritedFromFooButABitBigger();/* 4 */ foo.doSomething(); 


Now suppose both foo and bar are allocated on the stack, as suggested. If the condition at line 3
succeeds, a new sub class of foo is instantiated a bit further on the stack as you suggested.
Code has been generated for line 4 which expects a foo at its original location, i.e. the first object
on the stack while it may not be there anymore (or an obsolete copy of the Foo instantiated at line 1.
may still be present there; or not.

As I wrote before, in general stack allocation is not possible in Java; only in very restricted kindergarten
contexts a compiler may deduce that it safely can be done; in most practical situations this would
not be the case. Only if the kindergarten context applies, i.e. the objects are strictly local (not 'passed out'
to other methods and not returned to the caller), not altered by instantiating a (bigger) sub class object,
only then it can be done; but not in general which I stated in a previous reply. Moving them somwhere
else on the stack is not an option either as the example showed above.

kind regards,

Jos
 

Posts:11,186
Registered: 06.04.04
Re: Heap vs. Stack  
Jun 15, 2004 4:24 AM (reply 23 of 30)



 
Sorry for the new new typo at line three.

Jos
 

Posts:3,081
Registered: 2/15/99
Re: Heap vs. Stack  
Jun 15, 2004 4:56 AM (reply 24 of 30)



 
<div class="jive-quote">/* 1 */ Foo foo= new Foo();/* 2 */ Bar bar= new Bar();/* 3 */ if (someCondition()) foo= new newInheritedFromFooButABitBigger();/* 4 */ foo.doSomething();</div>

I don't see why all three objects couldn't be allocated on the stack. Pseudo-assembler:
    functionEntryPoint:        add 54, sp        # let's say Foo = 20 bytes, Bar = 10, Inherited = 24        mov -54(sp), r1   # address of Foo (constructor calls not shown for simplicity)        mov -34(sp), r2   # address of Bar        cmp ...something...        jne label1        mov -24(sp), r1   # r1 now points to Inherited if condition was true    label1:        mov r1(0), r3     # get class object        mov r3(32), r3    # index "virtual function table"        call *r3          # indirect call        ret

"add 54,sp" allocates all three objects at once; this is common in e.g. C compilation (all local blocks get allocated at function entry.)

Only if the kindergarten context
applies, i.e. the objects are strictly local (not
'passed out'
to other methods and not returned to the caller),

Yes, needs to be done. Google "escape analysis" for papers on how to do it. Function inlining helps to expose more opportunities for this optimization.

not altered by instantiating a (bigger) sub class object,

I don't see how this affects things. It's all pointers. You can't "overlay" a bigger object on top of a smaller object, which is why you wouldn't even try.

only then it can be done; but not in general which I
stated in a previous reply.

Right, many optimizations apply to specific cases, not in all general cases. E.g. keeping values in CPU registers only applies for local variables that are of suitable size, there aren't too many live ones at once, and their address is not taken. Even though not generally applicable, only in limited "kindergarten" situations, register allocation is still a useful optimization.
 

Posts:11,186
Registered: 06.04.04
Re: Heap vs. Stack  
Jun 15, 2004 5:15 AM (reply 25 of 30)



 
I don't see why all three objects couldn't be allocated on the stack. Pseudo-assembler:
[ example deleted for brevity, see previousreply ]

Sure it can be done, but your method fails too when not enough registers are available to keep track
of the addresses of the local objects. Of course, one can include a 'dope' vector on the stack and store
these addresses overthere, but then the stack becomes an almost heap like thingy of itself ... and
all object access becomes an indirect fetch again, which was not the idea of the optimization itself.

All I stated that it could not be done in general. And that's what I showed. Of course I agree that
in a kindergarten context objects can be allocated on the stack itself.

Only if the kindergarten context applies, i.e. the objects are strictly local (not 'passed out'
to other methods and not returned to the caller),

Yes, needs to be done. Google "escape analysis" for papers on how to do it. Function inlining helps to
expose more opportunities for this optimization.

That would be difficult too; inlining a method from another class would be impossible, so only methods
from the class itself could safely be inlined.

only then it can be done; but not in general which I stated in a previous reply.

Right, many optimizations apply to specific cases, not in all general cases. E.g. keeping values in CPU
registers only applies for local variables that are of suitable size, there aren't too many live ones at
once, and their address is not taken. Even though not generally applicable, only in limited "kindergarten"
situations, register allocation is still a useful optimization.

Right; that's all I stated: it can not be done in general and that's why I brought up the examples where
stack allocation could not be applied. Your 'dope vector stored in registers' example buys a few objects
but, as I wrote (and I'm sure you know this already), more objects than free registers ruins this
scenario again; again showing that it can not be done in general.

kind regards,

Jos
 

Posts:1,160
Registered: 7/24/97
Re: Heap vs. Stack  
Jun 15, 2004 5:18 AM (reply 26 of 30)



 
The case you are describing is easy to deal with, the first reference creation can result in a stack local allocation, subsequent changes to the same reference pointer can result in heap allocations.

The initial reference to null (always the default) does not need to be allocated.

ie
Foo foo = new Foo(); // allocate stack local...foo = new InheritedFromFooButABitBigger(); // Allocated on heapfoo = new Foo(); //** This can also be created on the stack because it is the same concrete class which always have the same instance size in bytes.doSomethingWithFoo( foo ); //** Method can be analysed at runtime to ensure that the reference does not escape.//** First run always allocates to the heap, subsequent runs can allocate purely local references from the stack

It is interesting that a class whose instances have non-primitive instance variables would almost certainly have to have those references allocated from the heap and not the stack.
As one of the things you need in order to be able to allocate to a call stack is knowledge about the size of
the thing you wish to push onto that stack having you can only allocate the fixed size portion of the instance
(its primitive data and the reference pointers[we don't see those]).
Although such optimisations are possible there is little evidence to suggest that such such optimisations are really worth it.
Heap allocation is now lightning fast and generational heaps ease the problems with GC performance.
Heap allocation in Java is far more performant than the C/C++ equivalent now.
 

Posts:11,186
Registered: 06.04.04
Re: Heap vs. Stack  
Jun 15, 2004 5:37 AM (reply 27 of 30)



 
[code]
doSomethingWithFoo( foo ); /* Method can be analysed
at runtime to ensure that the reference does not escape. */

That isn't necessary when the stack addresses are tracked by register (or whatever) as sjasja described
in reply #24. (for a limited number of local objects).

Although such optimisations are possible there is little evidence to suggest that such such
optimisations are really worth it. Heap allocation is now lightning fast and generational heaps
ease the problems with GC performance.

The current Java heaps are no more than a stack; generation scavenging GCs know perfectly well
how to handle those. As I stated before: stack local object allocation can not be done in general;
clever local optimizations (as showed by you and others) do make it possible that some objects
can be allocated on the stack, I never denied that, but it takes additional complexity (read: additional code)
to handle it all which effectively annihilates the pros of such 'optimizations' (mind the quotes)

Heap allocation in Java is far more performant than the C/C++ equivalent now.

C++ dynamically allocated objects cannot be moved around easily, so garbage collectors would have a
hell of a job there; the availability of C's good ol' malloc() is a burden too.

kind regards,

Jos
 

Posts:11,186
Registered: 06.04.04
Re: Heap vs. Stack  
Jun 15, 2004 5:39 AM (reply 28 of 30)



 
Sorry for the format mangling; I intended to write this:
<div class="jive-quote">doSomethingWithFoo( foo ); /* Method can be analysed</div>at runtime to ensure that the reference does not escape. */ 


That isn't necessary when the stack addresses are tracked by register (or whatever) as sjasja described
in reply #24. (for a limited number of local objects).

Although such optimisations are possible there is little evidence to suggest that such such
optimisations are really worth it. Heap allocation is now lightning fast and generational heaps
ease the problems with GC performance.

The current Java heaps are no more than a stack; generation scavenging GCs know perfectly well
how to handle those. As I stated before: stack local object allocation can not be done in general;
clever local optimizations (as showed by you and others) do make it possible that some objects
can be allocated on the stack, I never denied that, but it takes additional complexity (read: additional code)
to handle it all which effectively annihilates the pros of such 'optimizations' (mind the quotes)

Heap allocation in Java is far more performant than the C/C++ equivalent now.

C++ dynamically allocated objects cannot be moved around easily, so garbage collectors would have a
hell of a job there; the availability of C's good ol' malloc() is a burden too.

kind regards,

Jos
 

Posts:3,081
Registered: 2/15/99
Re: Heap vs. Stack  
Jun 15, 2004 5:58 AM (reply 29 of 30)



 
I don't see why all three objects couldn't be
allocated on the stack. Pseudo-assembler:
[ example deleted for brevity, see previousreply ]

Sure it can be done, but your method fails too when
not enough registers are available to keep track
of the addresses of the local objects.

No it doesn't. As you describe yourself:

Of course, one
can include a 'dope' vector on the stack and store
these addresses overthere, but then the stack becomes
an almost heap like thingy of itself ...

Yes, if the CPU runs out of registers, the compiler puts values on the stack (or the compiler puts everything on the stack initially, and then allocates whatever it can to registers.) Is this somehow unusual?

and all object access becomes an indirect fetch again,
which was not the idea of the optimization itself.

I thought the idea was to move heap objects to the stack??

Actually, there is another way to optimize this particular case: if the "foo" pointer can point to a 20-byte object or a 24-byte object, allocate 24 bytes on the stack. Put the 20-byte object in the 24-byte stack slot. If the pointer gets assigned to the 24-byte object, simply clear out the 24-byte memory area without adjusting the pointer.

All I stated that it could not be done in
general
. And that's what I showed.

Yes, many (most? all?) optimizations can't or shouldn't be done "in general", only when specific conditions are met. Loop unrolling, strength reduction, register allocation, array index check removal, etc etc.

Yes, needs to be done. Google "escape analysis" for
papers on how to do it. Function inlining helps to
expose more opportunities for this optimization.

That would be difficult too; inlining a method from
another class would be impossible, so only methods
from the class itself could safely be inlined.

Huh? I don't understand what you mean.

Right; that's all I stated: it can not be done in
general and that's why I brought up the examples where
stack allocation could not be applied.

Except that it can as I showed...

Your 'dope
vector stored in registers' example buys a few objects
but, as I wrote (and I'm sure you know this already),
more objects than free registers ruins this
scenario again; again showing that it can not be done
in general.

Except that it doesn't ruin optimizing heap to stack allocation... If there are more variables than registers, some of those variables get spilled to the stack. Quite normal and nothing to be ashamed of, and certainly doesn't prevent stack allocation.

You use the phrase "can not be done" in a rather peculiar way for things that demonstratably can be done. "You can't do that... well, you can... which proves you can't."
 
This topic has 30 replies on 3 pages.    « Previous | 1 | 2 | 3 | Next »