Improve ahat dominators computation.

Improve the space complexity of the ahat dominators computation
algorithm to be linear in the size of the heap dump being processed.

Performance of the algorithm is on par with the previous version of the
algorithm, verified by running it on a collection of 150 or so Android
heap dumps laying around from old memory investigations. For example:

  old          new
0m1.161s --> 0m1.333s
0m2.800s --> 0m3.350s
0m2.805s --> 0m2.429s
0m4.161s --> 0m5.547s
0m4.553s --> 0m3.482s
0m5.714s --> 0m6.373s
0m6.254s --> 0m5.439s
0m11.615s --> 0m11.456s
0m14.377s --> 0m14.543s

The new algorithm performs considerably better in those cases where the
old algorithm has excessive memory requirements. For example:

   old          new
0m11.135s --> 0m5.915s
0m11.596s --> 0m7.805s
0m31.886s --> 0m10.569s
1m10.972s --> 0m14.350s

For the heap dump in b/79200800, the old algorithm would be killed after
trying to use more than 64GB of memory. The new algorithm takes roughly
2m30s and 5GB of memory to process that same heap dump.

Bug: 79200800
Test: m ahat-test
Test: Open a non-trivial heap dump and compare retained sizes for the
      top 30 or so rooted instances between the old and new version of
      the algorithm.

Change-Id: I8f939b35cf3867d3062863fd9dedeee487db9591

0 files changed, 0 insertions, 0 deletions