Create slab allocator for small allocs (< 512 bytes) to avoid hitting the segment allocator constantly

[greg7mdp]

Currently, many nodeos allocations hit the segment manager. The table below shows the allocations/deallocation which occured during one hour of running nodeos.

We see that there were:

• over 12 million allocations of buffers of size less than 512 bytes
• less than 30 thousand allocations of buffers of size greater than 512 bytes

so 99.7% of allocations were of buffers less than 512 bytes.

We should have slab allocators for small buffer sizes to avoid hitting the segment manager for every small allocation/deallocation, with it heavy cost of rebalancing the avl tree of free blocks.

We propose to have 64 allocators, for each size (modulo 8 bytes) from 8 to 512.

Benefits:

1. much better efficiency
2. much reduced fragmentation of the segment manager heap
3. memory saving (at most 7 bytes wasted per allocation, while segment manager allocations have an overhead of 16 to 23 bytes).

Shared segment allocations after loading Aug-11-2024 snapshot

Runtime 1 hour, debug build of nodeos.

alloc size	num allocs	num free	bytes allocated	bytes freed
13	817	813	10,621	10,569
14	41	40	574	560
15	3	0	45	0
17	60,431	60,359	1,027,327	1,026,103
18	1,770	1,736	31,860	31,248
21	3,645	1,252	76,545	26,292
22	325,077	324,737	7,151,694	7,144,214
23	95	95	2,185	2,185
25	1,111,364	1,063,157	27,784,100	26,578,925
26	3,424	2,944	89,024	76,544
27	48	35	1,296	945
28	339,294	338,966	9,500,232	9,491,048
29	410,561	408,336	11,906,269	11,841,744
30	184,333	478	5,529,990	14,340
32	229	171	7,328	5,472
33	1,516,259	1,514,011	50,036,547	49,962,363
34	3,486	3,189	118,524	108,426
35	929	922	32,515	32,270
37	992	899	36,704	33,263
38	1	0	38	0
39	5	1	195	39
41	362,791	331,489	14,874,431	13,591,049
42	5	3	210	126
43	75,987	75,295	3,267,441	3,237,685
44	13	7	572	308
45	230	146	10,350	6,570
46	11,958	6,009	550,068	276,414
47	41	20	1,927	940
48	5,110	2,831	245,280	135,888
49	217,316	207,617	10,648,484	10,173,233
50	10,917	9,588	545,850	479,400
51	11,025	4,721	562,275	240,771
52	479	262	24,908	13,624
53	18,643	18,069	988,079	957,657
54	16,457	16,321	888,678	881,334
55	220	107	12,100	5,885
56	2,218	1,071	124,208	59,976
57	125,596	117,037	7,158,972	6,671,109
58	60,582	32,888	3,513,756	1,907,504
59	1,138	736	67,142	43,424
60	5,260	2,007	315,600	120,420
61	704	499	42,944	30,439
62	413,328	409,032	25,626,336	25,359,984
63	370	222	23,310	13,986
64	7,586	5,186	485,504	331,904
65-72	227,494	223,404	16,379,568	16,085,088
73-80	17,142	12,995	1,371,360	1,039,600
81-88	22,404	18,508	1,971,552	1,628,704
89-96	127,842	119,441	12,272,832	11,466,336
97-104	72,559	71,439	7,546,136	7,429,656
105-112	7,885	4,253	883,120	476,336
113-120	107,856	106,671	12,942,720	12,800,520
121-128	14,556	13,644	1,863,168	1,746,432
129-136	49,710	49,203	6,760,560	6,691,608
137-144	136,478	136,213	19,652,832	19,614,672
145-152	20,941	20,548	3,183,032	3,123,296
153-160	4,468	4,224	714,880	675,840
161-168	340,005	339,595	57,120,840	57,051,960
169-176	4,698	3,988	826,848	701,888
177-184	730	628	134,320	115,552
185-192	1,733	1,554	332,736	298,368
193-200	896	451	179,200	90,200
201-208	299	262	62,192	54,496
209-216	843	610	182,088	131,760
217-224	1,181	1,129	264,544	252,896
225-232	1,770	1,635	410,640	379,320
233-240	217	180	52,080	43,200
241-248	682	376	169,136	93,248
249-256	10,092	10,063	2,583,552	2,576,128
257-264	80	40	21,120	10,560
265-272	250	236	68,000	64,192
273-280	606	145	169,680	40,600
281-288	114	103	32,832	29,664
289-296	253	236	74,888	69,856
297-304	236	210	71,744	63,840
305-312	1,346	1,320	419,952	411,840
313-320	1,261	1,193	403,520	381,760
321-328	566	550	185,648	180,400
329-336	11	8	3,696	2,688
337-344	968	930	332,992	319,920
345-352	418	352	147,136	123,904
353-360	113	112	40,680	40,320
361-368	11	10	4,048	3,680
369-376	116	109	43,616	40,984
377-384	207	140	79,488	53,760
385-392	236	219	92,512	85,848
393-400	75	57	30,000	22,800
401-408	3,435	3,434	1,401,480	1,401,072
409-416	5	4	2,080	1,664
417-424	663	560	281,112	237,440
425-432	19	17	8,208	7,344
433-440	178	173	78,320	76,120
441-448	22	17	9,856	7,616
449-456	35	33	15,960	15,048
457-464	2	1	928	464
465-472	145	142	68,440	67,024
473-480	12	10	5,760	4,800
481-488	651	552	317,688	269,376
489-496	21	16	10,416	7,936
497-504	3,422	3,387	1,724,688	1,707,048
505-512	6,327,397	6,326,835	3,239,627,264	3,239,339,520
513-1,024	24,618	24,024	25,208,832	24,600,576
1,025-2,048	4,638	4,586	9,498,624	9,392,128
2,049-4,096	282	263	1,155,072	1,077,248
4,097-8,192	2,565	280	21,012,480	2,293,760
8,193-16,384	469	456	7,684,096	7,471,104
16,385-32,768	930	924	30,474,240	30,277,632
32,769-65,536	1,355	1,354	88,801,280	88,735,744
65,537-131,072	1,351	1,350	177,078,272	176,947,200
131,073-262,144	277	273	72,613,888	71,565,312

total allocs: 4,010,482,510 bytes
total deallocs: 3,972,943,076 bytes