dw-cache

v0.0.120

Published

4 months ago

The highest performance constant complexity cache algorithm.

Downloads

0High
0Medium
0Low

falsandtru

cache lru lfu arc

Dual Window Cache

The highest performance constant complexity cache algorithm.

Maintenance

The source code is maintained on the next source repository.

https://github.com/falsandtru/spica

Properties

Generally superior and almost flawless.

Highest performance
- High hit ratio
  - Highest hit ratio of all the general-purpose cache algorithms.
    - W-TinyLFU is basically not a general-purpose cache algorithm due to some problems.
      - W-TinyLFU is not a general-purpose cache algorithm without dynamic window and incremental reset.
      - W-TinyLFU is impossible to efficiently implement without pointer addresses or fast hash functions.
      - W-TinyLFU has a lower hit ratio for keys other than a single numeric type.
      - W-TinyLFU's benchmark settings are not described (Especially suspicious with OLTP).
  - Highest engineering hit ratio of all the advanced cache algorithms.
    - As a result of engineering efficiency.
- Low time overhead (High throughput)
  - Use only two lists.
- Low latency
  - Constant time complexity.
  - No batch processing like LIRS, TinyLFU, and W-TinyLFU.
- Parallel suitable
  - Separated lists are suitable for lock-free processing.
Efficient
- Low memory usage
  - Largest cache size per memory size of all the advanced cache algorithms.
  - Constant extra space complexity.
  - Retain only keys of resident entries (No history).
- Immediate release of evicted keys
  - Primary cache algorithm in the standard library must release memory immediately.
- Low space overhead
  - Add only two smallest fields to entries.
High resistance
- Scan, loop, and burst resistance
Few tradeoffs
- Not the highest hit ratio
  - Highest hit ratio of each workload is resulted by W-TinyLFU or ARC.
- Statistical accuracy dependent
  - Too smaller capacity than appropriate can degrade hit ratio.
    - The amount of available information decreases at an accelerating rate as cache size decreases.
    - The more complex the statistical method, the greater the impact of the decrease in the amount of information.
  - Minimum operating unit is 0.02% of cache size.
    - 5,000 or more is the recommended cache size to satisfy this point.
  - Very small cache size reduces operating precision.
    - 200 or more is the recommended cache size to satisfy this point.
  - On discontinuous workloads, TLRU is better.
- No tradeoffs other than hit ratio
  - Other advanced cache algorithms have some tradeoffs such as spike latency by linear time complexity, delayed memory release by linear space complexity, or implementability.
    - Other advanced cache algorithms cannot generally replace LRU due to these tradeoffs.

Tradeoffs

Note that LIRS and TinyLFU are risky cache algorithms.

LRU
- Low performance
- No resistance
  - Scan access clears all entries.
TLRU
- Middle performance
  - Lower hit ratio than DWC.
- Limited resistance
  - Limited loop resistance.
DWC
- Not the highest hit ratio
- Statistical accuracy dependent
ARC
- Middle performance
- Inefficient
  - 2x key size.
- High overhead
  - 4 lists.
- Few resistance
  - No loop resistance.
LIRS
- Extremely inefficient
  - 3-2,500x key size.
- Spike latency
  - Bulk deletion of low-frequency entries takes linear time.
- Vulnerable algorithm
  - Continuous cache misses for the last LIR entry or the HIR entries explode key size.
    - https://issues.redhat.com/browse/ISPN-7171
    - https://issues.redhat.com/browse/ISPN-7246
TinyLFU
- Incomplete algorithm
  - TinyLFU is just a vulnerable incomplete base-algorithm of W-TinyLFU.
  - Burst access saturates Bloom filters.
  - TinyLFU is worse than LRU in theory.
- Language dependent
  - Impossible to efficiently implement without pointer addresses or fast hash functions.
- High overhead
  - Read and write average 40 array elements per access.
- Restricted delete operation
  - Bloom filters don't support delete operation.
  - Frequent delete operations degrade performance.
