OLD | NEW |
| (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 } | |
OLD | NEW |