ahat: add support for diffing two heap dumps.

ahat now has the option to specify a --baseline hprof file to use as
the basis for comparing two heap dumps. When a baseline hprof file is
provided, ahat will highlight how the heap dump has changed relative
to the hprof file.

Differences that are highlighted include:
* overall heap sizes
* total bytes and number of allocations by type
* new and deleted instances of a given type
* retained sizes of objects
* instance fields, static fields, and array elements of modified objects

Also:
* Remove support for showing NativeAllocations, because I haven't ever
  found it to be useful, it is not obvious what a "native" allocation
  is, and I don't feel like adding diff support for them.
* Remove help page. Because it is outdated, not well maintained, and
  not very helpful in the first place.

Test: m ahat-test
Test: Run in diff mode for tests and added new tests for diff.
Test: Manually run with and without diff mode on heap dumps from system server.
Bug: 33770653
Change-Id: Id9a392ac75588200e716bbc3edbae6e9cd97c26b

39 files changed, 1436 insertions, 590 deletions

diff --git a/tools/ahat/Android.mk b/tools/ahat/Android.mk
index 8859c68467..f79377d518 100644
--- a/tools/ahat/Android.mk
+++ b/tools/ahat/Android.mk
@@ -23,7 +23,6 @@ include $(CLEAR_VARS)
 LOCAL_SRC_FILES := $(call all-java-files-under, src)
 LOCAL_JAR_MANIFEST := src/manifest.txt
 LOCAL_JAVA_RESOURCE_FILES := \
-  $(LOCAL_PATH)/src/help.html \
   $(LOCAL_PATH)/src/style.css
 
 LOCAL_STATIC_JAVA_LIBRARIES := perflib-prebuilt guavalib trove-prebuilt
@@ -79,8 +78,9 @@ include $(BUILD_HOST_DALVIK_JAVA_LIBRARY)
 # BUILD_HOST_DALVIK_JAVA_LIBRARY above.
 AHAT_TEST_DUMP_JAR := $(LOCAL_BUILT_MODULE)
 AHAT_TEST_DUMP_HPROF := $(intermediates.COMMON)/test-dump.hprof
+AHAT_TEST_DUMP_BASE_HPROF := $(intermediates.COMMON)/test-dump-base.hprof
 
-# Run ahat-test-dump.jar to generate test-dump.hprof
+# Run ahat-test-dump.jar to generate test-dump.hprof and test-dump-base.hprof
 AHAT_TEST_DUMP_DEPENDENCIES := \
   $(ART_HOST_EXECUTABLES) \
   $(ART_HOST_SHARED_LIBRARY_DEPENDENCIES) \