- Spike latency
  - Whole reset of Bloom filters takes linear time.
- Hit ratio degradation in general use
  - Different hash keys can be obtained from the same key since memory addresses are used for hash keys such as strings.
  - Impossible to distinguish between different keys of different types that are the same hash key since hash keys have no type.
  - The impact varies depending on the OS, language, implementation, etc., and cannot be predicted without individual investigation.
- Vulnerable algorithm
  - Burst access degrades performance.
W-TinyLFU
- Language dependent
  - Impossible to efficiently implement without pointer addresses or fast hash functions.
- High overhead
  - Read and write average 40 array elements per access.
- Restricted delete operation
  - Bloom filters don't support delete operation.
  - Frequent delete operations degrade performance.
- Hit ratio degradation in general use
  - Different hash keys can be obtained from the same key since memory addresses are used for hash keys such as strings.
  - Impossible to distinguish between different keys of different types that are the same hash key since hash keys have no type.
  - The impact varies depending on the OS, language, implementation, etc., and cannot be predicted without individual investigation.
- Spike latency
  - Whole reset of Bloom filters takes linear time.

Strategies

Dynamic partition
Sampled history injection
Transitive wide MRU with cyclic replacement

Efficiency

TLRU and TRC are abbreviations for TrueLRU (spica/tlru).

Mathematical efficiency

Some different cache algorithms require extra memory space to retain evicted keys. Linear time complexity indicates the existence of batch processing. Note that admission algorithm doesn't work without eviction algorithm.

https://github.com/ben-manes/caffeine/wiki/Efficiency https://github.com/zhongch4g/LIRS2/blob/master/src/replace_lirs_base.cc

Engineering efficiency

A pointer is 8 bytes, bool and int8 are each 1 byte in C.

8 byte key and value (int64, float64, 8 chars)

In-memory cache, memoize, etc.

|Algorithm|Entry overhead|Key size|Total per entry|Attenuation coefficient| |:-------:|-------------:|-------:|--------------:|----------------------:| |LRU | 16 bytes| 1x| 32 bytes| 100.00%| |TLRU | 16 bytes| 1x| 32 bytes| 100.00%| |DWC | 17 bytes| 1x| 33 bytes| 96.96%| |ARC | 17 bytes| 2x| 58 bytes| 55.17%| |LIRS | 33 bytes| 3x| 131 bytes| 24.42%| |LIRS | 33 bytes| 10x| 418 bytes| 7.65%| |TinyLFU | 56 bytes| 1x| 72 bytes| 44.44%| |W-TinyLFU| 56 bytes| 1x| 72 bytes| 44.44%|

32 byte key and 8 byte value (Session ID / ID)

In-memory KVS, etc.

|Algorithm|Entry overhead|Key size|Total per entry|Attenuation coefficient| |:-------:|-------------:|-------:|--------------:|----------------------:| |LRU | 16 bytes| 1x| 56 bytes| 100.00%| |TLRU | 16 bytes| 1x| 56 bytes| 100.00%| |DWC | 17 bytes| 1x| 57 bytes| 98.24%| |ARC | 17 bytes| 2x| 88 bytes| 63.63%| |LIRS | 33 bytes| 3x| 203 bytes| 27.58%| |LIRS | 33 bytes| 10x| 658 bytes| 8.51%| |TinyLFU | 56 bytes| 1x| 96 bytes| 58.33%| |W-TinyLFU| 56 bytes| 1x| 96 bytes| 58.33%|

16 byte key and 512 byte value (Domain / DNS packet)

DNS cache server, etc.

