binary_size: Avoid creating nodes with many thousand children.

tools/binary_size/run_binary_size_analysis.py

Index: tools/binary_size/run_binary_size_analysis.py
diff --git a/tools/binary_size/run_binary_size_analysis.py b/tools/binary_size/run_binary_size_analysis.py
index 7647a22dcb69b351b429f0e6e35911dd39e1b8be..a6ab4976c92a8fccc31bfae95f085613bac5ce14 100755
--- a/tools/binary_size/run_binary_size_analysis.py
+++ b/tools/binary_size/run_binary_size_analysis.py
@@ -61,32 +61,107 @@ def SymbolTypeToHuman(symbol_type):
           '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:
 
@@ -112,36 +187,22 @@ def MakeCompactTree(symbols):
         continue
       depth += 1
       node = _MkChild(node, path_part)
-      assert not 'k' in node or node['k'] == 'p'
-      node['k'] = 'p' # p for path
-
-    # '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)
+      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 #

+
+    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