chromium / chromium / src / 98e2e6b5887a2a70eceee641c1a8a44c35487a89 / . / tools / cygprofile / cluster.py

# Copyright 2018 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. | |

"""Clustering for function call-graph. | |

See the Clustering class for a detailed description. | |

""" | |

import collections | |

import itertools | |

import logging | |

Neighbor = collections.namedtuple('Neighbor', ('src', 'dst', 'dist')) | |

class Clustering(object): | |

"""Cluster symbols. | |

We are given a list of the first function calls, ordered by | |

time. There are multiple lists: different benchmarks run multiple | |

times, as well as list from startup and then a second list after | |

startup (5 seconds) that runs until the benchmark memory dump. | |

We have evidence (see below) that this simple ordering of code from a | |

single profiling run (a load of a website) improves performance, | |

presumably by improving code locality. To reconstruct this ordering | |

using profiling information from multiple files, we cluster. Doing | |

this clustering over multiple runs on the speedometer benchmark | |

recovered speedometer performance compared with the legacy benchmark. | |

For each offset list, we record the distances between each symbol and | |

its neighborhood of the following k symbols (k=19, chosen | |

arbitrarily). For example, if we have an offset list of symbols | |

'abcdef', we add the neighbors (a->b, 1), (a->c, 2), (b->c, 1), (b->e, | |

3), etc. Then we average distances of a given neighbor pair over all | |

seen symbol lists. If we see an inversion (for example, (b->a, 3), we | |

use this as a distance of -3). For each file that a given pair does | |

not appear, that is, if the pair does not appear in that file or they | |

are separated by 20 symbols, we use a large distance D (D=1000). The | |

distances are then averages over all files. If the average is | |

negative, the neighbor pair is inverted and the distance flipped. The | |

idea is that if two symbols appear near each other in all profiling | |

runs, there is high confidence that they are usually called | |

together. If they don't appear near in some runs, there is less | |

confidence that they should be colocated. Symbol distances are taken | |

only as following distances to avoid confusing double-counting | |

possibilities as well as to give a clear ordering to combining | |

clusters. | |

Neighbors are sorted, and starting with the shortest distance, symbols | |

are coalesced into clusters. If the neighbor pair is (a->b), the | |

clusters containing a and b are combined in that order. If a and b are | |

already in the same cluster, nothing happens. After processing all | |

neighbors there is usually only one cluster; if there are multiple | |

clusters they are combined in order from largest to smallest (although | |

that choice may not matter). | |

Cluster merging may optionally be halted if they get above the size | |

of an android page. As of November 2018 this slightly reduces | |

performance and should not be used (1.7% decline in speedometer2, | |

450K native library memory regression). | |

""" | |

NEIGHBOR_DISTANCE = 20 | |

FAR_DISTANCE = 1000 | |

MAX_CLUSTER_SIZE = 4096 # 4k pages on android. | |

class _Cluster(object): | |

def __init__(self, syms, size): | |

assert len(set(syms)) == len(syms), 'Duplicated symbols in cluster' | |

self._syms = syms | |

self._size = size | |

@property | |

def syms(self): | |

return self._syms | |

@property | |

def binary_size(self): | |

return self._size | |

@classmethod | |

def ClusteredSymbolLists(cls, sym_lists, size_map): | |

c = cls() | |

c.AddSymbolLists(sym_lists) | |

return c.ClusterToList(size_map) | |

def __init__(self): | |

self._num_lists = None | |

self._neighbors = None | |

self._cluster_map = {} | |

self._symbol_size = lambda _: 0 # Maps a symbol to a size. | |

def _MakeCluster(self, syms): | |

c = self._Cluster(syms, sum(self._symbol_size(s) for s in syms)) | |

for s in syms: | |

self._cluster_map[s] = c | |

return c | |

def ClusterOf(self, s): | |

if isinstance(s, self._Cluster): | |

assert self._cluster_map[s.syms[0]] == s | |

return s | |

if s in self._cluster_map: | |

return self._cluster_map[s] | |

return self._MakeCluster([s]) | |

def Combine(self, a, b): | |

"""Combine clusters. | |

Args: | |

a, b: Clusters or str. The canonical cluster (ClusterOf) will be | |

used to do the combining. | |

Returns: | |

A merged cluster from a and b, or None if a and b are in the same cluster. | |

""" | |

canonical_a = self.ClusterOf(a) | |

canonical_b = self.ClusterOf(b) | |

if canonical_a == canonical_b: | |

return None | |

return self._MakeCluster(canonical_a._syms + canonical_b._syms) | |

def AddSymbolLists(self, sym_lists): | |

self._num_lists = len(sym_lists) | |

self._neighbors = self._CoalesceNeighbors( | |

self._ConstructNeighbors(sym_lists)) | |

def _ConstructNeighbors(self, sym_lists): | |

neighbors = [] | |

for sym_list in sym_lists: | |

for i, s in enumerate(sym_list): | |

for j in xrange(i + 1, min(i + self.NEIGHBOR_DISTANCE, len(sym_list))): | |

if s == sym_list[j]: | |

# Free functions that are static inline seem to be the only | |

# source of these duplicates. | |

continue | |

neighbors.append(Neighbor(s, sym_list[j], j - i)) | |

logging.info('Constructed %s symbol neighbors', len(neighbors)) | |

return neighbors | |

def _CoalesceNeighbors(self, neighbors): | |

