Malloc internal memory fragmentation footprint

Author: Wojciech Muła
Added on:2019-02-03

Contents

Introduction

When we allocate memory using malloc or another interface, like operator new in C++, we get a pointer and promise that nobody else would acquire the same memory area. But underneath, more memory is needed. For instance the allocator has to keep the size of block to implement realloc.

More important is that the allocator unlikely allocate the exact number of bytes we requested, rather it will round the size up. Internal memory fragmentation is how we call this extra memory — which is allocated, but not legally available for a program.

This text shows internal memory fragmentation effects in different synthetic scenarios. However, memory fragmentation is a real problem. I came across this issue when was developing pyahcorasic module, that is built around multi-way trees — tries. To build a trie we need to allocate a large number of quite small fixed-size nodes associated with (also rather small) edge structures of variable size. It appeared that while theoretical size of all structures is smaller than memory I had available in my system, malloc reported no memory.

malloc in GNU libc

GNU libc provides a set of functions which allow to query statistics of the allocator; function mallinfo seems to be most friendly, as it returns a structure. The structure has two fields interesting :

Experiments

In experiments we allocate a defined memory by multiple calls of malloc; target sizes are: 1MB, 10MB and 100MB.

Each malloc call gets either a fixed number, or a random number from given range.

Fixed size

