binary_size: Avoid creating nodes with many thousand children.

tools/binary_size/run_binary_size_analysis.py

 #!/usr/bin/env python
 # Copyright 2014 The Chromium Authors. All rights reserved.
 # Use of this source code is governed by a BSD-style license that can be
 # found in the LICENSE file.
 
 """Generate a spatial analysis against an arbitrary library.
 
 To use, build the 'binary_size_tool' target. Then run this tool, passing
 in the location of the library to be analyzed along with any other options
 you desire.
@@ skipping 43 matching lines @@
 # TODO(andrewhayden): Only used for legacy reports. Delete.
 def SymbolTypeToHuman(symbol_type):
   """Convert a symbol type as printed by nm into a human-readable name."""
   return {'b': 'bss',
           'd': 'data',
           'r': 'read-only data',
           't': 'code',
           'w': 'weak symbol',
           'v': 'weak symbol'}[symbol_type]
 
+# Node dictionary keys. These are output in json read by the webapp so
+# keep them short to save file size.
+# Note: If these change, the webapp must also change.
+NODE_TYPE_KEY = 'k'

[Primiano Tucci (use gerrit), 2014/05/27 09:24:17]

Globals and constatns should go between imports and the first top level
class/function (i.e. on line 27). Remember two newlines between top levels (i.e.
between import and globals, and one between globals and the first def)

[Daniel Bratell, 2014/06/04 13:04:45]

Done.

+NODE_NAME_KEY = 'n'
+NODE_CHILDREN_KEY = 'children'
+NODE_SYMBOL_TYPE_KEY = 't'
+NODE_SYMBOL_SIZE_KEY = 'value'
+NODE_MAX_DEPTH_KEY = 'maxDepth'
+NODE_LAST_PATH_ELEMENT_KEY = 'lastPathElement'
 
 def _MkChild(node, name):
-  child = node['children'].get(name)
+  child = node[NODE_CHILDREN_KEY].get(name)

[Primiano Tucci (use gerrit), 2014/05/27 09:24:17]

To be honest, sounds like your nodes should start being typed objects at this
point, something like

class Node(object):
  def __init__(self, ...):
    self.name = ...
    self.children = ...

instead of keep defining constants to populate a dictionary with well known
keys. That's why python objects are essentially dictionaries, to avoid you
hacking dictionaries yourself.

[Daniel Bratell, 2014/06/04 13:04:45]

I agree, but I'd prefer to postpone that change to a later cleanup pass. It
would require some custom serialization code since the structures need to look
as dicts when serialized through json so it is big enough to warrant a pass of
its own.

   if child is None:
-    child = {'n': name, 'children': {}}
-    node['children'][name] = child
+    child = {NODE_NAME_KEY: name,
+             NODE_CHILDREN_KEY: {}}
+    node[NODE_CHILDREN_KEY][name] = child
   return child
 
 
+BIG_BUCKET_LIMIT = 2000

[Primiano Tucci (use gerrit), 2014/05/27 09:24:17]

Ditto. Globals should live all together happily in the initial part of the
module.

[Andrew Hayden (chromium.org), 2014/05/27 10:04:11]

Minor nit, the review says 3k and this constant is initialized to 2k.

[Daniel Bratell, 2014/06/04 13:04:45]

Done.

[Daniel Bratell, 2014/06/04 13:04:45]

Done.

+
+
+def SplitNoPathBucket(node):
+  """(No Path) can be too large for the graphing lib to handle. Split
+  it into sub-buckets in that case."""
+  root_children = node[NODE_CHILDREN_KEY]
+  if '(No Path)' in root_children:

[Andrew Hayden (chromium.org), 2014/05/27 10:04:11]

We should probably extract the string "(No Path)" into a constant at this point,
or keep a special reference to it around.

[Daniel Bratell, 2014/06/04 13:04:45]

Done.

+    no_path_bucket = root_children['(No Path)']
+    old_children = no_path_bucket[NODE_CHILDREN_KEY]
+    count = 0
+    for symbol_type, symbol_bucket in old_children.iteritems():
+      count += len(symbol_bucket[NODE_CHILDREN_KEY])
+    if count > BIG_BUCKET_LIMIT:
+      new_children = {}
+      no_path_bucket[NODE_CHILDREN_KEY] = new_children
+      current_bucket = None
+      index = 0
+      for symbol_type, symbol_bucket in old_children.iteritems():
+        for symbol_name, value in symbol_bucket[NODE_CHILDREN_KEY].iteritems():
+          if index % BIG_BUCKET_LIMIT == 0:
+            group_no = (index / BIG_BUCKET_LIMIT) + 1
+            current_bucket = _MkChild(no_path_bucket,
+                                      '(No Path) subgroup %d' % group_no)
+            assert not NODE_TYPE_KEY in node or node[NODE_TYPE_KEY] == 'p'
+            node[NODE_TYPE_KEY] = 'p' # p for path
+          index += 1
+          symbol_size = value[NODE_SYMBOL_SIZE_KEY]
+          AddSymbolIntoFileNode(current_bucket, symbol_type,
+                                symbol_name, symbol_size)
+      no_path_bucket[NODE_CHILDREN_KEY] = new_children

[Primiano Tucci (use gerrit), 2014/05/27 09:24:17]

Uh? Looks like you already did this on line 99? Or am I missing something?

[Daniel Bratell, 2014/06/04 13:04:45]

Yes, duplicate assignments. Fixed.

+
+
 def MakeChildrenDictsIntoLists(node):
   largest_list_len = 0
-  if 'children' in node:
-    largest_list_len = len(node['children'])
+  if NODE_CHILDREN_KEY in node:
+    largest_list_len = len(node[NODE_CHILDREN_KEY])
     child_list = []
-    for child in node['children'].itervalues():
+    for child in node[NODE_CHILDREN_KEY].itervalues():
       child_largest_list_len = MakeChildrenDictsIntoLists(child)
       if child_largest_list_len > largest_list_len:
         largest_list_len = child_largest_list_len
       child_list.append(child)
-    node['children'] = child_list
+    node[NODE_CHILDREN_KEY] = child_list
 
   return largest_list_len
 
 
+def AddSymbolIntoFileNode(node, symbol_type, symbol_name, symbol_size):
+  """Puts symbol into the file path node |node|. Returns the number of

