12.5 KB450 lines
Blame
1/**
2 * Copyright (c) Meta Platforms, Inc. and affiliates.
3 *
4 * This source code is licensed under the MIT license found in the
5 * LICENSE file in the root directory of this source tree.
6 */
7
8import type {LRUWithStats} from '../LRU';
9
10import {List, Record} from 'immutable';
11import {cached, cachedMethod, clearTrackedCache, LRU} from '../LRU';
12import {SelfUpdate} from '../immutableExt';
13
14describe('LRU', () => {
15 it('evicts oldest items after reaching the max', () => {
16 const lru = new LRU(3);
17 lru.set(1, 1);
18 lru.set(2, 2);
19 lru.set(3, 3);
20 lru.set(4, 4);
21 expect(lru.get(4)).toEqual(4);
22 expect(lru.get(3)).toEqual(3);
23 expect(lru.get(2)).toEqual(2);
24 expect(lru.get(1)).toEqual(undefined);
25 });
26
27 it('refreshes items on get', () => {
28 const lru = new LRU(3);
29 lru.set(1, 1);
30 lru.set(2, 2);
31 lru.set(3, 3);
32 expect(lru.get(1)).toEqual(1);
33 lru.set(4, 4);
34 expect(lru.get(2)).toEqual(undefined);
35 expect(lru.get(3)).toEqual(3);
36 expect(lru.get(4)).toEqual(4);
37 });
38
39 it('refreshes items on set', () => {
40 const lru = new LRU(3);
41 lru.set(1, 1);
42 lru.set(2, 2);
43 lru.set(3, 3);
44 lru.set(4, 4);
45 lru.set(1, 1.1);
46 expect(lru.get(4)).toEqual(4);
47 expect(lru.get(3)).toEqual(3);
48 expect(lru.get(2)).toEqual(undefined);
49 expect(lru.get(1)).toEqual(1.1);
50 });
51
52 it('can delete items', () => {
53 const lru = new LRU(3);
54 lru.set(1, 1);
55 lru.set(2, 2);
56 lru.set(3, 3);
57 lru.delete(3);
58 lru.set(4, 4);
59 expect(lru.get(4)).toEqual(4);
60 expect(lru.get(3)).toEqual(undefined);
61 expect(lru.get(2)).toEqual(2);
62 expect(lru.get(1)).toEqual(1);
63 });
64
65 it('allows storing falsey values', () => {
66 const lru = new LRU(8);
67 lru.set(1, null);
68 lru.set(2, undefined);
69 lru.set(3, '');
70 lru.set(4, false);
71 const emptyArray: Array<number> = [];
72 lru.set(5, emptyArray);
73 const emptyObject = {};
74 lru.set(6, emptyObject);
75
76 expect(lru.get(1)).toBe(null);
77 expect(lru.get(2)).toBe(undefined);
78 expect(lru.get(3)).toBe('');
79 expect(lru.get(4)).toBe(false);
80 expect(lru.get(5)).toBe(emptyArray);
81 expect(lru.get(6)).toBe(emptyObject);
82 });
83
84 it('allows falsey keys', () => {
85 const lru = new LRU(8);
86 lru.set(null, 1);
87 lru.set(undefined, 2);
88 lru.set('', 3);
89 lru.set(false, 4);
90 const emptyArray: Array<number> = [];
91 lru.set(emptyArray, 5);
92 const emptyObject = {};
93 lru.set(emptyObject, 6);
94
95 expect(lru.get(null)).toBe(1);
96 expect(lru.get(undefined)).toBe(2);
97 expect(lru.get('')).toBe(3);
98 expect(lru.get(false)).toBe(4);
99 expect(lru.get(emptyArray)).toBe(5);
100 expect(lru.get(emptyObject)).toBe(6);
101 });
102
103 it('undefined keys are evictable', () => {
104 const lru = new LRU(2);
105 lru.set(undefined, 1);
106 lru.set(2, 2);
107 lru.set(3, 3);
108
109 expect(lru.get(undefined)).toBe(undefined);
110 });
111
112 it('setting an undefined value does not take space in the cache', () => {
113 const lru = new LRU(2);
114 lru.set(1, undefined);
115 lru.set(2, null);
116 lru.set(3, undefined);
117 lru.set(4, null);
118 lru.set(5, undefined);
119 lru.set(6, undefined);
120
121 expect(lru.get(1)).toBe(undefined);
122 expect(lru.get(2)).toBe(null);
123 expect(lru.get(3)).toBe(undefined);
124 expect(lru.get(4)).toBe(null);
125 expect(lru.get(5)).toBe(undefined);
126 expect(lru.get(6)).toBe(undefined);
127 });
128
129 it('works with SelfUpdate keys to avoid repetitive deepEquals', () => {
130 const ListEqualsMock = jest.spyOn(List.prototype, 'equals');
131
132 type NestedList = List<number | NestedList>;
133 const nestedList = (level: number): NestedList =>
134 level <= 0 ? List([10]) : List([nestedList(level - 1)]);
135
136 const list1 = new SelfUpdate(nestedList(10));
137 const list2 = new SelfUpdate(nestedList(10));
138
139 const lru = new LRU(1);
140 lru.set(list1, 'x');
141
142 expect(lru.get(list2)).toBe('x');
143 expect(ListEqualsMock).toHaveBeenCalledTimes(11);
144 ListEqualsMock.mockClear();
145
146 // SelfUpdate avoids deepEquals after the first lru.get().
147 expect(lru.get(list2)).toBe('x');
148 expect(ListEqualsMock).toHaveBeenCalledTimes(1);
149 ListEqualsMock.mockClear();
150
151 // SelfUpdate can be used in a nested structure.
152 const list3 = List([List([new SelfUpdate(nestedList(8))])]);
153 const list4 = List([List([new SelfUpdate(nestedList(8))])]);
154
155 lru.set(list3, 'y');
156 expect(lru.get(list4)).toBe('y');
157 expect(ListEqualsMock).toHaveBeenCalledTimes(11);
158 ListEqualsMock.mockClear();
159
160 expect(lru.get(list4)).toBe('y');
161 expect(ListEqualsMock).toHaveBeenCalledTimes(3);
162 ListEqualsMock.mockClear();
163
164 ListEqualsMock.mockRestore();
165 });
166});
167
168describe('LRU benchmark', () => {
169 const getLru = new LRU(1000);
170 const n = 1000;
171 for (let i = 0; i < n; i++) {
172 getLru.set(List([i]), i);
173 }
174
175 it('get() with a large cache size', () => {
176 for (let j = 0; j < 100; j++) {
177 let equalCount = 0;
178 for (let i = 0; i < n; i++) {
179 const item = getLru.get(List([i]));
180 equalCount += item === i ? 1 : 0;
181 }
182 expect(equalCount).toBe(n);
183 }
184 });
185
186 it('set() with a large cache size', () => {
187 const setLru = new LRU(1000);
188 for (let j = 0; j < 100; j++) {
189 for (let i = 0; i < n; i++) {
190 setLru.set(List([i]), i);
191 }
192 }
193 });
194});
195
196describe('cached()', () => {
197 describe('for pure functions', () => {
198 it('works for pure function', () => {
199 let calledTimes = 0;
200 const fib = cached((n: number): number => {
201 calledTimes += 1;
202 return n < 2 ? n : fib(n - 1) + fib(n - 2);
203 });
204 expect(fib(20)).toBe(6765);
205 expect(calledTimes).toBe(21);
206 });
207
208 it('takes user-provided cache', () => {
209 const cache = new LRU(10);
210 const fib = cached(
211 (n: number): number => {
212 return n < 2 ? n : fib(n - 1) + fib(n - 2);
213 },
214 {cache},
215 );
216 expect(fib(20)).toBe(6765);
217 expect(cache.get(List([20]))).toBe(6765);
218 });
219
220 it('provides access to cache via func.cache', () => {
221 const fib = cached((n: number): number => {
222 return n < 2 ? n : fib(n - 1) + fib(n - 2);
223 });
224 expect(fib(20)).toBe(6765);
225 expect(fib.cache.get(List([20]))).toBe(6765);
226 });
227
228 it('counts cache miss and hit if cache.stats is present', () => {
229 const fib = cached((n: number): number => {
230 return n < 2 ? n : fib(n - 1) + fib(n - 2);
231 });
232 fib.cache.stats = {};
233 expect(fib(20)).toBe(6765);
234 expect(fib.cache.stats).toMatchObject({hit: 18, miss: 21});
235 });
236
237 it('caches async results', async () => {
238 let calledTimes = 0;
239 const fib = cached(async (n: number): Promise<number> => {
240 calledTimes += 1;
241 return n < 2 ? n : (await fib(n - 1)) + (await fib(n - 2));
242 });
243 expect(await fib(20)).toBe(6765);
244 expect(calledTimes).toBe(21);
245 });
246
247 it('skips cache if an arg is non-cachable', () => {
248 const max = cached((a: number, b: number, map?: (v: number) => number): number => {
249 const pickA = map == null ? a > b : map(a) > map(b);
250 return pickA ? a : b;
251 });
252 const stats = (max.cache.stats = {});
253 // number is cacheable.
254 expect(max(1, 2) + max(1, 2)).toBe(4);
255 expect(stats).toMatchObject({hit: 1, miss: 1});
256 // function is not cacheable.
257 expect(max(1, 2, v => 3 - v) + max(1, 2, v => 3 - v)).toBe(2);
258 expect(max(1, 2, v => v)).toBe(2);
259 expect(stats).toMatchObject({skip: 3});
260 });
261
262 it('can audit results', () => {
263 let n = 0;
264 const inc = cached(
265 (rhs: number): number => {
266 n += 1;
267 return n + rhs;
268 },
269 {audit: true},
270 );
271 expect(inc(1)).toBe(2);
272 expect(() => inc(1)).toThrow();
273 });
274 });
275
276 describe('for class methods', () => {
277 it('can be used as a decorator', () => {
278 let calledTimes = 0;
279 class Fib {
280 @cached()
281 fib(n: number): number {
282 calledTimes += 1;
283 return n < 2 ? n : this.fib(n - 1) + this.fib(n - 2);
284 }
285 }
286 const f = new Fib();
287 expect(f.fib(20)).toBe(6765);
288 expect(calledTimes).toBe(21);
289 });
290
291 it('takes properties as extra cache keys', () => {
292 const cache: LRUWithStats = new LRU(10);
293 class Add {
294 // lhs will be used as an extra cache key.
295 lhs: number;
296 constructor(lhs: number) {
297 this.lhs = lhs;
298 }
299 @cached({cache})
300 add(rhs: number): number {
301 return this.lhs + rhs;
302 }
303 }
304 const stats = (cache.stats = {});
305 const a1 = new Add(100);
306 const a2 = new Add(200);
307 // `add(5)` for both a1 and a2. No cache hit since lhs is different.
308 expect(a1.add(5)).toBe(105);
309 expect(a2.add(5)).toBe(205);
310 expect(stats).toMatchObject({miss: 2});
311 // `a3.add(5)` gets a cache hit, since a3.lhs == a1.lhs.
312 const a3 = new Add(200);
313 expect(a3.add(5)).toBe(205);
314 expect(stats).toMatchObject({hit: 1});
315 });
316
317 it('takes immutable object as an extra key', () => {
318 const cache: LRUWithStats = new LRU(10);
319 // Position is an immutable Record, and will be used as an extra cache key.
320 class Position extends Record({x: 10, y: 20}) {
321 @cached({cache})
322 offset(dx: number, dy: number): [number, number] {
323 return [this.x + dx, this.y + dy];
324 }
325 }
326 const stats = (cache.stats = {});
327 const p1 = new Position();
328 const p2 = new Position({x: 30, y: 40});
329 [...Array(3)].forEach(() => {
330 expect(p1.offset(1, 2)).toMatchObject([11, 22]);
331 });
332 expect(stats).toMatchObject({miss: 1, hit: 2});
333 [...Array(3)].forEach(() => {
334 expect(p2.offset(1, 2)).toMatchObject([31, 42]);
335 });
336 expect(stats).toMatchObject({miss: 2, hit: 4});
337 // p3 is a different instance, but can reuse p2 cache
338 // since Immutable.is(p2, p3).
339 const p3 = new Position({x: 30, y: 40});
340 expect(p3).not.toBe(p1);
341 expect(p3.offset(1, 2)).toMatchObject([31, 42]);
342 expect(stats).toMatchObject({miss: 2, hit: 5});
343 });
344
345 it('can audit results', () => {
346 let n = 0;
347 class Impure {
348 @cached({audit: true})
349 inc(rhs: number): number {
350 n += 1;
351 return n + rhs;
352 }
353 }
354 const obj = new Impure();
355 expect(obj.inc(1)).toBe(2);
356 expect(() => obj.inc(1)).toThrow();
357 });
358
359 it('can clear cache', () => {
360 let fCalled = 0;
361 let gCalled = 0;
362
363 class A {
364 @cached({track: true})
365 f() {
366 fCalled += 1;
367 return 1;
368 }
369 @cached({track: false})
370 g() {
371 gCalled += 1;
372 return 1;
373 }
374 }
375
376 const a = new A();
377 a.f();
378 a.f();
379 a.g();
380 a.g();
381 expect(fCalled).toBe(1);
382 expect(gCalled).toBe(1);
383 clearTrackedCache();
384 a.f();
385 a.g();
386 expect(fCalled).toBe(2);
387 expect(gCalled).toBe(1);
388 });
389 });
390});
391
392describe('cachedMethod', () => {
393 it('is an alternative to `@cached()` decorator', () => {
394 let calledTimes = 0;
395 class Fib {
396 fib = cachedMethod(this.fibImpl);
397 fibImpl(n: number): number {
398 calledTimes += 1;
399 return n < 2 ? n : this.fib(n - 1) + this.fib(n - 2);
400 }
401 }
402 const f = new Fib();
403 expect(f.fib(20)).toBe(6765);
404 expect(calledTimes).toBe(21);
405 // Note new Fib() instance does not share the cache like the decorator version.
406 const f2 = new Fib();
407 expect(f2.fib(20)).toBe(6765);
408 expect(calledTimes).toBe(42);
409 });
410
411 it('supports shared cache among instances', () => {
412 let calledTimes = 0;
413 const cache: LRUWithStats = new LRU(10);
414 class Fib {
415 fib = cachedMethod(this.fibImpl, {cache});
416 fibImpl(n: number): number {
417 calledTimes += 1;
418 return n < 2 ? n : this.fib(n - 1) + this.fib(n - 2);
419 }
420 }
421 const f1 = new Fib();
422 const f2 = new Fib();
423 expect(f1.fib(20)).toBe(6765);
424 expect(calledTimes).toBe(21);
425 expect(f2.fib(20)).toBe(6765);
426 expect(calledTimes).toBe(21); // f2 reuses f1's cache.
427 });
428
429 it('considers state of `this`', () => {
430 let calledTimes = 0;
431 class Add {
432 constructor(public n: number) {}
433 add: (n: number) => number = cachedMethod(this.addImpl);
434 addImpl(n: number): number {
435 calledTimes += 1;
436 return this.n + n;
437 }
438 }
439 const a = new Add(10);
440 expect(a.add(5)).toBe(15);
441 expect(calledTimes).toBe(1);
442 a.n = 20;
443 expect(a.add(5)).toBe(25); // `this` changed
444 expect(calledTimes).toBe(2);
445 a.n = 10;
446 expect(a.add(5)).toBe(15);
447 expect(calledTimes).toBe(2); // reused cache
448 });
449});
450