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 {assertTrue} from '../base/logging'; 16 17export const BUCKETS_PER_PIXEL = 2; 18 19// CacheKey is a specific region of the timeline defined by the 20// following four properties: 21// - startNs 22// - endNs 23// - bucketNs 24// - windowSizePx 25// startNs is the beginning of the region in ns 26// endNs is the end of the region in ns 27// bucketNs is the size of a single bucket within the region which is 28// used for quantizing the timeline. 29// windowSizePx is the size of the whole window in pixels. 30// 31// In the nominal case bucketNs is 32// set so that 1px of the screen corresponds to N bucketNs worth of 33// time where 1 < N < 10. This ensures that we show the maximum 34// amount of data given the available screen real estate. 35// We shouldn't rely on this property when rendering however since in 36// some situations (i.e. after zooming before new data has loaded) it 37// may not be the case. 38// 39// CacheKey's can be 'normalized' - rounding the interval up and the 40// bucket size down. For a given CacheKey key ('foo') the normalized 41// version ('normal') has the properties: 42// normal.startNs <= foo.startNs 43// normal.endNs => foo.endNs 44// normal.bucketNs <= foo.bucketNs 45// normal.windowSizePx ~= windowSizePx (we round to the nearest 100px) 46// foo.isCoveredBy(foo) == true 47// foo.isCoveredBy(normal) == true 48// normal.isCoveredBy(normal) == true 49// normal.isCoveredBy(foo) == false unless normal == foo 50// normalize(normal) == normal 51// 52// In other words the normal window is a superset of the data of the 53// non-normal window at a higher resolution. Normalization is used to 54// avoid re-fetching data on tiny zooms/moves/resizes. 55// TODO(stevegolton): Convert to bigint timestamps. 56export class CacheKey { 57 readonly startNs: number; 58 readonly endNs: number; 59 readonly bucketNs: number; 60 readonly windowSizePx: number; 61 62 static create(startNs: number, endNs: number, windowSizePx: number): 63 CacheKey { 64 const bucketNs = (endNs - startNs) / (windowSizePx * BUCKETS_PER_PIXEL); 65 return new CacheKey(startNs, endNs, bucketNs, windowSizePx); 66 } 67 68 private constructor( 69 startNs: number, endNs: number, bucketNs: number, windowSizePx: number) { 70 this.startNs = startNs; 71 this.endNs = endNs; 72 this.bucketNs = bucketNs; 73 this.windowSizePx = windowSizePx; 74 } 75 76 static zero(): CacheKey { 77 return new CacheKey(0, 0, 0, 100); 78 } 79 80 get normalizedBucketNs(): number { 81 // Round bucketNs down to the nearest smaller power of 2 (minimum 1): 82 return Math.max(1, Math.pow(2, Math.floor(Math.log2(this.bucketNs)))); 83 } 84 85 get normalizedWindowSizePx(): number { 86 return Math.max(100, Math.round(this.windowSizePx / 100) * 100); 87 } 88 89 normalize(): CacheKey { 90 const windowSizePx = this.normalizedWindowSizePx; 91 const bucketNs = this.normalizedBucketNs; 92 const windowNs = windowSizePx * BUCKETS_PER_PIXEL * bucketNs; 93 const startNs = Math.floor(this.startNs / windowNs) * windowNs; 94 const endNs = Math.ceil(this.endNs / windowNs) * windowNs; 95 return new CacheKey(startNs, endNs, bucketNs, windowSizePx); 96 } 97 98 isNormalized(): boolean { 99 return this.toString() === this.normalize().toString(); 100 } 101 102 isCoveredBy(other: CacheKey): boolean { 103 let r = true; 104 r = r && other.startNs <= this.startNs; 105 r = r && other.endNs >= this.endNs; 106 r = r && other.normalizedBucketNs === this.normalizedBucketNs; 107 r = r && other.normalizedWindowSizePx === this.normalizedWindowSizePx; 108 return r; 109 } 110 111 // toString is 'load bearing' in that it's used to key e.g. caches 112 // with CacheKey's. 113 toString() { 114 const start = this.startNs; 115 const end = this.endNs; 116 const bucket = this.bucketNs; 117 const size = this.windowSizePx; 118 return `CacheKey<${start}, ${end}, ${bucket}, ${size}>`; 119 } 120} 121 122 123interface CacheItem<T> { 124 t: T; 125 lastAccessId: number; 126} 127 128 129// LRU cache for the tracks. 130// T is all the data needed for a displaying the track in a given 131// CacheKey area - generally an array of slices. 132export class TrackCache<T> { 133 private cacheSize: number; 134 private cache: Map<string, CacheItem<T>>; 135 private lastAccessId: number; 136 137 constructor(cacheSize: number) { 138 assertTrue(cacheSize >= 2); 139 this.cacheSize = cacheSize; 140 this.cache = new Map(); 141 this.lastAccessId = 0; 142 } 143 144 insert(cacheKey: CacheKey, t: T): void { 145 assertTrue(cacheKey.isNormalized()); 146 const key = cacheKey.toString(); 147 this.cache.set(key, { 148 t, 149 lastAccessId: this.lastAccessId++, 150 }); 151 this.updateLru(); 152 } 153 154 lookup(cacheKey: CacheKey): undefined|T { 155 assertTrue(cacheKey.isNormalized()); 156 const key = cacheKey.toString(); 157 const item = this.cache.get(key); 158 if (item) { 159 item.lastAccessId = this.lastAccessId++; 160 this.updateLru(); 161 } 162 return item === undefined ? undefined : item.t; 163 } 164 165 private updateLru(): void { 166 while (this.cache.size > this.cacheSize) { 167 let oldestKey = ''; 168 let oldestAccessId = Number.MAX_SAFE_INTEGER; 169 for (const [k, v] of this.cache.entries()) { 170 if (v.lastAccessId < oldestAccessId) { 171 oldestAccessId = v.lastAccessId; 172 oldestKey = k; 173 } 174 } 175 this.cache.delete(oldestKey); 176 } 177 } 178} 179