| # Copyright 2018 The Chromium Authors |
| # 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')) |
| CalleeInfo = collections.namedtuple('CalleeInfo', |
| ('index', 'callee_symbol', |
| 'misses', 'caller_and_count')) |
| CallerInfo = collections.namedtuple('CallerInfo', ('caller_symbol', 'count')) |
| |
| |
| class Clustering: |
| """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: |
| 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 range(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 _GetOffsetSymbolName(processor, dump_offset): |
| dump_offset_to_symbol_info = \ |
| processor.GetDumpOffsetToSymboInfolIncludingWhitelist() |
| offset_to_primary = processor.OffsetToPrimaryMap() |
| idx = dump_offset // 2 |
| assert dump_offset >= 0 and idx < len(dump_offset_to_symbol_info), ( |
| 'Dump offset out of binary range') |
| symbol_info = dump_offset_to_symbol_info[idx] |
| assert symbol_info, ('A return address (offset = 0x{:08x}) does not map ' |
| 'to any symbol'.format(dump_offset)) |
| assert symbol_info.offset in offset_to_primary, ( |
| 'Offset not found in primary map!') |
| return offset_to_primary[symbol_info.offset].name |
| |
| def _ClusterOffsetsLists(profiles, processor, limit_cluster_size=False): |
| 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 = list(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 |
| |
| |
| 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. |
| """ |
| return _ClusterOffsetsLists(profiles, processor, limit_cluster_size) |
