Author |
Topic: Storing stack backtraces (Read 981 times) |
|
pharaoh
Newbie
Gender: 
Posts: 50
|
 |
Storing stack backtraces
« on: Feb 19th, 2009, 10:56pm » |
 Quote  Modify
|
Hello fellas,
This is not an interview question, rather a real problem I am trying to solve off late.
I am writing a tool, which reports detected memory leaks in programs. I will spare the rest of details.
At some predetermined points in program , I collect the stack trace and store it in a hash table. This happens way too often and the amount of data I end up storing increases significantly. I do not store duplicate backtraces though. When need arises I hash these stack traces and take some decisions.
Now the real problem, if you look carefully at the stack traces in larger programs, you will notice that for a N level deep stack trace i.e. N frames in stack trace, first few frames are same many times.
Two different stack trace might look like this:
stack 1 stack 2
0x1234 0xb7841
0xabcd 0xabcd
0x0xyz 0x0xyz
0x8000 0x8000
Here only the top most frame differes, but these are two different execution paths and currently I store them as seperate. There is scope here for reducing the redundancy
by storing only the different elements and somehow relating the same elements in different nodes.
I vaguely remember reading somewhere that some graph kind of data structure being used for this kind of purpose, but I dont want to break the existing hash table infrastructure, for some time to come.
I am looking some kind of compression mechanism here.
Any alternate approaches to do the same thing?
|
|
 IP Logged |
Cogito ergo sum.
-Pharaoh
|
|
|
cuckoo
Junior Member
Gender:
Posts: 57
|
|
Re: Storing stack backtraces
« Reply #1 on: Feb 20th, 2009, 12:14am » |
Quote Modify
|
May be you can use the "trie" structure to store the paths. And for trie structure, there are many methods for its compact representation, such as the double array trie. 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Storing stack backtraces
« Reply #2 on: Feb 20th, 2009, 12:39am » |
Quote Modify
|
Perhaps you could store an N-level stack as top plus hashed (N-1)-level stack.
hash#5 -> (0xb7841, hash#3)
hash#4 -> (0x1234, hash#3)
hash#3 -> (0xabcd, hash#2)
hash#2 -> (0x0xyz, hash#1)
hash#1 -> (0x8000, null)
Of course, all this really is is a way to build a graph inside a hash-map.
|
| « Last Edit: Feb 20th, 2009, 2:24am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pharaoh
Newbie
Gender:
Posts: 50
|
|
Re: Storing stack backtraces
« Reply #3 on: Feb 20th, 2009, 1:52am » |
Quote Modify
|
towr,
can you please elaborate this a bit more? Not sure I understand it fully.
|
|
IP Logged |
Cogito ergo sum.
-Pharaoh
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Storing stack backtraces
« Reply #4 on: Feb 20th, 2009, 2:32am » |
Quote Modify
|
on Feb 20th, 2009, 1:52am, pharaoh wrote:| can you please elaborate this a bit more? Not sure I understand it fully. |
|
It probably didn't help that I wrote it down incorrectly.
I'm suggesting incremental hashing. The hash for N levels consists of hashing the combination of the top element and the hash of the next N-1 levels.
So if the last X levels are the same for several stack, they have the same hash, and you don't need to store them more than once. Each entry of the hashtable gives you the top element and a hash that tells you where to find the rest of the stack. (So it acts like a pointer).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pharaoh
Newbie
Gender:
Posts: 50
|
|
Re: Storing stack backtraces
« Reply #5 on: Feb 20th, 2009, 2:38am » |
Quote Modify
|
Got it now, and it makes a lot of sense to me!! I might end up implementing some thing like this.
OTOH, about the compress/decompress functions I was talking about earlier, I don't think there will some light weight magic functions to accomplish this. What I mean is, these functions might internally do stuff like incremental hashing etc as you suggest.
|
|
IP Logged |
Cogito ergo sum.
-Pharaoh
|
|
|
kaka
Newbie
Gender:
Posts: 24
|
|
Re: Storing stack backtraces
« Reply #6 on: Mar 28th, 2010, 10:43am » |
Quote Modify
|
I can think of something like this.
hash1: -> (top1-> a -> b -> c -> d -> e)
hash2: -> (top2-> f -> g -> {ptr to c } )
hash3: -> (top3-> h -> i -> [ptr to d } )
at each node we maintain ref count and increment it when we point to it. We'll free its memory when ref count = 0.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print