pd.if.org Git - nbds/blob - runtime/mem_class_calc.c

   1 #include <stdlib.h>
   2 #include <stdio.h>
   3 #include <assert.h>
   4
   5 typedef unsigned char      uint8_t;
   6 typedef unsigned short     uint16_t;
   7 typedef unsigned int     uint32_t;
   8
   9 #define CACHE_LINE_SCALE 6
  10
  11 // Return the expected fraction of bytes wasted per slab.
  12 //
  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)
  16 {
  17     double quant = (double)delta / 2 / block_size;
  18     assert(quant >= 0.0);
  19     int blocks_per_slab = (int)(slab_size / block_size);
  20
  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);
  24
  25     // number of different cache line colors needed to evenly distribute cache line accesses
  26     int num_colors = block_size >> CACHE_LINE_SCALE;
  27     if (num_colors <= 1)
  28         return (double)extra_space/slab_size + quant;
  29
  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;
  33
  34     double coloring = (double)num_overflow * block_size / num_colors;
  35     return ((double)extra_space + coloring)/slab_size + quant;
  36 }
  37
  38 // size classes for various alignments, max 6% expected internal fragmentation
  39
  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 };
  46
  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 };
  51
  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 };
  56
  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,
  61     98496, 100864
  62 };
  63
  64 int main (void) {
  65
  66     double x = 100864;
  67     int n;
  68     for (n = 0; n < 40 && x < (1 << 21); ++n) {
  69         x *= 1.1;
  70         x = (uint32_t)x & ~63;
  71         printf("%u, ", (uint32_t)x);
  72     }
  73     printf("\n%d\n", n);
  74     return 0;
  75     const int start1 = 120832;
  76     const int start2 = 1408;
  77     const int alignment = 64;
  78 #define ischosen(x) \
  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)
  88
  89     const int slab_size = 1 << 21;
  90     const double thresh = .06;
  91     int block_size;
  92     int i = 0;
  93     for (block_size = start1; i < 87 && block_size < (slab_size >> 3); ++i, block_size += alignment) {
  94         printf("%5d ", block_size);
  95
  96         int d;
  97         double min = 1;
  98         int ch = block_size + alignment;
  99         for (d = block_size; d >= alignment; d-=alignment) {
 100             int x = block_size - d;
 101             if (ischosen(x)) {
 102                 double f = calc_frag(slab_size, block_size, d);
 103                 if (f < thresh && f < min) { min = f; ch = d; }
 104             }
 105         }
 106
 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);
 110                 if (f < thresh) {
 111                     if (d == ch) {
 112                         printf(" *%3.1f%% ", f*100);
 113                     } else {
 114                         printf(" %4.1f%% ", f*100);
 115                     }
 116                     continue;
 117                 }
 118             }
 119             if (d-1 <= block_size && d-alignment <= ch && calc_frag(slab_size, block_size, d - alignment) < thresh) {
 120                 printf("%6d ", block_size);
 121                 continue;
 122             }
 123             printf("       ");
 124         }
 125
 126         if (ischosen(block_size)) {
 127             printf("%5d*", block_size);
 128         } else {
 129             printf("%5d", block_size);
 130         }
 131         printf("\n");
 132     }
 133     return 0;
 134 }