Bitwise Clock

A clock variant cache algorithm 2x faster than LRU.

• 2x faster than lru-cache which is the most popular and fastest cache package except bclock.
• 32x faster than the original clock algorithm in worst-case time complexity.

Maintenance

The source code is maintained on the next source repository.

https://github.com/falsandtru/spica

Hit ratio

WS1

WS1 1,000,000
LRU   hit ratio 2.95%
Clock hit ratio 4.33%
Clock - LRU hit ratio delta 1.38%

WS1 2,000,000
LRU   hit ratio 6.08%
Clock hit ratio 10.10%
Clock - LRU hit ratio delta 4.01%

WS1 3,000,000
LRU   hit ratio 9.63%
Clock hit ratio 15.87%
Clock - LRU hit ratio delta 6.24%

WS1 4,000,000
LRU   hit ratio 21.59%
Clock hit ratio 25.34%
Clock - LRU hit ratio delta 3.74%

WS1 5,000,000
LRU   hit ratio 33.91%
Clock hit ratio 37.14%
Clock - LRU hit ratio delta 3.22%

WS1 6,000,000
LRU   hit ratio 45.74%
Clock hit ratio 47.91%
Clock - LRU hit ratio delta 2.17%

WS1 7,000,000
LRU   hit ratio 54.89%
Clock hit ratio 56.53%
Clock - LRU hit ratio delta 1.63%

WS1 8,000,000
LRU   hit ratio 61.40%
Clock hit ratio 62.05%
Clock - LRU hit ratio delta 0.65%

WS2

WS2 1,000,000
LRU   hit ratio 2.91%
Clock hit ratio 4.80%
Clock - LRU hit ratio delta 1.89%

WS2 2,000,000
LRU   hit ratio 6.19%
Clock hit ratio 12.21%
Clock - LRU hit ratio delta 6.01%

WS2 3,000,000
LRU   hit ratio 10.09%
Clock hit ratio 20.10%
Clock - LRU hit ratio delta 10.00%

WS2 4,000,000
LRU   hit ratio 23.45%
Clock hit ratio 29.01%
Clock - LRU hit ratio delta 5.55%

WS2 5,000,000
LRU   hit ratio 37.94%
Clock hit ratio 43.12%
Clock - LRU hit ratio delta 5.18%

WS2 6,000,000
LRU   hit ratio 51.69%
Clock hit ratio 55.65%
Clock - LRU hit ratio delta 3.96%

WS2 7,000,000
LRU   hit ratio 63.81%
Clock hit ratio 66.31%
Clock - LRU hit ratio delta 2.50%

WS2 8,000,000
LRU   hit ratio 73.11%
Clock hit ratio 74.70%
Clock - LRU hit ratio delta 1.58%

F1

F1 2,500
LRU   hit ratio 27.74%
Clock hit ratio 28.47%
Clock - LRU hit ratio delta 0.72%

F1 5,000
LRU   hit ratio 30.55%
Clock hit ratio 31.76%
Clock - LRU hit ratio delta 1.20%

F1 7,500
LRU   hit ratio 32.18%
Clock hit ratio 33.61%
Clock - LRU hit ratio delta 1.43%

F1 10,000
LRU   hit ratio 33.27%
Clock hit ratio 34.85%
Clock - LRU hit ratio delta 1.58%

F1 12,500
LRU   hit ratio 34.19%
Clock hit ratio 35.83%
Clock - LRU hit ratio delta 1.64%

F1 15,000
LRU   hit ratio 34.97%
Clock hit ratio 36.58%
Clock - LRU hit ratio delta 1.61%

F1 17,500
LRU   hit ratio 35.62%
Clock hit ratio 37.26%
Clock - LRU hit ratio delta 1.64%

F1 20,000
LRU   hit ratio 36.17%
Clock hit ratio 37.84%
Clock - LRU hit ratio delta 1.67%

DS1

