1f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)# Copyright 2013 The Chromium Authors. All rights reserved. 2f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)# Use of this source code is governed by a BSD-style license that can be 3f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)# found in the LICENSE file. 45f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 55f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)from telemetry.value import failure 65f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)from telemetry.value import skip 75f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 86e8cce623b6e4fe0c9e4af605d675dd9d0338c38Torne (Richard Coles) 9f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)def MergeLikeValuesFromSamePage(all_values): 10f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) """Merges values that measure the same thing on the same page. 11f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 12f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) A page may end up being measured multiple times, meaning that we may end up 13f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) with something like this: 14f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) ScalarValue(page1, 'x', 1) 15f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) ScalarValue(page2, 'x', 4) 16f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) ScalarValue(page1, 'x', 2) 17f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) ScalarValue(page2, 'x', 5) 18f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 19f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) This function will produce: 20f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) ListOfScalarValues(page1, 'x', [1, 2]) 21f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) ListOfScalarValues(page2, 'x', [4, 5]) 22f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 23f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) The workhorse of this code is Value.MergeLikeValuesFromSamePage. 24f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 25f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) This requires (but assumes) that the values passed in with the same grouping 26f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) key pass the Value.IsMergableWith test. If this is not obeyed, the 27f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) results will be undefined. 28f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) """ 29f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return _MergeLikeValuesCommon( 30f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) all_values, 31f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) lambda x: (x.page, x.name), 32f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) lambda v0, merge_group: v0.MergeLikeValuesFromSamePage(merge_group)) 33f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 34f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 35f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)def MergeLikeValuesFromDifferentPages(all_values, group_by_name_suffix=False): 36f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) """Merges values that measure the same thing on different pages. 37f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 38f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) After using MergeLikeValuesFromSamePage, one still ends up with values from 39f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) different pages: 40f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) ScalarValue(page1, 'x', 1) 41f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) ScalarValue(page1, 'y', 30) 42f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) ScalarValue(page2, 'x', 2) 43f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) ScalarValue(page2, 'y', 40) 44f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 45f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) This function will group the values of the same value_name together: 46f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) ListOfScalarValues(None, 'x', [1, 2]) 47f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) ListOfScalarValues(None, 'y', [30, 40]) 48f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 49f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) If group_by_name_suffix is True, then x.z and y.z are considered to be the 50f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) same value and are grouped together. If false, then x.z and y.z are 51f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) considered different. 52f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 53f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) The workhorse of this code is Value.MergeLikeValuesFromDifferentPages. 54f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 55f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) Not all values that go into this function will come out: not every value can 56f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) be merged across pages. Values whose MergeLikeValuesFromDifferentPages returns 57f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) None will be omitted from the results. 58f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 59f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) This requires (but assumes) that the values passed in with the same name pass 60f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) the Value.IsMergableWith test. If this is not obeyed, the results 61f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) will be undefined. 62f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) """ 63f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) if group_by_name_suffix: 64f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) def key(value): 65f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return value.name_suffix 66f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) else: 67f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) key = lambda x: x.name 68f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return _MergeLikeValuesCommon( 69f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) all_values, 70f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) key, 71f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) lambda v0, merge_group: v0.MergeLikeValuesFromDifferentPages( 72f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) merge_group, group_by_name_suffix=group_by_name_suffix)) 73f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 74f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 75f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)def _MergeLikeValuesCommon(all_values, key_func, merge_func): 76f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) """Groups all_values by key_func then applies merge_func to the groups. 77f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 78f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) This takes the all_values list and groups each item in that using the key 79f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) provided by key_func. This produces groups of values with like keys. Thes are 80f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) then handed to the merge_func to produce a new key. If merge_func produces a 81f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) non-None return, it is added to the list of returned values. 82f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) """ 83f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) # When merging, we want to merge values in a consistent order, e.g. so that 84f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) # Scalar(1), Scalar(2) predictably produces ListOfScalarValues([1,2]) rather 85f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) # than 2,1. 86f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) # 87f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) # To do this, the values are sorted by key up front. Then, grouping is 88f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) # performed using a dictionary, but as new groups are found, the order in 89f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) # which they were found is also noted. 90f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) # 91f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) # Merging is then performed on groups in group-creation-order. This ensures 92f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) # that the returned array is in a stable order, group by group. 93f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) # 94f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) # Within a group, the order is stable because of the original sort. 95f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) all_values = list(all_values) 96f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) merge_groups = GroupStably(all_values, key_func) 97f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 98f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) res = [] 99f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) for merge_group in merge_groups: 100f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) v0 = merge_group[0] 101f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) vM = merge_func(v0, merge_group) 102f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) if vM: 103f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) res.append(vM) 104f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return res 105f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 106f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles)def GroupStably(all_values, key_func): 107f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) """Groups an array by key_func, with the groups returned in a stable order. 108f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 109f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) Returns a list of groups. 110f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) """ 111f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) all_values = list(all_values) 112f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) 113f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) merge_groups = {} 114f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) merge_groups_in_creation_order = [] 115f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) for value in all_values: 1165f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) # TODO(chrishenry): This is temporary. When we figure out the 1175f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) # right summarization strategy for page runs with failures/skips, we 1185f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) # should use that instead. 1195f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) should_skip_value = (isinstance(value, failure.FailureValue) or 1205f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) isinstance(value, skip.SkipValue)) 1215f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 1225f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) if should_skip_value: 1235f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) continue 1245f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) 125f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) key = key_func(value) 126f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) if key not in merge_groups: 127f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) merge_groups[key] = [] 128f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) merge_groups_in_creation_order.append(merge_groups[key]) 129f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) merge_groups[key].append(value) 130f2477e01787aa58f445919b809d89e252beef54fTorne (Richard Coles) return merge_groups_in_creation_order 131