|Algorithm|Entry overhead|Key size|Total per entry|Attenuation coefficient| |:-------:|-------------:|-------:|--------------:|----------------------:| |LRU | 16 bytes| 1x| 544 bytes| 100.00%| |TLRU | 16 bytes| 1x| 544 bytes| 100.00%| |DWC | 17 bytes| 1x| 545 bytes| 99.81%| |ARC | 17 bytes| 2x| 578 bytes| 94.11%| |LIRS | 33 bytes| 3x| 659 bytes| 82.54%| |LIRS | 33 bytes| 10x| 1,002 bytes| 54.29%| |TinyLFU | 56 bytes| 1x| 584 bytes| 93.15%| |W-TinyLFU| 56 bytes| 1x| 584 bytes| 93.15%|

Resistance

LIRS's burst resistance means the resistance to continuous cache misses for the last LIR entry or the HIR entries. TLRU's loop resistance is limited to initial only.

|Algorithm|Type |Scan|Loop|Burst| |:-------:|:---:|:--:|:--:|:---:| |LRU |Evict| | | ✓ | |TLRU |Evict| ✓ | ✓ | ✓ | |DWC |Evict| ✓ | ✓ | ✓ | |ARC |Evict| ✓ | | ✓ | |LIRS |Evict| ✓ | ✓ | | |TinyLFU |Admit| ✓ | ✓ | | |W-TinyLFU|Admit| ✓ | ✓ | ✓ |

Loop resistance

DWC automatically adjusts the history size according to the loop size.

|Algorithm|Method |Duration |Layout|History size|Resistance|Efficiency| |:-------:|:--------:|:-------:|:----:|-----------:|---------:|---------:| |TLRU |Eventual |Initial |Inner | 100%| > 10x| > 1,000%| |DWC |Statistics|Permanent|Inner | 8%| 4x| 5,000%| |DWC |Statistics|Permanent|Inner | 14%| 10x| 7,142%| |DWC |Statistics|Permanent|Inner | 100%| 96x| 9,600%| |LIRS |Log |Permanent|Outer |300-250,000%| 3-2,500x| 100%| |TinyLFU |Hash |Permanent|Outer | 500%| 4x| 80%| |W-TinyLFU|Hash |Permanent|Outer | 500%| 4x| 80%|

Hit ratio

Note that another cache algorithm sometimes changes the parameter values per workload to get a favorite result as the paper of TinyLFU has changed the window size of W-TinyLFU.

DWC's results are measured by the same default parameter values.
Other results are measured by the simulator in Caffeine.
- https://github.com/ben-manes/caffeine/wiki/Efficiency
- https://docs.google.com/spreadsheets/d/1G3deNz1gJCoXBE2IuraUSwLE7H_EMn4Sn2GU0HTpI5Y (https://github.com/jedisct1/rust-arc-cache/issues/1)

Set the datasets to ./benchmark/trace (See ./benchmark/ratio.ts).
- https://github.com/dgraph-io/benchmarks
- https://traces.cs.umass.edu/index.php/Storage/Storage
Run npm i.
Run npm run bench.
Click the DEBUG button to open a debug tab.
Close the previous tab.
Press F12 key to open devtools.
Select the console tab.

WS1

W-TinyLFU, (TinyLFU) > (LIRS), DWC > TLRU > ARC > LRU

WS1 1,000,000
LRU hit ratio 2.95%
TRC hit ratio 8.09%
DWC hit ratio 10.56%
DWC - LRU hit ratio delta 7.61%

WS1 2,000,000
LRU hit ratio 6.08%
TRC hit ratio 18.03%
DWC hit ratio 20.78%
DWC - LRU hit ratio delta 14.69%

WS1 3,000,000
LRU hit ratio 9.63%
TRC hit ratio 26.92%
DWC hit ratio 30.21%
DWC - LRU hit ratio delta 20.58%

WS1 4,000,000
LRU hit ratio 21.59%
TRC hit ratio 35.88%
DWC hit ratio 38.93%
DWC - LRU hit ratio delta 17.33%

WS1 5,000,000
LRU hit ratio 33.91%
TRC hit ratio 44.19%
DWC hit ratio 46.85%
DWC - LRU hit ratio delta 12.93%

