addons/shared/__tests__/LRU.test.tsblame
View source
b69ab311/**
b69ab312 * Copyright (c) Meta Platforms, Inc. and affiliates.
b69ab313 *
b69ab314 * This source code is licensed under the MIT license found in the
b69ab315 * LICENSE file in the root directory of this source tree.
b69ab316 */
b69ab317
b69ab318import type {LRUWithStats} from '../LRU';
b69ab319
b69ab3110import {List, Record} from 'immutable';
b69ab3111import {cached, cachedMethod, clearTrackedCache, LRU} from '../LRU';
b69ab3112import {SelfUpdate} from '../immutableExt';
b69ab3113
b69ab3114describe('LRU', () => {
b69ab3115 it('evicts oldest items after reaching the max', () => {
b69ab3116 const lru = new LRU(3);
b69ab3117 lru.set(1, 1);
b69ab3118 lru.set(2, 2);
b69ab3119 lru.set(3, 3);
b69ab3120 lru.set(4, 4);
b69ab3121 expect(lru.get(4)).toEqual(4);
b69ab3122 expect(lru.get(3)).toEqual(3);
b69ab3123 expect(lru.get(2)).toEqual(2);
b69ab3124 expect(lru.get(1)).toEqual(undefined);
b69ab3125 });
b69ab3126
b69ab3127 it('refreshes items on get', () => {
b69ab3128 const lru = new LRU(3);
b69ab3129 lru.set(1, 1);
b69ab3130 lru.set(2, 2);
b69ab3131 lru.set(3, 3);
b69ab3132 expect(lru.get(1)).toEqual(1);
b69ab3133 lru.set(4, 4);
b69ab3134 expect(lru.get(2)).toEqual(undefined);
b69ab3135 expect(lru.get(3)).toEqual(3);
b69ab3136 expect(lru.get(4)).toEqual(4);
b69ab3137 });
b69ab3138
b69ab3139 it('refreshes items on set', () => {
b69ab3140 const lru = new LRU(3);
b69ab3141 lru.set(1, 1);
b69ab3142 lru.set(2, 2);
b69ab3143 lru.set(3, 3);
b69ab3144 lru.set(4, 4);
b69ab3145 lru.set(1, 1.1);
b69ab3146 expect(lru.get(4)).toEqual(4);
b69ab3147 expect(lru.get(3)).toEqual(3);
b69ab3148 expect(lru.get(2)).toEqual(undefined);
b69ab3149 expect(lru.get(1)).toEqual(1.1);
b69ab3150 });
b69ab3151
b69ab3152 it('can delete items', () => {
b69ab3153 const lru = new LRU(3);
b69ab3154 lru.set(1, 1);
b69ab3155 lru.set(2, 2);
b69ab3156 lru.set(3, 3);
b69ab3157 lru.delete(3);
b69ab3158 lru.set(4, 4);
b69ab3159 expect(lru.get(4)).toEqual(4);
b69ab3160 expect(lru.get(3)).toEqual(undefined);
b69ab3161 expect(lru.get(2)).toEqual(2);
b69ab3162 expect(lru.get(1)).toEqual(1);
b69ab3163 });
b69ab3164
b69ab3165 it('allows storing falsey values', () => {
b69ab3166 const lru = new LRU(8);
b69ab3167 lru.set(1, null);
b69ab3168 lru.set(2, undefined);
b69ab3169 lru.set(3, '');
b69ab3170 lru.set(4, false);
b69ab3171 const emptyArray: Array<number> = [];
b69ab3172 lru.set(5, emptyArray);
b69ab3173 const emptyObject = {};
b69ab3174 lru.set(6, emptyObject);
b69ab3175
b69ab3176 expect(lru.get(1)).toBe(null);
b69ab3177 expect(lru.get(2)).toBe(undefined);
b69ab3178 expect(lru.get(3)).toBe('');
b69ab3179 expect(lru.get(4)).toBe(false);
b69ab3180 expect(lru.get(5)).toBe(emptyArray);
b69ab3181 expect(lru.get(6)).toBe(emptyObject);
b69ab3182 });
b69ab3183
b69ab3184 it('allows falsey keys', () => {
b69ab3185 const lru = new LRU(8);
b69ab3186 lru.set(null, 1);
b69ab3187 lru.set(undefined, 2);
b69ab3188 lru.set('', 3);
b69ab3189 lru.set(false, 4);
b69ab3190 const emptyArray: Array<number> = [];
b69ab3191 lru.set(emptyArray, 5);
b69ab3192 const emptyObject = {};
b69ab3193 lru.set(emptyObject, 6);
b69ab3194
b69ab3195 expect(lru.get(null)).toBe(1);
b69ab3196 expect(lru.get(undefined)).toBe(2);
b69ab3197 expect(lru.get('')).toBe(3);
b69ab3198 expect(lru.get(false)).toBe(4);
b69ab3199 expect(lru.get(emptyArray)).toBe(5);
b69ab31100 expect(lru.get(emptyObject)).toBe(6);
b69ab31101 });
b69ab31102
b69ab31103 it('undefined keys are evictable', () => {
b69ab31104 const lru = new LRU(2);
b69ab31105 lru.set(undefined, 1);
b69ab31106 lru.set(2, 2);
b69ab31107 lru.set(3, 3);
b69ab31108
b69ab31109 expect(lru.get(undefined)).toBe(undefined);
b69ab31110 });
b69ab31111
b69ab31112 it('setting an undefined value does not take space in the cache', () => {
b69ab31113 const lru = new LRU(2);
b69ab31114 lru.set(1, undefined);
b69ab31115 lru.set(2, null);
b69ab31116 lru.set(3, undefined);
b69ab31117 lru.set(4, null);
b69ab31118 lru.set(5, undefined);
b69ab31119 lru.set(6, undefined);
b69ab31120
b69ab31121 expect(lru.get(1)).toBe(undefined);
b69ab31122 expect(lru.get(2)).toBe(null);
b69ab31123 expect(lru.get(3)).toBe(undefined);
b69ab31124 expect(lru.get(4)).toBe(null);
b69ab31125 expect(lru.get(5)).toBe(undefined);
b69ab31126 expect(lru.get(6)).toBe(undefined);
b69ab31127 });
b69ab31128
b69ab31129 it('works with SelfUpdate keys to avoid repetitive deepEquals', () => {
b69ab31130 const ListEqualsMock = jest.spyOn(List.prototype, 'equals');
b69ab31131
b69ab31132 type NestedList = List<number | NestedList>;
b69ab31133 const nestedList = (level: number): NestedList =>
b69ab31134 level <= 0 ? List([10]) : List([nestedList(level - 1)]);
b69ab31135
b69ab31136 const list1 = new SelfUpdate(nestedList(10));
b69ab31137 const list2 = new SelfUpdate(nestedList(10));
b69ab31138
b69ab31139 const lru = new LRU(1);
b69ab31140 lru.set(list1, 'x');
b69ab31141
b69ab31142 expect(lru.get(list2)).toBe('x');
b69ab31143 expect(ListEqualsMock).toHaveBeenCalledTimes(11);
b69ab31144 ListEqualsMock.mockClear();
b69ab31145
b69ab31146 // SelfUpdate avoids deepEquals after the first lru.get().
b69ab31147 expect(lru.get(list2)).toBe('x');
b69ab31148 expect(ListEqualsMock).toHaveBeenCalledTimes(1);
b69ab31149 ListEqualsMock.mockClear();
b69ab31150
b69ab31151 // SelfUpdate can be used in a nested structure.
b69ab31152 const list3 = List([List([new SelfUpdate(nestedList(8))])]);
b69ab31153 const list4 = List([List([new SelfUpdate(nestedList(8))])]);
b69ab31154
b69ab31155 lru.set(list3, 'y');
b69ab31156 expect(lru.get(list4)).toBe('y');
b69ab31157 expect(ListEqualsMock).toHaveBeenCalledTimes(11);
b69ab31158 ListEqualsMock.mockClear();
b69ab31159
b69ab31160 expect(lru.get(list4)).toBe('y');
b69ab31161 expect(ListEqualsMock).toHaveBeenCalledTimes(3);
b69ab31162 ListEqualsMock.mockClear();
b69ab31163
b69ab31164 ListEqualsMock.mockRestore();
b69ab31165 });
b69ab31166});
b69ab31167
b69ab31168describe('LRU benchmark', () => {
b69ab31169 const getLru = new LRU(1000);
b69ab31170 const n = 1000;
b69ab31171 for (let i = 0; i < n; i++) {
b69ab31172 getLru.set(List([i]), i);
b69ab31173 }
b69ab31174
b69ab31175 it('get() with a large cache size', () => {
b69ab31176 for (let j = 0; j < 100; j++) {
b69ab31177 let equalCount = 0;
b69ab31178 for (let i = 0; i < n; i++) {
b69ab31179 const item = getLru.get(List([i]));
b69ab31180 equalCount += item === i ? 1 : 0;
b69ab31181 }
b69ab31182 expect(equalCount).toBe(n);
b69ab31183 }
b69ab31184 });
b69ab31185
b69ab31186 it('set() with a large cache size', () => {
b69ab31187 const setLru = new LRU(1000);
b69ab31188 for (let j = 0; j < 100; j++) {
b69ab31189 for (let i = 0; i < n; i++) {
b69ab31190 setLru.set(List([i]), i);
b69ab31191 }
b69ab31192 }
b69ab31193 });
b69ab31194});
b69ab31195
b69ab31196describe('cached()', () => {
b69ab31197 describe('for pure functions', () => {
b69ab31198 it('works for pure function', () => {
b69ab31199 let calledTimes = 0;
b69ab31200 const fib = cached((n: number): number => {
b69ab31201 calledTimes += 1;
b69ab31202 return n < 2 ? n : fib(n - 1) + fib(n - 2);
b69ab31203 });
b69ab31204 expect(fib(20)).toBe(6765);
b69ab31205 expect(calledTimes).toBe(21);
b69ab31206 });
b69ab31207
b69ab31208 it('takes user-provided cache', () => {
b69ab31209 const cache = new LRU(10);
b69ab31210 const fib = cached(
b69ab31211 (n: number): number => {
b69ab31212 return n < 2 ? n : fib(n - 1) + fib(n - 2);
b69ab31213 },
b69ab31214 {cache},
b69ab31215 );
b69ab31216 expect(fib(20)).toBe(6765);
b69ab31217 expect(cache.get(List([20]))).toBe(6765);
b69ab31218 });
b69ab31219
b69ab31220 it('provides access to cache via func.cache', () => {
b69ab31221 const fib = cached((n: number): number => {
b69ab31222 return n < 2 ? n : fib(n - 1) + fib(n - 2);
b69ab31223 });
b69ab31224 expect(fib(20)).toBe(6765);
b69ab31225 expect(fib.cache.get(List([20]))).toBe(6765);
b69ab31226 });
b69ab31227
b69ab31228 it('counts cache miss and hit if cache.stats is present', () => {
b69ab31229 const fib = cached((n: number): number => {
b69ab31230 return n < 2 ? n : fib(n - 1) + fib(n - 2);
b69ab31231 });
b69ab31232 fib.cache.stats = {};
b69ab31233 expect(fib(20)).toBe(6765);
b69ab31234 expect(fib.cache.stats).toMatchObject({hit: 18, miss: 21});
b69ab31235 });
b69ab31236
b69ab31237 it('caches async results', async () => {
b69ab31238 let calledTimes = 0;
b69ab31239 const fib = cached(async (n: number): Promise<number> => {
b69ab31240 calledTimes += 1;
b69ab31241 return n < 2 ? n : (await fib(n - 1)) + (await fib(n - 2));
b69ab31242 });
b69ab31243 expect(await fib(20)).toBe(6765);
b69ab31244 expect(calledTimes).toBe(21);
b69ab31245 });
b69ab31246
b69ab31247 it('skips cache if an arg is non-cachable', () => {
b69ab31248 const max = cached((a: number, b: number, map?: (v: number) => number): number => {
b69ab31249 const pickA = map == null ? a > b : map(a) > map(b);
b69ab31250 return pickA ? a : b;
b69ab31251 });
b69ab31252 const stats = (max.cache.stats = {});
b69ab31253 // number is cacheable.
b69ab31254 expect(max(1, 2) + max(1, 2)).toBe(4);
b69ab31255 expect(stats).toMatchObject({hit: 1, miss: 1});
b69ab31256 // function is not cacheable.
b69ab31257 expect(max(1, 2, v => 3 - v) + max(1, 2, v => 3 - v)).toBe(2);
b69ab31258 expect(max(1, 2, v => v)).toBe(2);
b69ab31259 expect(stats).toMatchObject({skip: 3});
b69ab31260 });
b69ab31261
b69ab31262 it('can audit results', () => {
b69ab31263 let n = 0;
b69ab31264 const inc = cached(
b69ab31265 (rhs: number): number => {
b69ab31266 n += 1;
b69ab31267 return n + rhs;
b69ab31268 },
b69ab31269 {audit: true},
b69ab31270 );
b69ab31271 expect(inc(1)).toBe(2);
b69ab31272 expect(() => inc(1)).toThrow();
b69ab31273 });
b69ab31274 });
b69ab31275
b69ab31276 describe('for class methods', () => {
b69ab31277 it('can be used as a decorator', () => {
b69ab31278 let calledTimes = 0;
b69ab31279 class Fib {
b69ab31280 @cached()
b69ab31281 fib(n: number): number {
b69ab31282 calledTimes += 1;
b69ab31283 return n < 2 ? n : this.fib(n - 1) + this.fib(n - 2);
b69ab31284 }
b69ab31285 }
b69ab31286 const f = new Fib();
b69ab31287 expect(f.fib(20)).toBe(6765);
b69ab31288 expect(calledTimes).toBe(21);
b69ab31289 });
b69ab31290
b69ab31291 it('takes properties as extra cache keys', () => {
b69ab31292 const cache: LRUWithStats = new LRU(10);
b69ab31293 class Add {
b69ab31294 // lhs will be used as an extra cache key.
b69ab31295 lhs: number;
b69ab31296 constructor(lhs: number) {
b69ab31297 this.lhs = lhs;
b69ab31298 }
b69ab31299 @cached({cache})
b69ab31300 add(rhs: number): number {
b69ab31301 return this.lhs + rhs;
b69ab31302 }
b69ab31303 }
b69ab31304 const stats = (cache.stats = {});
b69ab31305 const a1 = new Add(100);
b69ab31306 const a2 = new Add(200);
b69ab31307 // `add(5)` for both a1 and a2. No cache hit since lhs is different.
b69ab31308 expect(a1.add(5)).toBe(105);
b69ab31309 expect(a2.add(5)).toBe(205);
b69ab31310 expect(stats).toMatchObject({miss: 2});
b69ab31311 // `a3.add(5)` gets a cache hit, since a3.lhs == a1.lhs.
b69ab31312 const a3 = new Add(200);
b69ab31313 expect(a3.add(5)).toBe(205);
b69ab31314 expect(stats).toMatchObject({hit: 1});
b69ab31315 });
b69ab31316
b69ab31317 it('takes immutable object as an extra key', () => {
b69ab31318 const cache: LRUWithStats = new LRU(10);
b69ab31319 // Position is an immutable Record, and will be used as an extra cache key.
b69ab31320 class Position extends Record({x: 10, y: 20}) {
b69ab31321 @cached({cache})
b69ab31322 offset(dx: number, dy: number): [number, number] {
b69ab31323 return [this.x + dx, this.y + dy];
b69ab31324 }
b69ab31325 }
b69ab31326 const stats = (cache.stats = {});
b69ab31327 const p1 = new Position();
b69ab31328 const p2 = new Position({x: 30, y: 40});
b69ab31329 [...Array(3)].forEach(() => {
b69ab31330 expect(p1.offset(1, 2)).toMatchObject([11, 22]);
b69ab31331 });
b69ab31332 expect(stats).toMatchObject({miss: 1, hit: 2});
b69ab31333 [...Array(3)].forEach(() => {
b69ab31334 expect(p2.offset(1, 2)).toMatchObject([31, 42]);
b69ab31335 });
b69ab31336 expect(stats).toMatchObject({miss: 2, hit: 4});
b69ab31337 // p3 is a different instance, but can reuse p2 cache
b69ab31338 // since Immutable.is(p2, p3).
b69ab31339 const p3 = new Position({x: 30, y: 40});
b69ab31340 expect(p3).not.toBe(p1);
b69ab31341 expect(p3.offset(1, 2)).toMatchObject([31, 42]);
b69ab31342 expect(stats).toMatchObject({miss: 2, hit: 5});
b69ab31343 });
b69ab31344
b69ab31345 it('can audit results', () => {
b69ab31346 let n = 0;
b69ab31347 class Impure {
b69ab31348 @cached({audit: true})
b69ab31349 inc(rhs: number): number {
b69ab31350 n += 1;
b69ab31351 return n + rhs;
b69ab31352 }
b69ab31353 }
b69ab31354 const obj = new Impure();
b69ab31355 expect(obj.inc(1)).toBe(2);
b69ab31356 expect(() => obj.inc(1)).toThrow();
b69ab31357 });
b69ab31358
b69ab31359 it('can clear cache', () => {
b69ab31360 let fCalled = 0;
b69ab31361 let gCalled = 0;
b69ab31362
b69ab31363 class A {
b69ab31364 @cached({track: true})
b69ab31365 f() {
b69ab31366 fCalled += 1;
b69ab31367 return 1;
b69ab31368 }
b69ab31369 @cached({track: false})
b69ab31370 g() {
b69ab31371 gCalled += 1;
b69ab31372 return 1;
b69ab31373 }
b69ab31374 }
b69ab31375
b69ab31376 const a = new A();
b69ab31377 a.f();
b69ab31378 a.f();
b69ab31379 a.g();
b69ab31380 a.g();
b69ab31381 expect(fCalled).toBe(1);
b69ab31382 expect(gCalled).toBe(1);
b69ab31383 clearTrackedCache();
b69ab31384 a.f();
b69ab31385 a.g();
b69ab31386 expect(fCalled).toBe(2);
b69ab31387 expect(gCalled).toBe(1);
b69ab31388 });
b69ab31389 });
b69ab31390});
b69ab31391
b69ab31392describe('cachedMethod', () => {
b69ab31393 it('is an alternative to `@cached()` decorator', () => {
b69ab31394 let calledTimes = 0;
b69ab31395 class Fib {
b69ab31396 fib = cachedMethod(this.fibImpl);
b69ab31397 fibImpl(n: number): number {
b69ab31398 calledTimes += 1;
b69ab31399 return n < 2 ? n : this.fib(n - 1) + this.fib(n - 2);
b69ab31400 }
b69ab31401 }
b69ab31402 const f = new Fib();
b69ab31403 expect(f.fib(20)).toBe(6765);
b69ab31404 expect(calledTimes).toBe(21);
b69ab31405 // Note new Fib() instance does not share the cache like the decorator version.
b69ab31406 const f2 = new Fib();
b69ab31407 expect(f2.fib(20)).toBe(6765);
b69ab31408 expect(calledTimes).toBe(42);
b69ab31409 });
b69ab31410
b69ab31411 it('supports shared cache among instances', () => {
b69ab31412 let calledTimes = 0;
b69ab31413 const cache: LRUWithStats = new LRU(10);
b69ab31414 class Fib {
b69ab31415 fib = cachedMethod(this.fibImpl, {cache});
b69ab31416 fibImpl(n: number): number {
b69ab31417 calledTimes += 1;
b69ab31418 return n < 2 ? n : this.fib(n - 1) + this.fib(n - 2);
b69ab31419 }
b69ab31420 }
b69ab31421 const f1 = new Fib();
b69ab31422 const f2 = new Fib();
b69ab31423 expect(f1.fib(20)).toBe(6765);
b69ab31424 expect(calledTimes).toBe(21);
b69ab31425 expect(f2.fib(20)).toBe(6765);
b69ab31426 expect(calledTimes).toBe(21); // f2 reuses f1's cache.
b69ab31427 });
b69ab31428
b69ab31429 it('considers state of `this`', () => {
b69ab31430 let calledTimes = 0;
b69ab31431 class Add {
b69ab31432 constructor(public n: number) {}
b69ab31433 add: (n: number) => number = cachedMethod(this.addImpl);
b69ab31434 addImpl(n: number): number {
b69ab31435 calledTimes += 1;
b69ab31436 return this.n + n;
b69ab31437 }
b69ab31438 }
b69ab31439 const a = new Add(10);
b69ab31440 expect(a.add(5)).toBe(15);
b69ab31441 expect(calledTimes).toBe(1);
b69ab31442 a.n = 20;
b69ab31443 expect(a.add(5)).toBe(25); // `this` changed
b69ab31444 expect(calledTimes).toBe(2);
b69ab31445 a.n = 10;
b69ab31446 expect(a.add(5)).toBe(15);
b69ab31447 expect(calledTimes).toBe(2); // reused cache
b69ab31448 });
b69ab31449});