5 typedef unsigned char uint8_t;
6 typedef unsigned short uint16_t;
7 typedef unsigned int uint32_t;
9 #define CACHE_LINE_SCALE 6
11 // Return the expected fraction of bytes wasted per slab.
13 // The internal fragmentation due to using size classes is biased by including the space required,
14 // for a pointer to each block.
15 double calc_frag(int slab_size, int block_size, int delta)
17 double quant = (double)delta / 2 / block_size;
19 int blocks_per_slab = (int)(slab_size / block_size);
21 // internal fragmentation that comes from tiling non-power-of-2 sized blocks in slabs
22 int extra_space = slab_size - blocks_per_slab * block_size;
23 assert(extra_space < block_size);
25 // number of different cache line colors needed to evenly distribute cache line accesses
26 int num_colors = block_size >> CACHE_LINE_SCALE;
28 return (double)extra_space/slab_size + quant;
30 int num_overflow = num_colors - 1 - (extra_space >> CACHE_LINE_SCALE);
31 if (num_overflow <= 0)
32 return (double)extra_space/slab_size + quant;
34 double coloring = (double)num_overflow * block_size / num_colors;
35 return ((double)extra_space + coloring)/slab_size + quant;
38 // size classes for various alignments, max 6% expected internal fragmentation
40 // 2B-128B blocks, 4k slab
41 static uint8_t A1_4kB[] = { 2, 3, 5, 7, 9, 11, 14, 17, 20, 24, 28, 33, 39, 46, 53, 62, 70, 80, 91, 105, 120, 128 };
42 static uint8_t A2_4kB[] = { 2, 4, 6, 8, 10, 14, 18, 22, 28, 34, 40, 48, 56, 66, 74, 84, 94, 104, 120, 128 };
43 static uint8_t A4_4kB[] = { 4, 8, 12, 16, 20, 24, 32, 40, 48, 56, 68, 80, 92, 104, 120, 128 };
44 static uint8_t A8_4kB[] = { 8, 16, 24, 32, 40, 48, 64, 80, 96, 112, 120, 128 };
45 static uint8_t A16_4kB[] = { 16, 32, 48, 64, 80, 96, 112, 128 };
47 // 128B-1kB blocks, 32k slab
48 static uint16_t A1_32kB[] = { 137, 156, 178, 201, 227, 256, 288, 323, 361, 402, 447, 494, 545, 598, 654, 712, 771, 832, 895, 958, 1022 };
49 static uint16_t A8_32kB[] = { 144, 168, 192, 224, 256, 296, 336, 376, 424, 472, 528, 584, 640, 704, 768, 832, 896, 960, 1024 };
50 static uint16_t A16_32kB[] = { 144, 176, 208, 240, 272, 320, 368, 416, 464, 512, 576, 640, 704, 768, 832, 896, 960, 1024 };
52 // 1kB-8kB blocks, 256k slab
53 static uint16_t A1_256kB[] = { 1152, 1297, 1458, 1636, 1832, 2048, 2284, 2541, 2820, 3124, 3550, 3904, 4280, 4676, 5092, 5525, 5974, 6435, 6906, 7380, 7856 };
54 static uint16_t A8_256kB[] = { 1152, 1288, 1440, 1608, 1792, 2000, 2224, 2472, 2744, 3032, 3344, 3680, 4040, 4416, 4816, 5232, 5664, 6112, 6568, 7032, 7504, 7976 };
55 static uint16_t A64_256kB[] = { 1152, 1280, 1408, 1536, 1664, 1856, 2048, 2240, 2432, 2688, 2944, 3200, 3520, 3840, 4160, 4544, 4928, 5312, 5696, 6144, 6592, 7040, 7488, 7936 };
57 // 8kB-100kB blocks, 2MB slab
58 static uint32_t A64_2MB[] = {
59 8896, 9984, 11200, 12544, 14016, 15616, 17408, 19328, 21440, 23744, 26176, 28800, 31616, 34624, 37760, 41024,
60 44416, 47936, 51584, 55296, 59008, 62784, 66496, 70208, 73856, 77376, 80832, 84160, 87360, 90368, 93248, 95936,
68 for (n = 0; n < 40 && x < (1 << 21); ++n) {
70 x = (uint32_t)x & ~63;
71 printf("%u, ", (uint32_t)x);
75 const int start1 = 120832;
76 const int start2 = 1408;
77 const int alignment = 64;
79 (x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || \
80 x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || \
81 x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || \
82 x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || \
83 x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || \
84 x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || \
85 x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || \
86 x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || \
87 x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || x == 0)
89 const int slab_size = 1 << 21;
90 const double thresh = .06;
93 for (block_size = start1; i < 87 && block_size < (slab_size >> 3); ++i, block_size += alignment) {
94 printf("%5d ", block_size);
98 int ch = block_size + alignment;
99 for (d = block_size; d >= alignment; d-=alignment) {
100 int x = block_size - d;
102 double f = calc_frag(slab_size, block_size, d);
103 if (f < thresh && f < min) { min = f; ch = d; }
107 for (d = start2; d > start2 - 1024; d-=alignment) {
108 if (d <= block_size && d <= ch) {
109 double f = calc_frag(slab_size, block_size, d);
112 printf(" *%3.1f%% ", f*100);
114 printf(" %4.1f%% ", f*100);
119 if (d-1 <= block_size && d-alignment <= ch && calc_frag(slab_size, block_size, d - alignment) < thresh) {
120 printf("%6d ", block_size);
126 if (ischosen(block_size)) {
127 printf("%5d*", block_size);
129 printf("%5d", block_size);