pairs = collections.defaultdict(list) | |

for n in neighbors: | |

pairs[(n.src, n.dst)].append(n.dist) | |

coalesced = [] | |

logging.info('Will coalesce over %s neighbor pairs', len(pairs)) | |

count = 0 | |

for (s, t) in pairs: | |

assert s != t, '{} != {}'.format(s, t) | |

if (t, s) in pairs and t < s: | |

# Only process each unordered pair once. | |

continue | |

count += 1 | |

if not (count % 1e6): | |

logging.info('tick') | |

distances = [] | |

if (s, t) in pairs: | |

distances.extend(pairs[(s, t)]) | |

if (t, s) in pairs: | |

distances.extend(-d for d in pairs[(t, s)]) | |

if distances: | |

num_missing = self._num_lists - len(distances) | |

avg_distance = (float(sum(distances)) + | |

self.FAR_DISTANCE * num_missing) / self._num_lists | |

if avg_distance > 0: | |

coalesced.append(Neighbor(s, t, avg_distance)) | |

else: | |

coalesced.append(Neighbor(t, s, avg_distance)) | |

return coalesced | |

def ClusterToList(self, size_map=None): | |

"""Merge the clusters with the smallest distances. | |

Args: | |

size_map ({symbol: size} or None): Map symbol names to their size. Cluster | |

growth will be stopped at MAX_CLUSTER_SIZE. If None, sizes are taken to | |

be zero and cluster growth is not stopped. | |

Returns: | |

An ordered list of symbols from AddSymbolLists, appropriately clustered. | |

""" | |

if size_map: | |

self._symbol_size = lambda s: size_map[s] | |

if not self._num_lists or not self._neighbors: | |

# Some sort of trivial set of symbol lists, such as all being | |

# length 1. Return an empty ordering. | |

return [] | |

logging.info('Sorting %s neighbors', len(self._neighbors)) | |

self._neighbors.sort(key=lambda n: (-n.dist, n.src, n.dst)) | |

logging.info('Clustering...') | |

count = 0 | |

while self._neighbors: | |

count += 1 | |

if not (count % 1e6): | |

logging.info('tock') | |

neighbor = self._neighbors.pop() | |

src = self.ClusterOf(neighbor.src) | |

dst = self.ClusterOf(neighbor.dst) | |

if (src == dst or | |

src.binary_size + dst.binary_size > self.MAX_CLUSTER_SIZE): | |

continue | |

self.Combine(src, dst) | |

if size_map: | |

clusters_by_size = sorted(list(set(self._cluster_map.values())), | |

key=lambda c: -c.binary_size) | |

else: | |

clusters_by_size = sorted(list(set(self._cluster_map.values())), | |

key=lambda c: -len(c.syms)) | |

logging.info('Produced %s clusters', len(clusters_by_size)) | |

logging.info('Top sizes: %s', ['{}/{}'.format(len(c.syms), c.binary_size) | |

for c in clusters_by_size[:4]]) | |

logging.info('Bottom sizes: %s', ['{}/{}'.format(len(c.syms), c.binary_size) | |

for c in clusters_by_size[-4:]]) | |

ordered_syms = [] | |

for c in clusters_by_size: | |

ordered_syms.extend(c.syms) | |

assert len(ordered_syms) == len(set(ordered_syms)), 'Duplicated symbols!' | |

return ordered_syms | |

def ClusterOffsets(profiles, processor, limit_cluster_size=False): | |

"""Cluster profile offsets. | |

Args: | |

profiles (ProfileManager) Manager of the profile dump files. | |

processor (SymbolOffsetProcessor) Symbol table processor for the dumps. | |

Returns: | |

A list of clustered symbol offsets. | |

""" | |

raw_offsets = profiles.GetProcessOffsetLists() | |

process_symbols = collections.defaultdict(list) | |

seen_symbols = set() | |

for p in raw_offsets: | |

for offsets in raw_offsets[p]: | |

symbol_names = processor.GetOrderedSymbols( | |

processor.GetReachedOffsetsFromDump(offsets)) | |

process_symbols[p].append(symbol_names) | |

seen_symbols |= set(symbol_names) | |

if limit_cluster_size: | |

name_map = processor.NameToSymbolMap() | |

size_map = {name: name_map[name].size for name in seen_symbols} | |

else: | |

size_map = None | |

# Process names from the profile dumps that are treated specially. | |

_RENDERER = 'renderer' | |

_BROWSER = 'browser' | |

assert _RENDERER in process_symbols | |

assert _BROWSER in process_symbols | |

renderer_clustering = Clustering.ClusteredSymbolLists( | |

process_symbols[_RENDERER], size_map) | |

browser_clustering = Clustering.ClusteredSymbolLists( | |

process_symbols[_BROWSER], size_map) | |

other_lists = [] | |

for process, syms in process_symbols.items(): | |

if process not in (_RENDERER, _BROWSER): | |

other_lists.extend(syms) | |

if other_lists: | |

other_clustering = Clustering.ClusteredSymbolLists(other_lists, size_map) | |

else: | |

other_clustering = [] | |

# Start with the renderer cluster to favor rendering performance. | |

final_ordering = [s for s in renderer_clustering] | |

seen = set(final_ordering) | |

final_ordering.extend(s for s in browser_clustering if s not in seen) | |

seen |= set(browser_clustering) | |

final_ordering.extend(s for s in other_clustering if s not in seen) | |

return final_ordering |