-
Notifications
You must be signed in to change notification settings - Fork 3.8k
/
fifo_cache
123 lines (94 loc) · 2.23 KB
/
fifo_cache
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
# 24240 bytes is enough for a fifoCache with 3 fully filled eviction block.
init capacity=24240
----
cache_size: 0
newInputBlock name=block1 percentageFilled=0.25
----
blockSize: 42
insertBlock name=block1
----
cache_size: 5056
verifyBlockExistence names=block1
----
inspectEvictionListShape
----
blockIdx: 0, blockSize: 42
ensureEvictionBlockOrdering names=block1
----
blockIdx: 0, blockName: block1
newInputBlock name=block2 percentageFilled=0.50
----
blockSize: 84
insertBlock name=block2
----
cache_size: 11120
verifyBlockExistence names=block1,block2
----
inspectEvictionListShape
----
blockIdx: 0, blockSize: 42
blockIdx: 1, blockSize: 84
ensureEvictionBlockOrdering names=block1,block2
----
blockIdx: 0, blockName: block1
blockIdx: 1, blockName: block2
newInputBlock name=block3 percentageFilled=1.0
----
blockSize: 168
insertBlock name=block3
----
cache_size: 19200
verifyBlockExistence names=block1,block2,block3
----
inspectEvictionListShape
----
blockIdx: 0, blockSize: 42
blockIdx: 1, blockSize: 84
blockIdx: 2, blockSize: 168
ensureEvictionBlockOrdering names=block1,block2,block3
----
blockIdx: 0, blockName: block1
blockIdx: 1, blockName: block2
blockIdx: 2, blockName: block3
# Any subsequent insertion will cause evictions
newInputBlock name=block4 percentageFilled=1.0
----
blockSize: 168
insertBlock name=block4
----
cache_size: 22224
verifyBlockExistence names=block2,block3,block4
----
verifyBlockNonExistence names=block1
----
inspectEvictionListShape
----
blockIdx: 0, blockSize: 84
blockIdx: 1, blockSize: 168
blockIdx: 2, blockSize: 168
ensureEvictionBlockOrdering names=block2,block3,block4
----
blockIdx: 0, blockName: block2
blockIdx: 1, blockName: block3
blockIdx: 2, blockName: block4
# Inserting sparse blocks can cause premature eviction.
newInputBlock name=block5 percentageFilled=0.01786
----
blockSize: 3
insertBlock name=block5
----
cache_size: 20280
verifyBlockExistence names=block3,block4,block5
----
verifyBlockNonExistence names=block1,block2
----
inspectEvictionListShape
----
blockIdx: 0, blockSize: 168
blockIdx: 1, blockSize: 168
blockIdx: 2, blockSize: 3
ensureEvictionBlockOrdering names=block3,block4,block5
----
blockIdx: 0, blockName: block3
blockIdx: 1, blockName: block4
blockIdx: 2, blockName: block5