WS1 6,000,000
LRU hit ratio 45.74%
TRC hit ratio 51.66%
DWC hit ratio 53.50%
DWC - LRU hit ratio delta 7.76%

WS1 7,000,000
LRU hit ratio 54.89%
TRC hit ratio 57.70%
DWC hit ratio 58.89%
DWC - LRU hit ratio delta 3.99%

WS1 8,000,000
LRU hit ratio 61.40%
TRC hit ratio 62.46%
DWC hit ratio 62.93%
DWC - LRU hit ratio delta 1.53%

WS2

W-TinyLFU, (TinyLFU) > (LIRS), DWC > TLRU > ARC > LRU

WS2 1,000,000
LRU hit ratio 2.91%
TRC hit ratio 9.28%
DWC hit ratio 12.74%
DWC - LRU hit ratio delta 9.82%

WS2 2,000,000
LRU hit ratio 6.19%
TRC hit ratio 19.86%
DWC hit ratio 24.21%
DWC - LRU hit ratio delta 18.01%

WS2 3,000,000
LRU hit ratio 10.09%
TRC hit ratio 30.05%
DWC hit ratio 35.02%
DWC - LRU hit ratio delta 24.92%

WS2 4,000,000
LRU hit ratio 23.45%
TRC hit ratio 40.41%
DWC hit ratio 44.82%
DWC - LRU hit ratio delta 21.36%

WS2 5,000,000
LRU hit ratio 37.94%
TRC hit ratio 50.39%
DWC hit ratio 54.07%
DWC - LRU hit ratio delta 16.13%

WS2 6,000,000
LRU hit ratio 51.69%
TRC hit ratio 60.05%
DWC hit ratio 62.40%
DWC - LRU hit ratio delta 10.71%

WS2 7,000,000
LRU hit ratio 63.81%
TRC hit ratio 69.29%
DWC hit ratio 69.48%
DWC - LRU hit ratio delta 5.66%

WS2 8,000,000
LRU hit ratio 73.11%
TRC hit ratio 76.33%
DWC hit ratio 75.77%
DWC - LRU hit ratio delta 2.66%

F1

ARC > SLRU, TLRU > (LIRS), DWC > LRU > W-TinyLFU > TinyLFU

F1 2,500
LRU hit ratio 27.74%
TRC hit ratio 27.48%
DWC hit ratio 24.70%
DWC - LRU hit ratio delta -3.03%

F1 5,000
LRU hit ratio 30.55%
TRC hit ratio 31.52%
DWC hit ratio 29.18%
DWC - LRU hit ratio delta -1.37%

F1 7,500
LRU hit ratio 32.18%
TRC hit ratio 34.04%
DWC hit ratio 32.20%
DWC - LRU hit ratio delta 0.02%

F1 10,000
LRU hit ratio 33.27%
TRC hit ratio 35.57%
DWC hit ratio 34.66%
DWC - LRU hit ratio delta 1.39%

F1 12,500
LRU hit ratio 34.19%
TRC hit ratio 36.72%
DWC hit ratio 36.22%
DWC - LRU hit ratio delta 2.03%

F1 15,000
LRU hit ratio 34.97%
TRC hit ratio 37.60%
DWC hit ratio 37.19%
DWC - LRU hit ratio delta 2.21%

F1 17,500
LRU hit ratio 35.62%
TRC hit ratio 38.32%
DWC hit ratio 37.87%
DWC - LRU hit ratio delta 2.24%

F1 20,000
LRU hit ratio 36.17%
TRC hit ratio 38.82%
DWC hit ratio 38.32%
DWC - LRU hit ratio delta 2.15%

DS1

W-TinyLFU, (TinyLFU) > DWC > TLRU, (LIRS) > ARC > LRU

DS1 1,000,000
LRU hit ratio 3.08%
TRC hit ratio 10.47%
DWC hit ratio 14.05%
DWC - LRU hit ratio delta 10.96%

