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
Efficiency
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.
Algorithm  Type  Time complexity (Worst case) 
Space complexity (Extra) 
Key size  Data structures 

LRU  Evict  Constant  Constant  1x  1 list 
DWC  Evict  Constant  Constant  1x  2 lists 
ARC  Evict  Constant  Linear  2x  4 lists 
LIRS  Evict  Linear  Linear  32500x  2 lists 
TinyLFU  Admit  Linear  Linear 
~110x (8bit * 10N * 4) 
5 arrays 
WTinyLFU  Admit  Linear  Linear 
~110x (8bit * 10N * 4) 
1 list 4 arrays 
https://github.com/benmanes/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)
Memoize, etc.
Algorithm  Entry overhead  Key size  Total per entry  Attenuation coefficient 

LRU  16 bytes  1x  32 bytes  100.00% 
ARC  18 bytes  2x  60 bytes  53.33% 
DWC  18 bytes  1x  34 bytes  94.11% 
(LIRS)  35 bytes  3x  137 bytes  23.35% 
(LIRS)  35 bytes  10x  438 bytes  7.30% 
(TinyLFU)  56 bytes  1x  72 bytes  44.44% 
WTinyLFU  56 bytes  1x  72 bytes  44.44% 
128 byte key and 8 byte value (Session ID / ID, index)
Inmemory KVS, etc.
Algorithm  Entry overhead  Key size  Total per entry  Attenuation coefficient 

LRU  16 bytes  1x  152 bytes  100.00% 
ARC  18 bytes  2x  300 bytes  50.66% 
DWC  18 bytes  1x  154 bytes  98.70% 
(LIRS)  35 bytes  3x  497 bytes  30.58% 
(LIRS)  35 bytes  10x  1,638 bytes  9.27% 
(TinyLFU)  56 bytes  1x  192 bytes  79.16% 
WTinyLFU  56 bytes  1x  192 bytes  79.16% 
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% 
ARC  18 bytes  2x  580 bytes  93.37% 
DWC  18 bytes  1x  546 bytes  99.63% 
(LIRS)  35 bytes  3x  665 bytes  81.80% 
(LIRS)  35 bytes  10x  1,022 bytes  53.22% 
(TinyLFU)  56 bytes  1x  584 bytes  93.15% 
WTinyLFU  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.
Algorithm  Type  Scan  Loop  Burst 

LRU  Evict  ✓  
DWC  Evict  ✓  ✓  ✓ 
ARC  Evict  ✓  ✓  
LIRS  Evict  ✓  ✓  
TinyLFU  Admit  ✓  ✓  
WTinyLFU  Admit  ✓  ✓  ✓ 
Strategies
 Dynamic partition
 Sampled history injection
 Transitive wide MRU with cyclic replacement
Properties
Generally superior and almost flawless.

Highest performance
 High hit ratio (DS1, S3, OLTP, GLI)

Highest hit ratio of all the generalpurpose cache algorithms.
 Approximate to WTinyLFU (DS1, GLI).
 Approximate to ARC (S3, OLTP).
 WTinyLFU is basically not a generalpurpose cache algorithm due to some problems.
 WTinyLFU is not a generalpurpose cache algorithm without dynamic window and incremental reset.
 WTinyLFU is impossible to efficiently implement without pointer addresses or fast hash functions.
 WTinyLFU's benchmark settings are not described (Especially suspicious with OLTP).

Highest engineering hit ratio of all the general cache algorithms.
 As a result of engineering efficiency.

Highest hit ratio of all the generalpurpose cache algorithms.
 Low time overhead (High throughput)
 Use only two lists.
 Low latency
 Constant time complexity.
 No batch processing like LIRS and TinyLFU.
 Parallel suitable
 Separated lists are suitable for lockfree processing.
 High hit ratio (DS1, S3, OLTP, GLI)
 Efficient
 Low memory usage
 Largest capacity 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.
 Low memory usage
 High resistance
 Scan, loop, and burst resistance
 Few tradeoffs
 Not the highest mathematical hit ratio
 Highest hit ratio of each workload are resulted by WTinyLFU or ARC.
 Statistical accuracy dependent
 Very smaller cache size than sufficient can degrade hit ratio.
 Not the highest mathematical hit ratio
