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

Side by Side Diff: runtime/observatory/lib/object_graph.dart

Issue 2480293003: Observatory: Add view of dominator tree with siblings merged by class. (Closed)
Patch Set: . Created 4 years, 1 month 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
OLDNEW
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
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
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
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
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
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 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698