DS1 1,000,000
LRU   hit ratio 3.08%
Clock hit ratio 4.16%
Clock - LRU hit ratio delta 1.08%

DS1 2,000,000
LRU   hit ratio 10.74%
Clock hit ratio 14.92%
Clock - LRU hit ratio delta 4.18%

DS1 3,000,000
LRU   hit ratio 18.59%
Clock hit ratio 26.95%
Clock - LRU hit ratio delta 8.36%

DS1 4,000,000
LRU   hit ratio 20.24%
Clock hit ratio 32.25%
Clock - LRU hit ratio delta 12.01%

DS1 5,000,000
LRU   hit ratio 21.03%
Clock hit ratio 36.48%
Clock - LRU hit ratio delta 15.45%

DS1 6,000,000
LRU   hit ratio 33.95%
Clock hit ratio 45.71%
Clock - LRU hit ratio delta 11.75%

DS1 7,000,000
LRU   hit ratio 38.89%
Clock hit ratio 54.17%
Clock - LRU hit ratio delta 15.27%

DS1 8,000,000
LRU   hit ratio 43.03%
Clock hit ratio 60.13%
Clock - LRU hit ratio delta 17.10%

S3

S3 100,000
LRU   hit ratio 2.32%
Clock hit ratio 3.69%
Clock - LRU hit ratio delta 1.36%

S3 200,000
LRU   hit ratio 4.63%
Clock hit ratio 9.26%
Clock - LRU hit ratio delta 4.63%

S3 300,000
LRU   hit ratio 7.58%
Clock hit ratio 15.37%
Clock - LRU hit ratio delta 7.78%

S3 400,000
LRU   hit ratio 12.03%
Clock hit ratio 21.55%
Clock - LRU hit ratio delta 9.51%

S3 500,000
LRU   hit ratio 22.76%
Clock hit ratio 28.71%
Clock - LRU hit ratio delta 5.94%

S3 600,000
LRU   hit ratio 34.63%
Clock hit ratio 39.79%
Clock - LRU hit ratio delta 5.16%

S3 700,000
LRU   hit ratio 46.04%
Clock hit ratio 50.49%
Clock - LRU hit ratio delta 4.44%

S3 800,000
LRU   hit ratio 56.59%
Clock hit ratio 59.99%
Clock - LRU hit ratio delta 3.39%

OLTP

OLTP 250
LRU   hit ratio 16.47%
Clock hit ratio 16.13%
Clock - LRU hit ratio delta -0.33%

OLTP 500
LRU   hit ratio 23.44%
Clock hit ratio 24.06%
Clock - LRU hit ratio delta 0.61%

OLTP 750
LRU   hit ratio 28.28%
Clock hit ratio 28.86%
Clock - LRU hit ratio delta 0.58%

OLTP 1,000
LRU   hit ratio 32.83%
Clock hit ratio 32.35%
Clock - LRU hit ratio delta -0.47%

OLTP 1,250
LRU   hit ratio 36.20%
Clock hit ratio 35.54%
Clock - LRU hit ratio delta -0.66%

OLTP 1,500
LRU   hit ratio 38.69%
Clock hit ratio 38.00%
Clock - LRU hit ratio delta -0.69%

OLTP 1,750
LRU   hit ratio 40.78%
Clock hit ratio 40.43%
Clock - LRU hit ratio delta -0.35%

OLTP 2,000
LRU   hit ratio 42.46%
Clock hit ratio 42.21%
Clock - LRU hit ratio delta -0.25%

GLI

GLI 250
LRU   hit ratio 0.93%
Clock hit ratio 1.34%
Clock - LRU hit ratio delta 0.41%

GLI 500
LRU   hit ratio 0.96%
Clock hit ratio 1.42%
Clock - LRU hit ratio delta 0.46%

GLI 750
LRU   hit ratio 1.16%
Clock hit ratio 1.39%
Clock - LRU hit ratio delta 0.23%

GLI 1,000
LRU   hit ratio 11.22%
Clock hit ratio 27.82%
Clock - LRU hit ratio delta 16.60%