@@ -93,12 +93,19 @@ $(AHAT_TEST_DUMP_HPROF): PRIVATE_AHAT_TEST_DUMP_DEPENDENCIES := $(AHAT_TEST_DUMP
 $(AHAT_TEST_DUMP_HPROF): $(AHAT_TEST_DUMP_JAR) $(AHAT_TEST_DUMP_DEPENDENCIES)
 	$(PRIVATE_AHAT_TEST_ART) -cp $(PRIVATE_AHAT_TEST_DUMP_JAR) Main $@
 
+$(AHAT_TEST_DUMP_BASE_HPROF): PRIVATE_AHAT_TEST_ART := $(HOST_OUT_EXECUTABLES)/art
+$(AHAT_TEST_DUMP_BASE_HPROF): PRIVATE_AHAT_TEST_DUMP_JAR := $(AHAT_TEST_DUMP_JAR)
+$(AHAT_TEST_DUMP_BASE_HPROF): PRIVATE_AHAT_TEST_DUMP_DEPENDENCIES := $(AHAT_TEST_DUMP_DEPENDENCIES)
+$(AHAT_TEST_DUMP_BASE_HPROF): $(AHAT_TEST_DUMP_JAR) $(AHAT_TEST_DUMP_DEPENDENCIES)
+	$(PRIVATE_AHAT_TEST_ART) -cp $(PRIVATE_AHAT_TEST_DUMP_JAR) Main $@ --base
+
 .PHONY: ahat-test
 ahat-test: PRIVATE_AHAT_TEST_DUMP_HPROF := $(AHAT_TEST_DUMP_HPROF)
+ahat-test: PRIVATE_AHAT_TEST_DUMP_BASE_HPROF := $(AHAT_TEST_DUMP_BASE_HPROF)
 ahat-test: PRIVATE_AHAT_TEST_JAR := $(AHAT_TEST_JAR)
 ahat-test: PRIVATE_AHAT_PROGUARD_MAP := $(AHAT_TEST_DUMP_PROGUARD_MAP)
-ahat-test: $(AHAT_TEST_JAR) $(AHAT_TEST_DUMP_HPROF)
-	java -enableassertions -Dahat.test.dump.hprof=$(PRIVATE_AHAT_TEST_DUMP_HPROF) -Dahat.test.dump.map=$(PRIVATE_AHAT_PROGUARD_MAP) -jar $(PRIVATE_AHAT_TEST_JAR)
+ahat-test: $(AHAT_TEST_JAR) $(AHAT_TEST_DUMP_HPROF) $(AHAT_TEST_DUMP_BASE_HPROF)
+	java -enableassertions -Dahat.test.dump.hprof=$(PRIVATE_AHAT_TEST_DUMP_HPROF) -Dahat.test.dump.base.hprof=$(PRIVATE_AHAT_TEST_DUMP_BASE_HPROF) -Dahat.test.dump.map=$(PRIVATE_AHAT_PROGUARD_MAP) -jar $(PRIVATE_AHAT_TEST_JAR)
 
 # Clean up local variables.
 AHAT_TEST_DUMP_DEPENDENCIES :=
diff --git a/tools/ahat/README.txt b/tools/ahat/README.txt
index 8dfb4abe5b..08d41f0feb 100644
--- a/tools/ahat/README.txt
+++ b/tools/ahat/README.txt
@@ -1,22 +1,21 @@
 AHAT - Android Heap Analysis Tool
 
 Usage:
-  java -jar ahat.jar [-p port] [--proguard-map FILE] FILE
-    Launch an http server for viewing the given Android heap-dump FILE.
+  java -jar ahat.jar [OPTIONS] FILE
+    Launch an http server for viewing the given Android heap dump FILE.
 
-  Options:
+  OPTIONS:
     -p <port>
        Serve pages on the given port. Defaults to 7100.
     --proguard-map FILE
        Use the proguard map FILE to deobfuscate the heap dump.
+    --baseline FILE
+       Diff the heap dump against the given baseline heap dump FILE.
+    --baseline-proguard-map FILE
+       Use the proguard map FILE to deobfuscate the baseline heap dump.
 
 TODO:
- * Have a way to diff two heap dumps.
-
- * Add more tips to the help page.
-   - Recommend how to start looking at a heap dump.
-   - Say how to enable allocation sites.
-   - Where to submit feedback, questions, and bug reports.
+ * Add a user guide.
  * Dim 'image' and 'zygote' heap sizes slightly? Why do we even show these?
  * Let user re-sort sites objects info by clicking column headers.
  * Let user re-sort "Objects" list.
@@ -49,9 +48,9 @@ Things to Test:
    time.
  * That we don't show the 'extra' column in the DominatedList if we are
    showing all the instances.
- * That InstanceUtils.asString properly takes into account "offset" and
+ * That Instance.asString properly takes into account "offset" and
    "count" fields, if they are present.
- * InstanceUtils.getDexCacheLocation
+ * Instance.getDexCacheLocation
 
 Reported Issues:
  * Request to be able to sort tables by size.
@@ -76,7 +75,11 @@ Things to move to perflib:
  * Instance.isRoot and Instance.getRootTypes.
 
 Release History:
- 0.9 Pending
+ 1.0 Dec 20, 2016
+   Add support for diffing two heap dumps.
+   Remove native allocations view.
+   Remove outdated help page.
+   Significant refactoring of ahat internals.
 
  0.8 Oct 18, 2016
    Show sample path from GC root with field names in place of dominator path.
diff --git a/tools/ahat/src/Column.java b/tools/ahat/src/Column.java
index b7f2829c58..819e586ef9 100644
--- a/tools/ahat/src/Column.java
+++ b/tools/ahat/src/Column.java
@@ -22,14 +22,24 @@ package com.android.ahat;
 class Column {
   public DocString heading;
   public Align align;
+  public boolean visible;
 
   public static enum Align {
     LEFT, RIGHT
   };
 
-  public Column(DocString heading, Align align) {
+  public Column(DocString heading, Align align, boolean visible) {
     this.heading = heading;
     this.align = align;
+    this.visible = visible;
+  }
+
+  public Column(String heading, Align align, boolean visible) {
+    this(DocString.text(heading), align, visible);
+  }
+
+  public Column(DocString heading, Align align) {
+    this(heading, align, true);
   }
 
   /**
diff --git a/tools/ahat/src/DocString.java b/tools/ahat/src/DocString.java
index 19666dea8c..c6303c8c35 100644
--- a/tools/ahat/src/DocString.java
+++ b/tools/ahat/src/DocString.java
@@ -53,7 +53,6 @@ class DocString {
   public static DocString link(URI uri, DocString content) {
     DocString doc = new DocString();
     return doc.appendLink(uri, content);
-
   }
 
   /**
@@ -86,6 +85,78 @@ class DocString {
     return this;
   }
 
+  /**
+   * Adorn the given string to indicate it represents something added relative
+   * to a baseline.
+   */
+  public static DocString added(DocString str) {
+    DocString string = new DocString();
+    string.mStringBuilder.append("<span class=\"added\">");
+    string.mStringBuilder.append(str.html());
+    string.mStringBuilder.append("</span>");
+    return string;
+  }
+
+  /**
+   * Adorn the given string to indicate it represents something added relative
+   * to a baseline.
+   */
+  public static DocString added(String str) {
+    return added(text(str));
+  }
+
+  /**
+   * Adorn the given string to indicate it represents something removed relative
+   * to a baseline.
+   */
+  public static DocString removed(DocString str) {
+    DocString string = new DocString();
+    string.mStringBuilder.append("<span class=\"removed\">");
+    string.mStringBuilder.append(str.html());
+    string.mStringBuilder.append("</span>");
+    return string;
+  }
+
+  /**
+   * Adorn the given string to indicate it represents something removed relative
+   * to a baseline.
+   */
+  public static DocString removed(String str) {
+    return removed(text(str));
+  }
+
+  /**
+   * Standard formatted DocString for describing a change in size relative to
+   * a baseline.
+   * @param noCurrent - whether no current object exists.
+   * @param noBaseline - whether no basline object exists.
+   * @param current - the size of the current object.
+   * @param baseline - the size of the baseline object.
+   */
+  public static DocString delta(boolean noCurrent, boolean noBaseline,
+      long current, long baseline) {
+    DocString doc = new DocString();
+    return doc.appendDelta(noCurrent, noBaseline, current, baseline);
+  }
+
+  /**
+   * Standard formatted DocString for describing a change in size relative to
+   * a baseline.
+   */
+  public DocString appendDelta(boolean noCurrent, boolean noBaseline,
+      long current, long baseline) {
+    if (noCurrent) {
+      append(removed(format("%+,14d", 0 - baseline)));
+    } else if (noBaseline) {
+      append(added("new"));
+    } else if (current > baseline) {
+      append(added(format("%+,14d", current - baseline)));
+    } else if (current < baseline) {
+      append(removed(format("%+,14d", current - baseline)));
+    }
+    return this;
+  }
+
   public DocString appendLink(URI uri, DocString content) {
     mStringBuilder.append("<a href=\"");
     mStringBuilder.append(uri.toASCIIString());
diff --git a/tools/ahat/src/DominatedList.java b/tools/ahat/src/DominatedList.java
index c884e7fcf6..f73e3ca027 100644
--- a/tools/ahat/src/DominatedList.java
+++ b/tools/ahat/src/DominatedList.java
@@ -19,6 +19,7 @@ package com.android.ahat;
 import com.android.ahat.heapdump.AhatHeap;
 import com.android.ahat.heapdump.AhatInstance;
 import com.android.ahat.heapdump.AhatSnapshot;
+import com.android.ahat.heapdump.Sort;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Collections;
diff --git a/tools/ahat/src/HeapTable.java b/tools/ahat/src/HeapTable.java
index 22188b00e2..9abbe4a4ed 100644
--- a/tools/ahat/src/HeapTable.java
+++ b/tools/ahat/src/HeapTable.java
@@ -18,6 +18,7 @@ package com.android.ahat;
 
 import com.android.ahat.heapdump.AhatHeap;
 import com.android.ahat.heapdump.AhatSnapshot;
+import com.android.ahat.heapdump.Diffable;
 import java.util.ArrayList;
 import java.util.HashMap;
 import java.util.List;
@@ -44,12 +45,22 @@ class HeapTable {
     List<ValueConfig<T>> getValueConfigs();
   }
 
+  private static DocString sizeString(long size, boolean isPlaceHolder) {
+    DocString string = new DocString();
+    if (isPlaceHolder) {
+      string.append(DocString.removed("del"));
+    } else if (size != 0) {
+      string.appendFormat("%,14d", size);
+    }
+    return string;
+  }
+
   /**
    * Render the table to the given document.
    * @param query - The page query.
    * @param id - A unique identifier for the table on the page.
    */
-  public static <T> void render(Doc doc, Query query, String id,
+  public static <T extends Diffable<T>> void render(Doc doc, Query query, String id,
       TableConfig<T> config, AhatSnapshot snapshot, List<T> elements) {
     // Only show the heaps that have non-zero entries.
     List<AhatHeap> heaps = new ArrayList<AhatHeap>();
@@ -62,14 +73,14 @@ class HeapTable {
     List<ValueConfig<T>> values = config.getValueConfigs();
 
     // Print the heap and values descriptions.
-    boolean showTotal = heaps.size() > 1;
     List<Column> subcols = new ArrayList<Column>();
     for (AhatHeap heap : heaps) {
       subcols.add(new Column(heap.getName(), Column.Align.RIGHT));
+      subcols.add(new Column("Δ", Column.Align.RIGHT, snapshot.isDiffed()));
     }
-    if (showTotal) {
-      subcols.add(new Column("Total", Column.Align.RIGHT));
-    }
+    boolean showTotal = heaps.size() > 1;
+    subcols.add(new Column("Total", Column.Align.RIGHT, showTotal));
+    subcols.add(new Column("Δ", Column.Align.RIGHT, showTotal && snapshot.isDiffed()));
     List<Column> cols = new ArrayList<Column>();
     for (ValueConfig value : values) {
       cols.add(new Column(value.getDescription()));
@@ -80,16 +91,20 @@ class HeapTable {
     SubsetSelector<T> selector = new SubsetSelector(query, id, elements);
     ArrayList<DocString> vals = new ArrayList<DocString>();
     for (T elem : selector.selected()) {
+      T base = elem.getBaseline();
       vals.clear();
       long total = 0;
+      long basetotal = 0;
       for (AhatHeap heap : heaps) {
         long size = config.getSize(elem, heap);
+        long basesize = config.getSize(base, heap.getBaseline());
         total += size;
-        vals.add(size == 0 ? DocString.text("") : DocString.format("%,14d", size));
-      }
-      if (showTotal) {
-        vals.add(total == 0 ? DocString.text("") : DocString.format("%,14d", total));
+        basetotal += basesize;
+        vals.add(sizeString(size, elem.isPlaceHolder()));
+        vals.add(DocString.delta(elem.isPlaceHolder(), base.isPlaceHolder(), size, basesize));
       }
+      vals.add(sizeString(total, elem.isPlaceHolder()));
+      vals.add(DocString.delta(elem.isPlaceHolder(), base.isPlaceHolder(), total, basetotal));
 
       for (ValueConfig<T> value : values) {
         vals.add(value.render(elem));
@@ -101,26 +116,35 @@ class HeapTable {
     List<T> remaining = selector.remaining();
     if (!remaining.isEmpty()) {
       Map<AhatHeap, Long> summary = new HashMap<AhatHeap, Long>();
+      Map<AhatHeap, Long> basesummary = new HashMap<AhatHeap, Long>();
       for (AhatHeap heap : heaps) {
         summary.put(heap, 0L);
+        basesummary.put(heap, 0L);
       }
 
       for (T elem : remaining) {
         for (AhatHeap heap : heaps) {
-          summary.put(heap, summary.get(heap) + config.getSize(elem, heap));
+          long size = config.getSize(elem, heap);
+          summary.put(heap, summary.get(heap) + size);
+
+          long basesize = config.getSize(elem.getBaseline(), heap.getBaseline());
+          basesummary.put(heap, basesummary.get(heap) + basesize);
         }
       }
 
       vals.clear();
       long total = 0;
+      long basetotal = 0;
       for (AhatHeap heap : heaps) {
         long size = summary.get(heap);
+        long basesize = basesummary.get(heap);
         total += size;
-        vals.add(DocString.format("%,14d", size));
-      }
-      if (showTotal) {
-        vals.add(DocString.format("%,14d", total));
+        basetotal += basesize;
+        vals.add(sizeString(size, false));
+        vals.add(DocString.delta(false, false, size, basesize));
       }
+      vals.add(sizeString(total, false));
+      vals.add(DocString.delta(false, false, total, basetotal));
 
       for (ValueConfig<T> value : values) {
         vals.add(DocString.text("..."));
@@ -132,11 +156,13 @@ class HeapTable {
   }
 
   // Returns true if the given heap has a non-zero size entry.
-  public static <T> boolean hasNonZeroEntry(AhatHeap heap,
+  public static <T extends Diffable<T>> boolean hasNonZeroEntry(AhatHeap heap,
       TableConfig<T> config, List<T> elements) {
-    if (heap.getSize() > 0) {
+    AhatHeap baseheap = heap.getBaseline();
+    if (heap.getSize() > 0 || baseheap.getSize() > 0) {
       for (T element : elements) {
-        if (config.getSize(element, heap) > 0) {
+        if (config.getSize(element, heap) > 0 ||
+            config.getSize(element.getBaseline(), baseheap) > 0) {
           return true;
         }
       }
diff --git a/tools/ahat/src/HelpHandler.java b/tools/ahat/src/HelpHandler.java
deleted file mode 100644
index 8de3c85f5c..0000000000
--- a/tools/ahat/src/HelpHandler.java
+++ /dev/null
@@ -1,52 +0,0 @@
-/*
- * Copyright (C) 2015 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package com.android.ahat;
-
-import com.google.common.io.ByteStreams;
-import com.sun.net.httpserver.HttpExchange;
-import com.sun.net.httpserver.HttpHandler;
-import java.io.IOException;
-import java.io.InputStream;
-import java.io.PrintStream;
-
-/**
- * HelpHandler.
- *
- * HttpHandler to show the help page.
- */
-class HelpHandler implements HttpHandler {
-
-  @Override
-  public void handle(HttpExchange exchange) throws IOException {
-    ClassLoader loader = HelpHandler.class.getClassLoader();
-    exchange.getResponseHeaders().add("Content-Type", "text/html;charset=utf-8");
-    exchange.sendResponseHeaders(200, 0);
-    PrintStream ps = new PrintStream(exchange.getResponseBody());
-    HtmlDoc doc = new HtmlDoc(ps, DocString.text("ahat"), DocString.uri("style.css"));
-    doc.menu(Menu.getMenu());
-
-    InputStream is = loader.getResourceAsStream("help.html");
-    if (is == null) {
-      ps.println("No help available.");
-    } else {
-      ByteStreams.copy(is, ps);
-    }
-
-    doc.close();
-    ps.close();
-  }
-}
diff --git a/tools/ahat/src/HtmlDoc.java b/tools/ahat/src/HtmlDoc.java
index 5ccbacb2d6..5a22fc75fe 100644
--- a/tools/ahat/src/HtmlDoc.java
+++ b/tools/ahat/src/HtmlDoc.java
@@ -86,19 +86,27 @@ public class HtmlDoc implements Doc {
     mCurrentTableColumns = columns;
     ps.println("<table>");
     for (int i = 0; i < columns.length - 1; i++) {
-      ps.format("<th>%s</th>", columns[i].heading.html());
+      if (columns[i].visible) {
+        ps.format("<th>%s</th>", columns[i].heading.html());
+      }
     }
 
     // Align the last header to the left so it's easier to see if the last
     // column is very wide.
-    ps.format("<th align=\"left\">%s</th>", columns[columns.length - 1].heading.html());
+    if (columns[columns.length - 1].visible) {
+      ps.format("<th align=\"left\">%s</th>", columns[columns.length - 1].heading.html());
+    }
   }
 
   @Override
   public void table(DocString description, List<Column> subcols, List<Column> cols) {
     mCurrentTableColumns = new Column[subcols.size() + cols.size()];
     int j = 0;
+    int visibleSubCols = 0;
     for (Column col : subcols) {
+      if (col.visible) {
+        visibleSubCols++;
+      }
       mCurrentTableColumns[j] = col;
       j++;
     }
@@ -108,21 +116,27 @@ public class HtmlDoc implements Doc {
     }
 
     ps.println("<table>");
-    ps.format("<tr><th colspan=\"%d\">%s</th>", subcols.size(), description.html());
+    ps.format("<tr><th colspan=\"%d\">%s</th>", visibleSubCols, description.html());
     for (int i = 0; i < cols.size() - 1; i++) {
-      ps.format("<th rowspan=\"2\">%s</th>", cols.get(i).heading.html());
+      if (cols.get(i).visible) {
+        ps.format("<th rowspan=\"2\">%s</th>", cols.get(i).heading.html());
+      }
     }
     if (!cols.isEmpty()) {
       // Align the last column header to the left so it can still be seen if
       // the last column is very wide.
-      ps.format("<th align=\"left\" rowspan=\"2\">%s</th>",
-          cols.get(cols.size() - 1).heading.html());
+      Column col = cols.get(cols.size() - 1);
+      if (col.visible) {
+        ps.format("<th align=\"left\" rowspan=\"2\">%s</th>", col.heading.html());
+      }
     }
     ps.println("</tr>");
 
     ps.print("<tr>");
     for (Column subcol : subcols) {
-      ps.format("<th>%s</th>", subcol.heading.html());
+      if (subcol.visible) {
+        ps.format("<th>%s</th>", subcol.heading.html());
+      }
     }
     ps.println("</tr>");
   }
@@ -141,11 +155,13 @@ public class HtmlDoc implements Doc {
 
     ps.print("<tr>");
     for (int i = 0; i < values.length; i++) {
+      if (mCurrentTableColumns[i].visible) {
       ps.print("<td");
-      if (mCurrentTableColumns[i].align == Column.Align.RIGHT) {
-        ps.print(" align=\"right\"");
+        if (mCurrentTableColumns[i].align == Column.Align.RIGHT) {
+          ps.print(" align=\"right\"");
+        }
+        ps.format(">%s</td>", values[i].html());
       }
-      ps.format(">%s</td>", values[i].html());
     }
     ps.println("</tr>");
   }
diff --git a/tools/ahat/src/Main.java b/tools/ahat/src/Main.java
index 405ac778ce..b8552fe1ce 100644
--- a/tools/ahat/src/Main.java
+++ b/tools/ahat/src/Main.java
@@ -17,6 +17,7 @@
 package com.android.ahat;
 
 import com.android.ahat.heapdump.AhatSnapshot;
+import com.android.ahat.heapdump.Diff;
 import com.android.tools.perflib.heap.ProguardMap;
 import com.sun.net.httpserver.HttpServer;
 import java.io.File;
@@ -30,15 +31,18 @@ import java.util.concurrent.Executors;
 public class Main {
 
   public static void help(PrintStream out) {
-    out.println("java -jar ahat.jar [-p port] [--proguard-map FILE] FILE");
-    out.println("  Launch an http server for viewing "
-        + "the given Android heap-dump FILE.");
+    out.println("java -jar ahat.jar [OPTIONS] FILE");
+    out.println("  Launch an http server for viewing the given Android heap dump FILE.");
     out.println("");
-    out.println("Options:");
+    out.println("OPTIONS:");
     out.println("  -p <port>");
     out.println("     Serve pages on the given port. Defaults to 7100.");
     out.println("  --proguard-map FILE");
     out.println("     Use the proguard map FILE to deobfuscate the heap dump.");
+    out.println("  --baseline FILE");
+    out.println("     Diff the heap dump against the given baseline heap dump FILE.");
+    out.println("  --baseline-proguard-map FILE");
+    out.println("     Use the proguard map FILE to deobfuscate the baseline heap dump.");
     out.println("");
   }
 
@@ -52,7 +56,9 @@ public class Main {
     }
 
     File hprof = null;
+    File hprofbase = null;
     ProguardMap map = new ProguardMap();
+    ProguardMap mapbase = new ProguardMap();
     for (int i = 0; i < args.length; i++) {
       if ("-p".equals(args[i]) && i + 1 < args.length) {
         i++;
@@ -65,6 +71,22 @@ public class Main {
           System.out.println("Unable to read proguard map: " + ex);
           System.out.println("The proguard map will not be used.");
         }
+      } else if ("--baseline-proguard-map".equals(args[i]) && i + 1 < args.length) {
+        i++;
+        try {
+          mapbase.readFromFile(new File(args[i]));
+        } catch (IOException|ParseException ex) {
+          System.out.println("Unable to read baselline proguard map: " + ex);
+          System.out.println("The proguard map will not be used.");
+        }
+      } else if ("--baseline".equals(args[i]) && i + 1 < args.length) {
+        i++;
+        if (hprofbase != null) {
+          System.err.println("multiple baseline heap dumps.");
+          help(System.err);
+          return;
+        }
+        hprofbase = new File(args[i]);
       } else {
         if (hprof != null) {
           System.err.println("multiple input files.");
@@ -89,14 +111,21 @@ public class Main {
 
     System.out.println("Processing hprof file...");
     AhatSnapshot ahat = AhatSnapshot.fromHprof(hprof, map);
-    server.createContext("/", new AhatHttpHandler(new OverviewHandler(ahat, hprof)));
+
+    if (hprofbase != null) {
+      System.out.println("Processing baseline hprof file...");
+      AhatSnapshot base = AhatSnapshot.fromHprof(hprofbase, mapbase);
+
+      System.out.println("Diffing hprof files...");
+      Diff.snapshots(ahat, base);
+    }
+
+    server.createContext("/", new AhatHttpHandler(new OverviewHandler(ahat, hprof, hprofbase)));
     server.createContext("/rooted", new AhatHttpHandler(new RootedHandler(ahat)));
     server.createContext("/object", new AhatHttpHandler(new ObjectHandler(ahat)));
     server.createContext("/objects", new AhatHttpHandler(new ObjectsHandler(ahat)));
     server.createContext("/site", new AhatHttpHandler(new SiteHandler(ahat)));
-    server.createContext("/native", new AhatHttpHandler(new NativeAllocationsHandler(ahat)));
     server.createContext("/bitmap", new BitmapHandler(ahat));
-    server.createContext("/help", new HelpHandler());
     server.createContext("/style.css", new StaticHandler("style.css", "text/css"));
     server.setExecutor(Executors.newFixedThreadPool(1));
     System.out.println("Server started on localhost:" + port);
diff --git a/tools/ahat/src/Menu.java b/tools/ahat/src/Menu.java
index 232b849c28..6d38dc5731 100644
--- a/tools/ahat/src/Menu.java
+++ b/tools/ahat/src/Menu.java
@@ -25,11 +25,7 @@ class Menu {
       .append(" - ")
       .appendLink(DocString.uri("rooted"), DocString.text("rooted"))
       .append(" - ")
-      .appendLink(DocString.uri("sites"), DocString.text("allocations"))
-      .append(" - ")
-      .appendLink(DocString.uri("native"), DocString.text("native"))
-      .append(" - ")
-      .appendLink(DocString.uri("help"), DocString.text("help"));
+      .appendLink(DocString.uri("sites"), DocString.text("allocations"));
 
   /**
    * Returns the menu as a DocString.
diff --git a/tools/ahat/src/NativeAllocationsHandler.java b/tools/ahat/src/NativeAllocationsHandler.java
deleted file mode 100644
index 605a0678ce..0000000000
--- a/tools/ahat/src/NativeAllocationsHandler.java
+++ /dev/null
@@ -1,97 +0,0 @@
-/*
- * Copyright (C) 2015 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package com.android.ahat;
-
-import com.android.ahat.heapdump.AhatSnapshot;
-import com.android.ahat.heapdump.NativeAllocation;
-import java.io.IOException;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.List;
-
-class NativeAllocationsHandler implements AhatHandler {
-  private static final String ALLOCATIONS_ID = "allocations";
-
-  private AhatSnapshot mSnapshot;
-
-  public NativeAllocationsHandler(AhatSnapshot snapshot) {
-    mSnapshot = snapshot;
-  }
-
-  @Override
-  public void handle(Doc doc, Query query) throws IOException {
-    List<NativeAllocation> allocs = mSnapshot.getNativeAllocations();
-
-    doc.title("Registered Native Allocations");
-
-    doc.section("Overview");
-    long totalSize = 0;
-    for (NativeAllocation alloc : allocs) {
-      totalSize += alloc.size;
-    }
-    doc.descriptions();
-    doc.description(DocString.text("Number of Registered Native Allocations"),
-        DocString.format("%,14d", allocs.size()));
-    doc.description(DocString.text("Total Size of Registered Native Allocations"),
-        DocString.format("%,14d", totalSize));
-    doc.end();
-
-    doc.section("List of Allocations");
-    if (allocs.isEmpty()) {
-      doc.println(DocString.text("(none)"));
-    } else {
-      doc.table(
-          new Column("Size", Column.Align.RIGHT),
-          new Column("Heap"),
-          new Column("Native Pointer"),
-          new Column("Referent"));
-      Comparator<NativeAllocation> compare
-        = new Sort.WithPriority<NativeAllocation>(
-            new Sort.NativeAllocationByHeapName(),
-            new Sort.NativeAllocationBySize());
-      Collections.sort(allocs, compare);
-      SubsetSelector<NativeAllocation> selector
-        = new SubsetSelector(query, ALLOCATIONS_ID, allocs);
-      for (NativeAllocation alloc : selector.selected()) {
-        doc.row(
-            DocString.format("%,14d", alloc.size),
-            DocString.text(alloc.heap.getName()),
-            DocString.format("0x%x", alloc.pointer),
-            Summarizer.summarize(alloc.referent));
-      }
-
-      // Print a summary of the remaining entries if there are any.
-      List<NativeAllocation> remaining = selector.remaining();
-      if (!remaining.isEmpty()) {
-        long total = 0;
-        for (NativeAllocation alloc : remaining) {
-          total += alloc.size;
-        }
-
-        doc.row(
-            DocString.format("%,14d", total),
-            DocString.text("..."),
-            DocString.text("..."),
-            DocString.text("..."));
-      }
-
-      doc.end();
-      selector.render(doc);
-    }
-  }
-}
-
diff --git a/tools/ahat/src/ObjectHandler.java b/tools/ahat/src/ObjectHandler.java
index 2546b0c32d..2e0ae6ed2d 100644
--- a/tools/ahat/src/ObjectHandler.java
+++ b/tools/ahat/src/ObjectHandler.java
@@ -22,6 +22,7 @@ import com.android.ahat.heapdump.AhatClassObj;
 import com.android.ahat.heapdump.AhatHeap;
 import com.android.ahat.heapdump.AhatInstance;
 import com.android.ahat.heapdump.AhatSnapshot;
+import com.android.ahat.heapdump.Diff;
 import com.android.ahat.heapdump.FieldValue;
 import com.android.ahat.heapdump.PathElement;
 import com.android.ahat.heapdump.Site;
@@ -30,6 +31,7 @@ import java.io.IOException;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.List;
+import java.util.Objects;
 
 
 class ObjectHandler implements AhatHandler {
@@ -57,6 +59,7 @@ class ObjectHandler implements AhatHandler {
       doc.println(DocString.format("No object with id %08xl", id));
       return;
     }
+    AhatInstance base = inst.getBaseline();
 
     doc.title("Object %08x", inst.getId());
     doc.big(Summarizer.summarize(inst));
@@ -68,10 +71,17 @@ class ObjectHandler implements AhatHandler {
     AhatClassObj cls = inst.getClassObj();
     doc.descriptions();
     doc.description(DocString.text("Class"), Summarizer.summarize(cls));
-    doc.description(DocString.text("Size"), DocString.format("%d", inst.getSize()));
-    doc.description(
-        DocString.text("Retained Size"),
-        DocString.format("%d", inst.getTotalRetainedSize()));
+
+    DocString sizeDescription = DocString.format("%,14d ", inst.getSize());
+    sizeDescription.appendDelta(false, base.isPlaceHolder(),
+        inst.getSize(), base.getSize());
+    doc.description(DocString.text("Size"), sizeDescription);
+
+    DocString rsizeDescription = DocString.format("%,14d ", inst.getTotalRetainedSize());
+    rsizeDescription.appendDelta(false, base.isPlaceHolder(),
+        inst.getTotalRetainedSize(), base.getTotalRetainedSize());
+    doc.description(DocString.text("Retained Size"), rsizeDescription);
+
     doc.description(DocString.text("Heap"), DocString.text(inst.getHeap().getName()));
 
     Collection<String> rootTypes = inst.getRootTypes();
@@ -102,33 +112,76 @@ class ObjectHandler implements AhatHandler {
 
   private static void printClassInstanceFields(Doc doc, Query query, AhatClassInstance inst) {
     doc.section("Fields");
-    doc.table(new Column("Type"), new Column("Name"), new Column("Value"));
-    SubsetSelector<FieldValue> selector
-      = new SubsetSelector(query, INSTANCE_FIELDS_ID, inst.getInstanceFields());
-    for (FieldValue field : selector.selected()) {
-      doc.row(
-          DocString.text(field.getType()),
-          DocString.text(field.getName()),
-          Summarizer.summarize(field.getValue()));
+    AhatInstance base = inst.getBaseline();
+    List<FieldValue> fields = inst.getInstanceFields();
+    if (!base.isPlaceHolder()) {
+      Diff.fields(fields, base.asClassInstance().getInstanceFields());
     }
-    doc.end();
+    SubsetSelector<FieldValue> selector = new SubsetSelector(query, INSTANCE_FIELDS_ID, fields);
+    printFields(doc, inst != base && !base.isPlaceHolder(), selector.selected());
     selector.render(doc);
   }
 
   private static void printArrayElements(Doc doc, Query query, AhatArrayInstance array) {
     doc.section("Array Elements");
-    doc.table(new Column("Index", Column.Align.RIGHT), new Column("Value"));
+    AhatInstance base = array.getBaseline();
+    boolean diff = array.getBaseline() != array && !base.isPlaceHolder();
+    doc.table(
+        new Column("Index", Column.Align.RIGHT),
+        new Column("Value"),
+        new Column("Δ", Column.Align.LEFT, diff));
+
     List<Value> elements = array.getValues();
     SubsetSelector<Value> selector = new SubsetSelector(query, ARRAY_ELEMENTS_ID, elements);
     int i = 0;
-    for (Value elem : selector.selected()) {
-      doc.row(DocString.format("%d", i), Summarizer.summarize(elem));
+    for (Value current : selector.selected()) {
+      DocString delta = new DocString();
+      if (diff) {
+        Value previous = Value.getBaseline(base.asArrayInstance().getValue(i));
+        if (!Objects.equals(current, previous)) {
+          delta.append("was ");
+          delta.append(Summarizer.summarize(previous));
+        }
+      }
+      doc.row(DocString.format("%d", i), Summarizer.summarize(current), delta);
       i++;
     }
     doc.end();
     selector.render(doc);
   }
 
+  private static void printFields(Doc doc, boolean diff, List<FieldValue> fields) {
+    doc.table(
+        new Column("Type"),
+        new Column("Name"),
+        new Column("Value"),
+        new Column("Δ", Column.Align.LEFT, diff));
+
+    for (FieldValue field : fields) {
+      Value current = field.getValue();
+      DocString value;
+      if (field.isPlaceHolder()) {
+        value = DocString.removed("del");
+      } else {
+        value = Summarizer.summarize(current);
+      }
+
+      DocString delta = new DocString();
+      FieldValue basefield = field.getBaseline();
+      if (basefield.isPlaceHolder()) {
+        delta.append(DocString.added("new"));
+      } else {
+        Value previous = Value.getBaseline(basefield.getValue());
+        if (!Objects.equals(current, previous)) {
+          delta.append("was ");
+          delta.append(Summarizer.summarize(previous));
+        }
+      }
+      doc.row(DocString.text(field.getType()), DocString.text(field.getName()), value, delta);
+    }
+    doc.end();
+  }
+
   private static void printClassInfo(Doc doc, Query query, AhatClassObj clsobj) {
     doc.section("Class Info");
     doc.descriptions();
@@ -139,16 +192,13 @@ class ObjectHandler implements AhatHandler {
     doc.end();
 
     doc.section("Static Fields");
-    doc.table(new Column("Type"), new Column("Name"), new Column("Value"));
+    AhatInstance base = clsobj.getBaseline();
     List<FieldValue> fields = clsobj.getStaticFieldValues();
-    SubsetSelector<FieldValue> selector = new SubsetSelector(query, STATIC_FIELDS_ID, fields);
-    for (FieldValue field : selector.selected()) {
-      doc.row(
-          DocString.text(field.getType()),
-          DocString.text(field.getName()),
-          Summarizer.summarize(field.getValue()));
+    if (!base.isPlaceHolder()) {
+      Diff.fields(fields, base.asClassObj().getStaticFieldValues());
     }
-    doc.end();
+    SubsetSelector<FieldValue> selector = new SubsetSelector(query, STATIC_FIELDS_ID, fields);
+    printFields(doc, clsobj != base && !base.isPlaceHolder(), selector.selected());
     selector.render(doc);
   }
 
@@ -200,8 +250,9 @@ class ObjectHandler implements AhatHandler {
     doc.section("Sample Path from GC Root");
     List<PathElement> path = inst.getPathFromGcRoot();
 
-    // Add 'null' as a marker for the root.
-    path.add(0, null);
+    // Add a dummy PathElement as a marker for the root.
+    final PathElement root = new PathElement(null, null);
+    path.add(0, root);
 
     HeapTable.TableConfig<PathElement> table = new HeapTable.TableConfig<PathElement>() {
       public String getHeapsDescription() {
@@ -209,7 +260,7 @@ class ObjectHandler implements AhatHandler {
       }
 
       public long getSize(PathElement element, AhatHeap heap) {
-        if (element == null) {
+        if (element == root) {
           return heap.getSize();
         }
         if (element.isDominator) {
@@ -225,7 +276,7 @@ class ObjectHandler implements AhatHandler {
           }
 
           public DocString render(PathElement element) {
-            if (element == null) {
+            if (element == root) {
               return DocString.link(DocString.uri("rooted"), DocString.text("ROOT"));
             } else {
               DocString label = DocString.text("→ ");
diff --git a/tools/ahat/src/ObjectsHandler.java b/tools/ahat/src/ObjectsHandler.java
index 412647462c..3062d23b53 100644
--- a/tools/ahat/src/ObjectsHandler.java
+++ b/tools/ahat/src/ObjectsHandler.java
@@ -19,6 +19,7 @@ package com.android.ahat;
 import com.android.ahat.heapdump.AhatInstance;
 import com.android.ahat.heapdump.AhatSnapshot;
 import com.android.ahat.heapdump.Site;
+import com.android.ahat.heapdump.Sort;
 import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Collections;
@@ -52,14 +53,20 @@ class ObjectsHandler implements AhatHandler {
     Collections.sort(insts, Sort.defaultInstanceCompare(mSnapshot));
 
     doc.title("Objects");
+
     doc.table(
         new Column("Size", Column.Align.RIGHT),
+        new Column("Δ", Column.Align.RIGHT, mSnapshot.isDiffed()),
         new Column("Heap"),
         new Column("Object"));
+
     SubsetSelector<AhatInstance> selector = new SubsetSelector(query, OBJECTS_ID, insts);
     for (AhatInstance inst : selector.selected()) {
+      AhatInstance base = inst.getBaseline();
       doc.row(
-          DocString.format("%,d", inst.getSize()),
+          DocString.format("%,14d", inst.getSize()),
+          DocString.delta(inst.isPlaceHolder(), base.isPlaceHolder(),
+            inst.getSize(), base.getSize()),
           DocString.text(inst.getHeap().getName()),
           Summarizer.summarize(inst));
     }
diff --git a/tools/ahat/src/OverviewHandler.java b/tools/ahat/src/OverviewHandler.java
index 3a34d13991..ea305c4e94 100644
--- a/tools/ahat/src/OverviewHandler.java
+++ b/tools/ahat/src/OverviewHandler.java
@@ -18,7 +18,7 @@ package com.android.ahat;
 
 import com.android.ahat.heapdump.AhatHeap;
 import com.android.ahat.heapdump.AhatSnapshot;
-import com.android.ahat.heapdump.NativeAllocation;
+import com.android.ahat.heapdump.Diffable;
 import java.io.File;
 import java.io.IOException;
 import java.util.Collections;
@@ -30,10 +30,12 @@ class OverviewHandler implements AhatHandler {
 
   private AhatSnapshot mSnapshot;
   private File mHprof;
+  private File mBaseHprof;
 
-  public OverviewHandler(AhatSnapshot snapshot, File hprof) {
+  public OverviewHandler(AhatSnapshot snapshot, File hprof, File basehprof) {
     mSnapshot = snapshot;
     mHprof = hprof;
+    mBaseHprof = basehprof;
   }
 
   @Override
@@ -46,42 +48,40 @@ class OverviewHandler implements AhatHandler {
         DocString.text("ahat version"),
         DocString.format("ahat-%s", OverviewHandler.class.getPackage().getImplementationVersion()));
     doc.description(DocString.text("hprof file"), DocString.text(mHprof.toString()));
+    if (mBaseHprof != null) {
+      doc.description(DocString.text("baseline hprof file"), DocString.text(mBaseHprof.toString()));
+    }
     doc.end();
 
     doc.section("Heap Sizes");
     printHeapSizes(doc, query);
 
-    List<NativeAllocation> allocs = mSnapshot.getNativeAllocations();
-    if (!allocs.isEmpty()) {
-      doc.section("Registered Native Allocations");
-      long totalSize = 0;
-      for (NativeAllocation alloc : allocs) {
-        totalSize += alloc.size;
-      }
-      doc.descriptions();
-      doc.description(DocString.text("Number of Registered Native Allocations"),
-          DocString.format("%,14d", allocs.size()));
-      doc.description(DocString.text("Total Size of Registered Native Allocations"),
-          DocString.format("%,14d", totalSize));
-      doc.end();
+    doc.big(Menu.getMenu());
+  }
+
+  private static class TableElem implements Diffable<TableElem> {
+    @Override public TableElem getBaseline() {
+      return this;
     }
 
-    doc.big(Menu.getMenu());
+    @Override public boolean isPlaceHolder() {
+      return false;
+    }
   }
 
   private void printHeapSizes(Doc doc, Query query) {
-    List<Object> dummy = Collections.singletonList(null);
+    List<TableElem> dummy = Collections.singletonList(new TableElem());
 
-    HeapTable.TableConfig<Object> table = new HeapTable.TableConfig<Object>() {
+    HeapTable.TableConfig<TableElem> table = new HeapTable.TableConfig<TableElem>() {
       public String getHeapsDescription() {
         return "Bytes Retained by Heap";
       }
 
-      public long getSize(Object element, AhatHeap heap) {
+      public long getSize(TableElem element, AhatHeap heap) {
         return heap.getSize();
       }
 
-      public List<HeapTable.ValueConfig<Object>> getValueConfigs() {
+      public List<HeapTable.ValueConfig<TableElem>> getValueConfigs() {
         return Collections.emptyList();
       }
     };
diff --git a/tools/ahat/src/SiteHandler.java b/tools/ahat/src/SiteHandler.java
index cfd5c9a796..febf1713fb 100644
--- a/tools/ahat/src/SiteHandler.java
+++ b/tools/ahat/src/SiteHandler.java
@@ -19,6 +19,7 @@ package com.android.ahat;
 import com.android.ahat.heapdump.AhatHeap;
 import com.android.ahat.heapdump.AhatSnapshot;
 import com.android.ahat.heapdump.Site;
+import com.android.ahat.heapdump.Sort;
 import java.io.IOException;
 import java.util.Collections;
 import java.util.Comparator;
@@ -79,27 +80,34 @@ class SiteHandler implements AhatHandler {
     }
 
     doc.section("Objects Allocated");
+
     doc.table(
         new Column("Reachable Bytes Allocated", Column.Align.RIGHT),
+        new Column("Δ", Column.Align.RIGHT, mSnapshot.isDiffed()),
         new Column("Instances", Column.Align.RIGHT),
+        new Column("Δ", Column.Align.RIGHT, mSnapshot.isDiffed()),
         new Column("Heap"),
         new Column("Class"));
+
     List<Site.ObjectsInfo> infos = site.getObjectsInfos();
     Comparator<Site.ObjectsInfo> compare = new Sort.WithPriority<Site.ObjectsInfo>(
-        new Sort.ObjectsInfoByHeapName(),
-        new Sort.ObjectsInfoBySize(),
-        new Sort.ObjectsInfoByClassName());
+        Sort.OBJECTS_INFO_BY_HEAP_NAME,
+        Sort.OBJECTS_INFO_BY_SIZE,
+        Sort.OBJECTS_INFO_BY_CLASS_NAME);
     Collections.sort(infos, compare);
     SubsetSelector<Site.ObjectsInfo> selector
       = new SubsetSelector(query, OBJECTS_ALLOCATED_ID, infos);
     for (Site.ObjectsInfo info : selector.selected()) {
+      Site.ObjectsInfo baseinfo = info.getBaseline();
       String className = info.getClassName();
       doc.row(
           DocString.format("%,14d", info.numBytes),
+          DocString.delta(false, false, info.numBytes, baseinfo.numBytes),
           DocString.link(
             DocString.formattedUri("objects?id=%d&depth=%d&heap=%s&class=%s",
-                site.getId(), site.getDepth(), info.heap.getName(), className),
+              site.getId(), site.getDepth(), info.heap.getName(), className),
             DocString.format("%,14d", info.numInstances)),
+          DocString.delta(false, false, info.numInstances, baseinfo.numInstances),
           DocString.text(info.heap.getName()),
           Summarizer.summarize(info.classObj));
     }
diff --git a/tools/ahat/src/Summarizer.java b/tools/ahat/src/Summarizer.java
index 40a0499160..7f4dcbf9c4 100644
--- a/tools/ahat/src/Summarizer.java
+++ b/tools/ahat/src/Summarizer.java
@@ -36,25 +36,40 @@ class Summarizer {
   public static DocString summarize(AhatInstance inst) {
     DocString formatted = new DocString();
     if (inst == null) {
-      formatted.append("(null)");
+      formatted.append("null");
       return formatted;
     }
 
+    // Annotate new objects as new.
+    if (inst.getBaseline().isPlaceHolder()) {
+      formatted.append(DocString.added("new "));
+    }
+
+    // Annotate deleted objects as deleted.
+    if (inst.isPlaceHolder()) {
+      formatted.append(DocString.removed("del "));
+    }
+
     // Annotate roots as roots.
     if (inst.isRoot()) {
-      formatted.append("(root) ");
+      formatted.append("root ");
     }
 
     // Annotate classes as classes.
-    DocString link = new DocString();
+    DocString linkText = new DocString();
     if (inst.isClassObj()) {
-      link.append("class ");
+      linkText.append("class ");
     }
 
-    link.append(inst.toString());
+    linkText.append(inst.toString());
 
-    URI objTarget = DocString.formattedUri("object?id=%d", inst.getId());
-    formatted.appendLink(objTarget, link);
+    if (inst.isPlaceHolder()) {
+      // Don't make links to placeholder objects.
+      formatted.append(linkText);
+    } else {
+      URI objTarget = DocString.formattedUri("object?id=%d", inst.getId());
+      formatted.appendLink(objTarget, linkText);
+    }
 
     // Annotate Strings with their values.
     String stringValue = inst.asString(kMaxChars);
@@ -83,7 +98,6 @@ class Summarizer {
       }
     }
 
-
     // Annotate bitmaps with a thumbnail.
     AhatInstance bitmap = inst.getAssociatedBitmapInstance();
     String thumbnail = "";
diff --git a/tools/ahat/src/heapdump/AhatClassInstance.java b/tools/ahat/src/heapdump/AhatClassInstance.java
index fae34b0d29..273530af64 100644
--- a/tools/ahat/src/heapdump/AhatClassInstance.java
+++ b/tools/ahat/src/heapdump/AhatClassInstance.java
@@ -143,55 +143,6 @@ public class AhatClassInstance extends AhatInstance {
     return null;
   }
 
-  @Override public NativeAllocation getNativeAllocation() {
-    if (!isInstanceOfClass("libcore.util.NativeAllocationRegistry$CleanerThunk")) {
-      return null;
-    }
-
-    Long pointer = getLongField("nativePtr", null);
-    if (pointer == null) {
-      return null;
-    }
-
-    // Search for the registry field of inst.
-    AhatInstance registry = null;
-    for (FieldValue field : mFieldValues) {
-      Value fieldValue = field.getValue();
-      if (fieldValue.isAhatInstance()) {
-        AhatClassInstance fieldInst = fieldValue.asAhatInstance().asClassInstance();
-        if (fieldInst != null
-            && fieldInst.isInstanceOfClass("libcore.util.NativeAllocationRegistry")) {
-          registry = fieldInst;
-          break;
-        }
-      }
-    }
-
-    if (registry == null || !registry.isClassInstance()) {
-      return null;
-    }
-
-    Long size = registry.asClassInstance().getLongField("size", null);
-    if (size == null) {
-      return null;
-    }
-
-    AhatInstance referent = null;
-    for (AhatInstance ref : getHardReverseReferences()) {
-      if (ref.isClassInstance() && ref.asClassInstance().isInstanceOfClass("sun.misc.Cleaner")) {
-        referent = ref.getReferent();
-        if (referent != null) {
-          break;
-        }
-      }
-    }
-
-    if (referent == null) {
-      return null;
-    }
-    return new NativeAllocation(size, getHeap(), pointer, referent);
-  }
-
   @Override public String getDexCacheLocation(int maxChars) {
     if (isInstanceOfClass("java.lang.DexCache")) {
       AhatInstance location = getRefField("location");
diff --git a/tools/ahat/src/heapdump/AhatClassObj.java b/tools/ahat/src/heapdump/AhatClassObj.java
index 828bbfc555..c5ade1d405 100644
--- a/tools/ahat/src/heapdump/AhatClassObj.java
+++ b/tools/ahat/src/heapdump/AhatClassObj.java
@@ -107,5 +107,9 @@ public class AhatClassObj extends AhatInstance {
   @Override public String toString() {
     return mClassName;
   }
+
+  @Override AhatInstance newPlaceHolderInstance() {
+    return new AhatPlaceHolderClassObj(this);
+  }
 }
 
diff --git a/tools/ahat/src/heapdump/AhatHeap.java b/tools/ahat/src/heapdump/AhatHeap.java
index 0bc2a02ee5..c39adc4b41 100644
--- a/tools/ahat/src/heapdump/AhatHeap.java
+++ b/tools/ahat/src/heapdump/AhatHeap.java
@@ -16,14 +16,35 @@
 
 package com.android.ahat.heapdump;
 
-public class AhatHeap {
+public class AhatHeap implements Diffable<AhatHeap> {
   private String mName;
   private long mSize = 0;
   private int mIndex;
+  private AhatHeap mBaseline;
+  private boolean mIsPlaceHolder = false;
 
   AhatHeap(String name, int index) {
     mName = name;
     mIndex = index;
+    mBaseline = this;
+  }
+
+  /**
+   * Construct a place holder heap.
+   */
+  private AhatHeap(String name, AhatHeap baseline) {
+    mName = name;
+    mIndex = -1;
+    mBaseline = baseline;
+    baseline.setBaseline(this);
+    mIsPlaceHolder = true;
+  }
+
+  /**
+   * Construct a new place holder heap that has the given baseline heap.
+   */
+  static AhatHeap newPlaceHolderHeap(String name, AhatHeap baseline) {
+    return new AhatHeap(name, baseline);
   }
 
   void addToSize(long increment) {
@@ -32,7 +53,7 @@ public class AhatHeap {
 
   /**
    * Returns a unique instance for this heap between 0 and the total number of
-   * heaps in this snapshot.
+   * heaps in this snapshot, or -1 if this is a placeholder heap.
    */
   int getIndex() {
     return mIndex;
@@ -51,4 +72,18 @@ public class AhatHeap {
   public long getSize() {
     return mSize;
   }
+
+  void setBaseline(AhatHeap baseline) {
+    mBaseline = baseline;
+  }
+
+  @Override
+  public AhatHeap getBaseline() {
+    return mBaseline;
+  }
+
+  @Override
+  public boolean isPlaceHolder() {
+    return mIsPlaceHolder;
+  }
 }
diff --git a/tools/ahat/src/heapdump/AhatInstance.java b/tools/ahat/src/heapdump/AhatInstance.java
index d1730d11fa..24956f2712 100644
--- a/tools/ahat/src/heapdump/AhatInstance.java
+++ b/tools/ahat/src/heapdump/AhatInstance.java
@@ -26,7 +26,7 @@ import java.util.Collection;
 import java.util.Collections;
 import java.util.List;
 
-public abstract class AhatInstance {
+public abstract class AhatInstance implements Diffable<AhatInstance> {
   private long mId;
   private long mSize;
   private long mTotalRetainedSize;
@@ -47,8 +47,11 @@ public abstract class AhatInstance {
   // List of instances this instance immediately dominates.
   private List<AhatInstance> mDominated = new ArrayList<AhatInstance>();
 
+  private AhatInstance mBaseline;
+
   public AhatInstance(long id) {
     mId = id;
+    mBaseline = this;
   }
 
   /**
@@ -62,8 +65,8 @@ public abstract class AhatInstance {
     mSize = inst.getSize();
     mTotalRetainedSize = inst.getTotalRetainedSize();
 
-    AhatHeap[] heaps = snapshot.getHeaps();
-    mRetainedSizes = new long[heaps.length];
+    List<AhatHeap> heaps = snapshot.getHeaps();
+    mRetainedSizes = new long[heaps.size()];
     for (AhatHeap heap : heaps) {
       mRetainedSizes[heap.getIndex()] = inst.getRetainedSize(heap.getIndex());
     }
@@ -134,7 +137,8 @@ public abstract class AhatInstance {
    * retains.
    */
   public long getRetainedSize(AhatHeap heap) {
-    return mRetainedSizes[heap.getIndex()];
+    int index = heap.getIndex();
+    return 0 <= index && index < mRetainedSizes.length ? mRetainedSizes[heap.getIndex()] : 0;
   }
 
   /**
@@ -258,16 +262,6 @@ public abstract class AhatInstance {
   }
 
   /**
-   * Assuming this instance represents a NativeAllocation, return information
-   * about the native allocation. Returns null if the given instance does not
-   * represent a native allocation.
-   */
-  public NativeAllocation getNativeAllocation() {
-    // Overridden by AhatClassInstance.
-    return null;
-  }
-
-  /**
    * Returns true if the given instance is a class instance
    */
   public boolean isClassInstance() {
@@ -430,4 +424,23 @@ public abstract class AhatInstance {
   byte[] asByteArray() {
     return null;
   }
+
+  public void setBaseline(AhatInstance baseline) {
+    mBaseline = baseline;
+  }
+
+  @Override public AhatInstance getBaseline() {
+    return mBaseline;
+  }
+
+  @Override public boolean isPlaceHolder() {
+    return false;
+  }
+
+  /**
+   * Returns a new place holder instance corresponding to this instance.
+   */
+  AhatInstance newPlaceHolderInstance() {
+    return new AhatPlaceHolderInstance(this);
+  }
 }
diff --git a/tools/ahat/src/heapdump/AhatPlaceHolderClassObj.java b/tools/ahat/src/heapdump/AhatPlaceHolderClassObj.java
new file mode 100644
index 0000000000..c6ad87fda5
--- /dev/null
+++ b/tools/ahat/src/heapdump/AhatPlaceHolderClassObj.java
@@ -0,0 +1,71 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.ahat.heapdump;
+
+/**
+ * PlaceHolder instance to take the place of a real AhatClassObj for
+ * the purposes of displaying diffs.
+ *
+ * This should be created through a call to newPlaceHolder();
+ */
+public class AhatPlaceHolderClassObj extends AhatClassObj {
+  AhatPlaceHolderClassObj(AhatClassObj baseline) {
+    super(-1);
+    setBaseline(baseline);
+    baseline.setBaseline(this);
+  }
+
+  @Override public long getSize() {
+    return 0;
+  }
+
+  @Override public long getRetainedSize(AhatHeap heap) {
+    return 0;
+  }
+
+  @Override public long getTotalRetainedSize() {
+    return 0;
+  }
+
+  @Override public AhatHeap getHeap() {
+    return getBaseline().getHeap().getBaseline();
+  }
+
+  @Override public String getClassName() {
+    return getBaseline().getClassName();
+  }
+
+  @Override public String toString() {
+    return getBaseline().toString();
+  }
+
+  @Override public boolean isPlaceHolder() {
+    return true;
+  }
+
+  @Override public String getName() {
+    return getBaseline().asClassObj().getName();
+  }
+
+  @Override public AhatClassObj getSuperClassObj() {
+    return getBaseline().asClassObj().getSuperClassObj().getBaseline().asClassObj();
+  }
+
+  @Override public AhatInstance getClassLoader() {
+    return getBaseline().asClassObj().getClassLoader().getBaseline();
+  }
+}
diff --git a/tools/ahat/src/heapdump/AhatPlaceHolderInstance.java b/tools/ahat/src/heapdump/AhatPlaceHolderInstance.java
new file mode 100644
index 0000000000..9412eae9a1
--- /dev/null
+++ b/tools/ahat/src/heapdump/AhatPlaceHolderInstance.java
@@ -0,0 +1,63 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.ahat.heapdump;
+
+/**
+ * Generic PlaceHolder instance to take the place of a real AhatInstance for
+ * the purposes of displaying diffs.
+ *
+ * This should be created through a call to AhatInstance.newPlaceHolder();
+ */
+public class AhatPlaceHolderInstance extends AhatInstance {
+  AhatPlaceHolderInstance(AhatInstance baseline) {
+    super(-1);
+    setBaseline(baseline);
+    baseline.setBaseline(this);
+  }
+
+  @Override public long getSize() {
+    return 0;
+  }
+
+  @Override public long getRetainedSize(AhatHeap heap) {
+    return 0;
+  }
+
+  @Override public long getTotalRetainedSize() {
+    return 0;
+  }
+
+  @Override public AhatHeap getHeap() {
+    return getBaseline().getHeap().getBaseline();
+  }
+
+  @Override public String getClassName() {
+    return getBaseline().getClassName();
+  }
+
+  @Override public String asString(int maxChars) {
+    return getBaseline().asString(maxChars);
+  }
+
+  @Override public String toString() {
+    return getBaseline().toString();
+  }
+
+  @Override public boolean isPlaceHolder() {
+    return true;
+  }
+}
diff --git a/tools/ahat/src/heapdump/AhatSnapshot.java b/tools/ahat/src/heapdump/AhatSnapshot.java
index 400f093464..6b4953e77e 100644
--- a/tools/ahat/src/heapdump/AhatSnapshot.java
+++ b/tools/ahat/src/heapdump/AhatSnapshot.java
@@ -38,7 +38,7 @@ import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 
-public class AhatSnapshot {
+public class AhatSnapshot implements Diffable<AhatSnapshot> {
   private final Site mRootSite = new Site("ROOT");
 
   // Collection of objects whose immediate dominator is the SENTINEL_ROOT.
@@ -50,9 +50,9 @@ public class AhatSnapshot {
   // Map from class name to class object.
   private final Map<String, AhatClassObj> mClasses = new HashMap<String, AhatClassObj>();
 
-  private final AhatHeap[] mHeaps;
+  private final List<AhatHeap> mHeaps = new ArrayList<AhatHeap>();
 
-  private final List<NativeAllocation> mNativeAllocations = new ArrayList<NativeAllocation>();
+  private AhatSnapshot mBaseline = this;
 
   /**
    * Create an AhatSnapshot from an hprof file.
@@ -98,10 +98,11 @@ public class AhatSnapshot {
 
     // Create mappings from id to ahat instance and heaps.
     Collection<Heap> heaps = snapshot.getHeaps();
-    mHeaps = new AhatHeap[heaps.size()];
     for (Heap heap : heaps) {
-      int heapIndex = snapshot.getHeapIndex(heap);
-      mHeaps[heapIndex] = new AhatHeap(heap.getName(), snapshot.getHeapIndex(heap));
+      // Note: mHeaps will not be in index order if snapshot.getHeaps does not
+      // return heaps in index order. That's fine, because we don't rely on
+      // mHeaps being in index order.
+      mHeaps.add(new AhatHeap(heap.getName(), snapshot.getHeapIndex(heap)));
       TObjectProcedure<Instance> doCreate = new TObjectProcedure<Instance>() {
         @Override
         public boolean execute(Instance inst) {
@@ -165,14 +166,6 @@ public class AhatSnapshot {
       }
     }
     snapshot.dispose();
-
-    // Update the native allocations.
-    for (AhatInstance ahat : mInstances) {
-      NativeAllocation alloc = ahat.getNativeAllocation();
-      if (alloc != null) {
-        mNativeAllocations.add(alloc);
-      }
-    }
   }
 
   /**
@@ -233,8 +226,10 @@ public class AhatSnapshot {
 
   /**
    * Returns a list of heaps in the snapshot in canonical order.
+   * Modifications to the returned list are visible to this AhatSnapshot,
+   * which is used by diff to insert place holder heaps.
    */
-  public AhatHeap[] getHeaps() {
+  public List<AhatHeap> getHeaps() {
     return mHeaps;
   }
 
@@ -247,10 +242,10 @@ public class AhatSnapshot {
   }
 
   /**
-   * Returns a list of native allocations identified in the heap dump.
+   * Returns the root site for this snapshot.
    */
-  public List<NativeAllocation> getNativeAllocations() {
-    return mNativeAllocations;
+  public Site getRootSite() {
+    return mRootSite;
   }
 
   // Get the site associated with the given id and depth.
@@ -275,4 +270,24 @@ public class AhatSnapshot {
     }
     return value == null ? null : new Value(value);
   }
+
+  public void setBaseline(AhatSnapshot baseline) {
+    mBaseline = baseline;
+  }
+
+  /**
+   * Returns true if this snapshot has been diffed against another, different
+   * snapshot.
+   */
+  public boolean isDiffed() {
+    return mBaseline != this;
+  }
+
+  @Override public AhatSnapshot getBaseline() {
+    return mBaseline;
+  }
+
+  @Override public boolean isPlaceHolder() {
+    return false;
+  }
 }
diff --git a/tools/ahat/src/heapdump/Diff.java b/tools/ahat/src/heapdump/Diff.java
new file mode 100644
index 0000000000..943e6e63f5
--- /dev/null
+++ b/tools/ahat/src/heapdump/Diff.java
@@ -0,0 +1,383 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.ahat.heapdump;
+
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Deque;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+
+public class Diff {
+  /**
+   * Perform a diff between two heap lists.
+   *
+   * Heaps are diffed based on heap name. PlaceHolder heaps will be added to
+   * the given lists as necessary so that every heap in A has a corresponding
+   * heap in B and vice-versa.
+   */
+  private static void heaps(List<AhatHeap> a, List<AhatHeap> b) {
+    int asize = a.size();
+    int bsize = b.size();
+    for (int i = 0; i < bsize; i++) {
+      // Set the B heap's baseline as null to mark that we have not yet
+      // matched it with an A heap.
+      b.get(i).setBaseline(null);
+    }
+
+    for (int i = 0; i < asize; i++) {
+      AhatHeap aheap = a.get(i);
+      aheap.setBaseline(null);
+      for (int j = 0; j < bsize; j++) {
+        AhatHeap bheap = b.get(j);
+        if (bheap.getBaseline() == null && aheap.getName().equals(bheap.getName())) {
+          // We found a match between aheap and bheap.
+          aheap.setBaseline(bheap);
+          bheap.setBaseline(aheap);
+          break;
+        }
+      }
+
+      if (aheap.getBaseline() == null) {
+        // We did not find any match for aheap in snapshot B.
+        // Create a placeholder heap in snapshot B to use as the baseline.
+        b.add(AhatHeap.newPlaceHolderHeap(aheap.getName(), aheap));
+      }
+    }
+
+    // Make placeholder heaps in snapshot A for any unmatched heaps in
+    // snapshot B.
+    for (int i = 0; i < bsize; i++) {
+      AhatHeap bheap = b.get(i);
+      if (bheap.getBaseline() == null) {
+        a.add(AhatHeap.newPlaceHolderHeap(bheap.getName(), bheap));
+      }
+    }
+  }
+
+  /**
+   * Key represents an equivalence class of AhatInstances that are allowed to
+   * be considered for correspondence between two different snapshots.
+   */
+  private static class Key {
+    // Corresponding objects must belong to classes of the same name.
+    private final String mClass;
+
+    // Corresponding objects must belong to heaps of the same name.
+    private final String mHeapName;
+
+    // Corresponding string objects must have the same value.
+    // mStringValue is set to the empty string for non-string objects.
+    private final String mStringValue;
+
+    // Corresponding class objects must have the same class name.
+    // mClassName is set to the empty string for non-class objects.
+    private final String mClassName;
+
+    // Corresponding array objects must have the same length.
+    // mArrayLength is set to 0 for non-array objects.
+    private final int mArrayLength;
+
+
+    private Key(AhatInstance inst) {
+      mClass = inst.getClassName();
+      mHeapName = inst.getHeap().getName();
+      mClassName = inst.isClassObj() ? inst.asClassObj().getName() : "";
+      String string = inst.asString();
+      mStringValue = string == null ? "" : string;
+      AhatArrayInstance array = inst.asArrayInstance();
+      mArrayLength = array == null ? 0 : array.getLength();
+    }
+
+    /**
+     * Return the key for the given instance.
+     */
+    public static Key keyFor(AhatInstance inst) {
+      return new Key(inst);
+    }
+
+    @Override
+    public boolean equals(Object other) {
+      if (!(other instanceof Key)) {
+        return false;
+      }
+      Key o = (Key)other;
+      return mClass.equals(o.mClass)
+          && mHeapName.equals(o.mHeapName)
+          && mStringValue.equals(o.mStringValue)
+          && mClassName.equals(o.mClassName)
+          && mArrayLength == o.mArrayLength;
+    }
+
+    @Override
+    public int hashCode() {
+      return Objects.hash(mClass, mHeapName, mStringValue, mClassName, mArrayLength);
+    }
+  }
+
+  private static class InstanceListPair {
+    public final List<AhatInstance> a;
+    public final List<AhatInstance> b;
+
+    public InstanceListPair() {
+      this.a = new ArrayList<AhatInstance>();
+      this.b = new ArrayList<AhatInstance>();
+    }
+
+    public InstanceListPair(List<AhatInstance> a, List<AhatInstance> b) {
+      this.a = a;
+      this.b = b;
+    }
+  }
+
+  /**
+   * Recursively create place holder instances for the given instance and
+   * every instance dominated by that instance.
+   * Returns the place holder instance created for the given instance.
+   * Adds all allocated placeholders to the given placeholders list.
+   */
+  private static AhatInstance createPlaceHolders(AhatInstance inst,
+      List<AhatInstance> placeholders) {
+    // Don't actually use recursion, because we could easily smash the stack.
+    // Instead we iterate.
+    AhatInstance result = inst.newPlaceHolderInstance();
+    placeholders.add(result);
+    Deque<AhatInstance> deque = new ArrayDeque<AhatInstance>();
+    deque.push(inst);
+    while (!deque.isEmpty()) {
+      inst = deque.pop();
+
+      for (AhatInstance child : inst.getDominated()) {
+        placeholders.add(child.newPlaceHolderInstance());
+        deque.push(child);
+      }
+    }
+    return result;
+  }
+
+  /**
+   * Recursively diff two dominator trees of instances.
+   * PlaceHolder objects are appended to the lists as needed to ensure every
+   * object has a corresponding baseline in the other list. All PlaceHolder
+   * objects are also appended to the given placeholders list, so their Site
+   * info can be updated later on.
+   */
+  private static void instances(List<AhatInstance> a, List<AhatInstance> b,
+      List<AhatInstance> placeholders) {
+    // Don't actually use recursion, because we could easily smash the stack.
+    // Instead we iterate.
+    Deque<InstanceListPair> deque = new ArrayDeque<InstanceListPair>();
+    deque.push(new InstanceListPair(a, b));
+    while (!deque.isEmpty()) {
+      InstanceListPair p = deque.pop();
+
+      // Group instances of the same equivalence class together.
+      Map<Key, InstanceListPair> byKey = new HashMap<Key, InstanceListPair>();
+      for (AhatInstance inst : p.a) {
+        Key key = Key.keyFor(inst);
+        InstanceListPair pair = byKey.get(key);
+        if (pair == null) {
+          pair = new InstanceListPair();
+          byKey.put(key, pair);
+        }
+        pair.a.add(inst);
+      }
+      for (AhatInstance inst : p.b) {
+        Key key = Key.keyFor(inst);
+        InstanceListPair pair = byKey.get(key);
+        if (pair == null) {
+          pair = new InstanceListPair();
+          byKey.put(key, pair);
+        }
+        pair.b.add(inst);
+      }
+
+      // diff objects from the same key class.
+      for (InstanceListPair pair : byKey.values()) {
+        // Sort by retained size and assume the elements at the top of the lists
+        // correspond to each other in that order. This could probably be
+        // improved if desired, but it gives good enough results for now.
+        Collections.sort(pair.a, Sort.INSTANCE_BY_TOTAL_RETAINED_SIZE);
+        Collections.sort(pair.b, Sort.INSTANCE_BY_TOTAL_RETAINED_SIZE);
+
+        int common = Math.min(pair.a.size(), pair.b.size());
+        for (int i = 0; i < common; i++) {
+          AhatInstance ainst = pair.a.get(i);
+          AhatInstance binst = pair.b.get(i);
+          ainst.setBaseline(binst);
+          binst.setBaseline(ainst);
+          deque.push(new InstanceListPair(ainst.getDominated(), binst.getDominated()));
+        }
+
+        // Add placeholder objects for anything leftover.
+        for (int i = common; i < pair.a.size(); i++) {
+          p.b.add(createPlaceHolders(pair.a.get(i), placeholders));
+        }
+
+        for (int i = common; i < pair.b.size(); i++) {
+          p.a.add(createPlaceHolders(pair.b.get(i), placeholders));
+        }
+      }
+    }
+  }
+
+  /**
+   * Sets the baseline for root and all its descendants to baseline.
+   */
+  private static void setSitesBaseline(Site root, Site baseline) {
+    root.setBaseline(baseline);
+    for (Site child : root.getChildren()) {
+      setSitesBaseline(child, baseline);
+    }
+  }
+
+  /**
+   * Recursively diff the two sites, setting them and their descendants as
+   * baselines for each other as appropriate.
+   *
+   * This requires that instances have already been diffed. In particular, we
+   * require all AhatClassObjs in one snapshot have corresponding (possibly
+   * place-holder) AhatClassObjs in the other snapshot.
+   */
+  private static void sites(Site a, Site b) {
+    // Set the sites as baselines of each other.
+    a.setBaseline(b);
+    b.setBaseline(a);
+
+    // Set the site's ObjectsInfos as baselines of each other. This implicitly
+    // adds new empty ObjectsInfo as needed.
+    for (Site.ObjectsInfo ainfo : a.getObjectsInfos()) {
+      AhatClassObj baseClassObj = null;
+      if (ainfo.classObj != null) {
+        baseClassObj = (AhatClassObj) ainfo.classObj.getBaseline();
+      }
+      ainfo.setBaseline(b.getObjectsInfo(ainfo.heap.getBaseline(), baseClassObj));
+    }
+    for (Site.ObjectsInfo binfo : b.getObjectsInfos()) {
+      AhatClassObj baseClassObj = null;
+      if (binfo.classObj != null) {
+        baseClassObj = (AhatClassObj) binfo.classObj.getBaseline();
+      }
+      binfo.setBaseline(a.getObjectsInfo(binfo.heap.getBaseline(), baseClassObj));
+    }
+
+    // Set B children's baselines as null to mark that we have not yet matched
+    // them with A children.
+    for (Site bchild : b.getChildren()) {
+      bchild.setBaseline(null);
+    }
+
+    for (Site achild : a.getChildren()) {
+      achild.setBaseline(null);
+      for (Site bchild : b.getChildren()) {
+        if (achild.getLineNumber() == bchild.getLineNumber()
+            && achild.getMethodName().equals(bchild.getMethodName())
+            && achild.getSignature().equals(bchild.getSignature())
+            && achild.getFilename().equals(bchild.getFilename())) {
+          // We found a match between achild and bchild.
+          sites(achild, bchild);
+          break;
+        }
+      }
+
+      if (achild.getBaseline() == null) {
+        // We did not find any match for achild in site B.
+        // Use B for the baseline of achild and its descendants.
+        setSitesBaseline(achild, b);
+      }
+    }
+
+    for (Site bchild : b.getChildren()) {
+      if (bchild.getBaseline() == null) {
+        setSitesBaseline(bchild, a);
+      }
+    }
+  }
+
+  /**
+   * Perform a diff of the two snapshots, setting each as the baseline for the
+   * other.
+   */
+  public static void snapshots(AhatSnapshot a, AhatSnapshot b) {
+    a.setBaseline(b);
+    b.setBaseline(a);
+
+    // Diff the heaps of each snapshot.
+    heaps(a.getHeaps(), b.getHeaps());
+
+    // Diff the instances of each snapshot.
+    List<AhatInstance> placeholders = new ArrayList<AhatInstance>();
+    instances(a.getRooted(), b.getRooted(), placeholders);
+
+    // Diff the sites of each snapshot.
+    // This requires the instances have already been diffed.
+    sites(a.getRootSite(), b.getRootSite());
+
+    // Add placeholders to their corresponding sites.
+    // This requires the sites have already been diffed.
+    for (AhatInstance placeholder : placeholders) {
+      placeholder.getBaseline().getSite().getBaseline().addPlaceHolderInstance(placeholder);
+    }
+  }
+
+  /**
+   * Diff two lists of field values.
+   * PlaceHolder objects are added to the given lists as needed to ensure
+   * every FieldValue in A ends up with a corresponding FieldValue in B.
+   */
+  public static void fields(List<FieldValue> a, List<FieldValue> b) {
+    // Fields with the same name and type are considered matching fields.
+    // For simplicity, we assume the matching fields are in the same order in
+    // both A and B, though some fields may be added or removed in either
+    // list. If our assumption is wrong, in the worst case the quality of the
+    // field diff is poor.
+
+    for (int i = 0; i < a.size(); i++) {
+      FieldValue afield = a.get(i);
+      afield.setBaseline(null);
+
+      // Find the matching field in B, if any.
+      for (int j = i; j < b.size(); j++) {
+        FieldValue bfield = b.get(j);
+        if (afield.getName().equals(bfield.getName())
+            && afield.getType().equals(bfield.getType())) {
+          // We found the matching field in B.
+          // Assume fields i, ..., j-1 in B have no match in A.
+          for ( ; i < j; i++) {
+            a.add(i, FieldValue.newPlaceHolderFieldValue(b.get(i)));
+          }
+
+          afield.setBaseline(bfield);
+          bfield.setBaseline(afield);
+          break;
+        }
+      }
+
+      if (afield.getBaseline() == null) {
+        b.add(i, FieldValue.newPlaceHolderFieldValue(afield));
+      }
+    }
+
+    // All remaining fields in B are unmatched by any in A.
+    for (int i = a.size(); i < b.size(); i++) {
+      a.add(i, FieldValue.newPlaceHolderFieldValue(b.get(i)));
+    }
+  }
+}
diff --git a/tools/ahat/src/heapdump/NativeAllocation.java b/tools/ahat/src/heapdump/Diffable.java
index 5188f44d03..53442c857e 100644
--- a/tools/ahat/src/heapdump/NativeAllocation.java
+++ b/tools/ahat/src/heapdump/Diffable.java
@@ -16,16 +16,23 @@
 
 package com.android.ahat.heapdump;
 
-public class NativeAllocation {
-  public long size;
-  public AhatHeap heap;
-  public long pointer;
-  public AhatInstance referent;
+/**
+ * An interface for objects that have corresponding objects in a baseline heap
+ * dump.
+ */
+public interface Diffable<T> {
+  /**
+   * Return the baseline object that corresponds to this one.
+   */
+  T getBaseline();
 
-  public NativeAllocation(long size, AhatHeap heap, long pointer, AhatInstance referent) {
-    this.size = size;
-    this.heap = heap;
-    this.pointer = pointer;
-    this.referent = referent;
-  }
+  /**
+   * Returns true if this is a placeholder object.
+   * A placeholder object is used to indicate there is some object in the
+   * baseline heap dump that is not in this heap dump. In that case, we create
+   * a dummy place holder object in this heap dump as an indicator of the
+   * object removed from the baseline heap dump.
+   */
+  boolean isPlaceHolder();
 }
+
diff --git a/tools/ahat/src/heapdump/FieldValue.java b/tools/ahat/src/heapdump/FieldValue.java
index dd9cb07174..3f65cd3030 100644
--- a/tools/ahat/src/heapdump/FieldValue.java
+++ b/tools/ahat/src/heapdump/FieldValue.java
@@ -16,15 +16,36 @@
 
 package com.android.ahat.heapdump;
 
-public class FieldValue {
+public class FieldValue implements Diffable<FieldValue> {
   private final String mName;
   private final String mType;
   private final Value mValue;
+  private FieldValue mBaseline;
+  private final boolean mIsPlaceHolder;
 
   public FieldValue(String name, String type, Value value) {
     mName = name;
     mType = type;
     mValue = value;
+    mBaseline = this;
+    mIsPlaceHolder = false;
+  }
+
+  /**
+   * Construct a place holder FieldValue
+   */
+  private FieldValue(FieldValue baseline) {
+    mName = baseline.mName;
+    mType = baseline.mType;
+    mValue = Value.getBaseline(baseline.mValue);
+    mBaseline = baseline;
+    mIsPlaceHolder = true;
+  }
+
+  static FieldValue newPlaceHolderFieldValue(FieldValue baseline) {
+    FieldValue field = new FieldValue(baseline);
+    baseline.setBaseline(field);
+    return field;
   }
 
   /**
@@ -47,4 +68,16 @@ public class FieldValue {
   public Value getValue() {
     return mValue;
   }
+
+  public void setBaseline(FieldValue baseline) {
+    mBaseline = baseline;
+  }
+
+  @Override public FieldValue getBaseline() {
+    return mBaseline;
+  }
+
+  @Override public boolean isPlaceHolder() {
+    return mIsPlaceHolder;
+  }
 }
diff --git a/tools/ahat/src/heapdump/PathElement.java b/tools/ahat/src/heapdump/PathElement.java
index bbae59e0e0..196a24628c 100644
--- a/tools/ahat/src/heapdump/PathElement.java
+++ b/tools/ahat/src/heapdump/PathElement.java
@@ -16,7 +16,7 @@
 
 package com.android.ahat.heapdump;
 
-public class PathElement {
+public class PathElement implements Diffable<PathElement> {
   public final AhatInstance instance;
   public final String field;
   public boolean isDominator;
@@ -26,4 +26,12 @@ public class PathElement {
     this.field = field;
     this.isDominator = false;
   }
+
+  @Override public PathElement getBaseline() {
+    return this;
+  }
+
+  @Override public boolean isPlaceHolder() {
+    return false;
+  }
 }
diff --git a/tools/ahat/src/heapdump/Site.java b/tools/ahat/src/heapdump/Site.java
index 97cbf18dd9..a551901a6d 100644
--- a/tools/ahat/src/heapdump/Site.java
+++ b/tools/ahat/src/heapdump/Site.java
@@ -23,7 +23,7 @@ import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
 
-public class Site {
+public class Site implements Diffable<Site> {
   // The site that this site was directly called from.
   // mParent is null for the root site.
   private Site mParent;
@@ -54,17 +54,21 @@ public class Site {
   private List<ObjectsInfo> mObjectsInfos;
   private Map<AhatHeap, Map<AhatClassObj, ObjectsInfo>> mObjectsInfoMap;
 
-  public static class ObjectsInfo {
+  private Site mBaseline;
+
+  public static class ObjectsInfo implements Diffable<ObjectsInfo> {
     public AhatHeap heap;
-    public AhatClassObj classObj;
+    public AhatClassObj classObj;   // May be null.
     public long numInstances;
     public long numBytes;
+    private ObjectsInfo baseline;
 
     public ObjectsInfo(AhatHeap heap, AhatClassObj classObj, long numInstances, long numBytes) {
       this.heap = heap;
       this.classObj = classObj;
       this.numInstances = numInstances;
       this.numBytes = numBytes;
+      this.baseline = this;
     }
 
     /**
@@ -73,6 +77,18 @@ public class Site {
     public String getClassName() {
       return classObj == null ? "???" : classObj.getName();
     }
+
+    public void setBaseline(ObjectsInfo baseline) {
+      this.baseline = baseline;
+    }
+
+    @Override public ObjectsInfo getBaseline() {
+      return baseline;
+    }
+
+    @Override public boolean isPlaceHolder() {
+      return false;
+    }
   }
 
   /**
@@ -96,6 +112,7 @@ public class Site {
     mObjects = new ArrayList<AhatInstance>();
     mObjectsInfos = new ArrayList<ObjectsInfo>();
     mObjectsInfoMap = new HashMap<AhatHeap, Map<AhatClassObj, ObjectsInfo>>();
+    mBaseline = this;
   }
 
   /**
@@ -122,19 +139,7 @@ public class Site {
       }
       site.mSizesByHeap[heap.getIndex()] += inst.getSize();
 
-      Map<AhatClassObj, ObjectsInfo> classToObjectsInfo = site.mObjectsInfoMap.get(inst.getHeap());
-      if (classToObjectsInfo == null) {
-        classToObjectsInfo = new HashMap<AhatClassObj, ObjectsInfo>();
-        site.mObjectsInfoMap.put(inst.getHeap(), classToObjectsInfo);
-      }
-
-      ObjectsInfo info = classToObjectsInfo.get(inst.getClassObj());
-      if (info == null) {
-        info = new ObjectsInfo(inst.getHeap(), inst.getClassObj(), 0, 0);
-        site.mObjectsInfos.add(info);
-        classToObjectsInfo.put(inst.getClassObj(), info);
-      }
-
+      ObjectsInfo info = site.getObjectsInfo(inst.getHeap(), inst.getClassObj());
       info.numInstances++;
       info.numBytes += inst.getSize();
 
@@ -167,7 +172,7 @@ public class Site {
   // Get the size of a site for a specific heap.
   public long getSize(AhatHeap heap) {
     int index = heap.getIndex();
-    return index < mSizesByHeap.length ? mSizesByHeap[index] : 0;
+    return index >= 0 && index < mSizesByHeap.length ? mSizesByHeap[index] : 0;
   }
 
   /**
@@ -178,6 +183,26 @@ public class Site {
     return mObjects;
   }
 
+  /**
+   * Returns the ObjectsInfo at this site for the given heap and class
+   * objects. Creates a new empty ObjectsInfo if none existed before.
+   */
+  ObjectsInfo getObjectsInfo(AhatHeap heap, AhatClassObj classObj) {
+    Map<AhatClassObj, ObjectsInfo> classToObjectsInfo = mObjectsInfoMap.get(heap);
+    if (classToObjectsInfo == null) {
+      classToObjectsInfo = new HashMap<AhatClassObj, ObjectsInfo>();
+      mObjectsInfoMap.put(heap, classToObjectsInfo);
+    }
+
+    ObjectsInfo info = classToObjectsInfo.get(classObj);
+    if (info == null) {
+      info = new ObjectsInfo(heap, classObj, 0, 0);
+      mObjectsInfos.add(info);
+      classToObjectsInfo.put(classObj, info);
+    }
+    return info;
+  }
+
   public List<ObjectsInfo> getObjectsInfos() {
     return mObjectsInfos;
   }
@@ -233,4 +258,25 @@ public class Site {
   public List<Site> getChildren() {
     return mChildren;
   }
+
+  void setBaseline(Site baseline) {
+    mBaseline = baseline;
+  }
+
+  @Override public Site getBaseline() {
+    return mBaseline;
+  }
+
+  @Override public boolean isPlaceHolder() {
+    return false;
+  }
+
+  /**
+   * Adds a place holder instance to this site and all parent sites.
+   */
+  void addPlaceHolderInstance(AhatInstance placeholder) {
+    for (Site site = this; site != null; site = site.mParent) {
+      site.mObjects.add(placeholder);
+    }
+  }
 }
diff --git a/tools/ahat/src/Sort.java b/tools/ahat/src/heapdump/Sort.java
index 6b93fbc702..93d147a49e 100644
--- a/tools/ahat/src/Sort.java
+++ b/tools/ahat/src/heapdump/Sort.java
@@ -14,13 +14,8 @@
  * limitations under the License.
  */
 
-package com.android.ahat;
+package com.android.ahat.heapdump;
 
-import com.android.ahat.heapdump.AhatHeap;
-import com.android.ahat.heapdump.AhatInstance;
-import com.android.ahat.heapdump.AhatSnapshot;
-import com.android.ahat.heapdump.NativeAllocation;
-import com.android.ahat.heapdump.Site;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Comparator;
@@ -35,30 +30,20 @@ import java.util.List;
  * with equals. They should not be used for element lookup or search. They
  * should only be used for showing elements to the user in different orders.
  */
-class Sort {
-  /**
-   * Compare instances by their instance id.
-   * This sorts instances from smaller id to larger id.
-   */
-  public static class InstanceById implements Comparator<AhatInstance> {
-    @Override
-    public int compare(AhatInstance a, AhatInstance b) {
-      return Long.compare(a.getId(), b.getId());
-    }
-  }
-
+public class Sort {
   /**
    * Compare instances by their total retained size.
    * Different instances with the same total retained size are considered
    * equal for the purposes of comparison.
    * This sorts instances from larger retained size to smaller retained size.
    */
-  public static class InstanceByTotalRetainedSize implements Comparator<AhatInstance> {
+  public static final Comparator<AhatInstance> INSTANCE_BY_TOTAL_RETAINED_SIZE
+    = new Comparator<AhatInstance>() {
     @Override
     public int compare(AhatInstance a, AhatInstance b) {
       return Long.compare(b.getTotalRetainedSize(), a.getTotalRetainedSize());
     }
-  }
+  };
 
   /**
    * Compare instances by their retained size for a given heap index.
@@ -115,7 +100,7 @@ class Sort {
     }
 
     // Next is by total retained size.
-    comparators.add(new InstanceByTotalRetainedSize());
+    comparators.add(INSTANCE_BY_TOTAL_RETAINED_SIZE);
     return new WithPriority<AhatInstance>(comparators);
   }
 
@@ -142,12 +127,12 @@ class Sort {
    * Compare Sites by the total size of objects allocated.
    * This sorts sites from larger size to smaller size.
    */
-  public static class SiteByTotalSize implements Comparator<Site> {
+  public static final Comparator<Site> SITE_BY_TOTAL_SIZE = new Comparator<Site>() {
     @Override
     public int compare(Site a, Site b) {
       return Long.compare(b.getTotalSize(), a.getTotalSize());
     }
-  }
+  };
 
   public static Comparator<Site> defaultSiteCompare(AhatSnapshot snapshot) {
     List<Comparator<Site>> comparators = new ArrayList<Comparator<Site>>();
@@ -159,7 +144,7 @@ class Sort {
     }
 
     // Next is by total size.
-    comparators.add(new SiteByTotalSize());
+    comparators.add(SITE_BY_TOTAL_SIZE);
     return new WithPriority<Site>(comparators);
   }
 
@@ -169,63 +154,40 @@ class Sort {
    * equal for the purposes of comparison.
    * This sorts object infos from larger retained size to smaller size.
    */
-  public static class ObjectsInfoBySize implements Comparator<Site.ObjectsInfo> {
+  public static final Comparator<Site.ObjectsInfo> OBJECTS_INFO_BY_SIZE
+    = new Comparator<Site.ObjectsInfo>() {
     @Override
     public int compare(Site.ObjectsInfo a, Site.ObjectsInfo b) {
       return Long.compare(b.numBytes, a.numBytes);
     }
-  }
+  };
 
   /**
    * Compare Site.ObjectsInfo by heap name.
    * Different object infos with the same heap name are considered equal for
    * the purposes of comparison.
    */
-  public static class ObjectsInfoByHeapName implements Comparator<Site.ObjectsInfo> {
+  public static final Comparator<Site.ObjectsInfo> OBJECTS_INFO_BY_HEAP_NAME
+    = new Comparator<Site.ObjectsInfo>() {
     @Override
     public int compare(Site.ObjectsInfo a, Site.ObjectsInfo b) {
       return a.heap.getName().compareTo(b.heap.getName());
     }
-  }
+  };
 
   /**
    * Compare Site.ObjectsInfo by class name.
    * Different object infos with the same class name are considered equal for
    * the purposes of comparison.
    */
-  public static class ObjectsInfoByClassName implements Comparator<Site.ObjectsInfo> {
+  public static final Comparator<Site.ObjectsInfo> OBJECTS_INFO_BY_CLASS_NAME
+    = new Comparator<Site.ObjectsInfo>() {
     @Override
     public int compare(Site.ObjectsInfo a, Site.ObjectsInfo b) {
       String aName = a.getClassName();
       String bName = b.getClassName();
       return aName.compareTo(bName);
     }
-  }
-
-  /**
-   * Compare NativeAllocation by heap name.
-   * Different allocations with the same heap name are considered equal for
-   * the purposes of comparison.
-   */
-  public static class NativeAllocationByHeapName
-      implements Comparator<NativeAllocation> {
-    @Override
-    public int compare(NativeAllocation a, NativeAllocation b) {
-      return a.heap.getName().compareTo(b.heap.getName());
-    }
-  }
-
-  /**
-   * Compare NativeAllocation by their size.
-   * Different allocations with the same size are considered equal for the
-   * purposes of comparison.
-   * This sorts allocations from larger size to smaller size.
-   */
-  public static class NativeAllocationBySize implements Comparator<NativeAllocation> {
-    @Override
-    public int compare(NativeAllocation a, NativeAllocation b) {
-      return Long.compare(b.size, a.size);
-    }
-  }
+  };
 }
 
diff --git a/tools/ahat/src/heapdump/Value.java b/tools/ahat/src/heapdump/Value.java
index e2bdc71738..6b2d38f7b1 100644
--- a/tools/ahat/src/heapdump/Value.java
+++ b/tools/ahat/src/heapdump/Value.java
@@ -115,4 +115,19 @@ public class Value {
   public String toString() {
     return mObject.toString();
   }
+
+  public static Value getBaseline(Value value) {
+    if (value == null || !value.isAhatInstance()) {
+      return value;
+    }
+    return new Value(value.asAhatInstance().getBaseline());
+  }
+
+  @Override public boolean equals(Object other) {
+    if (other instanceof Value) {
+      Value value = (Value)other;
+      return mObject.equals(value.mObject);
+    }
+    return false;
+  }
 }
diff --git a/tools/ahat/src/help.html b/tools/ahat/src/help.html
deleted file mode 100644
index ff04ad2840..0000000000
--- a/tools/ahat/src/help.html
+++ /dev/null
@@ -1,80 +0,0 @@
-<!--
-Copyright (C) 2015 The Android Open Source Project
-
-Licensed under the Apache License, Version 2.0 (the "License");
-you may not use this file except in compliance with the License.
-You may obtain a copy of the License at
-
-     http://www.apache.org/licenses/LICENSE-2.0
-
-Unless required by applicable law or agreed to in writing, software
-distributed under the License is distributed on an "AS IS" BASIS,
-WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-See the License for the specific language governing permissions and
-limitations under the License.
--->
-
-<h1>Help</h1>
-<h2>Information shown by ahat:</h2>
-<ul>
-  <li><a href="/">The total bytes retained by heap.</a></li>
-  <li><a href="/rooted">A list of rooted objects and their retained sizes for each heap.</a></li>
-  <li>Information about each allocated object:
-    <ul>
-      <li>The allocation site (stack trace) of the object (if available).</li>
-      <li>The dominator path from a root to the object.</li>
-      <li>The class, (shallow) size, retained size, and heap of the object.</li>
-      <li>The bitmap image for the object if the object represents a bitmap.</li>
-      <li>The instance fields or array elements of the object.</li>
-      <li>The super class, class loader, and static fields of class objects.</li>
-      <li>Other objects with references to the object.</li>
-      <li>Other objects immediately dominated by the object.</li>
-    </ul>
-  </li>
-  <li>A list of objects, optionally filtered by class, allocation site, and/or
-    heap.</li>
-  <li><a href="site">Information about each allocation site:</a>
-    <ul>
-      <li>The stack trace for the allocation site.</li>
-      <li>The number of bytes allocated at the allocation site.</li>
-      <li>Child sites called from the allocation site.</li>
-      <li>The size and count of objects allocated at the site, organized by
-        heap and object type.</li>
-    </ul>
-  </li>
-</ul>
-
-<h2>Tips:</h2>
-<h3>Heaps</h3>
-<p>
-Android heap dumps contain information for multiple heaps. The <b>app</b> heap
-is the memory used by your application. The <b>zygote</b> and <b>image</b>
-heaps are used by the system. You should ignore everything in the zygote and
-image heap and look only at the app heap. This is because changes in your
-application will not effect the zygote or image heaps, and because the zygote
-and image heaps are shared, they don't contribute significantly to your
-applications PSS.
-</p>
-
-<h3>Bitmaps</h3>
-<p>
-Bitmaps store their data using byte[] arrays. Whenever you see a large
-byte[], check if it is a bitmap by looking to see if there is a single
-android.graphics.Bitmap object referring to it. The byte[] will be marked as a
-root, but it is really being retained by the android.graphics.Bitmap object.
-</p>
-
-<h3>DexCaches</h3>
-<p>
-For each DexFile you load, there will be a corresponding DexCache whose size
-is proportional to the number of strings, fields, methods, and classes in your
-dex file. The DexCache entries may or may not be visible depending on the
-version of the Android platform the heap dump is from.
-</p>
-
-<h3>FinalizerReferences</h3>
-<p>
-A FinalizerReference is allocated for every object on the heap that has a
-non-trivial finalizer. These are stored in a linked list reachable from the
-FinalizerReference class object.
-</p>
diff --git a/tools/ahat/src/manifest.txt b/tools/ahat/src/manifest.txt
index 1993910513..87a82b9f99 100644
--- a/tools/ahat/src/manifest.txt
+++ b/tools/ahat/src/manifest.txt
@@ -1,4 +1,4 @@
 Name: ahat/
 Implementation-Title: ahat
-Implementation-Version: 0.8
+Implementation-Version: 1.0
 Main-Class: com.android.ahat.Main
diff --git a/tools/ahat/src/style.css b/tools/ahat/src/style.css
index ca074a526c..47fae1d551 100644
--- a/tools/ahat/src/style.css
+++ b/tools/ahat/src/style.css
@@ -18,6 +18,14 @@ div.menu {
   background-color: #eeffff;
 }
 
+span.added {
+  color: #770000;
+}
+
+span.removed {
+  color: #007700;
+}
+
 /*
  * Most of the columns show numbers of bytes. Numbers should be right aligned.
  */
diff --git a/tools/ahat/test-dump/Main.java b/tools/ahat/test-dump/Main.java
index e0b3da7494..4a2234cee7 100644
--- a/tools/ahat/test-dump/Main.java
+++ b/tools/ahat/test-dump/Main.java
@@ -19,7 +19,6 @@ import java.io.IOException;
 import java.lang.ref.PhantomReference;
 import java.lang.ref.ReferenceQueue;
 import java.lang.ref.WeakReference;
-import libcore.util.NativeAllocationRegistry;
 import org.apache.harmony.dalvik.ddmc.DdmVmInternal;
 
 /**
@@ -40,6 +39,25 @@ public class Main {
     }
   }
 
+  public static class AddedObject {
+  }
+
+  public static class RemovedObject {
+  }
+
+  public static class UnchangedObject {
+  }
+
+  public static class ModifiedObject {
+    public int value;
+    public String modifiedRefField;
+    public String unmodifiedRefField;
+  }
+
+  public static class StackSmasher {
+    public StackSmasher child;
+  }
+
   // We will take a heap dump that includes a single instance of this
   // DumpedStuff class. Objects stored as fields in this class can be easily
   // found in the hprof dump by searching for the instance of the DumpedStuff
@@ -62,17 +80,44 @@ public class Main {
           new ObjectTree(null, null)),
       null};
     public Object[] basicStringRef;
+    public AddedObject addedObject;
+    public UnchangedObject unchangedObject = new UnchangedObject();
+    public RemovedObject removedObject;
+    public ModifiedObject modifiedObject;
+    public StackSmasher stackSmasher;
+    public StackSmasher stackSmasherAdded;
+    public static String modifiedStaticField;
+    public int[] modifiedArray;
 
-    DumpedStuff() {
-      int N = 1000000;
+    DumpedStuff(boolean baseline) {
+      int N = baseline ? 400000 : 1000000;
       bigArray = new byte[N];
       for (int i = 0; i < N; i++) {
         bigArray[i] = (byte)((i*i) & 0xFF);
       }
 
-      NativeAllocationRegistry registry = new NativeAllocationRegistry(
-          Main.class.getClassLoader(), 0x12345, 42);
-      registry.registerNativeAllocation(anObject, 0xABCDABCD);
+      addedObject = baseline ? null : new AddedObject();
+      removedObject = baseline ? new RemovedObject() : null;
+      modifiedObject = new ModifiedObject();
+      modifiedObject.value = baseline ? 5 : 8;
+      modifiedObject.modifiedRefField = baseline ? "A1" : "A2";
+      modifiedObject.unmodifiedRefField = "B";
+      modifiedStaticField = baseline ? "C1" : "C2";
+      modifiedArray = baseline ? new int[]{0,1,2,3} : new int[]{3,1,2,0};
+
+      // Deep matching dominator trees shouldn't smash the stack when we try
+      // to diff them. Make some deep dominator trees to help test it.
+      for (int i = 0; i < 10000; i++) {
+        StackSmasher smasher = new StackSmasher();
+        smasher.child = stackSmasher;
+        stackSmasher = smasher;
+
+        if (!baseline) {
+          smasher = new StackSmasher();
+          smasher.child = stackSmasherAdded;
+          stackSmasherAdded = smasher;
+        }
+      }
 
       gcPathArray[2].right.left = gcPathArray[2].left.right;
     }
@@ -85,11 +130,15 @@ public class Main {
     }
     String file = args[0];
 
+    // If a --base argument is provided, it means we should generate a
+    // baseline hprof file suitable for using in testing diff.
+    boolean baseline = args.length > 1 && args[1].equals("--base");
+
     // Enable allocation tracking so we get stack traces in the heap dump.
     DdmVmInternal.enableRecentAllocations(true);
 
     // Allocate the instance of DumpedStuff.
-    stuff = new DumpedStuff();
+    stuff = new DumpedStuff(baseline);
 
     // Create a bunch of unreachable objects pointing to basicString for the
     // reverseReferencesAreNotUnreachable test
diff --git a/tools/ahat/test/DiffTest.java b/tools/ahat/test/DiffTest.java
new file mode 100644
index 0000000000..52b6b7b3ae
--- /dev/null
+++ b/tools/ahat/test/DiffTest.java
@@ -0,0 +1,163 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.ahat;
+
+import com.android.ahat.heapdump.AhatHeap;
+import com.android.ahat.heapdump.AhatInstance;
+import com.android.ahat.heapdump.AhatSnapshot;
+import com.android.ahat.heapdump.Diff;
+import com.android.ahat.heapdump.FieldValue;
+import com.android.tools.perflib.heap.hprof.HprofClassDump;
+import com.android.tools.perflib.heap.hprof.HprofConstant;
+import com.android.tools.perflib.heap.hprof.HprofDumpRecord;
+import com.android.tools.perflib.heap.hprof.HprofHeapDump;
+import com.android.tools.perflib.heap.hprof.HprofInstanceDump;
+import com.android.tools.perflib.heap.hprof.HprofInstanceField;
+import com.android.tools.perflib.heap.hprof.HprofLoadClass;
+import com.android.tools.perflib.heap.hprof.HprofPrimitiveArrayDump;
+import com.android.tools.perflib.heap.hprof.HprofRecord;
+import com.android.tools.perflib.heap.hprof.HprofRootDebugger;
+import com.android.tools.perflib.heap.hprof.HprofStaticField;
+import com.android.tools.perflib.heap.hprof.HprofStringBuilder;
+import com.android.tools.perflib.heap.hprof.HprofType;
+import com.google.common.io.ByteArrayDataOutput;
+import com.google.common.io.ByteStreams;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertTrue;
+
+public class DiffTest {
+  @Test
+  public void diffMatchedHeap() throws IOException {
+    TestDump dump = TestDump.getTestDump();
+    AhatHeap a = dump.getAhatSnapshot().getHeap("app");
+    assertNotNull(a);
+    AhatHeap b = dump.getBaselineAhatSnapshot().getHeap("app");
+    assertNotNull(b);
+    assertEquals(a.getBaseline(), b);
+    assertEquals(b.getBaseline(), a);
+  }
+
+  @Test
+  public void diffUnchanged() throws IOException {
+    TestDump dump = TestDump.getTestDump();
+
+    AhatInstance a = dump.getDumpedAhatInstance("unchangedObject");
+    assertNotNull(a);
+
+    AhatInstance b = dump.getBaselineDumpedAhatInstance("unchangedObject");
+    assertNotNull(b);
+    assertEquals(a, b.getBaseline());
+    assertEquals(b, a.getBaseline());
+    assertEquals(a.getSite(), b.getSite().getBaseline());
+    assertEquals(b.getSite(), a.getSite().getBaseline());
+  }
+
+  @Test
+  public void diffAdded() throws IOException {
+    TestDump dump = TestDump.getTestDump();
+
+    AhatInstance a = dump.getDumpedAhatInstance("addedObject");
+    assertNotNull(a);
+    assertNull(dump.getBaselineDumpedAhatInstance("addedObject"));
+    assertTrue(a.getBaseline().isPlaceHolder());
+  }
+
+  @Test
+  public void diffRemoved() throws IOException {
+    TestDump dump = TestDump.getTestDump();
+
+    assertNull(dump.getDumpedAhatInstance("removedObject"));
+    AhatInstance b = dump.getBaselineDumpedAhatInstance("removedObject");
+    assertNotNull(b);
+    assertTrue(b.getBaseline().isPlaceHolder());
+  }
+
+  @Test
+  public void nullClassObj() throws IOException {
+    // Set up a heap dump that has a null classObj.
+    // The heap dump is derived from the InstanceTest.asStringEmbedded test.
+    HprofStringBuilder strings = new HprofStringBuilder(0);
+    List<HprofRecord> records = new ArrayList<HprofRecord>();
+    List<HprofDumpRecord> dump = new ArrayList<HprofDumpRecord>();
+
+    final int stringClassObjectId = 1;
+    records.add(new HprofLoadClass(0, 0, stringClassObjectId, 0, strings.get("java.lang.String")));
+    dump.add(new HprofClassDump(stringClassObjectId, 0, 0, 0, 0, 0, 0, 0, 0,
+          new HprofConstant[0], new HprofStaticField[0],
+          new HprofInstanceField[]{
+            new HprofInstanceField(strings.get("count"), HprofType.TYPE_INT),
+            new HprofInstanceField(strings.get("hashCode"), HprofType.TYPE_INT),
+            new HprofInstanceField(strings.get("offset"), HprofType.TYPE_INT),
+            new HprofInstanceField(strings.get("value"), HprofType.TYPE_OBJECT)}));
+
+    dump.add(new HprofPrimitiveArrayDump(0x41, 0, HprofType.TYPE_CHAR,
+          new long[]{'n', 'o', 't', ' ', 'h', 'e', 'l', 'l', 'o', 'o', 'p'}));
+
+    ByteArrayDataOutput values = ByteStreams.newDataOutput();
+    values.writeInt(5);     // count
+    values.writeInt(0);     // hashCode
+    values.writeInt(4);     // offset
+    values.writeInt(0x41);  // value
+    dump.add(new HprofInstanceDump(0x42, 0, stringClassObjectId, values.toByteArray()));
+    dump.add(new HprofRootDebugger(stringClassObjectId));
+    dump.add(new HprofRootDebugger(0x42));
+
+    records.add(new HprofHeapDump(0, dump.toArray(new HprofDumpRecord[0])));
+    AhatSnapshot snapshot = SnapshotBuilder.makeSnapshot(strings, records);
+
+    // Diffing should not crash.
+    Diff.snapshots(snapshot, snapshot);
+  }
+
+  @Test
+  public void diffFields() {
+    List<FieldValue> a = new ArrayList<FieldValue>();
+    a.add(new FieldValue("n0", "t0", null));
+    a.add(new FieldValue("n2", "t2", null));
+    a.add(new FieldValue("n3", "t3", null));
+    a.add(new FieldValue("n4", "t4", null));
+    a.add(new FieldValue("n5", "t5", null));
+    a.add(new FieldValue("n6", "t6", null));
+
+    List<FieldValue> b = new ArrayList<FieldValue>();
+    b.add(new FieldValue("n0", "t0", null));
+    b.add(new FieldValue("n1", "t1", null));
+    b.add(new FieldValue("n2", "t2", null));
+    b.add(new FieldValue("n3", "t3", null));
+    b.add(new FieldValue("n5", "t5", null));
+    b.add(new FieldValue("n6", "t6", null));
+    b.add(new FieldValue("n7", "t7", null));
+
+    Diff.fields(a, b);
+    assertEquals(8, a.size());
+    assertEquals(8, b.size());
+    for (int i = 0; i < 8; i++) {
+      assertEquals(a.get(i), b.get(i).getBaseline());
+      assertEquals(b.get(i), a.get(i).getBaseline());
+    }
+    assertTrue(a.get(1).isPlaceHolder());
+    assertTrue(a.get(7).isPlaceHolder());
+    assertTrue(b.get(4).isPlaceHolder());
+  }
+}
diff --git a/tools/ahat/test/NativeAllocationTest.java b/tools/ahat/test/NativeAllocationTest.java
deleted file mode 100644
index 9babab903e..0000000000
--- a/tools/ahat/test/NativeAllocationTest.java
+++ /dev/null
@@ -1,47 +0,0 @@
-/*
- * Copyright (C) 2016 The Android Open Source Project
- *
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at
- *
- *      http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package com.android.ahat;
-
-import com.android.ahat.heapdump.AhatInstance;
-import com.android.ahat.heapdump.AhatSnapshot;
-import com.android.ahat.heapdump.NativeAllocation;
-import java.io.IOException;
-import org.junit.Test;
-
-import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.fail;
-
-public class NativeAllocationTest {
-
-  @Test
-  public void nativeAllocation() throws IOException {
-    TestDump dump = TestDump.getTestDump();
-
-    AhatSnapshot snapshot = dump.getAhatSnapshot();
-    AhatInstance referent = dump.getDumpedAhatInstance("anObject");
-    for (NativeAllocation alloc : snapshot.getNativeAllocations()) {
-      if (alloc.referent.equals(referent)) {
-        assertEquals(42 , alloc.size);
-        assertEquals(referent.getHeap(), alloc.heap);
-        assertEquals(0xABCDABCD , alloc.pointer);
-        return;
-      }
-    }
-    fail("No native allocation found with anObject as the referent");
-  }
-}
-
diff --git a/tools/ahat/test/OverviewHandlerTest.java b/tools/ahat/test/OverviewHandlerTest.java
index a46bfce07d..c2f773b64b 100644
--- a/tools/ahat/test/OverviewHandlerTest.java
+++ b/tools/ahat/test/OverviewHandlerTest.java
@@ -26,7 +26,9 @@ public class OverviewHandlerTest {
   @Test
   public void noCrash() throws IOException {
     AhatSnapshot snapshot = TestDump.getTestDump().getAhatSnapshot();
-    AhatHandler handler = new OverviewHandler(snapshot, new File("my.hprof.file"));
+    AhatHandler handler = new OverviewHandler(snapshot,
+        new File("my.hprof.file"),
+        new File("my.base.hprof.file"));
     TestHandler.testNoCrash(handler, "http://localhost:7100");
   }
 }
diff --git a/tools/ahat/test/TestDump.java b/tools/ahat/test/TestDump.java
index 531c9dda78..ceb7346bc4 100644
--- a/tools/ahat/test/TestDump.java
+++ b/tools/ahat/test/TestDump.java
@@ -19,6 +19,7 @@ package com.android.ahat;
 import com.android.ahat.heapdump.AhatClassObj;
 import com.android.ahat.heapdump.AhatInstance;
 import com.android.ahat.heapdump.AhatSnapshot;
+import com.android.ahat.heapdump.Diff;
 import com.android.ahat.heapdump.FieldValue;
 import com.android.ahat.heapdump.Value;
 import com.android.tools.perflib.heap.ProguardMap;
@@ -38,30 +39,46 @@ public class TestDump {
   // is visible to other test cases.
   private static TestDump mCachedTestDump = null;
 
+  // If the test dump fails to load the first time, it will likely fail every
+  // other test we try. Rather than having to wait a potentially very long
+  // time for test dump loading to fail over and over again, record when it
+  // fails and don't try to load it again.
+  private static boolean mTestDumpFailed = false;
+
   private AhatSnapshot mSnapshot = null;
+  private AhatSnapshot mBaseline = null;
 
   /**
-   * Load the test-dump.hprof file.
-   * The location of the file is read from the system property
-   * "ahat.test.dump.hprof", which is expected to be set on the command line.
-   * For example:
-   *   java -Dahat.test.dump.hprof=test-dump.hprof -jar ahat-tests.jar
+   * Load the test-dump.hprof and test-dump-base.hprof files.
+   * The location of the files are read from the system properties
+   * "ahat.test.dump.hprof" and "ahat.test.dump.base.hprof", which is expected
+   * to be set on the command line.
+   * The location of the proguard map for both hprof files is read from the
+   * system property "ahat.test.dump.map".  For example:
+   *   java -Dahat.test.dump.hprof=test-dump.hprof \
+   *        -Dahat.test.dump.base.hprof=test-dump-base.hprof \
+   *        -Dahat.test.dump.map=proguard.map \
+   *        -jar ahat-tests.jar
    *
-   * An IOException is thrown if there is a failure reading the hprof file or
+   * An IOException is thrown if there is a failure reading the hprof files or
    * the proguard map.
    */
   private TestDump() throws IOException {
-      String hprof = System.getProperty("ahat.test.dump.hprof");
-
-      String mapfile = System.getProperty("ahat.test.dump.map");
-      ProguardMap map = new ProguardMap();
-      try {
-        map.readFromFile(new File(mapfile));
-      } catch (ParseException e) {
-        throw new IOException("Unable to load proguard map", e);
-      }
+    // TODO: Make use of the baseline hprof for tests.
+    String hprof = System.getProperty("ahat.test.dump.hprof");
+    String hprofBase = System.getProperty("ahat.test.dump.base.hprof");
+
+    String mapfile = System.getProperty("ahat.test.dump.map");
+    ProguardMap map = new ProguardMap();
+    try {
+      map.readFromFile(new File(mapfile));
+    } catch (ParseException e) {
+      throw new IOException("Unable to load proguard map", e);
+    }
 
-      mSnapshot = AhatSnapshot.fromHprof(new File(hprof), map);
+    mSnapshot = AhatSnapshot.fromHprof(new File(hprof), map);
+    mBaseline = AhatSnapshot.fromHprof(new File(hprofBase), map);
+    Diff.snapshots(mSnapshot, mBaseline);
   }
 
   /**
@@ -72,11 +89,34 @@ public class TestDump {
   }
 
   /**
+   * Get the baseline AhatSnapshot for the test dump program.
+   */
+  public AhatSnapshot getBaselineAhatSnapshot() {
+    return mBaseline;
+  }
+
+  /**
    * Returns the value of a field in the DumpedStuff instance in the
    * snapshot for the test-dump program.
    */
   public Value getDumpedValue(String name) {
-    AhatClassObj main = mSnapshot.findClass("Main");
+    return getDumpedValue(name, mSnapshot);
+  }
+
+  /**
+   * Returns the value of a field in the DumpedStuff instance in the
+   * baseline snapshot for the test-dump program.
+   */
+  public Value getBaselineDumpedValue(String name) {
+    return getDumpedValue(name, mBaseline);
+  }
+
+  /**
+   * Returns the value of a field in the DumpedStuff instance in the
+   * given snapshot for the test-dump program.
+   */
+  private Value getDumpedValue(String name, AhatSnapshot snapshot) {
+    AhatClassObj main = snapshot.findClass("Main");
     AhatInstance stuff = null;
     for (FieldValue fields : main.getStaticFieldValues()) {
       if ("stuff".equals(fields.getName())) {
@@ -96,6 +136,15 @@ public class TestDump {
   }
 
   /**
+   * Returns the value of a non-primitive field in the DumpedStuff instance in
+   * the baseline snapshot for the test-dump program.
+   */
+  public AhatInstance getBaselineDumpedAhatInstance(String name) {
+    Value value = getBaselineDumpedValue(name);
+    return value == null ? null : value.asAhatInstance();
+  }
+
+  /**
    * Get the test dump.
    * An IOException is thrown if there is an error reading the test dump hprof
    * file.
@@ -103,8 +152,14 @@ public class TestDump {
    * when possible.
    */
   public static synchronized TestDump getTestDump() throws IOException {
+    if (mTestDumpFailed) {
+      throw new RuntimeException("Test dump failed before, assuming it will again");
+    }
+
     if (mCachedTestDump == null) {
+      mTestDumpFailed = true;
       mCachedTestDump = new TestDump();
+      mTestDumpFailed = false;
     }
     return mCachedTestDump;
   }
diff --git a/tools/ahat/test/Tests.java b/tools/ahat/test/Tests.java
index 6c29f27357..2fd3286172 100644
--- a/tools/ahat/test/Tests.java
+++ b/tools/ahat/test/Tests.java
@@ -22,8 +22,8 @@ public class Tests {
   public static void main(String[] args) {
     if (args.length == 0) {
       args = new String[]{
+        "com.android.ahat.DiffTest",
         "com.android.ahat.InstanceTest",
-        "com.android.ahat.NativeAllocationTest",
         "com.android.ahat.ObjectHandlerTest",
         "com.android.ahat.OverviewHandlerTest",
         "com.android.ahat.PerformanceTest",