X-Git-Url: https://pd.if.org/git/?p=nbds;a=blobdiff_plain;f=runtime%2Fmem_class_calc.c;fp=runtime%2Fmem_class_calc.c;h=93e34c822427ca6b5df4feffc54a1c71f51b2042;hp=0000000000000000000000000000000000000000;hb=778b8c8ca708b082a1192acfb114a6751b2ad7c9;hpb=5aa9223647fbb52fa8941d92c8896ebaf148b41c diff --git a/runtime/mem_class_calc.c b/runtime/mem_class_calc.c new file mode 100644 index 0000000..93e34c8 --- /dev/null +++ b/runtime/mem_class_calc.c @@ -0,0 +1,134 @@ +#include +#include +#include + +typedef unsigned char uint8_t; +typedef unsigned short uint16_t; +typedef unsigned int uint32_t; + +#define CACHE_LINE_SCALE 6 + +// Return the expected fraction of bytes wasted per slab. +// +// The internal fragmentation due to using size classes is biased by including the space required, +// for a pointer to each block. +double calc_frag(int slab_size, int block_size, int delta) +{ + double quant = (double)delta / 2 / block_size; + assert(quant >= 0.0); + int blocks_per_slab = (int)(slab_size / block_size); + + // internal fragmentation that comes from tiling non-power-of-2 sized blocks in slabs + int extra_space = slab_size - blocks_per_slab * block_size; + assert(extra_space < block_size); + + // number of different cache line colors needed to evenly distribute cache line accesses + int num_colors = block_size >> CACHE_LINE_SCALE; + if (num_colors <= 1) + return (double)extra_space/slab_size + quant; + + int num_overflow = num_colors - 1 - (extra_space >> CACHE_LINE_SCALE); + if (num_overflow <= 0) + return (double)extra_space/slab_size + quant; + + double coloring = (double)num_overflow * block_size / num_colors; + return ((double)extra_space + coloring)/slab_size + quant; +} + +// size classes for various alignments, max 6% expected internal fragmentation + +// 2B-128B blocks, 4k slab +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 }; +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 }; +static uint8_t A4_4kB[] = { 4, 8, 12, 16, 20, 24, 32, 40, 48, 56, 68, 80, 92, 104, 120, 128 }; +static uint8_t A8_4kB[] = { 8, 16, 24, 32, 40, 48, 64, 80, 96, 112, 120, 128 }; +static uint8_t A16_4kB[] = { 16, 32, 48, 64, 80, 96, 112, 128 }; + +// 128B-1kB blocks, 32k slab +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 }; +static uint16_t A8_32kB[] = { 144, 168, 192, 224, 256, 296, 336, 376, 424, 472, 528, 584, 640, 704, 768, 832, 896, 960, 1024 }; +static uint16_t A16_32kB[] = { 144, 176, 208, 240, 272, 320, 368, 416, 464, 512, 576, 640, 704, 768, 832, 896, 960, 1024 }; + +// 1kB-8kB blocks, 256k slab +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 }; +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 }; +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 }; + +// 8kB-100kB blocks, 2MB slab +static uint32_t A64_2MB[] = { + 8896, 9984, 11200, 12544, 14016, 15616, 17408, 19328, 21440, 23744, 26176, 28800, 31616, 34624, 37760, 41024, + 44416, 47936, 51584, 55296, 59008, 62784, 66496, 70208, 73856, 77376, 80832, 84160, 87360, 90368, 93248, 95936, + 98496, 100864 +}; + +int main (void) { + + double x = 100864; + int n; + for (n = 0; n < 40 && x < (1 << 21); ++n) { + x *= 1.1; + x = (uint32_t)x & ~63; + printf("%u, ", (uint32_t)x); + } + printf("\n%d\n", n); + return 0; + const int start1 = 120832; + const int start2 = 1408; + const int alignment = 64; +#define ischosen(x) \ + (x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || \ + x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || \ + x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || \ + x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || \ + x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || \ + x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || \ + x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || \ + x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || \ + x == 0 || x == 0 || x == 0 || x == 0 || x == 0 || x == 0) + + const int slab_size = 1 << 21; + const double thresh = .06; + int block_size; + int i = 0; + for (block_size = start1; i < 87 && block_size < (slab_size >> 3); ++i, block_size += alignment) { + printf("%5d ", block_size); + + int d; + double min = 1; + int ch = block_size + alignment; + for (d = block_size; d >= alignment; d-=alignment) { + int x = block_size - d; + if (ischosen(x)) { + double f = calc_frag(slab_size, block_size, d); + if (f < thresh && f < min) { min = f; ch = d; } + } + } + + for (d = start2; d > start2 - 1024; d-=alignment) { + if (d <= block_size && d <= ch) { + double f = calc_frag(slab_size, block_size, d); + if (f < thresh) { + if (d == ch) { + printf(" *%3.1f%% ", f*100); + } else { + printf(" %4.1f%% ", f*100); + } + continue; + } + } + if (d-1 <= block_size && d-alignment <= ch && calc_frag(slab_size, block_size, d - alignment) < thresh) { + printf("%6d ", block_size); + continue; + } + printf(" "); + } + + if (ischosen(block_size)) { + printf("%5d*", block_size); + } else { + printf("%5d", block_size); + } + printf("\n"); + } + return 0; +}