Profiler Take 2

tools/tracemerge.dart

Index: tools/tracemerge.dart
diff --git a/pkg/collection_helpers/lib/algorithms.dart b/tools/tracemerge.dart
similarity index 66%
copy from pkg/collection_helpers/lib/algorithms.dart
copy to tools/tracemerge.dart
index 057111a664625e3d4ab28a0f9421f03b340c73bb..6c7d5ddd45dcf2b9d2cca9aede54f084293ae6d5 100644
--- a/pkg/collection_helpers/lib/algorithms.dart
+++ b/tools/tracemerge.dart
@@ -2,99 +2,10 @@
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
-/**
- * Operations on collections.
- */
-library dart.collection_helpers.algorithms;
-
-import "dart:math" show Random;
-
-/** Version of [binarySearch] optimized for comparable keys */
-int _comparableBinarySearch(List<Comparable> list, Comparable key) {
-  int min = 0;
-  int max = list.length;
-  while (min < max) {
-    int mid = min + ((max - min) >> 1);
-    var element = list[mid];
-    int comp = element.compareTo(key);
-    if (comp == 0) return mid;
-    if (comp < 0) {
-      min = mid + 1;
-    } else {
-      max = mid;
-    }
-  }
-  return -1;
-}
-
-/**
- * Returns a position of the [key] in [sortedList], if it is there.
- *
- * If the list isn't sorted according to the [compare] function, the result
- * is unpredictable.
- *
- * If [compare] is omitted, it defaults to calling [Comparable.compareTo] on
- * the objects.
- *
- * Returns -1 if [key] is not in the list by default.
- */
-int binarySearch(List sortedList, var key,
-                 { int compare(var a, var b) }) {
-  if (compare == null) {
-    return _comparableBinarySearch(sortedList, key);
-  }
-  int min = 0;
-  int max = sortedList.length;
-  while (min < max) {
-    int mid = min + ((max - min) >> 1);
-    var element = sortedList[mid];
-    int comp = compare(element, key);
-    if (comp == 0) return mid;
-    if (comp < 0) {
-      min = mid + 1;
-    } else {
-      max = mid;
-    }
-  }
-  return -1;
-}
-
-
-/**
- * Shuffles a list randomly.
- *
- * A sub-range of a list can be shuffled by providing [start] and [end].
- */
-void shuffle(List list, [int start = 0, int end = null]) {
-  Random random = new Random();
-  if (end == null) end = list.length;
-  int length = end - start;
-  while (length > 1) {
-    int pos = random.nextInt(length);
-    length--;
-    var tmp1 = list[start + pos];
-    list[start + pos] = list[start + length];
-    list[start + length] = tmp1;
-  }
-}
-
+// Merge multiple isolate profiler tracing dumps into one.
 
-/**
- * Reverses a list, or a part of a list, in-place.
- */
-void reverse(List list, [int start = 0, int end = null]) {
-  if (end == null) end = list.length;
-  _reverse(list, start, end);
-}
-
-// Internal helper function that assumes valid arguments.
-void _reverse(List list, int start, int end) {
-  for (int i = start, j = end - 1; i < j; i++, j--) {
-    var tmp = list[i];
-    list[i] = list[j];
-    list[j] = tmp;
-  }
-}
+import 'dart:convert';
+import 'dart:io';
 
 /**
  * Sort a list using insertion sort.
@@ -299,3 +210,152 @@ void _merge(int compare(a, b),
   target.setRange(targetOffset, targetOffset + (secondEnd - cursor2),
       secondList, cursor2);
 }
+
+class TraceMerge {
+  Map _processes = {};
+  List _metaEvents = [];
+
+  void _processEventsFromFile(String name) {
+    var file = new File(name);
+    var events = [];
+    try {
+      var contents = file.readAsStringSync();
+      events = JSON.decode(contents);
+    } catch (e) {
+      print('Exception for $name $e');
+    }
+    _processEvents(events);
+  }
+
+  List _findOrAddProcessThread(pid, tid) {
+    var process = _processes[pid];
+    if (process == null) {
+      process = {};
+      _processes[pid] = process;
+    }
+    var thread = process[tid];
+    if (thread == null) {
+      thread = [];
+      process[tid] = thread;
+    }
+    return thread;
+  }
+
+  void _processEvents(List events) {
+    for (var i = 0; i < events.length; i++) {
+      Map event = events[i];
+      if (event['ph'] == 'M') {
+        _metaEvents.add(event);
+      } else {
+        var pid = event['pid'];
+        if (pid == null) {
+          throw "No pid in ${event}";
+        }
+        var tid = event['tid'];
+        if (tid == null) {
+          throw "No tid in ${event}";
+        }
+        var thread = _findOrAddProcessThread(pid, tid);
+        if (thread == null) {
+          throw "No thread list returned.";
+        }
+        thread.add(event);
+      }
+    }
+  }
+
+  int _compare(Map a, Map b) {
+    if (a['ts'] > b['ts']) {
+      return 1;
+    } else if (a['ts'] < b['ts']) {
+      return -1;
+    }
+    return 0;
+  }
+
+  void _sortEvents() {
+    _processes.forEach((k, Map process) {
+      process.forEach((k, List thread) {
+        mergeSort(thread, compare:_compare);
+      });
+    });
+  }
+
+  void _mergeEventsForThread(List thread) {
+    List<Map> stack = [];
+    int stackDepth = 0;
+    thread.forEach((event) {
+      if (event['ph'] == 'B') {
+        if (stackDepth == stack.length) {
+          stack.add(null);
+        }
+        stackDepth++;
+        var end_event = stack[stackDepth - 1];
+        if (end_event != null) {
+          if (end_event['name'] == event['name'] && stackDepth > 1) {
+            // Kill these events.
+            // event['dead'] = true;
+            // end_event['dead'] = true;
+          }
+        }
+      } else {
+        if (event['ph'] != 'E') {
+          throw 'Expected E event: ${event}';
+        }
+        if (stackDepth <= 0) {
+          throw 'Stack out of sync ${event}.';
+        }
+        stackDepth--;
+        stack[stackDepth] = event;
+      }
+    });
+  }
+
+  void _mergeEvents() {
+    _processes.forEach((k, Map process) {
+      process.forEach((k, List thread) {
+        _mergeEventsForThread(thread);
+      });
+    });
+  }
+
+  void writeEventsToFile(String name) {
+    var file = new File(name);
+    List final_events = _metaEvents;
+    _processes.forEach((pid, Map process) {
+      process.forEach((tid, List thread) {
+        thread.forEach((event) {
+          if (event['dead'] == null) {
+            // Not dead.
+            final_events.add(event);
+          }
+        });
+      });
+    });
+    file.writeAsStringSync(JSON.encode(final_events));
+  }
+
+  void merge(List<String> inputs) {
+    for (var i = 0; i < inputs.length; i++) {
+      _processEventsFromFile(inputs[i]);
+    }
+    _sortEvents();
+    _mergeEvents();
+  }
+}
+
+main(List<String> arguments) {
+  if (arguments.length < 2) {
+    print('${Platform.executable} ${Platform.script} <output> <inputs>');
+    return;
+  }
+  String output = arguments[0];
+  List<String> inputs = new List<String>();
+  for (var i = 1; i < arguments.length; i++) {
+    inputs.add(arguments[i]);
+  }
+  print('Merging $inputs into $output.');
+  TraceMerge tm = new TraceMerge();
+  tm.merge(inputs);
+  tm.writeEventsToFile(output);
+}