Model

Restart interval of front coding

The universal 16 comes straight from the memory hierarchy.

cost (r) = α lo g_{2} \frac{N}{r} + \frac{r}{2}, r^{*} = \frac{2 α}{ln 2}

$r$: Restart interval; a full key stored every r entries
$N$: Entries; entries in the block
$α$: Miss weight; a binary step weighted α times a linear step

Trade-off: Ordering vs. parallelism

How it behaves

One input on the horizontal axis, the others held fixed.

counting comparisons (α = 1)counting cache misses (α = 6.5)

Data table

Search cost by restart interval (N = 10⁶)
Restart interval r	series	Cost (linear-step units)
1	counting comparisons (α = 1)	20.4
1.06	counting comparisons (α = 1)	20.4
1.13	counting comparisons (α = 1)	20.3
1.2	counting comparisons (α = 1)	20.3
1.27	counting comparisons (α = 1)	20.2
1.35	counting comparisons (α = 1)	20.2
1.44	counting comparisons (α = 1)	20.1
1.53	counting comparisons (α = 1)	20.1
1.62	counting comparisons (α = 1)	20
1.73	counting comparisons (α = 1)	20
1.83	counting comparisons (α = 1)	20
1.95	counting comparisons (α = 1)	19.9
2.07	counting comparisons (α = 1)	19.9
2.2	counting comparisons (α = 1)	19.9
2.34	counting comparisons (α = 1)	19.9
2.48	counting comparisons (α = 1)	19.9
2.64	counting comparisons (α = 1)	19.9
2.8	counting comparisons (α = 1)	19.8
2.98	counting comparisons (α = 1)	19.8
3.17	counting comparisons (α = 1)	19.9
3.36	counting comparisons (α = 1)	19.9
3.57	counting comparisons (α = 1)	19.9
3.8	counting comparisons (α = 1)	19.9
4.03	counting comparisons (α = 1)	19.9
4.29	counting comparisons (α = 1)	20
4.56	counting comparisons (α = 1)	20
4.84	counting comparisons (α = 1)	20.1
5.14	counting comparisons (α = 1)	20.1
5.46	counting comparisons (α = 1)	20.2
5.81	counting comparisons (α = 1)	20.3
6.17	counting comparisons (α = 1)	20.4
6.55	counting comparisons (α = 1)	20.5
6.96	counting comparisons (α = 1)	20.6
7.4	counting comparisons (α = 1)	20.7
7.86	counting comparisons (α = 1)	20.9
8.35	counting comparisons (α = 1)	21
8.88	counting comparisons (α = 1)	21.2
9.43	counting comparisons (α = 1)	21.4
10	counting comparisons (α = 1)	21.6
10.6	counting comparisons (α = 1)	21.8
11.3	counting comparisons (α = 1)	22.1
12	counting comparisons (α = 1)	22.4
12.8	counting comparisons (α = 1)	22.6
13.6	counting comparisons (α = 1)	23
14.4	counting comparisons (α = 1)	23.3
15.3	counting comparisons (α = 1)	23.7
16.3	counting comparisons (α = 1)	24
17.3	counting comparisons (α = 1)	24.5
18.4	counting comparisons (α = 1)	24.9
19.5	counting comparisons (α = 1)	25.4
20.7	counting comparisons (α = 1)	25.9
22	counting comparisons (α = 1)	26.5
23.4	counting comparisons (α = 1)	27.1
24.9	counting comparisons (α = 1)	27.7
26.4	counting comparisons (α = 1)	28.4
28.1	counting comparisons (α = 1)	29.2
29.9	counting comparisons (α = 1)	30
31.7	counting comparisons (α = 1)	30.8
33.7	counting comparisons (α = 1)	31.7
35.8	counting comparisons (α = 1)	32.7
38.1	counting comparisons (α = 1)	33.7
40.4	counting comparisons (α = 1)	34.8
43	counting comparisons (α = 1)	36
45.6	counting comparisons (α = 1)	37.2
48.5	counting comparisons (α = 1)	38.6
51.5	counting comparisons (α = 1)	40
54.8	counting comparisons (α = 1)	41.5
58.2	counting comparisons (α = 1)	43.2
61.8	counting comparisons (α = 1)	44.9
65.7	counting comparisons (α = 1)	46.7
69.8	counting comparisons (α = 1)	48.7
74.2	counting comparisons (α = 1)	50.8
78.8	counting comparisons (α = 1)	53
83.7	counting comparisons (α = 1)	55.4
89	counting comparisons (α = 1)	57.9
94.5	counting comparisons (α = 1)	60.6
100	counting comparisons (α = 1)	63.5
107	counting comparisons (α = 1)	66.5
113	counting comparisons (α = 1)	69.8
120	counting comparisons (α = 1)	73.3
128	counting comparisons (α = 1)	76.9
1	counting cache misses (α = 6.5)	130
1.06	counting cache misses (α = 6.5)	130
1.13	counting cache misses (α = 6.5)	129
1.2	counting cache misses (α = 6.5)	128
1.27	counting cache misses (α = 6.5)	128
1.35	counting cache misses (α = 6.5)	127
1.44	counting cache misses (α = 6.5)	127
1.53	counting cache misses (α = 6.5)	126
1.62	counting cache misses (α = 6.5)	126
1.73	counting cache misses (α = 6.5)	125
1.83	counting cache misses (α = 6.5)	125
1.95	counting cache misses (α = 6.5)	124
2.07	counting cache misses (α = 6.5)	124
2.2	counting cache misses (α = 6.5)	123
2.34	counting cache misses (α = 6.5)	123
2.48	counting cache misses (α = 6.5)	122
2.64	counting cache misses (α = 6.5)	122
2.8	counting cache misses (α = 6.5)	121
2.98	counting cache misses (α = 6.5)	121
3.17	counting cache misses (α = 6.5)	120
3.36	counting cache misses (α = 6.5)	120
3.57	counting cache misses (α = 6.5)	119
3.8	counting cache misses (α = 6.5)	119
4.03	counting cache misses (α = 6.5)	118
4.29	counting cache misses (α = 6.5)	118
4.56	counting cache misses (α = 6.5)	118
4.84	counting cache misses (α = 6.5)	117
5.14	counting cache misses (α = 6.5)	117
5.46	counting cache misses (α = 6.5)	116
5.81	counting cache misses (α = 6.5)	116
6.17	counting cache misses (α = 6.5)	116
6.55	counting cache misses (α = 6.5)	115
6.96	counting cache misses (α = 6.5)	115
7.4	counting cache misses (α = 6.5)	114
7.86	counting cache misses (α = 6.5)	114
8.35	counting cache misses (α = 6.5)	114
8.88	counting cache misses (α = 6.5)	114
9.43	counting cache misses (α = 6.5)	113
10	counting cache misses (α = 6.5)	113
10.6	counting cache misses (α = 6.5)	113
11.3	counting cache misses (α = 6.5)	112
12	counting cache misses (α = 6.5)	112
12.8	counting cache misses (α = 6.5)	112
13.6	counting cache misses (α = 6.5)	112
14.4	counting cache misses (α = 6.5)	112
15.3	counting cache misses (α = 6.5)	112
16.3	counting cache misses (α = 6.5)	112
17.3	counting cache misses (α = 6.5)	111
18.4	counting cache misses (α = 6.5)	111
19.5	counting cache misses (α = 6.5)	111
20.7	counting cache misses (α = 6.5)	111
22	counting cache misses (α = 6.5)	112
23.4	counting cache misses (α = 6.5)	112
24.9	counting cache misses (α = 6.5)	112
26.4	counting cache misses (α = 6.5)	112
28.1	counting cache misses (α = 6.5)	112
29.9	counting cache misses (α = 6.5)	113
31.7	counting cache misses (α = 6.5)	113
33.7	counting cache misses (α = 6.5)	113
35.8	counting cache misses (α = 6.5)	114
38.1	counting cache misses (α = 6.5)	114
40.4	counting cache misses (α = 6.5)	115
43	counting cache misses (α = 6.5)	116
45.6	counting cache misses (α = 6.5)	117
48.5	counting cache misses (α = 6.5)	117
51.5	counting cache misses (α = 6.5)	118
54.8	counting cache misses (α = 6.5)	119
58.2	counting cache misses (α = 6.5)	121
61.8	counting cache misses (α = 6.5)	122
65.7	counting cache misses (α = 6.5)	123
69.8	counting cache misses (α = 6.5)	125
74.2	counting cache misses (α = 6.5)	126
78.8	counting cache misses (α = 6.5)	128
83.7	counting cache misses (α = 6.5)	130
89	counting cache misses (α = 6.5)	132
94.5	counting cache misses (α = 6.5)	134
100	counting cache misses (α = 6.5)	137
107	counting cache misses (α = 6.5)	139
113	counting cache misses (α = 6.5)	142
120	counting cache misses (α = 6.5)	145
128	counting cache misses (α = 6.5)	148

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

Encoding, Serialization & Compression
What do we turn our values into when we turn them into bytes, and what does that choice cost?
$lo g_{2} (N / r) + r /2; r \approx 2 α / ln 2$
Read it in place →