could u pls suggest me any data structure for holding a huge methodcall tree?

The entire call tree cannot be fit into memory. I need to insert or
visit any nodes (including internal nodes) when I construct this tree.
So, the tree getting bigger and bigger, finally, ... OutOfMemory...

Anyone could help me out?

On Sep 1, 3:27*pm, willpowerfore...@yahoo.com wrote:
> The entire call tree cannot be fit into memory. I need to insert or
> visit any nodes (including internal nodes) when I construct this tree.
> So, the tree getting bigger and bigger, finally, ... OutOfMemory...
>
> Anyone could help me out?

maybe if you post a bit more details of what you are doing it would be
possible to better help you.

for instance how many nodes are talking about here? is it an AST? how
large is one node? is speed an issue etc. more details=better help

willpowerforever@yahoo.com writes:

> The entire call tree cannot be fit into memory. I need to insert or
> visit any nodes (including internal nodes) when I construct this tree.
> So, the tree getting bigger and bigger, finally, ... OutOfMemory...
>
> Anyone could help me out?

How many nodes do you really have?

Otherwise, you can of course store your tree on disk. It will be much
much slower.

Perhaps you can reduce the size of the nodes, or change the
representation of the tree. For example, if there is a fixed number
of children per node, you can store the tree without any pointer (you
save one pointer per node).

a
/ \
b c
/ | | \
d e f g

can be stored as: a b c d e f g
and walking the tree involves only arithmetic on the index.


--
__Pascal Bourguignon__

Thanks for your attentions.

Actually, I am working on a code profiling tool. This tool need record
all methods time costs and construct a call tree at runtime. For an
enterprise system, it could has millions of method calls. For each
node, it has following members at least:
long timecost,
int count,
int methodKey, // used to get the full method name
Node parent,
List children,

So, save all the tree nodes in memory is not possible. Since it would
take up Gigabytes of memory.

For each node, the children size is not fixed.

And I cannot just flush all generated nodes to disk, since I may
revisit any of them later, the speed will be extremely slow.

Any suggestions?

<willpowerforever@yahoo.com> wrote in message
news:e1a743ad-7453-42f5-92d1-b33757369b46@k36g2000pri.googlegroups.com...
> Thanks for your attentions.
>
> Actually, I am working on a code profiling tool. This tool need record
> all methods time costs and construct a call tree at runtime. For an
> enterprise system, it could has millions of method calls. For each

Does each node of your tree correspond to one static call in the
application? So in:

fib(n): if n<=1 then n else fib(n-2)+fib(n-1) fi #or whatever...
fib(30)

there is 1 method and 3 static calls. Then you will already know in advance
the likely upper limit of your data and can plan accordingly.

On the other hand, fib(30) might generate several million dynamic calls. In
this case you will run out of memory very quickly, and should try another
approach.

--
Bartc

On Mon, 1 Sep 2008 18:56:06 -0700 (PDT), willpowerforever@yahoo.com
wrote:

>Thanks for your attentions.
>
>Actually, I am working on a code profiling tool. This tool need record
>all methods time costs and construct a call tree at runtime. For an
>enterprise system, it could has millions of method calls. For each
>node, it has following members at least:
>long timecost,
>int count,
>int methodKey, // used to get the full method name
>Node parent,
>List children,
>
>So, save all the tree nodes in memory is not possible. Since it would
>take up Gigabytes of memory.
>
>For each node, the children size is not fixed.
>
>And I cannot just flush all generated nodes to disk, since I may
>revisit any of them later, the speed will be extremely slow.
>
>Any suggestions?

try using a database to store your data, like mysql should do the
trick.

br/ajk