Tradeoffs
Note that LIRS and TinyLFU are risky cache algorithms.
 LRU
 Low performance
 No resistance
 Scan access clears all entries.
 ARC
 Middle performance
 Inefficient
 2x key size.
 High overhead
 4 lists.
 Few resistance
 No loop resistance.
 DWC
 Not the highest mathematical hit ratio
 Statistical accuracy dependent
 LIRS
 Extremely inefficient
 32500x key size.
 Spike latency
 Bulk deletion of lowfrequency entries takes linear time.
 Vulnerable algorithm
 Continuous cache misses for the last LIR entry or the HIR entries explode key size.
 Extremely inefficient
 TinyLFU
 Incomplete algorithm
 TinyLFU is just a vulnerable incomplete basealgorithm of WTinyLFU.
 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.
 Vulnerable algorithm
 Burst access degrades performance.
 Incomplete algorithm
 WTinyLFU
 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.
 Language dependent
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 WTinyLFU.
 DWC's results are measured by the same default parameter values.
 TinyLFU's results are the traces of Ristretto.
 WTinyLFU's results are the traces of Caffeine.
 Set the datasets to
./benchmark/trace
(See./benchmark/ratio.ts
).  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.
https://github.com/dgraphio/benchmarks
https://github.com/benmanes/caffeine/wiki/Efficiency
https://github.com/dgraphio/ristretto
https://docs.google.com/spreadsheets/d/1G3deNz1gJCoXBE2IuraUSwLE7H_EMn4Sn2GU0HTpI5Y (https://github.com/jedisct1/rustarccache/issues/1)
DS1
WTinyLFU > DWC > (LIRS) > (TinyLFU) > ARC > LRU
 DWC is an approximation of WTinyLFU.
DS1 1,000,000
LRU hit ratio 3.08%
DWC hit ratio 11.77%
DWC  LRU hit ratio delta 8.69%
DWC / LRU hit ratio rate 381%
DS1 2,000,000
LRU hit ratio 10.74%
DWC hit ratio 28.50%
DWC  LRU hit ratio delta 17.75%
DWC / LRU hit ratio rate 265%
DS1 3,000,000
LRU hit ratio 18.59%
DWC hit ratio 39.09%
DWC  LRU hit ratio delta 20.50%
DWC / LRU hit ratio rate 210%
DS1 4,000,000
LRU hit ratio 20.24%
DWC hit ratio 44.72%
DWC  LRU hit ratio delta 24.48%
DWC / LRU hit ratio rate 220%
DS1 5,000,000
LRU hit ratio 21.03%
DWC hit ratio 51.39%
DWC  LRU hit ratio delta 30.36%
DWC / LRU hit ratio rate 244%
DS1 6,000,000
LRU hit ratio 33.95%
DWC hit ratio 57.64%
DWC  LRU hit ratio delta 23.68%
DWC / LRU hit ratio rate 169%
DS1 7,000,000
LRU hit ratio 38.89%
DWC hit ratio 62.30%
DWC  LRU hit ratio delta 23.40%
DWC / LRU hit ratio rate 160%
DS1 8,000,000
LRU hit ratio 43.03%
DWC hit ratio 68.83%
DWC  LRU hit ratio delta 25.79%
DWC / LRU hit ratio rate 159%
S3
WTinyLFU > (TinyLFU) > (LIRS) > DWC, ARC > LRU
 DWC is an approximation of ARC.
S3 100,000
LRU hit ratio 2.32%
DWC hit ratio 10.15%
DWC  LRU hit ratio delta 7.83%
DWC / LRU hit ratio rate 436%
S3 200,000
LRU hit ratio 4.63%
DWC hit ratio 19.17%
DWC  LRU hit ratio delta 14.54%
DWC / LRU hit ratio rate 414%
S3 300,000
LRU hit ratio 7.58%
DWC hit ratio 25.12%
DWC  LRU hit ratio delta 17.53%
DWC / LRU hit ratio rate 331%
S3 400,000
LRU hit ratio 12.03%
DWC hit ratio 30.42%
DWC  LRU hit ratio delta 18.38%
DWC / LRU hit ratio rate 252%
S3 500,000
LRU hit ratio 22.76%
DWC hit ratio 38.04%
DWC  LRU hit ratio delta 15.27%
DWC / LRU hit ratio rate 167%
S3 600,000
LRU hit ratio 34.63%
DWC hit ratio 46.81%
DWC  LRU hit ratio delta 12.18%
DWC / LRU hit ratio rate 135%
S3 700,000
LRU hit ratio 46.04%
DWC hit ratio 55.70%
DWC  LRU hit ratio delta 9.66%
DWC / LRU hit ratio rate 120%
S3 800,000
LRU hit ratio 56.59%
DWC hit ratio 64.04%
DWC  LRU hit ratio delta 7.44%
DWC / LRU hit ratio rate 113%
OLTP
WTinyLFU > ARC > DWC > (LIRS) > LRU > (TinyLFU)
 DWC is an approximation of ARC.
