cluster.py 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415
  1. # Copyright 2018 The Chromium Authors. All rights reserved.
  2. # Use of this source code is governed by a BSD-style license that can be
  3. # found in the LICENSE file.
  4. """Clustering for function call-graph.
  5. See the Clustering class for a detailed description.
  6. """
  7. import collections
  8. import itertools
  9. import logging
  10. Neighbor = collections.namedtuple('Neighbor', ('src', 'dst', 'dist'))
  11. CalleeInfo = collections.namedtuple('CalleeInfo',
  12. ('index', 'callee_symbol',
  13. 'misses', 'caller_and_count'))
  14. CallerInfo = collections.namedtuple('CallerInfo', ('caller_symbol', 'count'))
  15. class Clustering:
  16. """Cluster symbols.
  17. We are given a list of the first function calls, ordered by
  18. time. There are multiple lists: different benchmarks run multiple
  19. times, as well as list from startup and then a second list after
  20. startup (5 seconds) that runs until the benchmark memory dump.
  21. We have evidence (see below) that this simple ordering of code from a
  22. single profiling run (a load of a website) improves performance,
  23. presumably by improving code locality. To reconstruct this ordering
  24. using profiling information from multiple files, we cluster. Doing
  25. this clustering over multiple runs on the speedometer benchmark
  26. recovered speedometer performance compared with the legacy benchmark.
  27. For each offset list, we record the distances between each symbol and
  28. its neighborhood of the following k symbols (k=19, chosen
  29. arbitrarily). For example, if we have an offset list of symbols
  30. 'abcdef', we add the neighbors (a->b, 1), (a->c, 2), (b->c, 1), (b->e,
  31. 3), etc. Then we average distances of a given neighbor pair over all
  32. seen symbol lists. If we see an inversion (for example, (b->a, 3), we
  33. use this as a distance of -3). For each file that a given pair does
  34. not appear, that is, if the pair does not appear in that file or they
  35. are separated by 20 symbols, we use a large distance D (D=1000). The
  36. distances are then averages over all files. If the average is
  37. negative, the neighbor pair is inverted and the distance flipped. The
  38. idea is that if two symbols appear near each other in all profiling
  39. runs, there is high confidence that they are usually called
  40. together. If they don't appear near in some runs, there is less
  41. confidence that they should be colocated. Symbol distances are taken
  42. only as following distances to avoid confusing double-counting
  43. possibilities as well as to give a clear ordering to combining
  44. clusters.
  45. Neighbors are sorted, and starting with the shortest distance, symbols
  46. are coalesced into clusters. If the neighbor pair is (a->b), the
  47. clusters containing a and b are combined in that order. If a and b are
  48. already in the same cluster, nothing happens. After processing all
  49. neighbors there is usually only one cluster; if there are multiple
  50. clusters they are combined in order from largest to smallest (although
  51. that choice may not matter).
  52. Cluster merging may optionally be halted if they get above the size
  53. of an android page. As of November 2018 this slightly reduces
  54. performance and should not be used (1.7% decline in speedometer2,
  55. 450K native library memory regression).
  56. """
  57. NEIGHBOR_DISTANCE = 20
  58. FAR_DISTANCE = 1000
  59. MAX_CLUSTER_SIZE = 4096 # 4k pages on android.
  60. class _Cluster:
  61. def __init__(self, syms, size):
  62. assert len(set(syms)) == len(syms), 'Duplicated symbols in cluster'
  63. self._syms = syms
  64. self._size = size
  65. @property
  66. def syms(self):
  67. return self._syms
  68. @property
  69. def binary_size(self):
  70. return self._size
  71. @classmethod
  72. def ClusteredSymbolLists(cls, sym_lists, size_map):
  73. c = cls()
  74. c.AddSymbolLists(sym_lists)
  75. return c.ClusterToList(size_map)
  76. @classmethod
  77. def ClusterSymbolCallGraph(cls, call_graph, whitelist):
  78. c = cls()
  79. c.AddSymbolCallGraph(call_graph, whitelist)
  80. return c.ClusterToList()
  81. def __init__(self):
  82. self._num_lists = None
  83. self._neighbors = None
  84. self._cluster_map = {}
  85. self._symbol_size = lambda _: 0 # Maps a symbol to a size.
  86. def _MakeCluster(self, syms):
  87. c = self._Cluster(syms, sum(self._symbol_size(s) for s in syms))
  88. for s in syms:
  89. self._cluster_map[s] = c
  90. return c
  91. def ClusterOf(self, s):
  92. if isinstance(s, self._Cluster):
  93. assert self._cluster_map[s.syms[0]] == s
  94. return s
  95. if s in self._cluster_map:
  96. return self._cluster_map[s]
  97. return self._MakeCluster([s])
  98. def Combine(self, a, b):
  99. """Combine clusters.
  100. Args:
  101. a, b: Clusters or str. The canonical cluster (ClusterOf) will be
  102. used to do the combining.
  103. Returns:
  104. A merged cluster from a and b, or None if a and b are in the same cluster.
  105. """
  106. canonical_a = self.ClusterOf(a)
  107. canonical_b = self.ClusterOf(b)
  108. if canonical_a == canonical_b:
  109. return None
  110. return self._MakeCluster(canonical_a._syms + canonical_b._syms)
  111. def AddSymbolLists(self, sym_lists):
  112. self._num_lists = len(sym_lists)
  113. self._neighbors = self._CoalesceNeighbors(
  114. self._ConstructNeighbors(sym_lists))
  115. def AddSymbolCallGraph(self, call_graph, whitelist):
  116. self._num_lists = len(call_graph)
  117. self._neighbors = self._ConstructNeighborsFromGraph(call_graph, whitelist)
  118. def _ConstructNeighborsFromGraph(self, call_graph, whitelist):
  119. neighbors = []
  120. pairs = collections.defaultdict()
  121. # Each list item is a list of dict.
  122. for process_items in call_graph:
  123. for callee_info in process_items:
  124. callee = callee_info.callee_symbol
  125. for caller_info in callee_info.caller_and_count:
  126. caller = caller_info.caller_symbol
  127. if caller in whitelist or callee == caller:
  128. continue
  129. # Multiply by -1, the bigger the count the smaller the distance
  130. # should be.
  131. dist = caller_info.count * -1
  132. if (caller, callee) in pairs:
  133. pairs[(caller, callee)] += dist
  134. elif (callee, caller) in pairs:
  135. pairs[(callee, caller)] += dist
  136. else:
  137. pairs[(caller, callee)] = dist
  138. for (s, t) in pairs:
  139. assert s != t and (t, s) not in pairs, ('Unexpected shuffled pair:'
  140. ' ({}, {})'.format(s, t))
  141. neighbors.append(Neighbor(s, t, pairs[(s, t)]))
  142. return neighbors
  143. def _ConstructNeighbors(self, sym_lists):
  144. neighbors = []
  145. for sym_list in sym_lists:
  146. for i, s in enumerate(sym_list):
  147. for j in range(i + 1, min(i + self.NEIGHBOR_DISTANCE, len(sym_list))):
  148. if s == sym_list[j]:
  149. # Free functions that are static inline seem to be the only
  150. # source of these duplicates.
  151. continue
  152. neighbors.append(Neighbor(s, sym_list[j], j - i))
  153. logging.info('Constructed %s symbol neighbors', len(neighbors))
  154. return neighbors
  155. def _CoalesceNeighbors(self, neighbors):
  156. pairs = collections.defaultdict(list)
  157. for n in neighbors:
  158. pairs[(n.src, n.dst)].append(n.dist)
  159. coalesced = []
  160. logging.info('Will coalesce over %s neighbor pairs', len(pairs))
  161. count = 0
  162. for (s, t) in pairs:
  163. assert s != t, '{} != {}'.format(s, t)
  164. if (t, s) in pairs and t < s:
  165. # Only process each unordered pair once.
  166. continue
  167. count += 1
  168. if not (count % 1e6):
  169. logging.info('tick')
  170. distances = []
  171. if (s, t) in pairs:
  172. distances.extend(pairs[(s, t)])
  173. if (t, s) in pairs:
  174. distances.extend(-d for d in pairs[(t, s)])
  175. if distances:
  176. num_missing = self._num_lists - len(distances)
  177. avg_distance = (float(sum(distances)) +
  178. self.FAR_DISTANCE * num_missing) / self._num_lists
  179. if avg_distance > 0:
  180. coalesced.append(Neighbor(s, t, avg_distance))
  181. else:
  182. coalesced.append(Neighbor(t, s, avg_distance))
  183. return coalesced
  184. def ClusterToList(self, size_map=None):
  185. """Merge the clusters with the smallest distances.
  186. Args:
  187. size_map ({symbol: size} or None): Map symbol names to their size. Cluster
  188. growth will be stopped at MAX_CLUSTER_SIZE. If None, sizes are taken to
  189. be zero and cluster growth is not stopped.
  190. Returns:
  191. An ordered list of symbols from AddSymbolLists, appropriately clustered.
  192. """
  193. if size_map:
  194. self._symbol_size = lambda s: size_map[s]
  195. if not self._num_lists or not self._neighbors:
  196. # Some sort of trivial set of symbol lists, such as all being
  197. # length 1. Return an empty ordering.
  198. return []
  199. logging.info('Sorting %s neighbors', len(self._neighbors))
  200. self._neighbors.sort(key=lambda n: (-n.dist, n.src, n.dst))
  201. logging.info('Clustering...')
  202. count = 0
  203. while self._neighbors:
  204. count += 1
  205. if not (count % 1e6):
  206. logging.info('tock')
  207. neighbor = self._neighbors.pop()
  208. src = self.ClusterOf(neighbor.src)
  209. dst = self.ClusterOf(neighbor.dst)
  210. if (src == dst or
  211. src.binary_size + dst.binary_size > self.MAX_CLUSTER_SIZE):
  212. continue
  213. self.Combine(src, dst)
  214. if size_map:
  215. clusters_by_size = sorted(list(set(self._cluster_map.values())),
  216. key=lambda c: -c.binary_size)
  217. else:
  218. clusters_by_size = sorted(list(set(self._cluster_map.values())),
  219. key=lambda c: -len(c.syms))
  220. logging.info('Produced %s clusters', len(clusters_by_size))
  221. logging.info('Top sizes: %s', ['{}/{}'.format(len(c.syms), c.binary_size)
  222. for c in clusters_by_size[:4]])
  223. logging.info('Bottom sizes: %s', ['{}/{}'.format(len(c.syms), c.binary_size)
  224. for c in clusters_by_size[-4:]])
  225. ordered_syms = []
  226. for c in clusters_by_size:
  227. ordered_syms.extend(c.syms)
  228. assert len(ordered_syms) == len(set(ordered_syms)), 'Duplicated symbols!'
  229. return ordered_syms
  230. def _GetOffsetSymbolName(processor, dump_offset):
  231. dump_offset_to_symbol_info = \
  232. processor.GetDumpOffsetToSymboInfolIncludingWhitelist()
  233. offset_to_primary = processor.OffsetToPrimaryMap()
  234. idx = dump_offset // 2
  235. assert dump_offset >= 0 and idx < len(dump_offset_to_symbol_info), (
  236. 'Dump offset out of binary range')
  237. symbol_info = dump_offset_to_symbol_info[idx]
  238. assert symbol_info, ('A return address (offset = 0x{:08x}) does not map '
  239. 'to any symbol'.format(dump_offset))
  240. assert symbol_info.offset in offset_to_primary, (
  241. 'Offset not found in primary map!')
  242. return offset_to_primary[symbol_info.offset].name
  243. def _GetSymbolsCallGraph(profiles, processor):
  244. """Maps each offset in the call graph to the corresponding symbol name.
  245. Args:
  246. profiles (ProfileManager) Manager of the profile dump files.
  247. processor (SymbolOffsetProcessor) Symbol table processor for the dumps.
  248. Returns:
  249. A dict that maps each process type (ex: browser, renderer, etc.) to a list
  250. of processes of that type. Each process is a list that contains the
  251. call graph information. The call graph is represented by a list where each
  252. item is a dict that contains: callee, 3 caller-count pairs, misses.
  253. """
  254. offsets_graph = profiles.GetProcessOffsetGraph();
  255. process_symbols_graph = collections.defaultdict(list)
  256. # |process_type| can be : browser, renderer, gpu-process, etc.
  257. for process_type in offsets_graph:
  258. for process in offsets_graph[process_type]:
  259. process = sorted(process, key=lambda k: int(k['index']))
  260. graph_list = []
  261. for el in process:
  262. index = int(el['index'])
  263. callee_symbol = _GetOffsetSymbolName(processor,
  264. int(el['callee_offset']))
  265. misses = 0
  266. caller_and_count = []
  267. for bucket in el['caller_and_count']:
  268. caller_offset = int(bucket['caller_offset'])
  269. count = int(bucket['count'])
  270. if caller_offset == 0:
  271. misses += count
  272. continue
  273. caller_symbol_name = _GetOffsetSymbolName(processor, caller_offset)
  274. caller_info = CallerInfo(caller_symbol=caller_symbol_name,
  275. count=count)
  276. caller_and_count.append(caller_info)
  277. callee_info = CalleeInfo(index=index,
  278. callee_symbol=callee_symbol,
  279. misses=misses,
  280. caller_and_count=caller_and_count)
  281. graph_list.append(callee_info)
  282. process_symbols_graph[process_type].append(graph_list)
  283. return process_symbols_graph
  284. def _ClusterOffsetsFromCallGraph(profiles, processor):
  285. symbols_call_graph = _GetSymbolsCallGraph(profiles, processor)
  286. # Process names from the profile dumps that are treated specially.
  287. _RENDERER = 'renderer'
  288. _BROWSER = 'browser'
  289. assert _RENDERER in symbols_call_graph
  290. assert _BROWSER in symbols_call_graph
  291. whitelist = processor.GetWhitelistSymbols()
  292. renderer_clustering = Clustering.ClusterSymbolCallGraph(
  293. symbols_call_graph[_RENDERER], whitelist)
  294. browser_clustering = Clustering.ClusterSymbolCallGraph(
  295. symbols_call_graph[_BROWSER], whitelist)
  296. other_lists = []
  297. for process in symbols_call_graph:
  298. if process not in (_RENDERER, _BROWSER):
  299. other_lists.extend(symbols_call_graph[process])
  300. if other_lists:
  301. other_clustering = Clustering.ClusterSymbolCallGraph(other_lists, whitelist)
  302. else:
  303. other_clustering = []
  304. # Start with the renderer cluster to favor rendering performance.
  305. final_ordering = list(renderer_clustering)
  306. seen = set(final_ordering)
  307. final_ordering.extend(s for s in browser_clustering if s not in seen)
  308. seen |= set(browser_clustering)
  309. final_ordering.extend(s for s in other_clustering if s not in seen)
  310. return final_ordering
  311. def _ClusterOffsetsLists(profiles, processor, limit_cluster_size=False):
  312. raw_offsets = profiles.GetProcessOffsetLists()
  313. process_symbols = collections.defaultdict(list)
  314. seen_symbols = set()
  315. for p in raw_offsets:
  316. for offsets in raw_offsets[p]:
  317. symbol_names = processor.GetOrderedSymbols(
  318. processor.GetReachedOffsetsFromDump(offsets))
  319. process_symbols[p].append(symbol_names)
  320. seen_symbols |= set(symbol_names)
  321. if limit_cluster_size:
  322. name_map = processor.NameToSymbolMap()
  323. size_map = {name: name_map[name].size for name in seen_symbols}
  324. else:
  325. size_map = None
  326. # Process names from the profile dumps that are treated specially.
  327. _RENDERER = 'renderer'
  328. _BROWSER = 'browser'
  329. assert _RENDERER in process_symbols
  330. assert _BROWSER in process_symbols
  331. renderer_clustering = Clustering.ClusteredSymbolLists(
  332. process_symbols[_RENDERER], size_map)
  333. browser_clustering = Clustering.ClusteredSymbolLists(
  334. process_symbols[_BROWSER], size_map)
  335. other_lists = []
  336. for process, syms in process_symbols.items():
  337. if process not in (_RENDERER, _BROWSER):
  338. other_lists.extend(syms)
  339. if other_lists:
  340. other_clustering = Clustering.ClusteredSymbolLists(other_lists, size_map)
  341. else:
  342. other_clustering = []
  343. # Start with the renderer cluster to favor rendering performance.
  344. final_ordering = list(renderer_clustering)
  345. seen = set(final_ordering)
  346. final_ordering.extend(s for s in browser_clustering if s not in seen)
  347. seen |= set(browser_clustering)
  348. final_ordering.extend(s for s in other_clustering if s not in seen)
  349. return final_ordering
  350. def ClusterOffsets(profiles, processor, limit_cluster_size=False,
  351. call_graph=False):
  352. """Cluster profile offsets.
  353. Args:
  354. profiles (ProfileManager) Manager of the profile dump files.
  355. processor (SymbolOffsetProcessor) Symbol table processor for the dumps.
  356. call_graph (bool) whether the call graph instrumentation was used.
  357. Returns:
  358. A list of clustered symbol offsets.
  359. """
  360. if not call_graph:
  361. return _ClusterOffsetsLists(profiles, processor, limit_cluster_size)
  362. return _ClusterOffsetsFromCallGraph(profiles, processor)