DS1 2,000,000
LRU hit ratio 10.74%
TRC hit ratio 22.78%
DWC hit ratio 27.90%
DWC - LRU hit ratio delta 17.16%

DS1 3,000,000
LRU hit ratio 18.59%
TRC hit ratio 34.45%
DWC hit ratio 39.55%
DWC - LRU hit ratio delta 20.96%

DS1 4,000,000
LRU hit ratio 20.24%
TRC hit ratio 39.68%
DWC hit ratio 43.45%
DWC - LRU hit ratio delta 23.20%

DS1 5,000,000
LRU hit ratio 21.03%
TRC hit ratio 46.69%
DWC hit ratio 49.71%
DWC - LRU hit ratio delta 28.68%

DS1 6,000,000
LRU hit ratio 33.95%
TRC hit ratio 53.64%
DWC hit ratio 56.46%
DWC - LRU hit ratio delta 22.50%

DS1 7,000,000
LRU hit ratio 38.89%
TRC hit ratio 61.28%
DWC hit ratio 63.21%
DWC - LRU hit ratio delta 24.31%

DS1 8,000,000
LRU hit ratio 43.03%
TRC hit ratio 68.93%
DWC hit ratio 69.44%
DWC - LRU hit ratio delta 26.40%

S3

W-TinyLFU, (TinyLFU) > (LIRS), DWC > TLRU, ARC > LRU

S3 100,000
LRU hit ratio 2.32%
TRC hit ratio 6.99%
DWC hit ratio 9.94%
DWC - LRU hit ratio delta 7.62%

S3 200,000
LRU hit ratio 4.63%
TRC hit ratio 15.49%
DWC hit ratio 19.39%
DWC - LRU hit ratio delta 14.76%

S3 300,000
LRU hit ratio 7.58%
TRC hit ratio 23.85%
DWC hit ratio 28.26%
DWC - LRU hit ratio delta 20.67%

S3 400,000
LRU hit ratio 12.03%
TRC hit ratio 31.94%
DWC hit ratio 36.77%
DWC - LRU hit ratio delta 24.73%

S3 500,000
LRU hit ratio 22.76%
TRC hit ratio 40.35%
DWC hit ratio 44.50%
DWC - LRU hit ratio delta 21.74%

S3 600,000
LRU hit ratio 34.63%
TRC hit ratio 48.40%
DWC hit ratio 52.22%
DWC - LRU hit ratio delta 17.59%

S3 700,000
LRU hit ratio 46.04%
TRC hit ratio 55.86%
DWC hit ratio 58.67%
DWC - LRU hit ratio delta 12.63%

S3 800,000
LRU hit ratio 56.59%
TRC hit ratio 63.88%
DWC hit ratio 66.02%
DWC - LRU hit ratio delta 9.42%

OLTP

ARC > DWC > TLRU > W-TinyLFU > (LIRS) > LRU > (TinyLFU)

OLTP 250
LRU hit ratio 16.47%
TRC hit ratio 17.06%
DWC hit ratio 19.55%
DWC - LRU hit ratio delta 3.08%

OLTP 500
LRU hit ratio 23.44%
TRC hit ratio 27.86%
DWC hit ratio 29.48%
DWC - LRU hit ratio delta 6.03%

OLTP 750
LRU hit ratio 28.28%
TRC hit ratio 33.11%
DWC hit ratio 34.71%
DWC - LRU hit ratio delta 6.43%

OLTP 1,000
LRU hit ratio 32.83%
TRC hit ratio 36.53%
DWC hit ratio 37.75%
DWC - LRU hit ratio delta 4.92%

OLTP 1,250
LRU hit ratio 36.20%
TRC hit ratio 38.88%
DWC hit ratio 40.07%
DWC - LRU hit ratio delta 3.86%

OLTP 1,500
LRU hit ratio 38.69%
TRC hit ratio 40.79%
DWC hit ratio 41.75%
DWC - LRU hit ratio delta 3.06%