OLTP 250
LRU hit ratio 16.47%
DWC hit ratio 19.39%
DWC  LRU hit ratio delta 2.92%
DWC / LRU hit ratio rate 117%
OLTP 500
LRU hit ratio 23.44%
DWC hit ratio 28.83%
DWC  LRU hit ratio delta 5.39%
DWC / LRU hit ratio rate 122%
OLTP 750
LRU hit ratio 28.28%
DWC hit ratio 34.11%
DWC  LRU hit ratio delta 5.83%
DWC / LRU hit ratio rate 120%
OLTP 1,000
LRU hit ratio 32.83%
DWC hit ratio 37.54%
DWC  LRU hit ratio delta 4.71%
DWC / LRU hit ratio rate 114%
OLTP 1,250
LRU hit ratio 36.20%
DWC hit ratio 39.74%
DWC  LRU hit ratio delta 3.53%
DWC / LRU hit ratio rate 109%
OLTP 1,500
LRU hit ratio 38.69%
DWC hit ratio 41.70%
DWC  LRU hit ratio delta 3.00%
DWC / LRU hit ratio rate 107%
OLTP 1,750
LRU hit ratio 40.78%
DWC hit ratio 43.33%
DWC  LRU hit ratio delta 2.54%
DWC / LRU hit ratio rate 106%
OLTP 2,000
LRU hit ratio 42.46%
DWC hit ratio 44.62%
DWC  LRU hit ratio delta 2.16%
DWC / LRU hit ratio rate 105%
GLI
WTinyLFU, (LIRS) > DWC > (TinyLFU) >> ARC > LRU
 DWC is an approximation of WTinyLFU.
GLI 250
LRU hit ratio 0.93%
DWC hit ratio 16.32%
DWC  LRU hit ratio delta 15.39%
DWC / LRU hit ratio rate 1753%
GLI 500
LRU hit ratio 0.96%
DWC hit ratio 32.84%
DWC  LRU hit ratio delta 31.88%
DWC / LRU hit ratio rate 3406%
GLI 750
LRU hit ratio 1.16%
DWC hit ratio 41.35%
DWC  LRU hit ratio delta 40.19%
DWC / LRU hit ratio rate 3554%
GLI 1,000
LRU hit ratio 11.22%
DWC hit ratio 49.61%
DWC  LRU hit ratio delta 38.39%
DWC / LRU hit ratio rate 442%
GLI 1,250
LRU hit ratio 21.25%
DWC hit ratio 52.60%
DWC  LRU hit ratio delta 31.34%
DWC / LRU hit ratio rate 247%
GLI 1,500
LRU hit ratio 36.56%
DWC hit ratio 53.78%
DWC  LRU hit ratio delta 17.22%
DWC / LRU hit ratio rate 147%
GLI 1,750
LRU hit ratio 45.04%
DWC hit ratio 55.66%
DWC  LRU hit ratio delta 10.62%
DWC / LRU hit ratio rate 123%
GLI 2,000
LRU hit ratio 57.41%
DWC hit ratio 57.96%
DWC  LRU hit ratio delta 0.54%
DWC / LRU hit ratio rate 100%
Throughput
80120% of lrucache.
Note that the number of trials per capacity for simulation 1,000,000 is insufficient.
No result with 10,000,000 because lrucache crushes with the next error on the next machine of GitHub Actions. It is verified that the error was thrown also when benchmarking only lrucache. Of course it is verified that DWC works fine under the same condition.
Error: Uncaught RangeError: Map maximum size exceeded
System:
OS: Linux 5.15 Ubuntu 20.04.5 LTS (Focal Fossa)
CPU: (2) x64 Intel(R) Xeon(R) Platinum 8370C CPU @ 2.80GHz
Memory: 5.88 GB / 6.78 GB
Clock: spica/clock
ISCCache: lrucache
LRUCache: spica/lru
DWCache: spica/cache
'Clock new x 1,328,833 ops/sec ±3.63% (113 runs sampled)'
'ISCCache new x 13,768 ops/sec ±1.00% (120 runs sampled)'
'LRUCache new x 27,168,783 ops/sec ±1.50% (122 runs sampled)'
'DWCache new x 6,049,201 ops/sec ±0.86% (122 runs sampled)'
'Clock simulation 100 x 13,493,137 ops/sec ±1.65% (121 runs sampled)'
'ISCCache simulation 100 x 8,651,793 ops/sec ±1.85% (121 runs sampled)'
'LRUCache simulation 100 x 10,604,646 ops/sec ±2.24% (120 runs sampled)'
'DWCache simulation 100 x 7,242,013 ops/sec ±1.65% (121 runs sampled)'
'Clock simulation 1,000 x 10,694,963 ops/sec ±1.81% (120 runs sampled)'
'ISCCache simulation 1,000 x 7,700,019 ops/sec ±1.90% (121 runs sampled)'
'LRUCache simulation 1,000 x 9,184,813 ops/sec ±2.13% (120 runs sampled)'
'DWCache simulation 1,000 x 7,041,470 ops/sec ±1.77% (120 runs sampled)'
'Clock simulation 10,000 x 10,517,215 ops/sec ±1.78% (122 runs sampled)'
'ISCCache simulation 10,000 x 7,365,593 ops/sec ±1.67% (121 runs sampled)'
'LRUCache simulation 10,000 x 8,685,666 ops/sec ±1.81% (121 runs sampled)'
'DWCache simulation 10,000 x 7,317,621 ops/sec ±1.42% (120 runs sampled)'
'Clock simulation 100,000 x 7,417,826 ops/sec ±1.60% (118 runs sampled)'
'ISCCache simulation 100,000 x 4,523,157 ops/sec ±1.22% (117 runs sampled)'
'LRUCache simulation 100,000 x 5,424,344 ops/sec ±2.10% (119 runs sampled)'
'DWCache simulation 100,000 x 4,190,537 ops/sec ±1.44% (113 runs sampled)'
'Clock simulation 1,000,000 x 4,519,623 ops/sec ±3.63% (106 runs sampled)'
'ISCCache simulation 1,000,000 x 2,081,961 ops/sec ±3.35% (101 runs sampled)'
'LRUCache simulation 1,000,000 x 2,686,808 ops/sec ±3.88% (103 runs sampled)'
'DWCache simulation 1,000,000 x 2,481,012 ops/sec ±2.54% (111 runs sampled)'
const key = random() < 0.9
? random() * capacity * 1  0
: random() * capacity * 9 + capacity  0;
cache.get(key) ?? cache.set(key, {});
Comprehensive evaluation
Hit ratio
Mathematical
Class  Algorithms 

