|  | could u pls suggest me any data structure for holding a huge | | |
| | | Guest |  |
|  Posted: Mon Sep 01, 2008 7:27 am Post subject: could u pls suggest me any data structure for holding a huge |  |
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? |
| |
| | | Pascal J. Bourguignon | |
| | Posted: Mon Sep 01, 2008 7:27 am Post subject: Re: could u pls suggest me any data structure for holding a | |
willpowerforever@yahoo.com writes:
| Quote: | 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__ |
| |
| | | ajk | |
| | Posted: Mon Sep 01, 2008 8:51 am Post subject: Re: could u pls suggest me any data structure for holding a | |
On Sep 1, 3:27 pm, willpowerfore...@yahoo.com wrote:
| Quote: | 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 |
| |
| | | Guest | |
| | Posted: Tue Sep 02, 2008 1:56 am Post subject: Re: could u pls suggest me any data structure for holding a | |
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? |
| |
| | | Bartc | |
| | Posted: Tue Sep 02, 2008 7:36 am Post subject: Re: could u pls suggest me any data structure for holding a | |
<willpowerforever@yahoo.com> wrote in message
news:e1a743ad-7453-42f5-92d1-b33757369b46@k36g2000pri.googlegroups.com...
| Quote: | 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 |
| |
| | | Anders Karlsson | |
| | Posted: Wed Sep 03, 2008 8:36 am Post subject: Re: could u pls suggest me any data structure for holding a | |
On Mon, 1 Sep 2008 18:56:06 -0700 (PDT), willpowerforever@yahoo.com
wrote:
| Quote: | 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 |
| |
|
|
