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, time, Time} from '../base/time'; 17 18export const BUCKETS_PER_PIXEL = 2; 19 20// CacheKey is a specific region of the timeline defined by the 21// following four properties: 22// - startNs 23// - endNs 24// - bucketNs 25// - windowSizePx 26// startNs is the beginning of the region in ns 27// endNs is the end of the region in ns 28// bucketNs is the size of a single bucket within the region which is 29// used for quantizing the timeline. 30// windowSizePx is the size of the whole window in pixels. 31// 32// In the nominal case bucketNs is 33// set so that 1px of the screen corresponds to N bucketNs worth of 34// time where 1 < N < 10. This ensures that we show the maximum 35// amount of data given the available screen real estate. 36// We shouldn't rely on this property when rendering however since in 37// some situations (i.e. after zooming before new data has loaded) it 38// may not be the case. 39// 40// CacheKey's can be 'normalized' - rounding the interval up and the 41// bucket size down. For a given CacheKey key ('foo') the normalized 42// version ('normal') has the properties: 43// normal.startNs <= foo.startNs 44// normal.endNs => foo.endNs 45// normal.bucketNs <= foo.bucketNs 46// normal.windowSizePx ~= windowSizePx (we round to the nearest 100px) 47// foo.isCoveredBy(foo) == true 48// foo.isCoveredBy(normal) == true 49// normal.isCoveredBy(normal) == true 50// normal.isCoveredBy(foo) == false unless normal == foo 51// normalize(normal) == normal 52// 53// In other words the normal window is a superset of the data of the 54// non-normal window at a higher resolution. Normalization is used to 55// avoid re-fetching data on tiny zooms/moves/resizes. 56export class CacheKey { 57 readonly start: time; 58 readonly end: time; 59 readonly bucketSize: duration; 60 readonly windowSizePx: number; 61 62 static create(startNs: time, endNs: time, windowSizePx: number): CacheKey { 63 const bucketNs = 64 (endNs - startNs) / BigInt(Math.round(windowSizePx * BUCKETS_PER_PIXEL)); 65 return new CacheKey( 66 startNs, 67 endNs, 68 BigintMath.max(1n, bucketNs), 69 windowSizePx, 70 ); 71 } 72 73 private constructor( 74 startNs: time, 75 endNs: time, 76 bucketNs: duration, 77 windowSizePx: number, 78 ) { 79 this.start = startNs; 80 this.end = endNs; 81 this.bucketSize = bucketNs; 82 this.windowSizePx = windowSizePx; 83 } 84 85 static zero(): CacheKey { 86 return new CacheKey(Time.ZERO, Time.ZERO, 0n, 100); 87 } 88 89 get normalizedBucketNs(): bigint { 90 // Round bucketNs down to the nearest smaller power of 2 (minimum 1): 91 return BigintMath.max(1n, BigintMath.bitFloor(this.bucketSize)); 92 } 93 94 get normalizedWindowSizePx(): number { 95 return Math.max(100, Math.round(this.windowSizePx / 100) * 100); 96 } 97 98 normalize(): CacheKey { 99 const windowSizePx = this.normalizedWindowSizePx; 100 const bucketNs = this.normalizedBucketNs; 101 const windowNs = BigInt(windowSizePx * BUCKETS_PER_PIXEL) * bucketNs; 102 const startNs = Time.quantFloor(this.start, windowNs); 103 const endNs = Time.quantCeil(this.end, windowNs); 104 return new CacheKey(startNs, endNs, bucketNs, windowSizePx); 105 } 106 107 isNormalized(): boolean { 108 return this.toString() === this.normalize().toString(); 109 } 110 111 isCoveredBy(other: CacheKey): boolean { 112 let r = true; 113 r = r && other.start <= this.start; 114 r = r && other.end >= this.end; 115 r = r && other.normalizedBucketNs === this.normalizedBucketNs; 116 r = r && other.normalizedWindowSizePx === this.normalizedWindowSizePx; 117 return r; 118 } 119 120 // toString is 'load bearing' in that it's used to key e.g. caches 121 // with CacheKey's. 122 toString() { 123 const start = this.start; 124 const end = this.end; 125 const bucket = this.bucketSize; 126 const size = this.windowSizePx; 127 return `CacheKey<${start}, ${end}, ${bucket}, ${size}>`; 128 } 129} 130