| 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 |
|---|
Chromium Code Reviews
