Context 0.1 performance

Context 0.1 performance.md

Benchmarking Context 0.1

Baseline

• strcmp in table read
• O(entries) lookup in Huffman tables

Unit tests

• BENCH TEXT: 0.007524s
• BENCH BIN: 0.008647s
• BENCH RATIO: 1.14925

real-js-samples

• BENCH TEXT: 8.58763s
• BENCH BIN: 14.5473s
• BENCH RATIO: 1.69

Introducing sHuffman HashMaps

• strcmp in table read
• O(entries) lookup in HuffmanTableBool, HuffmanTableMaybeInterface (HuffmanTableSmall)
• O(bit_length) lookup in all other tables (HuffmanTableMap)

Unit tests

• BENCH TEXT: 0.0076697s
• BENCH BIN: 0.0109749s
• BENCH RATIO: 1.43094

Ratio slowdown

Additional stats

The following count does not count instances of HuffmanTableSmall that are guaranteed to have size 0-2.

Size	Number of HuffmanTableMap	Ratio
1	56050	0.637004205023298
2	12120	0.137742925332424
3	8870	0.100806909876122
4	2880	0.0327309921582
5	1080	0.012274122059325
6	1350	0.015342652574156
7	1120	0.012728719172633
8	640	0.007273553812933
9	420	0.004773269689737
10	600	0.006818956699625
11	1320	0.015001704739175
12	360	0.004091374019775
13	290	0.003295829071485
14	200	0.002272985566542
15	120	0.001363791339925
16	120	0.001363791339925
17	80	0.000909194226617
18	70	0.00079554494829
19	60	0.000681895669962
20	40	0.000454597113308
21	50	0.000568246391635
22	20	0.000227298556654
23	40	0.000454597113308
24	10	0.000113649278327
25	20	0.000227298556654
26	10	0.000113649278327
27	0	0
28	0	0
29	0	0
30	10	0.000113649278327
31	0	0
32	0	0
33	10	0.000113649278327
34	10	0.000113649278327
35	0	0
36	0	0
37	0	0
38	0	0
39	0	0
40	10	0.000113649278327
41	0	0
42	0	0
43	0	0
44	0	0
45	10	0.000113649278327
46	0	0
47	0	0
48	0	0
49	0	0
50	0	0
51	0	0
52	0	0
53	0	0
54	0	0
55	0	0
56	0	0
57	0	0
58	0	0
59	0	0
60	0	0
61	0	0
62	0	0
63	0	0
64	0	0
65	0	0
66	0	0
67	0	0
68	0	0
69	0	0
70	0	0
71	0	0
72	0	0
73	0	0
74	0	0
75	0	0
76	0	0
77	0	0
78	0	0
79	0	0
80	0	0
81	0	0
82	0	0
83	0	0
84	0	0
85	0	0
86	0	0
87	0	0
88	0	0
89	0	0
90	0	0
91	0	0
92	0	0
93	0	0
94	0	0
95	0	0
96	0	0
97	0	0
98	0	0
99	0	0
100	0	0
101	0	0
102	0	0
103	0	0
104	0	0
105	0	0
106	0	0
107	0	0
108	0	0
109	0	0
110	0	0
111	0	0
112	0	0
113	0	0
114	0	0
115	0	0
116	0	0
117	0	0
118	0	0
119	0	0
120	0	0
121	0	0
122	0	0
123	0	0
124	0	0
125	0	0
126	0	0
127	0	0
128	0	0
129	0	0
130	0	0
131	0	0
132	0	0
133	0	0
134	0	0
135	0	0
136	0	0
137	0	0
138	0	0
139	0	0
140	0	0
141	0	0
142	0	0
143	0	0
144	0	0
145	0	0
146	0	0
147	0	0
148	0	0
149	0	0
150	0	0
151	0	0
152	0	0
153	0	0
154	0	0
155	0	0
156	0	0
157	0	0
158	0	0
159	0	0
160	0	0
161	0	0
162	0	0
163	0	0
164	0	0
165	0	0
166	0	0
167	0	0
168	0	0
169	0	0
170	0	0
171	0	0
172	0	0
173	0	0
174	0	0
175	0	0
176	0	0
177	0	0
178	0	0
179	0	0
180	0	0
181	0	0
182	0	0
183	0	0
184	0	0
185	0	0
186	0	0
187	0	0
188	0	0
189	0	0
190	0	0
191	0	0
192	0	0
193	0	0
194	0	0
195	0	0
196	0	0
197	0	0
198	0	0
199	0	0
200	0	0
201	0	0
202	0	0
203	0	0
204	0	0
205	0	0
206	0	0
207	0	0
208	0	0
209	0	0
210	0	0
211	0	0
212	0	0
213	0	0
214	0	0
215	0	0
216	0	0
217	0	0
218	0	0
219	0	0
220	0	0
221	0	0
222	0	0
223	0	0
224	0	0
225	0	0
226	0	0
227	0	0
228	0	0
229	0	0
230	0	0
231	0	0
232	0	0
233	0	0
234	0	0
235	0	0
236	0	0
237	0	0
238	0	0
239	0	0
240	0	0
241	0	0
242	0	0
243	0	0
244	0	0
245	0	0
246	0	0
247	0	0
248	0	0
249	0	0
250	0	0
251	0	0
252	0	0
253	0	0
254	0	0
255	0	0
256	0	0

