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

Side by Side 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, 11 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 unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « runtime/vm/service_test.cc ('k') | tools/tracesummary.dart » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file
2 // for details. All rights reserved. Use of this source code is governed by a
3 // BSD-style license that can be found in the LICENSE file.
4
5 // Merge multiple isolate profiler tracing dumps into one.
6
7 import 'dart:convert';
8 import 'dart:io';
9
10 /**
11 * Sort a list using insertion sort.
12 *
13 * Insertion sort is a simple sorting algorithm. For `n` elements it does on
14 * the order of `n * log(n)` comparisons but up to `n` squared moves. The
15 * sorting is performed in-place, without using extra memory.
16 *
17 * For short lists the many moves have less impact than the simple algorithm,
18 * and it is often the favored sorting algorithm for short lists.
19 *
20 * This insertion sort is stable: Equal elements end up in the same order
21 * as they started in.
22 */
23 void insertionSort(List list,
24 { int compare(a, b),
25 int start: 0,
26 int end: null }) {
27 // If the same method could have both positional and named optional
28 // parameters, this should be (list, [start, end], {compare}).
29 if (end == null) end = list.length;
30 if (compare == null) compare = Comparable.compare;
31 _insertionSort(list, compare, start, end, start + 1);
32 }
33
34 /**
35 * Internal helper function that assumes arguments correct.
36 *
37 * Assumes that the elements up to [sortedUntil] (not inclusive) are
38 * already sorted. The [sortedUntil] values should always be at least
39 * `start + 1`.
40 */
41 void _insertionSort(List list, int compare(a, b), int start, int end,
42 int sortedUntil) {
43 for (int pos = sortedUntil; pos < end; pos++) {
44 int min = start;
45 int max = pos;
46 var element = list[pos];
47 while (min < max) {
48 int mid = min + ((max - min) >> 1);
49 int comparison = compare(element, list[mid]);
50 if (comparison < 0) {
51 max = mid;
52 } else {
53 min = mid + 1;
54 }
55 }
56 list.setRange(min + 1, pos + 1, list, min);
57 list[min] = element;
58 }
59 }
60
61 /** Limit below which merge sort defaults to insertion sort. */
62 const int _MERGE_SORT_LIMIT = 32;
63
64 /**
65 * Sorts a list, or a range of a list, using the merge sort algorithm.
66 *
67 * Merge-sorting works by splitting the job into two parts, sorting each
68 * recursively, and then merging the two sorted parts.
69 *
70 * This takes on the order of `n * log(n)` comparisons and moves to sort
71 * `n` elements, but requires extra space of about the same size as the list
72 * being sorted.
73 *
74 * This merge sort is stable: Equal elements end up in the same order
75 * as they started in.
76 */
77 void mergeSort(List list, {int start: 0, int end: null, int compare(a, b)}) {
78 if (end == null) end = list.length;
79 if (compare == null) compare = Comparable.compare;
80 int length = end - start;
81 if (length < 2) return;
82 if (length < _MERGE_SORT_LIMIT) {
83 _insertionSort(list, compare, start, end, start + 1);
84 return;
85 }
86 // Special case the first split instead of directly calling
87 // _mergeSort, because the _mergeSort requires its target to
88 // be different from its source, and it requires extra space
89 // of the same size as the list to sort.
90 // This split allows us to have only half as much extra space,
91 // and it ends up in the original place.
92 int middle = start + ((end - start) >> 1);
93 int firstLength = middle - start;
94 int secondLength = end - middle;
95 // secondLength is always the same as firstLength, or one greater.
96 List scratchSpace = new List(secondLength);
97 _mergeSort(list, compare, middle, end, scratchSpace, 0);
98 int firstTarget = end - firstLength;
99 _mergeSort(list, compare, start, middle, list, firstTarget);
100 _merge(compare,
101 list, firstTarget, end,
102 scratchSpace, 0, secondLength,
103 list, start);
104 }
105
106 /**
107 * Performs an insertion sort into a potentially different list than the
108 * one containing the original values.
109 *
110 * It will work in-place as well.
111 */
112 void _movingInsertionSort(List list, int compare(a, b), int start, int end,
113 List target, int targetOffset) {
114 int length = end - start;
115 if (length == 0) return;
116 target[targetOffset] = list[start];
117 for (int i = 1; i < length; i++) {
118 var element = list[start + i];
119 int min = targetOffset;
120 int max = targetOffset + i;
121 while (min < max) {
122 int mid = min + ((max - min) >> 1);
123 if (compare(element, target[mid]) < 0) {
124 max = mid;
125 } else {
126 min = mid + 1;
127 }
128 }
129 target.setRange(min + 1, targetOffset + i + 1,
130 target, min);
131 target[min] = element;
132 }
133 }
134
135 /**
136 * Sorts [list] from [start] to [end] into [target] at [targetOffset].
137 *
138 * The `target` list must be able to contain the range from `start` to `end`
139 * after `targetOffset`.
140 *
141 * Allows target to be the same list as [list], as long as it's not
142 * overlapping the `start..end` range.
143 */
144 void _mergeSort(List list, int compare(a, b), int start, int end,
145 List target, int targetOffset) {
146 int length = end - start;
147 if (length < _MERGE_SORT_LIMIT) {
148 _movingInsertionSort(list, compare, start, end, target, targetOffset);
149 return;
150 }
151 int middle = start + (length >> 1);
152 int firstLength = middle - start;
153 int secondLength = end - middle;
154 // Here secondLength >= firstLength (differs by at most one).
155 int targetMiddle = targetOffset + firstLength;
156 // Sort the second half into the end of the target area.
157 _mergeSort(list, compare, middle, end,
158 target, targetMiddle);
159 // Sort the first half into the end of the source area.
160 _mergeSort(list, compare, start, middle,
161 list, middle);
162 // Merge the two parts into the target area.
163 _merge(compare,
164 list, middle, middle + firstLength,
165 target, targetMiddle, targetMiddle + secondLength,
166 target, targetOffset);
167 }
168
169 /**
170 * Merges two lists into a target list.
171 *
172 * One of the input lists may be positioned at the end of the target
173 * list.
174 *
175 * For equal object, elements from [firstList] are always preferred.
176 * This allows the merge to be stable if the first list contains elements
177 * that started out earlier than the ones in [secondList]
178 */
179 void _merge(int compare(a, b),
180 List firstList, int firstStart, int firstEnd,
181 List secondList, int secondStart, int secondEnd,
182 List target, int targetOffset) {
183 // No empty lists reaches here.
184 assert(firstStart < firstEnd);
185 assert(secondStart < secondEnd);
186 int cursor1 = firstStart;
187 int cursor2 = secondStart;
188 var firstElement = firstList[cursor1++];
189 var secondElement = secondList[cursor2++];
190 while (true) {
191 if (compare(firstElement, secondElement) <= 0) {
192 target[targetOffset++] = firstElement;
193 if (cursor1 == firstEnd) break; // Flushing second list after loop.
194 firstElement = firstList[cursor1++];
195 } else {
196 target[targetOffset++] = secondElement;
197 if (cursor2 != secondEnd) {
198 secondElement = secondList[cursor2++];
199 continue;
200 }
201 // Second list empties first. Flushing first list here.
202 target[targetOffset++] = firstElement;
203 target.setRange(targetOffset, targetOffset + (firstEnd - cursor1),
204 firstList, cursor1);
205 return;
206 }
207 }
208 // First list empties first. Reached by break above.
209 target[targetOffset++] = secondElement;
210 target.setRange(targetOffset, targetOffset + (secondEnd - cursor2),
211 secondList, cursor2);
212 }
213
214 class TraceMerge {
215 Map _processes = {};
216 List _metaEvents = [];
217
218 void _processEventsFromFile(String name) {
219 var file = new File(name);
220 var events = [];
221 try {
222 var contents = file.readAsStringSync();
223 events = JSON.decode(contents);
224 } catch (e) {
225 print('Exception for $name $e');
226 }
227 _processEvents(events);
228 }
229
230 List _findOrAddProcessThread(pid, tid) {
231 var process = _processes[pid];
232 if (process == null) {
233 process = {};
234 _processes[pid] = process;
235 }
236 var thread = process[tid];
237 if (thread == null) {
238 thread = [];
239 process[tid] = thread;
240 }
241 return thread;
242 }
243
244 void _processEvents(List events) {
245 for (var i = 0; i < events.length; i++) {
246 Map event = events[i];
247 if (event['ph'] == 'M') {
248 _metaEvents.add(event);
249 } else {
250 var pid = event['pid'];
251 if (pid == null) {
252 throw "No pid in ${event}";
253 }
254 var tid = event['tid'];
255 if (tid == null) {
256 throw "No tid in ${event}";
257 }
258 var thread = _findOrAddProcessThread(pid, tid);
259 if (thread == null) {
260 throw "No thread list returned.";
261 }
262 thread.add(event);
263 }
264 }
265 }
266
267 int _compare(Map a, Map b) {
268 if (a['ts'] > b['ts']) {
269 return 1;
270 } else if (a['ts'] < b['ts']) {
271 return -1;
272 }
273 return 0;
274 }
275
276 void _sortEvents() {
277 _processes.forEach((k, Map process) {
278 process.forEach((k, List thread) {
279 mergeSort(thread, compare:_compare);
280 });
281 });
282 }
283
284 void _mergeEventsForThread(List thread) {
285 List<Map> stack = [];
286 int stackDepth = 0;
287 thread.forEach((event) {
288 if (event['ph'] == 'B') {
289 if (stackDepth == stack.length) {
290 stack.add(null);
291 }
292 stackDepth++;
293 var end_event = stack[stackDepth - 1];
294 if (end_event != null) {
295 if (end_event['name'] == event['name'] && stackDepth > 1) {
296 // Kill these events.
297 // event['dead'] = true;
298 // end_event['dead'] = true;
299 }
300 }
301 } else {
302 if (event['ph'] != 'E') {
303 throw 'Expected E event: ${event}';
304 }
305 if (stackDepth <= 0) {
306 throw 'Stack out of sync ${event}.';
307 }
308 stackDepth--;
309 stack[stackDepth] = event;
310 }
311 });
312 }
313
314 void _mergeEvents() {
315 _processes.forEach((k, Map process) {
316 process.forEach((k, List thread) {
317 _mergeEventsForThread(thread);
318 });
319 });
320 }
321
322 void writeEventsToFile(String name) {
323 var file = new File(name);
324 List final_events = _metaEvents;
325 _processes.forEach((pid, Map process) {
326 process.forEach((tid, List thread) {
327 thread.forEach((event) {
328 if (event['dead'] == null) {
329 // Not dead.
330 final_events.add(event);
331 }
332 });
333 });
334 });
335 file.writeAsStringSync(JSON.encode(final_events));
336 }
337
338 void merge(List<String> inputs) {
339 for (var i = 0; i < inputs.length; i++) {
340 _processEventsFromFile(inputs[i]);
341 }
342 _sortEvents();
343 _mergeEvents();
344 }
345 }
346
347 main(List<String> arguments) {
348 if (arguments.length < 2) {
349 print('${Platform.executable} ${Platform.script} <output> <inputs>');
350 return;
351 }
352 String output = arguments[0];
353 List<String> inputs = new List<String>();
354 for (var i = 1; i < arguments.length; i++) {
355 inputs.add(arguments[i]);
356 }
357 print('Merging $inputs into $output.');
358 TraceMerge tm = new TraceMerge();
359 tm.merge(inputs);
360 tm.writeEventsToFile(output);
361 }
OLDNEW
« 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