#include <string.h>
#include <alloca.h>
-#define ASORT_MIN_RADIX 5000 // FIXME: var?
#define ASORT_MIN_SHIFT 2
static void
asort_radix(struct asort_context *ctx, void *array, void *buffer, uns num_elts, uns hash_bits, uns swapped_output)
{
+ // swap_output == 0 if result should be returned in `array', otherwise in `buffer'
uns buckets = (1 << ctx->radix_bits);
uns shift = (hash_bits > ctx->radix_bits) ? (hash_bits - ctx->radix_bits) : 0;
uns cnt[buckets];
for (uns i=0; i<buckets; i++)
{
uns n = cnt[i] - pos;
- if (n < ASORT_MIN_RADIX || shift < ASORT_MIN_SHIFT)
+ if (n < sorter_radix_threshold || shift < ASORT_MIN_SHIFT)
{
ctx->quicksort(buffer, n);
if (!swapped_output)
{
struct rs_work *w = (struct rs_work *) ww;
- DBG("Thread %d: Finishing %d items, shift=%d", thr->id, w->num_elts, w->shift);
- if (w->shift < ASORT_MIN_SHIFT || w->num_elts < ASORT_MIN_RADIX)
+ if (thr)
+ DBG("Thread %d: Finishing %d items, shift=%d", thr->id, w->num_elts, w->shift);
+ if (w->shift < ASORT_MIN_SHIFT || w->num_elts < sorter_radix_threshold)
{
- w->ctx->quicksort(w->out, w->num_elts);
- if (!w->swap_output)
- memcpy(w->in, w->out, w->num_elts * w->ctx->elt_size);
+ w->ctx->quicksort(w->in, w->num_elts);
+ if (w->swap_output)
+ memcpy(w->out, w->in, w->num_elts * w->ctx->elt_size);
}
else
- asort_radix(w->ctx, w->out, w->in, w->num_elts, w->shift, !w->swap_output);
- DBG("Thread %d: Finishing done", thr->id);
+ asort_radix(w->ctx, w->in, w->out, w->num_elts, w->shift, w->swap_output);
+ if (thr)
+ DBG("Thread %d: Finishing done", thr->id);
}
static void
w->w.go = rs_count;
w->ctx = ctx;
w->in = iptr;
- w->out = ctx->buffer;
+ w->out = buffer;
w->num_elts = blksize;
if (i == sorter_threads-1)
w->num_elts += num_elts % sorter_threads;
w->shift = shift;
iptr += w->num_elts * ctx->elt_size;
+ bzero(w->cnt, sizeof(uns) * buckets);
work_submit(ctx->rs_work_queue, &w->w);
}
for (uns i=0; i<buckets; i++)
{
uns n = cnt[i] - pos;
- if (n < sorter_thread_threshold)
+ if (!n)
+ continue;
+ if (n * ctx->elt_size < sorter_thread_threshold)
{
struct rs_work *w = ep_alloc(ctx->eltpool);
w->w.priority = 0;
w->w.go = rs_finish;
w->ctx = ctx;
- w->in = array;
- w->out = buffer;
+ w->in = buffer;
+ w->out = array;
w->num_elts = n;
w->shift = shift;
- w->swap_output = swapped_output;
- clist_add_tail(&ctx->rs_bits, &w->w.n);
- DBG("Scheduling block %d+%d", pos, n);
+ w->swap_output = !swapped_output;
+ if (n * ctx->elt_size < sorter_thread_chunk)
+ {
+ DBG("Sorting block %d+%d inline", pos, n);
+ rs_finish(NULL, &w->w);
+ ep_free(ctx->eltpool, w);
+ }
+ else
+ {
+ clist_add_tail(&ctx->rs_bits, &w->w.n);
+ DBG("Scheduling block %d+%d", pos, n);
+ }
}
else
rs_radix(ctx, buffer, array, n, shift, !swapped_output);
ctx->num_elts * ctx->elt_size >= sorter_thread_threshold &&
!(sorter_debug & SORT_DEBUG_ASORT_NO_THREADS));
- if (ctx->num_elts < ASORT_MIN_RADIX ||
+ if (ctx->num_elts < sorter_radix_threshold ||
ctx->hash_bits <= ASORT_MIN_SHIFT ||
!ctx->radix_split ||
(sorter_debug & SORT_DEBUG_ASORT_NO_RADIX))