sorter/s-internal.h

   1 /*
   2  *      UCW Library -- Universal Sorter: Internal Sorting Module
   3  *
   4  *      (c) 2007 Martin Mares <mj@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 #include "lib/stkstring.h"
  11
  12 typedef struct {
  13   P(key) *key;
  14   // FIXME: Add the hash here to save cache misses
  15 } P(internal_item_t);
  16
  17 #define ASORT_PREFIX(x) SORT_PREFIX(array_##x)
  18 #define ASORT_KEY_TYPE P(internal_item_t)
  19 #define ASORT_LT(x,y) (P(compare)((x).key, (y).key) < 0)
  20 #ifdef SORT_INTERNAL_RADIX
  21 #  define ASORT_HASH(x) P(hash)((x).key)
  22 #    ifdef SORT_LONG_HASH
  23 #      define ASORT_LONG_HASH
  24 #    endif
  25 #endif
  26 #include "lib/sorter/array.h"
  27
  28 /*
  29  *  The big_buf has the following layout:
  30  *
  31  *      +-------------------------------------------------------------------------------+
  32  *      | array of internal_item's                                                      |
  33  *      +-------------------------------------------------------------------------------+
  34  *      | padding to make the following part page-aligned                               |
  35  *      +--------------------------------+----------------------------------------------+
  36  *      | shadow copy of item array      | array of pointers to data for write_merged() |
  37  *      | used if radix-sorting          +----------------------------------------------+
  38  *      |                                | workspace for write_merged()                 |
  39  *      +--------------------------------+----------------------------------------------+
  40  *      |              +---------+                                                      |
  41  *      |              | key     |                                                      |
  42  *      |              +---------+                                                      |
  43  *      | sequence of  | padding |                                                      |
  44  *      | items        +---------+                                                      |
  45  *      |              | data    |                                                      |
  46  *      |              +---------+                                                      |
  47  *      |              | padding |                                                      |
  48  *      |              +---------+                                                      |
  49  *      +-------------------------------------------------------------------------------+
  50  *
  51  *  (the data which are in different columns are never accessed simultaneously,
  52  *   so we use a single buffer for both)
  53  */
  54
  55 static inline void *P(internal_get_data)(P(key) *key)
  56 {
  57   uns ksize = SORT_KEY_SIZE(*key);
  58 #ifdef SORT_UNIFY
  59   ksize = ALIGN_TO(ksize, CPU_STRUCT_ALIGN);
  60 #endif
  61   return (byte *) key + ksize;
  62 }
  63
  64 static inline size_t P(internal_workspace)(P(key) *key UNUSED)
  65 {
  66   size_t ws = 0;
  67 #ifdef SORT_UNIFY
  68   ws += sizeof(void *);
  69 #endif
  70 #ifdef SORT_UNIFY_WORKSPACE
  71   ws += SORT_UNIFY_WORKSPACE(*key);
  72 #endif
  73 #ifdef SORT_INTERNAL_RADIX
  74   ws = MAX(ws, sizeof(P(internal_item_t)));
  75 #endif
  76   return ws;
  77 }
  78
  79 static int P(internal)(struct sort_context *ctx, struct sort_bucket *bin, struct sort_bucket *bout, struct sort_bucket *bout_only)
  80 {
  81   sorter_alloc_buf(ctx);
  82   struct fastbuf *in = sbuck_read(bin);
  83
  84   P(key) key, *keybuf = ctx->key_buf;
  85   if (!keybuf)
  86     keybuf = ctx->key_buf = sorter_alloc(ctx, sizeof(key));
  87   if (ctx->more_keys)
  88     {
  89       key = *keybuf;
  90       ctx->more_keys = 0;
  91     }
  92   else if (!P(read_key)(in, &key))
  93     return 0;
  94
  95   size_t bufsize = ctx->big_buf_size;
  96 #ifdef SORT_VAR_DATA
  97   if (sizeof(key) + 2*CPU_PAGE_SIZE + SORT_DATA_SIZE(key) + P(internal_workspace)(&key) > bufsize)
  98     {
  99       SORT_XTRACE(3, "s-internal: Generating a giant run");
 100       struct fastbuf *out = sbuck_write(bout);
 101       P(copy_data)(&key, in, out);
 102       bout->runs++;
 103       return 1;                         // We don't know, but 1 is always safe
 104     }
 105 #endif
 106
 107   SORT_XTRACE(4, "s-internal: Reading");
 108   P(internal_item_t) *item_array = ctx->big_buf, *item = item_array, *last_item;
 109   byte *end = (byte *) ctx->big_buf + bufsize;
 110   size_t remains = bufsize - CPU_PAGE_SIZE;
 111   do
 112     {
 113       uns ksize = SORT_KEY_SIZE(key);
 114 #ifdef SORT_UNIFY
 115       uns ksize_aligned = ALIGN_TO(ksize, CPU_STRUCT_ALIGN);
 116 #else
 117       uns ksize_aligned = ksize;
 118 #endif
 119       uns dsize = SORT_DATA_SIZE(key);
 120       uns recsize = ALIGN_TO(ksize_aligned + dsize, CPU_STRUCT_ALIGN);
 121       size_t totalsize = recsize + sizeof(P(internal_item_t) *) + P(internal_workspace)(&key);
 122       if (unlikely(totalsize > remains
 123 #ifdef CPU_64BIT_POINTERS
 124                    || item >= item_array + ~0U          // The number of items must fit in an uns
 125 #endif
 126          ))
 127         {
 128           ctx->more_keys = 1;
 129           *keybuf = key;
 130           break;
 131         }
 132       remains -= totalsize;
 133       end -= recsize;
 134       memcpy(end, &key, ksize);
 135 #ifdef SORT_VAR_DATA
 136       breadb(in, end + ksize_aligned, dsize);
 137 #endif
 138       item->key = (P(key)*) end;
 139       item++;
 140     }
 141   while (P(read_key)(in, &key));
 142   last_item = item;
 143
 144   uns count = last_item - item_array;
 145   void *workspace UNUSED = ALIGN_PTR(last_item, CPU_PAGE_SIZE);
 146   SORT_XTRACE(3, "s-internal: Read %u items (%s items, %s workspace, %s data)",
 147         count,
 148         stk_fsize((byte*)last_item - (byte*)item_array),
 149         stk_fsize(end - (byte*)last_item - remains),
 150         stk_fsize((byte*)ctx->big_buf + bufsize - end));
 151   timestamp_t timer;
 152   init_timer(&timer);
 153   item_array = P(array_sort)(item_array, count,
 154 #ifdef SORT_INTERNAL_RADIX
 155     workspace, bin->hash_bits
 156 #else
 157     NULL, 0
 158 #endif
 159     );
 160   ctx->total_int_time += get_timer(&timer);
 161
 162   SORT_XTRACE(4, "s-internal: Writing");
 163   if (!ctx->more_keys)
 164     bout = bout_only;
 165   struct fastbuf *out = sbuck_write(bout);
 166   bout->runs++;
 167   uns merged UNUSED = 0;
 168   for (item = item_array; item < last_item; item++)
 169     {
 170 #ifdef SORT_UNIFY
 171       if (item < last_item - 1 && !P(compare)(item->key, item[1].key))
 172         {
 173           // Rewrite the item structures with just pointers to keys and place
 174           // pointers to data in the workspace.
 175           P(key) **key_array = (void *) item;
 176           void **data_array = workspace;
 177           key_array[0] = item[0].key;
 178           data_array[0] = P(internal_get_data)(key_array[0]);
 179           uns cnt;
 180           for (cnt=1; item+cnt < last_item && !P(compare)(key_array[0], item[cnt].key); cnt++)
 181             {
 182               key_array[cnt] = item[cnt].key;
 183               data_array[cnt] = P(internal_get_data)(key_array[cnt]);
 184             }
 185           P(write_merged)(out, key_array, data_array, cnt, data_array+cnt);
 186           item += cnt - 1;
 187           merged += cnt - 1;
 188           continue;
 189         }
 190 #endif
 191 #ifdef SORT_ASSERT_UNIQUE
 192       ASSERT(item == last_item-1 || P(compare)(item->key, item[1].key) < 0);
 193 #endif
 194       P(write_key)(out, item->key);
 195 #ifdef SORT_VAR_DATA
 196       bwrite(out, P(internal_get_data)(item->key), SORT_DATA_SIZE(*item->key));
 197 #endif
 198     }
 199 #ifdef SORT_UNIFY
 200   SORT_XTRACE(3, "Merging reduced %u records", merged);
 201 #endif
 202
 203   return ctx->more_keys;
 204 }
 205
 206 static u64
 207 P(internal_estimate)(struct sort_context *ctx, struct sort_bucket *b UNUSED)
 208 {
 209 #ifdef SORT_VAR_KEY
 210   uns avg = ALIGN_TO(sizeof(P(key))/4, CPU_STRUCT_ALIGN);       // Wild guess...
 211 #else
 212   uns avg = ALIGN_TO(sizeof(P(key)), CPU_STRUCT_ALIGN);
 213 #endif
 214   // We ignore the data part of records, it probably won't make the estimate much worse
 215   size_t bufsize = ctx->big_buf_size;
 216 #ifdef SORT_UNIFY_WORKSPACE             // FIXME: Or if radix-sorting
 217   bufsize /= 2;
 218 #endif
 219   return (bufsize / (avg + sizeof(P(internal_item_t))) * avg);
 220 }