Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(215)

Unified Diff: tools/tracemerge.dart

Issue 100103011: Changes to support dprof and Observatory profiler UIs (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Created 6 years, 12 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « runtime/vm/service_test.cc ('k') | tools/tracesummary.dart » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: tools/tracemerge.dart
diff --git a/tools/tracemerge.dart b/tools/tracemerge.dart
deleted file mode 100644
index 6c7d5ddd45dcf2b9d2cca9aede54f084293ae6d5..0000000000000000000000000000000000000000
--- a/tools/tracemerge.dart
+++ /dev/null
@@ -1,361 +0,0 @@
-// Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file
-// 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.
-
-// Merge multiple isolate profiler tracing dumps into one.
-
-import 'dart:convert';
-import 'dart:io';
-
-/**
- * Sort a list using insertion sort.
- *
- * Insertion sort is a simple sorting algorithm. For `n` elements it does on
- * the order of `n * log(n)` comparisons but up to `n` squared moves. The
- * sorting is performed in-place, without using extra memory.
- *
- * For short lists the many moves have less impact than the simple algorithm,
- * and it is often the favored sorting algorithm for short lists.
- *
- * This insertion sort is stable: Equal elements end up in the same order
- * as they started in.
- */
-void insertionSort(List list,
- { int compare(a, b),
- int start: 0,
- int end: null }) {
- // If the same method could have both positional and named optional
- // parameters, this should be (list, [start, end], {compare}).
- if (end == null) end = list.length;
- if (compare == null) compare = Comparable.compare;
- _insertionSort(list, compare, start, end, start + 1);
-}
-
-/**
- * Internal helper function that assumes arguments correct.
- *
- * Assumes that the elements up to [sortedUntil] (not inclusive) are
- * already sorted. The [sortedUntil] values should always be at least
- * `start + 1`.
- */
-void _insertionSort(List list, int compare(a, b), int start, int end,
- int sortedUntil) {
- for (int pos = sortedUntil; pos < end; pos++) {
- int min = start;
- int max = pos;
- var element = list[pos];
- while (min < max) {
- int mid = min + ((max - min) >> 1);
- int comparison = compare(element, list[mid]);
- if (comparison < 0) {
- max = mid;
- } else {
- min = mid + 1;
- }
- }
- list.setRange(min + 1, pos + 1, list, min);
- list[min] = element;
- }
-}
-
-/** Limit below which merge sort defaults to insertion sort. */
-const int _MERGE_SORT_LIMIT = 32;
-
-/**
- * Sorts a list, or a range of a list, using the merge sort algorithm.
- *
- * Merge-sorting works by splitting the job into two parts, sorting each
- * recursively, and then merging the two sorted parts.
- *
- * This takes on the order of `n * log(n)` comparisons and moves to sort
- * `n` elements, but requires extra space of about the same size as the list
- * being sorted.
- *
- * This merge sort is stable: Equal elements end up in the same order
- * as they started in.
- */
-void mergeSort(List list, {int start: 0, int end: null, int compare(a, b)}) {
- if (end == null) end = list.length;
- if (compare == null) compare = Comparable.compare;
- int length = end - start;
- if (length < 2) return;
- if (length < _MERGE_SORT_LIMIT) {
- _insertionSort(list, compare, start, end, start + 1);
- return;
- }
- // Special case the first split instead of directly calling
- // _mergeSort, because the _mergeSort requires its target to
- // be different from its source, and it requires extra space
- // of the same size as the list to sort.
- // This split allows us to have only half as much extra space,
- // and it ends up in the original place.
- int middle = start + ((end - start) >> 1);
- int firstLength = middle - start;
- int secondLength = end - middle;
- // secondLength is always the same as firstLength, or one greater.
- List scratchSpace = new List(secondLength);
- _mergeSort(list, compare, middle, end, scratchSpace, 0);
- int firstTarget = end - firstLength;
- _mergeSort(list, compare, start, middle, list, firstTarget);
- _merge(compare,
- list, firstTarget, end,
- scratchSpace, 0, secondLength,
- list, start);
-}
-
-/**
- * Performs an insertion sort into a potentially different list than the
- * one containing the original values.
- *
- * It will work in-place as well.
- */
-void _movingInsertionSort(List list, int compare(a, b), int start, int end,
- List target, int targetOffset) {
- int length = end - start;
- if (length == 0) return;
- target[targetOffset] = list[start];
- for (int i = 1; i < length; i++) {
- var element = list[start + i];
- int min = targetOffset;
- int max = targetOffset + i;
- while (min < max) {
- int mid = min + ((max - min) >> 1);
- if (compare(element, target[mid]) < 0) {
- max = mid;
- } else {
- min = mid + 1;
- }
- }
- target.setRange(min + 1, targetOffset + i + 1,
- target, min);
- target[min] = element;
- }
-}
-
-/**
- * Sorts [list] from [start] to [end] into [target] at [targetOffset].
- *
- * The `target` list must be able to contain the range from `start` to `end`
- * after `targetOffset`.
- *
- * Allows target to be the same list as [list], as long as it's not
- * overlapping the `start..end` range.
- */
-void _mergeSort(List list, int compare(a, b), int start, int end,
- List target, int targetOffset) {
- int length = end - start;
- if (length < _MERGE_SORT_LIMIT) {
- _movingInsertionSort(list, compare, start, end, target, targetOffset);
- return;
- }
- int middle = start + (length >> 1);
- int firstLength = middle - start;
- int secondLength = end - middle;
- // Here secondLength >= firstLength (differs by at most one).
- int targetMiddle = targetOffset + firstLength;
- // Sort the second half into the end of the target area.
- _mergeSort(list, compare, middle, end,
- target, targetMiddle);
- // Sort the first half into the end of the source area.
- _mergeSort(list, compare, start, middle,
- list, middle);
- // Merge the two parts into the target area.
- _merge(compare,
- list, middle, middle + firstLength,
- target, targetMiddle, targetMiddle + secondLength,
- target, targetOffset);
-}
-
-/**
- * Merges two lists into a target list.
- *
- * One of the input lists may be positioned at the end of the target
- * list.
- *
- * For equal object, elements from [firstList] are always preferred.
- * This allows the merge to be stable if the first list contains elements
- * that started out earlier than the ones in [secondList]
- */
-void _merge(int compare(a, b),
- List firstList, int firstStart, int firstEnd,
- List secondList, int secondStart, int secondEnd,
- List target, int targetOffset) {
- // No empty lists reaches here.
- assert(firstStart < firstEnd);
- assert(secondStart < secondEnd);
- int cursor1 = firstStart;
- int cursor2 = secondStart;
- var firstElement = firstList[cursor1++];
- var secondElement = secondList[cursor2++];
- while (true) {
- if (compare(firstElement, secondElement) <= 0) {
- target[targetOffset++] = firstElement;
- if (cursor1 == firstEnd) break; // Flushing second list after loop.
- firstElement = firstList[cursor1++];
- } else {
- target[targetOffset++] = secondElement;
- if (cursor2 != secondEnd) {
- secondElement = secondList[cursor2++];
- continue;
- }
- // Second list empties first. Flushing first list here.
- target[targetOffset++] = firstElement;
- target.setRange(targetOffset, targetOffset + (firstEnd - cursor1),
- firstList, cursor1);
- return;
- }
- }
- // First list empties first. Reached by break above.
- target[targetOffset++] = secondElement;
- 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);
-}
« no previous file with comments | « runtime/vm/service_test.cc ('k') | tools/tracesummary.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698