allocations libc memory usage
count min [B] max [B] total [B] allocated [B] free [B] waste [B] waste [%]
approx target memory usage: 1,048,576
1,048,576 1 1 1,048,576 33,627,744 29,088 32,550,080 96.80
524,288 2 2 1,048,576 16,850,528 45,472 15,756,480 93.51
349,526 3 3 1,048,578 11,258,144 95,968 10,113,598 89.83
262,144 4 4 1,048,576 8,461,920 53,664 7,359,680 86.97
209,716 5 5 1,048,580 6,784,224 109,344 5,626,300 82.93
174,763 6 6 1,048,578 5,665,728 11,328 4,605,822 81.29
149,797 7 7 1,048,579 4,866,816 134,400 3,683,837 75.69
131,072 8 8 1,048,576 4,267,616 57,760 3,161,280 74.08
116,509 9 9 1,048,581 3,801,600 118,272 2,634,747 69.31
104,858 10 10 1,048,580 3,428,768 85,600 2,294,588 66.92
95,326 11 11 1,048,586 3,123,744 120,288 1,954,870 62.58
87,382 12 12 1,048,584 2,869,536 104,160 1,716,792 59.83
80,660 13 13 1,048,580 2,654,432 48,928 1,556,924 58.65
74,899 14 14 1,048,586 2,470,080 98,112 1,323,382 53.58
69,906 15 15 1,048,590 2,310,304 122,720 1,138,994 49.30
65,536 16 16 1,048,576 2,170,464 127,392 994,496 45.82
61,681 17 17 1,048,577 2,047,104 115,584 882,943 43.13
58,255 18 18 1,048,590 1,937,472 90,048 798,834 41.23
55,189 19 19 1,048,591 1,839,360 52,992 737,777 40.11
52,429 20 20 1,048,580 1,751,040 6,144 696,316 39.77
49,933 21 21 1,048,593 1,671,168 86,016 536,559 32.11
47,663 22 22 1,048,586 1,598,528 23,488 526,454 32.93
45,591 23 23 1,048,593 1,532,224 89,792 393,839 25.70
43,691 24 24 1,048,584 1,471,424 15,424 407,416 27.69
41,944 25 25 1,048,600 2,086,624 76,064 961,960 46.10
40,330 26 26 1,048,580 2,009,152 18,368 942,204 46.90
38,837 27 27 1,048,599 1,937,488 90,032 798,857 41.23
37,450 28 28 1,048,600 1,870,912 21,440 800,872 42.81
36,158 29 29 1,048,582 1,808,896 83,456 676,858 37.42
34,953 30 30 1,048,590 1,751,056 6,128 696,338 39.77
33,826 31 31 1,048,606 1,696,960 60,224 588,130 34.66
32,768 32 32 1,048,576 1,646,176 111,008 486,592 29.56
21,846 48 48 1,048,608 1,471,456 15,392 407,456 27.69
16,384 64 64 1,048,576 1,384,032 102,816 232,640 16.81
8,192 128 128 1,048,576 1,252,960 98,720 105,664 8.43
4,096 256 256 1,048,576 1,187,424 29,088 109,760 9.24
2,048 512 512 1,048,576 1,154,656 61,856 44,224 3.83
1,024 1,024 1,024 1,048,576 1,138,272 78,240 11,456 1.01
512 2,048 2,048 1,048,576 1,130,080 86,432 -4,928 -0.44
approx target memory usage: 10,485,760
10,485,760 1 1 10,485,760 335,617,632 4,512 325,127,360 96.87
5,242,880 2 2 10,485,760 167,845,472 33,184 157,326,528 93.73
3,495,254 3 3 10,485,762 111,921,440 132,832 101,302,846 90.51
2,621,440 4 4 10,485,760 83,959,392 115,104 73,358,528 87.37
2,097,152 5 5 10,485,760 67,182,176 131,488 56,564,928 84.20
1,747,627 6 6 10,485,762 55,997,376 97,344 45,414,270 81.10
1,497,966 7 7 10,485,762 48,008,224 111,584 37,410,878 77.93
1,310,720 8 8 10,485,760 42,016,352 20,896 31,509,696 74.99
1,165,085 9 9 10,485,765 37,356,032 85,504 26,784,763 71.70
1,048,576 10 10 10,485,760 33,627,744 29,088 23,112,896 68.73
953,251 11 11 10,485,761 30,577,344 105,792 19,985,791 65.36
873,814 12 12 10,485,768 28,035,360 79,584 17,470,008 62.31
806,597 13 13 10,485,761 25,884,416 67,840 15,330,815 59.23
748,983 14 14 10,485,762 24,040,768 19,136 13,535,870 56.30
699,051 15 15 10,485,765 22,442,944 130,112 11,827,067 52.70
655,360 16 16 10,485,760 21,044,832 41,376 10,517,696 49.98
616,810 17 17 10,485,770 19,811,232 58,464 9,266,998 46.78
582,543 18 18 10,485,774 18,714,688 73,664 8,155,250 43.58
551,883 19 19 10,485,777 17,733,568 108,608 7,139,183 40.26
524,288 20 20 10,485,760 16,850,528 45,472 6,319,296 37.50
499,322 21 21 10,485,762 16,051,616 33,376 5,532,478 34.47
476,626 22 22 10,485,772 15,325,344 83,808 4,755,764 31.03
455,903 23 23 10,485,769 14,662,208 71,104 4,105,335 28.00
436,907 24 24 10,485,768 14,054,336 3,136 3,565,432 25.37
419,431 25 25 10,485,775 20,206,000 69,200 9,651,025 47.76
403,299 26 26 10,485,774 19,431,664 32,528 8,913,362 45.87
388,362 27 27 10,485,774 18,714,688 73,664 8,155,250 43.58
374,492 28 28 10,485,776 18,048,928 63,584 7,499,568 41.55
361,578 29 29 10,485,762 17,429,056 7,616 6,935,678 39.79
349,526 30 30 10,485,780 16,850,560 45,440 6,319,340 37.50
338,251 31 31 10,485,781 16,309,360 45,968 5,777,611 35.43
327,680 32 32 10,485,760 15,801,952 12,704 5,303,488 33.56
218,454 48 48 10,485,792 14,054,368 3,104 3,565,472 25.37
163,840 64 64 10,485,760 13,180,512 65,952 2,628,800 19.94
81,920 128 128 10,485,760 11,869,792 24,992 1,359,040 11.45
40,960 256 256 10,485,760 11,214,432 4,512 724,160 6.46
20,480 512 512 10,485,760 10,886,752 61,856 339,136 3.12
10,240 1,024 1,024 10,485,760 10,722,912 90,528 146,624 1.37
5,120 2,048 2,048 10,485,760 10,640,992 37,280 117,952 1.11
approx target memory usage: 104,857,600
104,857,600 1 1 104,857,600 -939,450,784 29,088 -1,044,337,472 111.16
52,428,800 2 2 104,857,600 1,677,794,912 45,472 1,572,891,840 93.75
34,952,534 3 3 104,857,602 1,118,554,400 95,968 1,013,600,830 90.62
26,214,400 4 4 104,857,600 838,934,112 53,664 734,022,848 87.49
20,971,520 5 5 104,857,600 671,161,952 82,336 566,222,016 84.36
17,476,267 6 6 104,857,602 559,313,856 11,328 454,444,926 81.25
14,979,658 7 7 104,857,606 479,422,368 18,528 374,546,234 78.12
13,107,200 8 8 104,857,600 419,503,712 57,760 314,588,352 74.99
11,650,845 9 9 104,857,605 372,900,352 28,160 268,014,587 71.87
10,485,760 10 10 104,857,600 335,617,632 4,512 230,755,520 68.76
9,532,510 11 11 104,857,610 305,113,632 95,712 200,160,310 65.60
8,738,134 12 12 104,857,608 279,693,600 104,160 174,731,832 62.47
8,065,970 13 13 104,857,610 258,184,352 121,696 153,205,046 59.34
7,489,829 14 14 104,857,606 239,747,840 40,192 134,850,042 56.25
6,990,507 15 15 104,857,605 223,769,536 68,672 118,843,259 53.11
6,553,600 16 16 104,857,600 209,788,512 127,392 104,803,520 49.96
6,168,095 17 17 104,857,615 197,452,352 28,096 92,566,641 46.88
5,825,423 18 18 104,857,614 186,486,848 44,992 81,584,242 43.75
5,518,822 19 19 104,857,618 176,675,616 124,128 71,693,870 40.58
5,242,880 20 20 104,857,600 167,845,472 33,184 62,954,688 37.51
4,993,220 21 21 104,857,620 159,856,352 47,392 54,951,340 34.38
4,766,255 22 22 104,857,610 152,593,472 11,200 47,724,662 31.28
4,559,027 23 23 104,857,621 145,962,176 19,264 41,085,291 28.15
4,369,067 24 24 104,857,608 139,883,456 15,424 35,010,424 25.03
4,194,304 25 25 104,857,600 201,399,904 416 96,541,888 47.94
4,032,985 26 26 104,857,610 193,656,592 39,152 88,759,830 45.83
3,883,615 27 27 104,857,605 186,486,832 45,008 81,584,219 43.75
3,744,915 28 28 104,857,620 179,829,232 79,376 74,892,236 41.65
3,615,780 29 29 104,857,620 173,630,752 60,128 68,713,004 39.57
3,495,254 30 30 104,857,620 167,845,504 33,152 62,954,732 37.51
3,382,504 31 31 104,857,624 162,433,504 38,432 57,537,448 35.42
3,276,800 32 32 104,857,600 157,359,712 111,008 52,391,104 33.29
2,184,534 48 48 104,857,632 139,883,488 15,392 35,010,464 25.03
1,638,400 64 64 104,857,600 131,145,312 102,816 26,184,896 19.97
819,200 128 128 104,857,600 118,038,112 98,720 13,081,792 11.08
409,600 256 256 104,857,600 111,484,512 29,088 6,597,824 5.92
204,800 512 512 104,857,600 108,207,712 61,856 3,288,256 3.04
102,400 1,024 1,024 104,857,600 106,569,312 78,240 1,633,472 1.53
51,200 2,048 2,048 104,857,600 105,750,112 86,432 806,080 0.76

