[javaflow] Stack class

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

[javaflow] Stack class

Kohsuke Kawaguchi

I noticed a few things with this class.

1. When an array gets filled up, the reallocation only increases the
array by a fixed amount (10). So if a stack is deep, you pay O(n^2)
cost. I wonder if the standard technique of doubling the size of the
array is better. You only pay O(n) and on average you utilize 75% of the
memory, which is reasonable. Can I make this change?

2. reallocation of the buffer is too eager. It should be:

         if (dTop == dstack.length) {
             double[] hlp = new double[dstack.length + 10];
             System.arraycopy(dstack, 0, hlp, 0, dstack.length);
             dstack = hlp;
         }
         dstack[dTop++] = d;

instead of:

         dstack[dTop++] = d;
         if (dTop == dstack.length) {
             double[] hlp = new double[dstack.length + 10];
             System.arraycopy(dstack, 0, hlp, 0, dstack.length);
             dstack = hlp;
         }

Can I make this change?


3. Stack has a memory leak. Imagine a thread that suspends twice. If in
the first suspend point a stack is very deep, the Stack object will have
a lot of objects in it. When it suspends next, assume the stack frame is
very shallow. When the new stack frame is captured into a Stack object,
the region of the arrays that aren't used still point to objects written
by the first Stack object. Can I change this?


4. Once populated, Stack conceptually becomes immutable, because
Continuation is conceptually immutable. However, every time you call the
continueWith method, javaflow makes a deep copy of a Stack just to read
from it. We can avoid this by just separating the array portion and the
index portion, so that the stack frame can be restored from a Stack
without destroying it.

In this approach a new Stack is allocated when you start capturing. This
needs changes to the bytecode manipulation layer, so it's just something
to consider when you port to ASM.

This will automatically fix the above memory leak in Stack, too.


5. Stack can have a better readObject/writeObject implementation that
doesn't write unused entries in the array. I'm planning to serialize a
lots of Continuations, so this matters for me. Can I make this change?




--
Kohsuke Kawaguchi

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [javaflow] Stack class

Torsten Curdt
>
> I noticed a few things with this class.
>
> 1. When an array gets filled up, the reallocation only increases  
> the array by a fixed amount (10). So if a stack is deep, you pay O
> (n^2) cost. I wonder if the standard technique of doubling the size  
> of the array is better. You only pay O(n) and on average you  
> utilize 75% of the memory, which is reasonable. Can I make this  
> change?

I haven't had too much of stack size yet
but I think you are right ...go ahead

> 2. reallocation of the buffer is too eager. It should be:
> Can I make this change?

Sure

> 3. Stack has a memory leak. Imagine a thread that suspends twice.  
> If in the first suspend point a stack is very deep, the Stack  
> object will have a lot of objects in it. When it suspends next,  
> assume the stack frame is very shallow. When the new stack frame is  
> captured into a Stack object, the region of the arrays that aren't  
> used still point to objects written by the first Stack object. Can  
> I change this?

Sorry, did not get that. Please elaborate.

> 4. Once populated, Stack conceptually becomes immutable, because  
> Continuation is conceptually immutable. However, every time you  
> call the continueWith method, javaflow makes a deep copy of a Stack  
> just to read from it. We can avoid this by just separating the  
> array portion and the index portion, so that the stack frame can be  
> restored from a Stack without destroying it.
>
> In this approach a new Stack is allocated when you start capturing.  
> This needs changes to the bytecode manipulation layer, so it's just  
> something to consider when you port to ASM.
>
> This will automatically fix the above memory leak in Stack, too.
Another idea is to record stack changes
...which would radically change the stack
handling and the memory consumption.

Let's say you start with Continuation1
and the full stack gets store in it.
We now continue with Continuation2
again we store the full stack!
Instead we could store what has changed
from the previous stack.

I am not totally sure whether this
really makes sense and is worth the
hassle ...would need some research.

> 5. Stack can have a better readObject/writeObject implementation  
> that doesn't write unused entries in the array. I'm planning to  
> serialize a lots of Continuations, so this matters for me. Can I  
> make this change?

Sure

cheers
--
Torsten

