OLD | NEW |
---|---|
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 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. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 library object_graph; | 5 library object_graph; |
6 | 6 |
7 import 'dart:async'; | 7 import 'dart:async'; |
8 import 'dart:collection'; | 8 import 'dart:collection'; |
9 import 'dart:typed_data'; | 9 import 'dart:typed_data'; |
10 | 10 |
(...skipping 264 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
275 for (var childId = 1; childId <= N; childId++) { | 275 for (var childId = 1; childId <= N; childId++) { |
276 if (doms[childId] == parentId) { | 276 if (doms[childId] == parentId) { |
277 domChildren.add(new ObjectVertex._(childId, _graph)); | 277 domChildren.add(new ObjectVertex._(childId, _graph)); |
278 } | 278 } |
279 } | 279 } |
280 | 280 |
281 return domChildren; | 281 return domChildren; |
282 } | 282 } |
283 } | 283 } |
284 | 284 |
285 | |
286 class MergedObjectVertex { | |
Cutch
2016/11/14 17:24:13
Doc comment explaining what this represents at a h
rmacnak
2016/11/15 00:44:15
Added comment. This class does *not* implement Obj
| |
287 // 0 represents invalid/uninitialized, 1 is the root. | |
Cutch
2016/11/14 17:24:13
Let's use a constant for 0 where you mean the inva
| |
288 final int _id; | |
289 final ObjectGraph _graph; | |
290 | |
291 MergedObjectVertex._(this._id, this._graph); | |
292 | |
293 bool get isRoot => _id == 1; | |
294 | |
295 bool operator ==(other) => _id == other._id && _graph == other._graph; | |
296 int get hashCode => _id; | |
297 | |
298 int get vmCid => _graph._cids[_id]; | |
299 | |
300 int get shallowSize { | |
301 var cids = _graph._cids; | |
302 var size = 0; | |
303 var sibling = _id; | |
304 while (sibling != 0 && | |
305 cids[sibling] == cids[_id]) { | |
306 size += _graph._shallowSizes[sibling]; | |
307 sibling = _graph._mergedDomNext[sibling]; | |
308 } | |
309 return size; | |
310 } | |
311 int get retainedSize { | |
312 var cids = _graph._cids; | |
313 var size = 0; | |
314 var sibling = _id; | |
315 while (sibling != 0 && | |
Cutch
2016/11/14 17:24:13
here and elsewhere != invalidNodeIndex
| |
316 cids[sibling] == cids[_id]) { | |
317 size += _graph._retainedSizes[sibling]; | |
318 sibling = _graph._mergedDomNext[sibling]; | |
319 } | |
320 return size; | |
321 } | |
322 int get instanceCount { | |
323 var cids = _graph._cids; | |
324 var count = 0; | |
325 var sibling = _id; | |
326 while (sibling != 0 && | |
327 cids[sibling] == cids[_id]) { | |
328 count++; | |
329 sibling = _graph._mergedDomNext[sibling]; | |
330 } | |
331 return count; | |
332 } | |
333 | |
334 List<ObjectVertex> dominatorTreeChildren() { | |
335 var next = _graph._mergedDomNext; | |
336 var cids = _graph._cids; | |
337 | |
338 var domChildren = []; | |
339 var prev = 0; | |
340 var child = _graph._mergedDomHead[_id]; | |
341 while (child != 0) { | |
Cutch
2016/11/14 17:24:13
Scan the list of siblings, creating MergedObjectVe
rmacnak
2016/11/15 00:44:15
Done.
| |
342 if (prev == 0 || | |
343 cids[prev] != cids[child]) { | |
344 domChildren.add(new MergedObjectVertex._(child, _graph)); | |
345 } | |
346 prev = child; | |
347 child = next[child]; | |
348 } | |
349 | |
350 return domChildren; | |
351 } | |
352 } | |
353 | |
285 class _SuccessorsIterable extends IterableBase<ObjectVertex> { | 354 class _SuccessorsIterable extends IterableBase<ObjectVertex> { |
286 final ObjectGraph _graph; | 355 final ObjectGraph _graph; |
287 final int _id; | 356 final int _id; |
288 | 357 |
289 _SuccessorsIterable(this._graph, this._id); | 358 _SuccessorsIterable(this._graph, this._id); |
290 | 359 |
291 Iterator<ObjectVertex> get iterator => new _SuccessorsIterator(_graph, _id); | 360 Iterator<ObjectVertex> get iterator => new _SuccessorsIterator(_graph, _id); |
292 } | 361 } |
293 | 362 |
294 class _SuccessorsIterator implements Iterator<ObjectVertex> { | 363 class _SuccessorsIterator implements Iterator<ObjectVertex> { |
(...skipping 44 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
339 class ObjectGraph { | 408 class ObjectGraph { |
340 ObjectGraph(List<ByteData> chunks, int nodeCount) | 409 ObjectGraph(List<ByteData> chunks, int nodeCount) |
341 : this._chunks = chunks, | 410 : this._chunks = chunks, |
342 this._N = nodeCount; | 411 this._N = nodeCount; |
343 | 412 |
344 int get size => _size; | 413 int get size => _size; |
345 int get vertexCount => _N; | 414 int get vertexCount => _N; |
346 int get edgeCount => _E; | 415 int get edgeCount => _E; |
347 | 416 |
348 ObjectVertex get root => new ObjectVertex._(1, this); | 417 ObjectVertex get root => new ObjectVertex._(1, this); |
418 MergedObjectVertex get mergedRoot => new MergedObjectVertex._(1, this); | |
349 Iterable<ObjectVertex> get vertices => new _VerticesIterable(this); | 419 Iterable<ObjectVertex> get vertices => new _VerticesIterable(this); |
350 | 420 |
351 Iterable<ObjectVertex> getMostRetained({int classId, int limit}) { | 421 Iterable<ObjectVertex> getMostRetained({int classId, int limit}) { |
352 List<ObjectVertex> _mostRetained = | 422 List<ObjectVertex> _mostRetained = |
353 new List<ObjectVertex>.from(vertices.where((u) => !u.isRoot)); | 423 new List<ObjectVertex>.from(vertices.where((u) => !u.isRoot)); |
354 _mostRetained.sort((u, v) => v.retainedSize - u.retainedSize); | 424 _mostRetained.sort((u, v) => v.retainedSize - u.retainedSize); |
355 | 425 |
356 var result = _mostRetained; | 426 var result = _mostRetained; |
357 if (classId != null) { | 427 if (classId != null) { |
358 result = result.where((u) => u.vmCid == classId); | 428 result = result.where((u) => u.vmCid == classId); |
(...skipping 15 matching lines...) Expand all Loading... | |
374 | 444 |
375 controller.add(["Remapping $_E references...", 15.0]); | 445 controller.add(["Remapping $_E references...", 15.0]); |
376 await new Future(() => _remapEdges()); | 446 await new Future(() => _remapEdges()); |
377 | 447 |
378 _addrToId = null; | 448 _addrToId = null; |
379 _chunks = null; | 449 _chunks = null; |
380 | 450 |
381 controller.add(["Finding depth-first order...", 30.0]); | 451 controller.add(["Finding depth-first order...", 30.0]); |
382 await new Future(() => _dfs()); | 452 await new Future(() => _dfs()); |
383 | 453 |
384 controller.add(["Finding predecessors...", 45.0]); | 454 controller.add(["Finding predecessors...", 40.0]); |
385 await new Future(() => _buildPredecessors()); | 455 await new Future(() => _buildPredecessors()); |
386 | 456 |
387 controller.add(["Finding dominators...", 60.0]); | 457 controller.add(["Finding dominators...", 50.0]); |
388 await new Future(() => _buildDominators()); | 458 await new Future(() => _buildDominators()); |
389 | 459 |
390 _firstPreds = null; | 460 _firstPreds = null; |
391 _preds = null; | 461 _preds = null; |
392 | 462 |
393 _semi = null; | 463 _semi = null; |
394 _parent = null; | 464 _parent = null; |
395 | 465 |
396 controller.add(["Finding retained sizes...", 75.0]); | 466 controller.add(["Finding retained sizes...", 60.0]); |
397 await new Future(() => _calculateRetainedSizes()); | 467 await new Future(() => _calculateRetainedSizes()); |
398 | 468 |
399 _vertex = null; | 469 _vertex = null; |
400 | 470 |
401 controller.add(["Loaded", 100.0]); | 471 controller.add(["Linking dominator tree children...", 70.0]); |
472 await new Future(() => _linkDominatorChildren()); | |
473 | |
474 controller.add(["Sorting dominator tree children...", 80.0]); | |
475 await new Future(() => _sortDominatorChildren()); | |
476 | |
477 controller.add(["Merging dominator tree siblings...", 90.0]); | |
478 await new Future(() => _mergeDominatorSiblings()); | |
479 | |
480 controller.add(["Processed", 100.0]); | |
402 controller.close(); | 481 controller.close(); |
403 }()); | 482 }()); |
404 return controller.stream; | 483 return controller.stream; |
405 } | 484 } |
406 | 485 |
407 List<ByteData> _chunks; | 486 List<ByteData> _chunks; |
408 | 487 |
409 int _kObjectAlignment; | 488 int _kObjectAlignment; |
410 int _N; | 489 int _N; |
411 int _E; | 490 int _E; |
(...skipping 12 matching lines...) Expand all Loading... | |
424 AddressMapper _addrToId; | 503 AddressMapper _addrToId; |
425 Uint32List _vertex; | 504 Uint32List _vertex; |
426 Uint32List _parent; | 505 Uint32List _parent; |
427 Uint32List _semi; | 506 Uint32List _semi; |
428 Uint32List _firstPreds; // Offset into preds. | 507 Uint32List _firstPreds; // Offset into preds. |
429 Uint32List _preds; | 508 Uint32List _preds; |
430 | 509 |
431 // Outputs. | 510 // Outputs. |
432 Uint32List _doms; | 511 Uint32List _doms; |
433 Uint32List _retainedSizes; | 512 Uint32List _retainedSizes; |
513 Uint32List _mergedDomHead; | |
514 Uint32List _mergedDomNext; | |
434 | 515 |
435 void _remapNodes() { | 516 void _remapNodes() { |
436 var N = _N; | 517 var N = _N; |
437 var E = 0; | 518 var E = 0; |
438 var addrToId = new AddressMapper(N); | 519 var addrToId = new AddressMapper(N); |
439 | 520 |
440 var addressesHigh = new Uint32List(N + 1); | 521 var addressesHigh = new Uint32List(N + 1); |
441 var addressesLow = new Uint32List(N + 1); | 522 var addressesLow = new Uint32List(N + 1); |
442 var shallowSizes = new Uint32List(N + 1); | 523 var shallowSizes = new Uint32List(N + 1); |
443 var cids = new Uint16List(N + 1); | 524 var cids = new Uint16List(N + 1); |
(...skipping 361 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
805 // size, skipping root. | 886 // size, skipping root. |
806 for (var i = N; i > 1; i--) { | 887 for (var i = N; i > 1; i--) { |
807 var v = vertex[i]; | 888 var v = vertex[i]; |
808 assert(v != 1); | 889 assert(v != 1); |
809 retainedSizes[doms[i]] += retainedSizes[i]; | 890 retainedSizes[doms[i]] += retainedSizes[i]; |
810 } | 891 } |
811 | 892 |
812 _retainedSizes = retainedSizes; | 893 _retainedSizes = retainedSizes; |
813 _size = size; | 894 _size = size; |
814 } | 895 } |
896 | |
897 void _linkDominatorChildren() { | |
Cutch
2016/11/14 17:24:13
// Build a set of linked lists of children dominat
| |
898 var N = _N; | |
Cutch
2016/11/14 17:24:13
Let's start typing local variables ....
rmacnak
2016/11/15 00:44:15
Not while we can still write Dart.
| |
899 var doms = _doms; | |
900 var head = new Uint32List(N + 1); | |
Cutch
2016/11/14 17:24:13
We need to start commenting at a high level what i
| |
901 var next = new Uint32List(N + 1); | |
902 | |
903 for (var child = 1; child <= N; child++) { | |
904 var parent = doms[child]; | |
905 next[child] = head[parent]; | |
906 head[parent] = child; | |
907 } | |
908 | |
909 _mergedDomHead = head; | |
910 _mergedDomNext = next; | |
911 } | |
912 | |
913 static int _mergeSorted(int head1, int head2, | |
914 Uint32List next, Uint16List key) { | |
915 var head = head1; | |
916 var beforeInsert = 0; | |
917 var afterInsert = head1; | |
918 var startInsert = head2; | |
919 | |
920 while (startInsert != 0) { | |
921 while ((afterInsert != 0) && | |
922 (key[afterInsert] <= key[startInsert])) { | |
923 beforeInsert = afterInsert; | |
924 afterInsert = next[beforeInsert]; | |
925 } | |
926 | |
927 var endInsert = startInsert; | |
928 var peek = next[endInsert]; | |
929 | |
930 while ((peek != 0) && (key[peek] < key[afterInsert])) { | |
931 endInsert = peek; | |
932 peek = next[endInsert]; | |
933 } | |
934 assert(endInsert != 0); | |
935 | |
936 if (beforeInsert == 0) { | |
937 head = startInsert; | |
938 } else { | |
939 next[beforeInsert] = startInsert; | |
940 } | |
941 next[endInsert] = afterInsert; | |
942 | |
943 startInsert = peek; | |
944 beforeInsert = endInsert; | |
945 } | |
946 | |
947 return head; | |
948 } | |
949 | |
950 void _sortDominatorChildren() { | |
951 var N = _N; | |
952 var cids = _cids; | |
953 var head = _mergedDomHead; | |
954 var next = _mergedDomNext; | |
955 | |
956 int sort(int head) { | |
Cutch
2016/11/14 17:24:13
/// Returns the first node index in the list after
| |
957 if (head == 0) return 0; | |
Cutch
2016/11/14 17:24:13
... == invalidNodeIndex) {
return invalidNodeInd
| |
958 if (next[head] == 0) return head; | |
959 | |
Cutch
2016/11/14 17:24:13
// Determine the mid and end point of the list by
| |
960 int head1 = head; | |
961 int slow = head; | |
962 int fast = head; | |
963 while (next[fast] != 0 && | |
964 next[next[fast]] != 0) { | |
965 slow = next[slow]; | |
966 fast = next[next[fast]]; | |
967 } | |
968 | |
969 int head2 = next[slow]; | |
Cutch
2016/11/14 17:24:13
// Split the list in half.
| |
970 next[slow] = 0; | |
971 | |
972 assert(head1 != head2); | |
973 int newHead1 = sort(head1); | |
Cutch
2016/11/14 17:24:13
Recursively sort each of the sublists
| |
974 int newHead2 = sort(head2); | |
975 return _mergeSorted(newHead1, newHead2, next, cids); | |
Cutch
2016/11/14 17:24:13
Merge them
| |
976 } | |
977 | |
978 for (var parent = 1; parent <= N; parent++) { | |
Cutch
2016/11/14 17:24:13
Sort all of the merged dominator sibling lists so
| |
979 head[parent] = sort(head[parent]); | |
980 } | |
981 } | |
982 | |
983 void _mergeDominatorSiblings() { | |
984 var N = _N; | |
985 var cids = _cids; | |
986 var head = _mergedDomHead; | |
987 var next = _mergedDomNext; | |
988 var workStack = new Uint32List(N); | |
989 var workStackTop = 0; | |
990 | |
991 mergeChildrenAndSort(var parent1, var end) { | |
992 assert(parent1 != 0); | |
993 if (next[parent1] == end) return; | |
994 | |
995 int cid = cids[parent1]; | |
996 int slow = parent1; | |
997 int fast = parent1; | |
998 while (next[fast] != end && | |
999 next[next[fast]] != end) { | |
Cutch
2016/11/14 17:24:13
this should be factored out and reused with the co
| |
1000 slow = next[slow]; | |
1001 fast = next[next[fast]]; | |
1002 } | |
1003 | |
1004 int parent2 = next[slow]; | |
1005 | |
1006 assert(parent2 != 0); | |
1007 assert(parent1 != parent2); | |
1008 assert(cids[parent1] == cids[parent2]); | |
1009 | |
1010 mergeChildrenAndSort(parent1, parent2); | |
1011 mergeChildrenAndSort(parent2, end); | |
1012 | |
1013 head[parent1] = _mergeSorted(head[parent1], head[parent2], next, cids); | |
1014 head[parent2] = 0; | |
Cutch
2016/11/14 17:24:12
// We have merged the siblings of parent2 into par
| |
1015 } | |
1016 | |
1017 // Push root. | |
1018 workStack[workStackTop++] = 1; | |
1019 | |
1020 while (workStackTop > 0) { | |
1021 var parent = workStack[--workStackTop]; | |
1022 | |
1023 var prev = 0; | |
1024 var child = head[parent]; | |
1025 while (child != 0) { | |
1026 // Push child. | |
1027 workStack[workStackTop++] = child; | |
1028 | |
1029 // Next sibling with a different cid. | |
1030 var after = child; | |
1031 while (after != 0 && | |
1032 cids[after] == cids[child]) { | |
1033 after = next[after]; | |
1034 } | |
1035 | |
1036 mergeChildrenAndSort(child, after); | |
Cutch
2016/11/14 17:24:13
// child is the first node with cid A and after is
| |
1037 | |
1038 child = after; | |
1039 } | |
1040 } | |
1041 } | |
815 } | 1042 } |
OLD | NEW |