return 0;
u64 in = sbuck_size(b);
- u64 mem = ctx->internal_estimate(ctx, b);
- if (in < mem)
+ u64 mem = ctx->internal_estimate(ctx, b) * 0.8; // FIXME: Magical factor for hash non-uniformity
+ if (in <= mem)
return 0;
- uns n;
- for (n = sorter_min_radix_bits; n < sorter_max_radix_bits && n < b->hash_bits; n++)
- if ((in >> n) < mem)
- break;
+ uns n = sorter_min_radix_bits;
+ while (n < sorter_max_radix_bits && n < b->hash_bits && (in >> n) > mem)
+ n++;
return n;
}
sorter_radix(struct sort_context *ctx, struct sort_bucket *b, uns bits)
{
uns nbuck = 1 << bits;
- SORT_XTRACE(2, "Running radix sort on %s with %d bits of %d (expected size %s)",
+ SORT_XTRACE(2, "Running radix split on %s with hash %d bits of %d (expecting %s buckets)",
F_BSIZE(b), bits, b->hash_bits, stk_fsize(sbuck_size(b) / nbuck));
+ sorter_free_buf(ctx);
sorter_start_timer(ctx);
struct sort_bucket **outs = alloca(nbuck * sizeof(struct sort_bucket *));
clist_init(&ctx->bucket_list);
sorter_prepare_buf(ctx);
- /* FIXME: Remember to test sorting of empty files */
-
// Create bucket containing the source
struct sort_bucket *bin = sbuck_new(ctx);
bin->flags = SBF_SOURCE | SBF_OPEN_READ;
else
bin->fb = ctx->in_fb;
bin->ident = "in";
- bin->size = ctx->in_size; /* FIXME: Sizes should be either sh_off_t or u64, not both; beware of ~0U */
+ bin->size = ctx->in_size;
bin->hash_bits = ctx->hash_bits;
clist_add_tail(&ctx->bucket_list, &bin->n);
SORT_XTRACE(2, "Input size: %s", F_BSIZE(bin));