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