256 | 0 | 0

real-js-samples

• BENCH TEXT: 12.3678s
• BENCH BIN: 17.509s
• BENCH RATIO: 1.42

Ratio improvement

Additional statistics

The following count does not count instances of HuffmanTableSmall that are guaranteed to have size 0-2.

Size	Number of HuffmanTableMap	Ratio	Number of tables with ≥ size
1	461446	44.01%	100.00%
2	95377	9.10%	55.99%
3	75778	7.23%	46.90%
4	57801	5.51%	39.67%
5	49093	4.68%	34.16%
6	40817	3.89%	29.48%
7	35317	3.37%	25.58%
8	28150	2.68%	22.22%
9	21652	2.06%	19.53%
10	18405	1.76%	17.47%
11	16388	1.56%	15.71%
12	13963	1.33%	14.15%
13	12365	1.18%	12.82%
14	12148	1.16%	11.64%
15	10393	0.99%	10.48%
16	9408	0.90%	9.49%
17	8508	0.81%	8.59%
18	7953	0.76%	7.78%
19	4435	0.42%	7.02%
20	3032	0.29%	6.60%
21	2301	0.22%	6.31%
22	2026	0.19%	6.09%
23	1963	0.19%	5.90%
24	1861	0.18%	5.71%
25	1326	0.13%	5.53%
26	1292	0.12%	5.40%
27	1312	0.13%	5.28%
28	1171	0.11%	5.16%
29	1071	0.10%	5.04%
30	1078	0.10%	4.94%
31	1000	0.10%	4.84%
32	828	0.08%	4.74%
33	879	0.08%	4.67%
34	772	0.07%	4.58%
35	915	0.09%	4.51%
36	893	0.09%	4.42%
37	585	0.06%	4.34%
38	601	0.06%	4.28%
39	873	0.08%	4.22%
40	823	0.08%	4.14%
41	613	0.06%	4.06%
42	566	0.05%	4.00%
43	531	0.05%	3.95%
44	484	0.05%	3.90%
45	577	0.06%	3.85%
46	444	0.04%	3.80%
47	584	0.06%	3.75%
48	416	0.04%	3.70%
49	473	0.05%	3.66%
50	410	0.04%	3.61%
51	479	0.05%	3.57%
52	399	0.04%	3.53%
53	438	0.04%	3.49%
54	457	0.04%	3.45%
55	361	0.03%	3.41%
56	422	0.04%	3.37%
57	366	0.03%	3.33%
58	429	0.04%	3.30%
59	385	0.04%	3.25%
60	268	0.03%	3.22%
61	276	0.03%	3.19%
62	360	0.03%	3.17%
63	282	0.03%	3.13%
64	289	0.03%	3.10%
65	257	0.02%	3.08%
66	351	0.03%	3.05%
67	342	0.03%	3.02%
68	203	0.02%	2.99%
69	374	0.04%	2.97%
70	285	0.03%	2.93%
71	298	0.03%	2.90%
72	302	0.03%	2.88%
73	237	0.02%	2.85%
74	263	0.03%	2.82%
75	236	0.02%	2.80%
76	260	0.02%	2.78%
77	228	0.02%	2.75%
78	199	0.02%	2.73%
79	253	0.02%	2.71%
80	201	0.02%	2.69%
81	211	0.02%	2.67%
82	185	0.02%	2.65%
83	236	0.02%	2.63%
84	180	0.02%	2.61%
85	190	0.02%	2.59%
86	150	0.01%	2.57%
87	191	0.02%	2.56%
88	220	0.02%	2.54%
89	166	0.02%	2.52%
90	180	0.02%	2.50%
91	144	0.01%	2.49%
92	157	0.01%	2.47%
93	130	0.01%	2.46%
94	157	0.01%	2.45%
95	172	0.02%	2.43%
96	210	0.02%	2.41%
97	148	0.01%	2.39%
98	193	0.02%	2.38%
99	146	0.01%	2.36%
100	149	0.01%	2.35%
101	143	0.01%	2.33%
102	164	0.02%	2.32%
103	138	0.01%	2.30%
104	94	0.01%	2.29%
105	102	0.01%	2.28%
106	111	0.01%	2.27%
107	125	0.01%	2.26%
108	190	0.02%	2.25%
109	146	0.01%	2.23%
110	122	0.01%	2.22%
111	83	0.01%	2.21%
112	115	0.01%	2.20%
113	126	0.01%	2.19%
114	140	0.01%	2.17%
115	167	0.02%	2.16%
116	147	0.01%	2.15%
117	105	0.01%	2.13%
118	131	0.01%	2.12%
119	132	0.01%	2.11%
120	81	0.01%	2.10%
121	67	0.01%	2.09%
122	85	0.01%	2.08%
123	88	0.01%	2.07%
124	107	0.01%	2.07%
125	118	0.01%	2.06%
126	108	0.01%	2.04%
127	68	0.01%	2.03%
128	95	0.01%	2.03%
129	124	0.01%	2.02%
130	127	0.01%	2.01%
131	77	0.01%	1.99%
132	137	0.01%	1.99%
133	135	0.01%	1.97%
134	103	0.01%	1.96%
135	78	0.01%	1.95%
136	123	0.01%	1.94%
137	119	0.01%	1.93%
138	107	0.01%	1.92%
139	110	0.01%	1.91%
140	108	0.01%	1.90%
141	64	0.01%	1.89%
142	113	0.01%	1.88%
143	142	0.01%	1.87%
144	67	0.01%	1.86%
145	81	0.01%	1.85%
146	102	0.01%	1.85%
147	108	0.01%	1.84%
148	103	0.01%	1.83%
149	56	0.01%	1.82%
150	69	0.01%	1.81%
151	84	0.01%	1.80%
152	76	0.01%	1.80%
153	89	0.01%	1.79%
154	88	0.01%	1.78%
155	51	0.00%	1.77%
156	96	0.01%	1.77%
157	94	0.01%	1.76%
158	60	0.01%	1.75%
159	100	0.01%	1.74%
160	118	0.01%	1.73%
161	54	0.01%	1.72%
162	113	0.01%	1.72%
163	106	0.01%	1.71%
164	98	0.01%	1.70%
165	76	0.01%	1.69%
166	113	0.01%	1.68%
167	168	0.02%	1.67%
168	128	0.01%	1.65%
169	75	0.01%	1.64%
170	127	0.01%	1.63%
171	71	0.01%	1.62%
172	52	0.00%	1.61%
173	58	0.01%	1.61%
174	38	0.00%	1.60%
175	52	0.00%	1.60%
176	60	0.01%	1.60%
177	100	0.01%	1.59%
178	65	0.01%	1.58%
179	62	0.01%	1.57%
180	63	0.01%	1.57%
181	59	0.01%	1.56%
182	57	0.01%	1.56%
183	72	0.01%	1.55%
184	74	0.01%	1.54%
185	73	0.01%	1.54%
186	57	0.01%	1.53%
187	166	0.02%	1.52%
188	106	0.01%	1.51%
189	52	0.00%	1.50%
190	44	0.00%	1.49%
191	50	0.00%	1.49%
192	62	0.01%	1.48%
193	53	0.01%	1.48%
194	75	0.01%	1.47%
195	66	0.01%	1.47%
196	48	0.00%	1.46%
197	53	0.01%	1.46%
198	83	0.01%	1.45%
199	58	0.01%	1.44%
200	47	0.00%	1.44%
201	65	0.01%	1.43%
202	80	0.01%	1.43%
203	60	0.01%	1.42%
204	64	0.01%	1.41%
205	97	0.01%	1.41%
206	35	0.00%	1.40%
207	18	0.00%	1.39%
208	48	0.00%	1.39%
209	49	0.00%	1.39%
210	71	0.01%	1.38%
211	40	0.00%	1.38%
212	47	0.00%	1.37%
213	51	0.00%	1.37%
214	79	0.01%	1.36%
215	51	0.00%	1.36%
216	55	0.01%	1.35%
217	30	0.00%	1.35%
218	53	0.01%	1.34%
219	52	0.00%	1.34%
220	63	0.01%	1.33%
221	34	0.00%	1.33%
222	59	0.01%	1.32%
223	44	0.00%	1.32%
224	46	0.00%	1.31%
225	90	0.01%	1.31%
226	55	0.01%	1.30%
227	30	0.00%	1.30%
228	58	0.01%	1.29%
229	44	0.00%	1.29%
230	29	0.00%	1.28%
231	42	0.00%	1.28%
232	21	0.00%	1.28%
233	48	0.00%	1.27%
234	27	0.00%	1.27%
235	59	0.01%	1.27%
236	38	0.00%	1.26%
237	46	0.00%	1.26%
238	26	0.00%	1.25%
239	55	0.01%	1.25%
240	20	0.00%	1.25%
241	50	0.00%	1.24%
242	60	0.01%	1.24%
243	17	0.00%	1.23%
244	44	0.00%	1.23%
245	35	0.00%	1.23%
246	26	0.00%	1.22%
247	26	0.00%	1.22%
248	68	0.01%	1.22%
249	38	0.00%	1.21%
250	55	0.01%	1.21%
251	55	0.01%	1.20%
252	42	0.00%	1.20%
253	57	0.01%	1.19%
254	29	0.00%	1.19%
255	36	0.00%	1.19%
256	53	0.01%	1.18%
257+	12353	1.18%	1.18%

Conclusion:

• we should be able to handle cases 1-256 with HuffmanTableAllPrefixes (larger memory use, slower initialization but constant-time lookup) and keep HuffmanTableMap for larger sets.