diff --git a/perflib/src/main/java/com/android/tools/perflib/vmtrace/Call.java b/perflib/src/main/java/com/android/tools/perflib/vmtrace/Call.java
index e6f0dc7..9144ea5 100644
--- a/perflib/src/main/java/com/android/tools/perflib/vmtrace/Call.java
+++ b/perflib/src/main/java/com/android/tools/perflib/vmtrace/Call.java
@@ -18,44 +18,49 @@
 
 import com.android.annotations.NonNull;
 import com.google.common.base.Strings;
+import com.google.common.collect.ImmutableList;
 
 import java.util.ArrayList;
+import java.util.Collections;
 import java.util.List;
 
 public class Call {
     private final long mMethodId;
 
-    private int mEntryThreadTime;
-    private int mEntryGlobalTime;
-    private int mExitGlobalTime;
-    private int mExitThreadTime;
+    private final int mEntryThreadTime;
+    private final int mEntryGlobalTime;
+    private final int mExitGlobalTime;
+    private final int mExitThreadTime;
 
-    private int mDepth = 0;
+    private final int mDepth;
 
-    private List<Call> mCallees = new ArrayList<Call>();
+    private final List<Call> mCallees;
 
-    public Call(long methodId) {
-        mMethodId = methodId;
+    private Call(Builder builder) {
+        mMethodId = builder.mMethodId;
+
+        mEntryThreadTime = builder.mEntryThreadTime;
+        mEntryGlobalTime = builder.mEntryGlobalTime;
+        mExitThreadTime = builder.mExitThreadTime;
+        mExitGlobalTime = builder.mExitGlobalTime;
+
+        mDepth = builder.mDepth;
+        if (builder.mCallees == null) {
+            mCallees = Collections.emptyList();
+        } else {
+            List<Call> callees = new ArrayList<Call>(builder.mCallees.size());
+            for (Builder b : builder.mCallees) {
+                b.setStackDepth(mDepth + 1);
+                callees.add(b.build());
+            }
+            mCallees = new ImmutableList.Builder<Call>().addAll(callees).build();
+        }
     }
 
     public long getMethodId() {
         return mMethodId;
     }
 
-    public void setMethodEntryTime(int threadTime, int globalTime) {
-        mEntryThreadTime = threadTime;
-        mEntryGlobalTime = globalTime;
-    }
-
-    public void setMethodExitTime(int threadTime, int globalTime) {
-        mExitThreadTime = threadTime;
-        mExitGlobalTime = globalTime;
-    }
-
-    public void addCallee(Call c) {
-        mCallees.add(c);
-    }
-
     @NonNull
     public List<Call> getCallees() {
         return mCallees;
@@ -65,8 +70,58 @@
         return mDepth;
     }
 
-    public void setDepth(int depth) {
-        mDepth = depth;
+    public int getEntryThreadTime() {
+        return mEntryThreadTime;
+    }
+
+    public int getExitThreadTime() {
+        return mExitThreadTime;
+    }
+
+    public static class Builder {
+        private final long mMethodId;
+
+        private int mEntryThreadTime;
+        private int mEntryGlobalTime;
+        private int mExitGlobalTime;
+        private int mExitThreadTime;
+
+        private int mDepth = 0;
+
+        private List<Builder> mCallees = null;
+
+        public Builder(long methodId) {
+            mMethodId = methodId;
+        }
+
+        public long getMethodId() {
+            return mMethodId;
+        }
+
+        public void setMethodEntryTime(int threadTime, int globalTime) {
+            mEntryThreadTime = threadTime;
+            mEntryGlobalTime = globalTime;
+        }
+
+        public void setMethodExitTime(int threadTime, int globalTime) {
+            mExitThreadTime = threadTime;
+            mExitGlobalTime = globalTime;
+        }
+
+        public void addCallee(Builder c) {
+            if (mCallees == null) {
+                mCallees = new ArrayList<Builder>();
+            }
+            mCallees.add(c);
+        }
+
+        public void setStackDepth(int depth) {
+            mDepth = depth;
+        }
+
+        public Call build() {
+            return new Call(this);
+        }
     }
 
     /**
@@ -100,9 +155,6 @@
         sb.append(formatter.format(this));
 
         List<Call> callees = getCallees();
-        if (callees == null) {
-            return;
-        }
 
         int lineStart = sb.lastIndexOf("\n");
         int depth = sb.length() - (lineStart + 1);
diff --git a/perflib/src/main/java/com/android/tools/perflib/vmtrace/CallStackReconstructor.java b/perflib/src/main/java/com/android/tools/perflib/vmtrace/CallStackReconstructor.java
index 027d550..e241db8 100644
--- a/perflib/src/main/java/com/android/tools/perflib/vmtrace/CallStackReconstructor.java
+++ b/perflib/src/main/java/com/android/tools/perflib/vmtrace/CallStackReconstructor.java
@@ -16,18 +16,24 @@
 
 package com.android.tools.perflib.vmtrace;
 
-import com.android.annotations.NonNull;
+import com.google.common.collect.ImmutableList;
 
 import java.util.ArrayList;
 import java.util.List;
 import java.util.Stack;
 
-/** Reconstructs call stacks from a sequence of trace events (method entry/exit events) */
+/**
+ * {@link CallStackReconstructor} helps in reconstructing per thread call stacks from a sequence of
+ * trace events (method entry/exit events).
+ */
 public class CallStackReconstructor {
-    private List<Call> mTopLevelCallees = new ArrayList<Call>();
-    private Stack<Call> mCallStack = new Stack<Call>();
+    /** List of calls currently assumed to be at stack depth 0 (called from the top level) */
+    private List<Call.Builder> mTopLevelCalls = new ArrayList<Call.Builder>();
 
-    private boolean mFixupComplete;
+    /** Current call stack based on the sequence of received trace events. */
+    private Stack<Call.Builder> mCallStack = new Stack<Call.Builder>();
+
+    private List<Call> mTopLevelCallees;
 
     public void addTraceAction(long methodId, TraceAction action, int threadTime, int globalTime) {
         if (action == TraceAction.METHOD_ENTER) {
@@ -38,22 +44,22 @@
     }
 
     private void enterMethod(long methodId, int threadTime, int globalTime) {
-        Call c = new Call(methodId);
-        c.setMethodEntryTime(threadTime, globalTime);
+        Call.Builder cb = new Call.Builder(methodId);
+        cb.setMethodEntryTime(threadTime, globalTime);
 
         if (mCallStack.isEmpty()) {
-            mTopLevelCallees.add(c);
+            mTopLevelCalls.add(cb);
         } else {
-            Call caller = mCallStack.peek();
-            caller.addCallee(c);
+            Call.Builder caller = mCallStack.peek();
+            caller.addCallee(cb);
         }
 
-        mCallStack.push(c);
+        mCallStack.push(cb);
     }
 
     private void exitMethod(long methodId, int threadTime, int globalTime) {
         if (!mCallStack.isEmpty()) {
-            Call c = mCallStack.pop();
+            Call.Builder c = mCallStack.pop();
             if (c.getMethodId() != methodId) {
                 String msg = String
                         .format("Error during call stack reconstruction. Attempt to exit from method 0x%1$x while in method 0x%2$x",
@@ -65,42 +71,35 @@
         } else {
             // We are exiting out of a method that was entered into before tracing was started.
             // In such a case, create this method
-            Call c = new Call(methodId);
+            Call.Builder c = new Call.Builder(methodId);
             c.setMethodExitTime(threadTime, globalTime);
 
             // All the previous calls at the top level are now assumed to have been called from
             // this method. So mark this method as having called all of those methods, and reset
             // the top level to only include this method
-            for (Call topLevelCallee : mTopLevelCallees) {
-                c.addCallee(topLevelCallee);
+            for (Call.Builder cb : mTopLevelCalls) {
+                c.addCallee(cb);
             }
-            mTopLevelCallees.clear();
-            mTopLevelCallees.add(c);
+            mTopLevelCalls.clear();
+            mTopLevelCalls.add(c);
         }
     }
 
     private void fixupCallStacks() {
-        if (mFixupComplete) {
+        if (mTopLevelCallees != null) {
             return;
         }
 
-        // fixup whatever needs fixing up
         // TODO: use global / thread times to infer context switches
 
-        // Fix call stack depths
-        for (Call c : mTopLevelCallees) {
-            setStackDepthRecursive(c, 0);
+        // Build calls from their respective builders
+        List<Call> topLevelCallees = new ArrayList<Call>(mTopLevelCalls.size());
+        for (Call.Builder b : mTopLevelCalls) {
+            b.setStackDepth(0);
+            topLevelCallees.add(b.build());
         }
 
-        mFixupComplete = true;
-    }
-
-    private void setStackDepthRecursive(@NonNull Call call, int i) {
-        call.setDepth(i);
-
-        for (Call c : call.getCallees()) {
-            setStackDepthRecursive(c, i+1);
-        }
+        mTopLevelCallees = new ImmutableList.Builder<Call>().addAll(topLevelCallees).build();
     }
 
     public List<Call> getTopLevelCallees() {
diff --git a/perflib/src/main/java/com/android/tools/perflib/vmtrace/MethodInfo.java b/perflib/src/main/java/com/android/tools/perflib/vmtrace/MethodInfo.java
index 518d5c8..c2b0edb 100644
--- a/perflib/src/main/java/com/android/tools/perflib/vmtrace/MethodInfo.java
+++ b/perflib/src/main/java/com/android/tools/perflib/vmtrace/MethodInfo.java
@@ -26,6 +26,9 @@
     public final String srcPath;
     public final int srcLineNumber;
 
+    private String mFullName;
+    private String mShortName;
+
     public MethodInfo(long id, String className, String methodName, String signature, String srcPath,
             int srcLineNumber) {
         this.id = id;
@@ -36,7 +39,26 @@
         this.srcLineNumber = srcLineNumber;
     }
 
-    public String getName() {
-        return String.format(Locale.US, "%s.%s: %s", className, methodName, signature);
+    public String getFullName() {
+        if (mFullName == null) {
+            mFullName = String.format(Locale.US, "%s.%s: %s", className, methodName, signature);
+        }
+        return mFullName;
+    }
+
+    public String getShortName() {
+        if (mShortName == null) {
+            mShortName = String.format(Locale.US, "%s.%s", getUnqualifiedClassName(), methodName);
+        }
+        return mShortName;
+    }
+
+    private String getUnqualifiedClassName() {
+        String cn = className;
+        int i = cn.lastIndexOf('/');
+        if (i > 0) {
+            cn = cn.substring(i + 1);
+        }
+        return cn;
     }
 }
diff --git a/perflib/src/main/java/com/android/tools/perflib/vmtrace/VmTraceData.java b/perflib/src/main/java/com/android/tools/perflib/vmtrace/VmTraceData.java
index cb5f54e..b6f27c8 100644
--- a/perflib/src/main/java/com/android/tools/perflib/vmtrace/VmTraceData.java
+++ b/perflib/src/main/java/com/android/tools/perflib/vmtrace/VmTraceData.java
@@ -17,10 +17,7 @@
 package com.android.tools.perflib.vmtrace;
 
 import com.android.utils.SparseArray;
-import com.google.common.base.Joiner;
 
-import java.util.ArrayList;
-import java.util.Collection;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
diff --git a/perflib/src/test/java/com/android/tools/perflib/vmtrace/VmTraceParserTest.java b/perflib/src/test/java/com/android/tools/perflib/vmtrace/VmTraceParserTest.java
index 19fad82..87b7109 100644
--- a/perflib/src/test/java/com/android/tools/perflib/vmtrace/VmTraceParserTest.java
+++ b/perflib/src/test/java/com/android/tools/perflib/vmtrace/VmTraceParserTest.java
@@ -27,7 +27,6 @@
 import java.net.URL;
 import java.util.ArrayList;
 import java.util.List;
-import java.util.Locale;
 import java.util.Map;
 
 public class VmTraceParserTest extends TestCase {
@@ -73,7 +72,7 @@
         @Override
         public String format(Call c) {
             MethodInfo info = mMethodInfo.get(c.getMethodId());
-            return info == null ? Long.toString(c.getMethodId()) : info.getName();
+            return info == null ? Long.toString(c.getMethodId()) : info.getFullName();
         }
     }