Very high  WTinyLFU 
High  DWC, (LIRS) 
Middle  ARC, (TinyLFU) 
Low  LRU 
Engineering
Class  Algorithms 

High  DWC 
Middle  LRU 
Low  WTinyLFU, (LIRS), ARC, (TinyLFU) 
Efficiency
Total per entry  Algorithm  Key size 

32 bytes  LRU  1x 
34 bytes  DWC  1x 
60 bytes  ARC  2x 
72 bytes  WTinyLFU  1x 
72 bytes  (TinyLFU)  1x 
137 bytes  (LIRS)  3x 
438 bytes  (LIRS)  10x 
Resistance
Class  Effect  Algorithms 

Total  High  WTinyLFU, DWC 
Most  High  (TinyLFU), (LIRS) 
Few  Low  ARC 
None  None  LRU 
Throughput
Type  Algorithms 

Dynamic lists (Lockfree)  DWC > (LIRS) > ARC 
Bloom filter + Dynamic lists  (TinyLFU) 
Dynamic lists + Bloom filter  WTinyLFU 
Static list  LRU 
Latency
Worst time  Algorithms 

Constant  LRU, DWC, ARC 
Linear (1)  WTinyLFU > (TinyLFU) 
Linear (> 1)  (LIRS) 
Vulnerability
Type  Algorithms 

Degrade  (TinyLFU) 
Crush  (LIRS) 
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: 0100
readonly window?: number;
// Sample ratio of LRU in LFU.
// Range: 0100
readonly sample?: number;
readonly sweep?: {
readonly threshold?: number;
readonly ratio?: number;
readonly window?: number;
readonly room?: number;
readonly range?: number;
readonly shift?: number;
};
}
}
export class Cache<K, V> {
constructor(capacity: number, opts?: Cache.Options<K, V>);
constructor(opts: Cache.Options<K, V>);
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;
readonly length: number;
readonly size: number;
[Symbol.iterator](): Iterator<[K, V], undefined, undefined>;
}