OLTP 1,750
LRU hit ratio 40.78%
TRC hit ratio 42.36%
DWC hit ratio 43.26%
DWC - LRU hit ratio delta 2.47%

OLTP 2,000
LRU hit ratio 42.46%
TRC hit ratio 43.65%
DWC hit ratio 44.59%
DWC - LRU hit ratio delta 2.12%

GLI

W-TinyLFU, (TinyLFU), (LIRS) > DWC > TLRU >> ARC > LRU

GLI 250
LRU hit ratio 0.93%
TRC hit ratio 10.62%
DWC hit ratio 15.82%
DWC - LRU hit ratio delta 14.89%

GLI 500
LRU hit ratio 0.96%
TRC hit ratio 25.03%
DWC hit ratio 31.38%
DWC - LRU hit ratio delta 30.41%

GLI 750
LRU hit ratio 1.16%
TRC hit ratio 37.28%
DWC hit ratio 41.65%
DWC - LRU hit ratio delta 40.49%

GLI 1,000
LRU hit ratio 11.22%
TRC hit ratio 47.17%
DWC hit ratio 47.87%
DWC - LRU hit ratio delta 36.65%

GLI 1,250
LRU hit ratio 21.25%
TRC hit ratio 52.04%
DWC hit ratio 52.54%
DWC - LRU hit ratio delta 31.28%

GLI 1,500
LRU hit ratio 36.56%
TRC hit ratio 53.00%
DWC hit ratio 53.64%
DWC - LRU hit ratio delta 17.07%

GLI 1,750
LRU hit ratio 45.04%
TRC hit ratio 55.88%
DWC hit ratio 54.77%
DWC - LRU hit ratio delta 9.72%

GLI 2,000
LRU hit ratio 57.41%
TRC hit ratio 57.96%
DWC hit ratio 57.96%
DWC - LRU hit ratio delta 0.54%

Throughput

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 namespace Cache {
  export interface Options<K, V = undefined> {
    // Max entries.
    // Range: 1-
    readonly capacity?: number;
    // Max costs.
    // Range: L-
    readonly resource?: number;
    readonly age?: number;
    readonly eagerExpiration?: boolean;
    // WARNING: Don't add any new key in disposing.
    readonly disposer?: (value: V, key: K) => void;
    readonly capture?: {
      readonly delete?: boolean;
      readonly clear?: boolean;
    };
    // Mainly for experiments.
    // Min LRU ratio.
    // Range: 0-100
    readonly window?: number;
    // Sample ratio of LRU in LFU.
    // Range: 0-100
    readonly sample?: number;
    readonly sweep?: {
      readonly threshold?: number;
      readonly window?: number;
      readonly room?: number;
      readonly ground?: number;
      readonly interval?: number;
      readonly slide?: number;
    };
  }
}
export class Cache<K, V> {
  constructor(capacity: number, sweep?: boolean);
  constructor(capacity: number, opts?: Cache.Options<K, V>);
  constructor(opts: Cache.Options<K, V>);
  readonly length: number;
  readonly size: number;
  add(key: K, value: V, opts?: { size?: number; age?: number; }): boolean;
  add(this: Cache<K, undefined>, key: K, value?: V, opts?: { size?: number; age?: number; }): boolean;
  put(key: K, value: V, opts?: { size?: number; age?: number; }): boolean;
  put(this: Cache<K, undefined>, key: K, value?: V, opts?: { size?: number; age?: number; }): boolean;
  set(key: K, value: V, opts?: { size?: number; age?: number; }): this;
  set(this: Cache<K, undefined>, key: K, value?: V, opts?: { size?: number; age?: number; }): this;
  get(key: K): V | undefined;
  has(key: K): boolean;
  delete(key: K): boolean;
  clear(): void;
  resize(capacity: number, resource?: number): void;
  [Symbol.iterator](): Iterator<[K, V], undefined, undefined>;
}