GLI 1,250
LRU   hit ratio 21.25%
Clock hit ratio 40.19%
Clock - LRU hit ratio delta 18.93%

GLI 1,500
LRU   hit ratio 36.56%
Clock hit ratio 49.91%
Clock - LRU hit ratio delta 13.34%

GLI 1,750
LRU   hit ratio 45.04%
Clock hit ratio 55.06%
Clock - LRU hit ratio delta 10.02%

GLI 2,000
LRU   hit ratio 57.41%
Clock hit ratio 57.41%
Clock - LRU hit ratio delta 0.00%

Throughput

Clock outperforms LRU, especially in the get operation by marking algorithm. Therefore, when the cache is less likely to overflow, Clock is particularly faster than LRU.

• Clock: spica/clock
• ILRU: lru-cache (https://www.npmjs.com/package/lru-cache)
• LRU: spica/lru
• TRC-C: spica/tlru (spica/tlru.clock)
• TRC-L: spica/tlru.lru
• DWC: spica/cache

https://github.com/falsandtru/spica/blob/master/benchmark/cache.ts

    OS: Linux 6.2 Ubuntu 22.04.4 LTS 22.04.4 LTS (Jammy Jellyfish)
    CPU: (4) x64 AMD EPYC 7763 64-Core Processor
    Memory: 14.61 GB / 15.61 GB
    Container: Yes

'Clock  new x 1,580,578 ops/sec ±2.36% (120 runs sampled)'

'TClock new x 1,635,917 ops/sec ±1.73% (114 runs sampled)'

'ILRU   new x 17,306 ops/sec ±0.72% (122 runs sampled)'

'LRU    new x 26,446,766 ops/sec ±1.27% (120 runs sampled)'

'TLRU-C new x 25,447,708 ops/sec ±1.16% (120 runs sampled)'

'TLRU-L new x 25,516,873 ops/sec ±1.15% (120 runs sampled)'

'DWC    new x 8,852,793 ops/sec ±0.48% (123 runs sampled)'

'Clock  simulation 100 10% x 9,916,253 ops/sec ±0.82% (121 runs sampled)'

'TClock simulation 100 10% x 9,178,812 ops/sec ±0.41% (122 runs sampled)'

'ILRU   simulation 100 10% x 8,795,920 ops/sec ±0.45% (121 runs sampled)'

'LRU    simulation 100 10% x 11,042,280 ops/sec ±0.41% (122 runs sampled)'

'TLRU-C simulation 100 10% x 10,776,622 ops/sec ±0.69% (122 runs sampled)'

'TLRU-L simulation 100 10% x 9,087,601 ops/sec ±0.55% (122 runs sampled)'

'DWC    simulation 100 10% x 5,970,465 ops/sec ±0.31% (122 runs sampled)'

'Clock  simulation 1,000 10% x 9,957,449 ops/sec ±0.44% (123 runs sampled)'

'TClock simulation 1,000 10% x 9,045,578 ops/sec ±0.87% (122 runs sampled)'

'ILRU   simulation 1,000 10% x 8,120,270 ops/sec ±0.40% (123 runs sampled)'

'LRU    simulation 1,000 10% x 10,033,399 ops/sec ±1.03% (121 runs sampled)'

'TLRU-C simulation 1,000 10% x 10,012,036 ops/sec ±0.48% (123 runs sampled)'

'TLRU-L simulation 1,000 10% x 8,728,394 ops/sec ±0.53% (123 runs sampled)'

'DWC    simulation 1,000 10% x 6,824,871 ops/sec ±0.44% (121 runs sampled)'

'Clock  simulation 10,000 10% x 8,950,040 ops/sec ±0.68% (122 runs sampled)'

'TClock simulation 10,000 10% x 8,184,728 ops/sec ±0.36% (123 runs sampled)'

'ILRU   simulation 10,000 10% x 6,836,598 ops/sec ±0.35% (121 runs sampled)'

'LRU    simulation 10,000 10% x 8,375,776 ops/sec ±0.40% (121 runs sampled)'

'TLRU-C simulation 10,000 10% x 8,056,049 ops/sec ±0.87% (120 runs sampled)'

'TLRU-L simulation 10,000 10% x 7,152,724 ops/sec ±0.30% (123 runs sampled)'

'DWC    simulation 10,000 10% x 5,707,307 ops/sec ±0.40% (122 runs sampled)'

'Clock  simulation 100,000 10% x 6,066,442 ops/sec ±1.54% (120 runs sampled)'

'TClock simulation 100,000 10% x 5,931,329 ops/sec ±1.52% (118 runs sampled)'

'ILRU   simulation 100,000 10% x 3,989,516 ops/sec ±1.24% (117 runs sampled)'

'LRU    simulation 100,000 10% x 5,775,982 ops/sec ±1.73% (119 runs sampled)'

'TLRU-C simulation 100,000 10% x 6,121,879 ops/sec ±2.03% (117 runs sampled)'

'TLRU-L simulation 100,000 10% x 5,372,740 ops/sec ±2.16% (117 runs sampled)'

'DWC    simulation 100,000 10% x 4,371,865 ops/sec ±1.97% (114 runs sampled)'

'Clock  simulation 1,000,000 10% x 2,921,542 ops/sec ±2.82% (107 runs sampled)'

'TClock simulation 1,000,000 10% x 2,734,509 ops/sec ±4.05% (102 runs sampled)'

'ILRU   simulation 1,000,000 10% x 1,702,357 ops/sec ±2.64% (108 runs sampled)'

'LRU    simulation 1,000,000 10% x 2,404,423 ops/sec ±3.55% (107 runs sampled)'

'TLRU-C simulation 1,000,000 10% x 2,509,557 ops/sec ±3.64% (106 runs sampled)'

'TLRU-L simulation 1,000,000 10% x 2,400,923 ops/sec ±3.88% (103 runs sampled)'

'DWC    simulation 1,000,000 10% x 3,086,653 ops/sec ±3.95% (107 runs sampled)'

'Clock  simulation 100 50% x 11,638,221 ops/sec ±0.44% (123 runs sampled)'

'TClock simulation 100 50% x 10,645,049 ops/sec ±0.69% (123 runs sampled)'

'ILRU   simulation 100 50% x 10,786,602 ops/sec ±0.47% (122 runs sampled)'

'LRU    simulation 100 50% x 12,558,754 ops/sec ±0.62% (121 runs sampled)'

'TLRU-C simulation 100 50% x 12,613,469 ops/sec ±0.48% (122 runs sampled)'

'TLRU-L simulation 100 50% x 10,785,803 ops/sec ±0.45% (122 runs sampled)'

'DWC    simulation 100 50% x 6,507,728 ops/sec ±0.43% (123 runs sampled)'

'Clock  simulation 1,000 50% x 11,225,959 ops/sec ±0.41% (122 runs sampled)'

'TClock simulation 1,000 50% x 10,633,288 ops/sec ±0.51% (123 runs sampled)'

'ILRU   simulation 1,000 50% x 9,807,774 ops/sec ±0.83% (122 runs sampled)'

'LRU    simulation 1,000 50% x 11,547,226 ops/sec ±0.47% (122 runs sampled)'

'TLRU-C simulation 1,000 50% x 11,500,223 ops/sec ±0.69% (121 runs sampled)'

'TLRU-L simulation 1,000 50% x 10,370,843 ops/sec ±0.40% (123 runs sampled)'

'DWC    simulation 1,000 50% x 5,861,780 ops/sec ±0.37% (123 runs sampled)'

'Clock  simulation 10,000 50% x 10,005,777 ops/sec ±0.58% (122 runs sampled)'

'TClock simulation 10,000 50% x 9,164,085 ops/sec ±0.44% (122 runs sampled)'

'ILRU   simulation 10,000 50% x 8,145,309 ops/sec ±0.44% (121 runs sampled)'

'LRU    simulation 10,000 50% x 8,836,874 ops/sec ±0.51% (120 runs sampled)'

'TLRU-C simulation 10,000 50% x 8,739,594 ops/sec ±0.53% (122 runs sampled)'

'TLRU-L simulation 10,000 50% x 7,752,474 ops/sec ±0.44% (121 runs sampled)'

'DWC    simulation 10,000 50% x 4,774,496 ops/sec ±0.49% (120 runs sampled)'

'Clock  simulation 100,000 50% x 6,886,961 ops/sec ±1.39% (118 runs sampled)'

'TClock simulation 100,000 50% x 6,671,489 ops/sec ±1.43% (118 runs sampled)'

'ILRU   simulation 100,000 50% x 4,727,141 ops/sec ±1.40% (117 runs sampled)'

'LRU    simulation 100,000 50% x 6,267,110 ops/sec ±2.01% (117 runs sampled)'

'TLRU-C simulation 100,000 50% x 6,497,513 ops/sec ±1.95% (118 runs sampled)'

'TLRU-L simulation 100,000 50% x 5,929,699 ops/sec ±2.30% (117 runs sampled)'

'DWC    simulation 100,000 50% x 4,007,906 ops/sec ±1.48% (110 runs sampled)'

'Clock  simulation 1,000,000 50% x 3,388,591 ops/sec ±3.09% (105 runs sampled)'

'TClock simulation 1,000,000 50% x 3,030,444 ops/sec ±3.52% (103 runs sampled)'

'ILRU   simulation 1,000,000 50% x 1,957,735 ops/sec ±3.24% (106 runs sampled)'

'LRU    simulation 1,000,000 50% x 2,378,468 ops/sec ±3.26% (107 runs sampled)'

'TLRU-C simulation 1,000,000 50% x 2,319,526 ops/sec ±3.01% (110 runs sampled)'

'TLRU-L simulation 1,000,000 50% x 2,326,281 ops/sec ±2.40% (107 runs sampled)'

'DWC    simulation 1,000,000 50% x 1,873,066 ops/sec ±3.42% (101 runs sampled)'

'Clock  simulation 100 90% x 17,142,365 ops/sec ±0.70% (122 runs sampled)'

'TClock simulation 100 90% x 17,515,002 ops/sec ±0.92% (120 runs sampled)'

'ILRU   simulation 100 90% x 16,941,103 ops/sec ±0.74% (121 runs sampled)'

'LRU    simulation 100 90% x 16,965,079 ops/sec ±0.89% (120 runs sampled)'

'TLRU-C simulation 100 90% x 16,764,673 ops/sec ±0.80% (119 runs sampled)'

'TLRU-L simulation 100 90% x 15,833,669 ops/sec ±0.67% (122 runs sampled)'

'DWC    simulation 100 90% x 8,241,562 ops/sec ±0.33% (122 runs sampled)'

'Clock  simulation 1,000 90% x 16,186,628 ops/sec ±0.92% (122 runs sampled)'

'TClock simulation 1,000 90% x 16,620,457 ops/sec ±0.68% (122 runs sampled)'

'ILRU   simulation 1,000 90% x 14,897,888 ops/sec ±0.62% (122 runs sampled)'

'LRU    simulation 1,000 90% x 15,072,880 ops/sec ±0.62% (122 runs sampled)'

'TLRU-C simulation 1,000 90% x 14,802,277 ops/sec ±1.06% (120 runs sampled)'

'TLRU-L simulation 1,000 90% x 14,243,896 ops/sec ±0.60% (122 runs sampled)'

'DWC    simulation 1,000 90% x 7,878,478 ops/sec ±0.55% (123 runs sampled)'

'Clock  simulation 10,000 90% x 14,397,140 ops/sec ±0.96% (122 runs sampled)'

'TClock simulation 10,000 90% x 14,674,408 ops/sec ±0.76% (122 runs sampled)'

'ILRU   simulation 10,000 90% x 12,163,240 ops/sec ±0.56% (122 runs sampled)'

'LRU    simulation 10,000 90% x 11,176,342 ops/sec ±1.02% (121 runs sampled)'

'TLRU-C simulation 10,000 90% x 10,623,051 ops/sec ±0.62% (120 runs sampled)'

'TLRU-L simulation 10,000 90% x 10,157,939 ops/sec ±0.90% (122 runs sampled)'

'DWC    simulation 10,000 90% x 7,044,033 ops/sec ±0.74% (122 runs sampled)'

'Clock  simulation 100,000 90% x 9,289,594 ops/sec ±1.22% (117 runs sampled)'

'TClock simulation 100,000 90% x 9,424,672 ops/sec ±1.28% (117 runs sampled)'

'ILRU   simulation 100,000 90% x 7,244,655 ops/sec ±0.98% (117 runs sampled)'

'LRU    simulation 100,000 90% x 7,412,012 ops/sec ±2.06% (115 runs sampled)'

'TLRU-C simulation 100,000 90% x 7,348,881 ops/sec ±2.79% (113 runs sampled)'

'TLRU-L simulation 100,000 90% x 7,138,284 ops/sec ±1.86% (113 runs sampled)'

'DWC    simulation 100,000 90% x 5,590,257 ops/sec ±1.48% (116 runs sampled)'

'Clock  simulation 1,000,000 90% x 5,098,637 ops/sec ±3.30% (103 runs sampled)'

'TClock simulation 1,000,000 90% x 4,743,456 ops/sec ±3.51% (103 runs sampled)'

'ILRU   simulation 1,000,000 90% x 3,168,501 ops/sec ±2.45% (111 runs sampled)'

'LRU    simulation 1,000,000 90% x 2,594,390 ops/sec ±3.09% (112 runs sampled)'

'TLRU-C simulation 1,000,000 90% x 2,546,277 ops/sec ±2.43% (109 runs sampled)'

'TLRU-L simulation 1,000,000 90% x 2,478,672 ops/sec ±2.63% (111 runs sampled)'

'DWC    simulation 1,000,000 90% x 2,154,161 ops/sec ±1.80% (114 runs sampled)'

'ILRU   simulation 100 90% expire x 4,875,225 ops/sec ±2.21% (119 runs sampled)'

'DWC    simulation 100 90% expire x 7,322,013 ops/sec ±0.68% (120 runs sampled)'

'ILRU   simulation 1,000 90% expire x 4,600,040 ops/sec ±2.52% (118 runs sampled)'

'DWC    simulation 1,000 90% expire x 7,126,746 ops/sec ±0.67% (122 runs sampled)'

'ILRU   simulation 10,000 90% expire x 3,992,238 ops/sec ±2.12% (119 runs sampled)'

'DWC    simulation 10,000 90% expire x 5,431,828 ops/sec ±0.87% (120 runs sampled)'

'ILRU   simulation 100,000 90% expire x 3,132,253 ops/sec ±2.06% (114 runs sampled)'

'DWC    simulation 100,000 90% expire x 2,914,127 ops/sec ±2.99% (100 runs sampled)'

'ILRU   simulation 1,000,000 90% expire x 1,361,462 ops/sec ±1.48% (114 runs sampled)'

'DWC    simulation 1,000,000 90% expire x 1,349,727 ops/sec ±2.02% (111 runs sampled)'

API

export class Clock<K, V> {
  // Capacity is rounded up to multiples of 32.
  constructor(capacity: number);
  add(key: K, value: V): number;
  put(key: K, value: V): boolean;
  set(key: K, value: V): this;
  get(key: K): V | undefined;
  has(key: K): boolean;
  delete(key: K): boolean;
  clear(): void;
  readonly length: number;
  readonly size: number;
  [Symbol.iterator](): Iterator<[K, V], undefined, undefined>;
}