Wednesday, 18 July 2007

FindRoots history

I see some folks at SAP have copied my FindRoots Dominator Tree approach so I thought I'd write a brief history of FindRoots.

I wrote the first version of FindRoots back in late 1999 to analyse HPROF dumps. At the time it was the only IBM tool available for analysing out of memory situations, the only alternative being Sun's own Heap Analysis Tool (HAT). The rather better known HeapRoots tool started life as an attempt by my mate Roland Paterson-Jones to write a similar tool but faster and using less memory. For a while we competed over whose tool used the least memory but eventually our tools diverged and especially since Dave Nice took over HeapRoots has concentrated on being a an interactive tool whereas FindRoots works in a batch report-generating mode. (It's worth noting btw that HeapRoots cheats by doing a simple DFS and does not produce accurate reachability counts. I got sidetracked for a long while by the problem of how to compute the exact transitive closure of a graph efficiently. It's an incredibly complex problem to crack!)

FindRoots introduced the idea of using the dominator tree back in 2003 and this has proved a very valuable approach.

I've been too busy on other stuff just lately to do much FindRoots work but I do have a partial rewrite in the works that promises to be much faster and leaner.

BTW you can get FindRoots here.

1 comment:

VedranLerenc said...

Hi David,

I am sorry that you got the impression, that we copied something from you, but that’s not the case. It took us a while to identify dominators as helpful graph-theoretical approach and we learned that the hard way. ;-)

If you are interested, in my blog I compiled a short history on how we exploited the dominators and how we stumbled over them in a research paper while trying to solve the problem of computing the retained size per single object instantly. We exploited dominators in various ways and the dominator tree was just one of them and was not even the first one.

Anyhow, I can understand your blog, but we really haven’t copied anything, especially not the dominator from you or anybody else. In fact, we are pretty happy that we have found out about them ourselves – and a bit proud, too, just like you. ;-)

Kind regards,