1// Copyright (C) 2023 The Android Open Source Project 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15import {BigintMath} from '../base/bigint_math'; 16import {Duration, duration} from '../base/time'; 17import {globals} from '../frontend/globals'; 18 19// We choose 100000 as the table size to cache as this is roughly the point 20// where SQLite sorts start to become expensive. 21const MIN_TABLE_SIZE_TO_CACHE = 100000; 22 23// Decides, based on the length of the trace and the number of rows 24// provided whether a TrackController subclass should cache its quantized 25// data. Returns the bucket size (in ns) if caching should happen and 26// undefined otherwise. 27export function calcCachedBucketSize(numRows: number): duration | undefined { 28 // Ensure that we're not caching when the table size isn't even that big. 29 if (numRows < MIN_TABLE_SIZE_TO_CACHE) { 30 return undefined; 31 } 32 33 const traceDuration = globals.stateTraceTimeTP().duration; 34 35 // For large traces, going through the raw table in the most zoomed-out 36 // states can be very expensive as this can involve going through O(millions 37 // of rows). The cost of this becomes high even for just iteration but is 38 // especially slow as quantization involves a SQLite sort on the quantized 39 // timestamp (for the group by). 40 // 41 // To get around this, we can cache a pre-quantized table which we can then 42 // in zoomed-out situations and fall back to the real table when zoomed in 43 // (which naturally constrains the amount of data by virtue of the window 44 // covering a smaller timespan) 45 // 46 // This method computes that cached table by computing an approximation for 47 // the bucket size we would use when totally zoomed out and then going a few 48 // resolution levels down which ensures that our cached table works for more 49 // than the literally most zoomed out state. Moving down a resolution level 50 // is defined as moving down a power of 2; this matches the logic in 51 // |globals.getCurResolution|. 52 // 53 // TODO(lalitm): in the future, we should consider having a whole set of 54 // quantized tables each of which cover some portion of resolution lvel 55 // range. As each table covers a large number of resolution levels, even 3-4 56 // tables should really cover the all concievable trace sizes. This set 57 // could be computed by looking at the number of events being processed one 58 // level below the cached table and computing another layer of caching if 59 // that count is too high (with respect to MIN_TABLE_SIZE_TO_CACHE). 60 61 // 4k monitors have 3840 horizontal pixels so use that for a worst case 62 // approximation of the window width. 63 const approxWidthPx = 3840n; 64 65 // Compute the outermost bucket size. This acts as a starting point for 66 // computing the cached size. 67 const outermostBucketSize = BigintMath.bitCeil(traceDuration / approxWidthPx); 68 const outermostResolutionLevel = BigintMath.log2(outermostBucketSize); 69 70 // This constant decides how many resolution levels down from our outermost 71 // bucket computation we want to be able to use the cached table. 72 // We've chosen 7 as it empirically seems to be a good fit for trace data. 73 const resolutionLevelsCovered = 7n; 74 75 // If we've got less resolution levels in the trace than the number of 76 // resolution levels we want to go down, bail out because this cached 77 // table is really not going to be used enough. 78 if (outermostResolutionLevel < resolutionLevelsCovered) { 79 return Duration.MAX; 80 } 81 82 // Another way to look at moving down resolution levels is to consider how 83 // many sub-intervals we are splitting the bucket into. 84 const bucketSubIntervals = 1n << resolutionLevelsCovered; 85 86 // Calculate the smallest bucket we want our table to be able to handle by 87 // dividing the outermsot bucket by the number of subintervals we should 88 // divide by. 89 const cachedBucketSize = outermostBucketSize / bucketSubIntervals; 90 91 return cachedBucketSize; 92} 93