[Primiano Tucci (use gerrit), 2014/05/27 09:24:17]

Nit: the first line of a docstring should fit in one line. Eventually, the rest
can go after one blank line, i.e.:

"""Puts symbol into the file path node |node|.

Returns the number of added levels in tree. I.e. returns 2."""

Also, from a purely latin roots standpoint, that should be "e.g.," not "i.e."...
unless all your trees in this module are of height two, in which case this
function should just "return 2" :)

[Daniel Bratell, 2014/06/04 13:04:45]

They are always of height 2. :-)

This is extracted code. I kept the code that became more or less meaningless as
a documentation to the reader. Changed it to "return 2" with a comment.

As you may have noticed I like doing multiple pass over code when refactoring
it. If every pass does a relatively small change it becomes easier to review and
harder to introduce bugs. It also makes the refactorings focus in on the areas
where they have the most values. Otherwise my experience is that refactorings
can become depth-first and you end up cleaning up code nobody ever reads and
that worked perfectly well.

+  added levels in tree. I.e. returns 2."""
+
+  depth = 0

[Andrew Hayden (chromium.org), 2014/05/27 10:04:11]

From a clarity standpoint I'd prefer if we avoid the raw word "depth" here,
since there's already an absolute notion of depth in each node. How about
"levels_added" or "deepend_by", etc?

[Daniel Bratell, 2014/06/04 13:04:45]

Done.

+
+  # 'node' is now the file node. Find the symbol-type bucket.

[Andrew Hayden (chromium.org), 2014/05/27 10:04:11]

The first part of this comment made sense in-situ, but now that you've
transplanted it you could probably ditch this comment.

[Daniel Bratell, 2014/06/04 13:04:45]

Done.

+  node[NODE_LAST_PATH_ELEMENT_KEY] = True
+  node = _MkChild(node, symbol_type)
+  assert not NODE_TYPE_KEY in node or node[NODE_TYPE_KEY] == 'b'
+  node[NODE_SYMBOL_TYPE_KEY] = symbol_type
+  node[NODE_TYPE_KEY] = 'b' # b for bucket
+  depth += 1
+
+  # 'node' is now the symbol-type bucket. Make the child entry.
+  node = _MkChild(node, symbol_name)
+  if NODE_CHILDREN_KEY in node:
+    if node[NODE_CHILDREN_KEY]:
+      logging.warning('A container node used as symbol for %s.' % symbol_name)
+    # This is going to be used as a leaf so no use for child list.
+    del node[NODE_CHILDREN_KEY]
+  node[NODE_SYMBOL_SIZE_KEY] = symbol_size
+  node[NODE_SYMBOL_TYPE_KEY] = symbol_type
+  node[NODE_TYPE_KEY] = 's' # s for symbol
+  depth += 1
+  return depth
+
+
 def MakeCompactTree(symbols):
-  result = {'n': '/', 'children': {}, 'k': 'p', 'maxDepth': 0}
+  result = {NODE_NAME_KEY: '/',
+            NODE_CHILDREN_KEY: {},
+            NODE_TYPE_KEY: 'p',
+            NODE_MAX_DEPTH_KEY: 0}
   seen_symbol_with_path = False
   for symbol_name, symbol_type, symbol_size, file_path in symbols:
 
     if 'vtable for ' in symbol_name:
       symbol_type = '@' # hack to categorize these separately
     # Take path like '/foo/bar/baz', convert to ['foo', 'bar', 'baz']
     if file_path:
       file_path = os.path.normpath(file_path)
       seen_symbol_with_path = True
     else:
       file_path = '(No Path)'
 
     if file_path.startswith('/'):
       file_path = file_path[1:]
     path_parts = file_path.split('/')
 
     # Find pre-existing node in tree, or update if it already exists
     node = result
     depth = 0
     while len(path_parts) > 0:
       path_part = path_parts.pop(0)
       if len(path_part) == 0:
         continue
       depth += 1
       node = _MkChild(node, path_part)
-      assert not 'k' in node or node['k'] == 'p'
-      node['k'] = 'p' # p for path
+      assert not NODE_TYPE_KEY in node or node[NODE_TYPE_KEY] == 'p'
+      node[NODE_TYPE_KEY] = 'p' # p for path

[Primiano Tucci (use gerrit), 2014/05/27 09:24:17]

Nit: add an extra space before #

 
-    # 'node' is now the file node. Find the symbol-type bucket.
-    node['lastPathElement'] = True
-    node = _MkChild(node, symbol_type)
-    assert not 'k' in node or node['k'] == 'b'
-    node['t'] = symbol_type
-    node['k'] = 'b' # b for bucket
-    depth += 1
-
-    # 'node' is now the symbol-type bucket. Make the child entry.
-    node = _MkChild(node, symbol_name)
-    if 'children' in node:
-      if node['children']:
-        logging.warning('A container node used as symbol for %s.' % symbol_name)
-      # This is going to be used as a leaf so no use for child list.
-      del node['children']
-    node['value'] = symbol_size
-    node['t'] = symbol_type
-    node['k'] = 's' # s for symbol
-    depth += 1
-    result['maxDepth'] = max(result['maxDepth'], depth)
+    depth += AddSymbolIntoFileNode(node, symbol_type, symbol_name, symbol_size)
+    result[NODE_MAX_DEPTH_KEY] = max(result[NODE_MAX_DEPTH_KEY], depth)
 
   if not seen_symbol_with_path:
     logging.warning('Symbols lack paths. Data will not be structured.')
 
+  # The (no path) bucket can be extremely large if we failed to get
+  # path information. Split it into subgroups if needed.
+  SplitNoPathBucket(result)
+
   largest_list_len = MakeChildrenDictsIntoLists(result)
 
-  if largest_list_len > 1000:
+  if largest_list_len > BIG_BUCKET_LIMIT:
     logging.warning('There are sections with %d nodes. '
                     'Results might be unusable.' % largest_list_len)
   return result
 
 
 # TODO(andrewhayden): Only used for legacy reports. Delete.
 def TreeifySymbols(symbols):
   """Convert symbols into a path-based tree, calculating size information
   along the way.
 
@@ skipping 526 matching lines @@
     print('Copying index.html')
     shutil.copy(os.path.join(template_src, 'index.html'), opts.destdir)
     shutil.copy(os.path.join(template_src, 'D3SymbolTreeMap.js'), opts.destdir)
 
   if opts.verbose:
     print 'Report saved to ' + opts.destdir + '/index.html'
 
 
 if __name__ == '__main__':
   sys.exit(main())