Random size

allocations libc memory usage
count min [B] max [B] total [B] allocated [B] free [B] waste [B] waste [%]
approx target memory usage: 1,048,576
63,377 1 32 1,048,590 2,356,896 76,128 1,232,178 52.28
42,870 1 48 1,048,612 1,901,488 126,032 726,844 38.23
32,159 1 64 1,048,601 1,684,192 72,992 562,599 33.40
16,345 1 128 1,048,634 1,391,984 94,864 248,486 17.85
8,197 1 256 1,048,725 1,252,976 98,704 105,547 8.42
4,133 1 512 1,048,794 1,187,664 28,848 110,022 9.26
2,041 1 1,024 1,048,722 1,154,272 62,240 43,310 3.75
987 1 2,048 1,048,660 1,137,552 78,960 9,932 0.87
approx target memory usage: 10,485,760
635,815 1 32 10,485,774 22,964,288 14,272 12,464,242 54.28
428,303 1 48 10,485,797 18,340,320 42,528 7,811,995 42.59
322,582 1 64 10,485,762 16,204,048 16,112 5,702,174 35.19
162,503 1 128 10,485,761 13,235,776 10,688 2,739,327 20.70
81,377 1 256 10,485,792 11,859,472 35,312 1,338,368 11.29
41,028 1 512 10,485,769 11,205,568 13,376 706,423 6.30
20,448 1 1,024 10,485,813 10,879,072 69,536 323,723 2.98
10,258 1 2,048 10,485,956 10,718,912 94,528 138,428 1.29
approx target memory usage: 104,857,600
6,357,646 1 32 104,857,611 228,927,488 47,104 124,022,773 54.18
4,279,460 1 48 104,857,606 182,670,512 76,624 77,736,282 42.56
3,226,147 1 64 104,857,639 161,384,448 6,144 56,520,665 35.02
1,626,125 1 128 104,857,633 131,760,032 28,768 26,873,631 20.40
815,436 1 256 104,857,712 117,968,464 33,200 13,077,552 11.09
408,507 1 512 104,857,727 111,360,416 18,016 6,484,673 5.82
204,830 1 1,024 104,858,013 108,128,288 6,112 3,264,163 3.02
102,413 1 2,048 104,859,345 106,524,928 122,624 1,542,959 1.45

Conclusions

Source code

Sample programs are available at github.