PGP.sig (193 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [javaflow] Stack class

Kohsuke Kawaguchi
Torsten Curdt wrote:
>> 3. Stack has a memory leak. Imagine a thread that suspends twice.  
>> If in the first suspend point a stack is very deep, the Stack  
>> object will have a lot of objects in it. When it suspends next,  
>> assume the stack frame is very shallow. When the new stack frame is  
>> captured into a Stack object, the region of the arrays that aren't  
>> used still point to objects written by the first Stack object. Can  
>> I change this?
>
> Sorry, did not get that. Please elaborate.

There are two key characteristics in the current Stack class:

1. an array may get bigger, but it will never get smaller, even when a
stack is copied, and even if the stack size shrinks.
2. popped objects won't be clobbered from an array.

Therefore, once an object is recorded to ostack or rstack, the only way
for them to be removed is for the entry to be overwritten by another
object, but this may never happen (the stack size may never grows back
to the same size.) IOW, a Stack retain references to objects even after
they are popped (this alone is OK, as popped objects are just copied
into stack), and those unnecessary references get copied to successive
Stack objects created from it. This causes memory leak for a long
running "thread".

The fix is actually easy, which is to change the copy constructor of
Stack so that it only copies the valid region of the parent array.



> Another idea is to record stack changes
> ..which would radically change the stack
> handling and the memory consumption.
>
> Let's say you start with Continuation1
> and the full stack gets store in it.
> We now continue with Continuation2
> again we store the full stack!
> Instead we could store what has changed
> from the previous stack.
>
> I am not totally sure whether this
> really makes sense and is worth the
> hassle ...would need some research.

The only algorithm I can think of to do this require a lot of additional
local variables on each stack frame (6 ints to record the stack top
while Continuation1 is being restored --- we can use this value while
capturing Continuation2.)

I don't know if this cost is worth the benefit. If the memory foot print
is a concern, maybe it's easier to capture all stack frames first and
then find the common part later. I suspect we need more user experience.

It's also bit tricky because Stacks will share their tops, not their roots.

--
Kohsuke Kawaguchi

---------------------------------------------------------------------
To unsubscribe, e-mail: [hidden email]
For additional commands, e-mail: [hidden email]

Reply | Threaded
Open this post in threaded view
|

Re: [javaflow] Stack class

Torsten Curdt

> There are two key characteristics in the current Stack class:
>
> 1. an array may get bigger, but it will never get smaller, even  
> when a stack is copied, and even if the stack size shrinks.
> 2. popped objects won't be clobbered from an array.
>
> Therefore, once an object is recorded to ostack or rstack, the only  
> way for them to be removed is for the entry to be overwritten by  
> another object, but this may never happen (the stack size may never  
> grows back to the same size.) IOW, a Stack retain references to  
> objects even after they are popped (this alone is OK, as popped  
> objects are just copied into stack), and those unnecessary  
> references get copied to successive Stack objects created from it.  
> This causes memory leak for a long running "thread".
>
> The fix is actually easy, which is to change the copy constructor  
> of Stack so that it only copies the valid region of the parent array.
Sure ...makes sense.
Good finding!

> The only algorithm I can think of to do this require a lot of  
> additional local variables on each stack frame (6 ints to record  
> the stack top while Continuation1 is being restored --- we can use  
> this value while capturing Continuation2.)
>
> I don't know if this cost is worth the benefit. If the memory foot  
> print is a concern, maybe it's easier to capture all stack frames  
> first and then find the common part later. I suspect we need more  
> user experience.
>
> It's also bit tricky because Stacks will share their tops, not  
> their roots.
I know it's a bit tricky ...and
whether it's worth the hassle is
really the question.

But we can leave that for later ;)

cheers
--
Torsten


PGP.sig (193 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [javaflow] Stack class

Kohsuke Kawaguchi-2
Torsten Curdt wrote:
> I know it's a bit tricky ...and
> whether it's worth the hassle is
> really the question.
>
> But we can leave that for later ;)

Agreed.


--
Kohsuke Kawaguchi
Sun Microsystems                   [hidden email]

smime.p7s (4K) Download Attachment