From 110efaf3f4fa1922af0160222e2011a92d3dd924 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 17 Sep 2007 21:39:02 +0200 Subject: [PATCH] Array sorter thresholds are now configured as 64-bit numbers of bytes, but they are recalculated to the number of elements internally with proper clamping to ~0U. --- lib/sorter/array.c | 27 +++++++++++++++++---------- lib/sorter/common.h | 10 ++++++++-- lib/sorter/config.c | 12 ++++++------ 3 files changed, 31 insertions(+), 18 deletions(-) diff --git a/lib/sorter/array.c b/lib/sorter/array.c index e1805245..a612e8f7 100644 --- a/lib/sorter/array.c +++ b/lib/sorter/array.c @@ -51,7 +51,7 @@ asort_radix(struct asort_context *ctx, void *array, void *buffer, uns num_elts, for (uns i=0; ielt_size < sorter_radix_threshold || shift < ASORT_MIN_SHIFT) + if (n < ctx->radix_threshold || shift < ASORT_MIN_SHIFT) { ctx->quicksort(buffer, n); if (!swapped_output) @@ -128,15 +128,16 @@ static void qs_handle_work(struct worker_thread *thr UNUSED, struct work *ww) { struct qs_work *w = (struct qs_work *) ww; + struct asort_context *ctx = w->ctx; DBG("Thread %d: got %d elts", thr->id, w->num_elts); - if (w->num_elts * w->ctx->elt_size < sorter_thread_threshold) + if (w->num_elts < ctx->thread_threshold) { - w->ctx->quicksort(w->array, w->num_elts); + ctx->quicksort(w->array, w->num_elts); w->left = w->right = LR_UNDEF; } else - w->ctx->quicksplit(w->array, w->num_elts, &w->left, &w->right); + ctx->quicksplit(w->array, w->num_elts, &w->left, &w->right); DBG("Thread %d: returning l=%d r=%d", thr->id, w->left, w->right); } @@ -231,7 +232,7 @@ rs_finish(struct worker_thread *thr UNUSED, struct work *ww) 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 * w->ctx->elt_size < sorter_radix_threshold) + if (w->shift < ASORT_MIN_SHIFT || w->num_elts < w->ctx->radix_threshold) { w->ctx->quicksort(w->array, w->num_elts); if (w->swap_output) @@ -332,7 +333,7 @@ rs_radix(struct asort_context *ctx, void *array, void *buffer, uns num_elts, uns uns n = cnt[i] - pos; if (!n) continue; - if (n * ctx->elt_size < sorter_thread_threshold || shift < ASORT_MIN_SHIFT) + if (n < ctx->thread_threshold || shift < ASORT_MIN_SHIFT) { struct rs_work *w = ep_alloc(ctx->eltpool); w->w.priority = 0; @@ -343,7 +344,7 @@ rs_radix(struct asort_context *ctx, void *array, void *buffer, uns num_elts, uns w->num_elts = n; w->shift = shift; w->swap_output = !swapped_output; - if (n * ctx->elt_size < sorter_thread_chunk) + if (n < ctx->thread_chunk) { DBG("Sorting block %d+%d inline", pos, n); rs_finish(NULL, &w->w); @@ -409,7 +410,7 @@ predict_swap(struct asort_context *ctx) uns elts = ctx->num_elts; uns swap = 0; - while (elts * ctx->elt_size >= sorter_radix_threshold && bits >= ASORT_MIN_SHIFT) + while (elts >= ctx->radix_threshold && bits >= ASORT_MIN_SHIFT) { DBG("Predicting pass: %d elts, %d bits", elts, bits); swap = !swap; @@ -422,12 +423,18 @@ predict_swap(struct asort_context *ctx) void asort_run(struct asort_context *ctx) { + ctx->thread_threshold = MIN(sorter_thread_threshold / ctx->elt_size, ~0U); + ctx->thread_chunk = MIN(sorter_thread_chunk / ctx->elt_size, ~0U); + ctx->radix_threshold = MIN(sorter_radix_threshold / ctx->elt_size, ~0U); + ASORT_TRACE("Array-sorting %d items per %d bytes, hash_bits=%d", ctx->num_elts, ctx->elt_size, ctx->hash_bits); + ASORT_XTRACE(2, "Limits: thread_threshold=%u, thread_chunk=%u, radix_threshold=%u", + ctx->thread_threshold, ctx->thread_chunk, ctx->radix_threshold); uns allow_threads UNUSED = (sorter_threads > 1 && - ctx->num_elts * ctx->elt_size >= sorter_thread_threshold && + ctx->num_elts >= ctx->thread_threshold && !(sorter_debug & SORT_DEBUG_ASORT_NO_THREADS)); - if (ctx->num_elts * ctx->elt_size < sorter_radix_threshold || + if (ctx->num_elts < ctx->radix_threshold || ctx->hash_bits <= ASORT_MIN_SHIFT || !ctx->radix_split || (sorter_debug & SORT_DEBUG_ASORT_NO_RADIX)) diff --git a/lib/sorter/common.h b/lib/sorter/common.h index bd243766..ddd7ba6f 100644 --- a/lib/sorter/common.h +++ b/lib/sorter/common.h @@ -16,9 +16,9 @@ extern uns sorter_trace, sorter_trace_array, sorter_stream_bufsize; extern uns sorter_debug, sorter_min_radix_bits, sorter_max_radix_bits, sorter_add_radix_bits; extern uns sorter_min_multiway_bits, sorter_max_multiway_bits; -extern uns sorter_threads, sorter_thread_threshold, sorter_thread_chunk; -extern uns sorter_radix_threshold; +extern uns sorter_threads; extern u64 sorter_bufsize, sorter_small_input; +extern u64 sorter_thread_threshold, sorter_thread_chunk, sorter_radix_threshold; extern struct fb_params sorter_fb_params, sorter_small_fb_params; #define SORT_TRACE(x...) do { if (sorter_trace) msg(L_DEBUG, x); } while(0) @@ -122,6 +122,7 @@ void sbuck_swap_out(struct sort_bucket *b); /* Contexts and helper functions for the array sorter */ struct asort_context { + // Interface between generic code in array.c and functions generated by array.h void *array; // Array to sort void *buffer; // Auxiliary buffer (required when radix-sorting) uns num_elts; // Number of elements in the array @@ -137,6 +138,11 @@ struct asort_context { struct rs_work **rs_works; struct work_queue *rs_work_queue; struct eltpool *eltpool; + + // Configured limits translated from bytes to elements + uns thread_threshold; + uns thread_chunk; + uns radix_threshold; }; void asort_run(struct asort_context *ctx); diff --git a/lib/sorter/config.c b/lib/sorter/config.c index 5e3da8dd..9ff646b2 100644 --- a/lib/sorter/config.c +++ b/lib/sorter/config.c @@ -22,9 +22,9 @@ uns sorter_add_radix_bits; uns sorter_min_multiway_bits; uns sorter_max_multiway_bits; uns sorter_threads; -uns sorter_thread_threshold = 1048576; -uns sorter_thread_chunk = 4096; -uns sorter_radix_threshold = 4096; +u64 sorter_thread_threshold = 1048576; +u64 sorter_thread_chunk = 4096; +u64 sorter_radix_threshold = 4096; struct fb_params sorter_fb_params; struct fb_params sorter_small_fb_params; u64 sorter_small_input; @@ -44,9 +44,9 @@ static struct cf_section sorter_config = { CF_UNS("MinMultiwayBits", &sorter_min_multiway_bits), CF_UNS("MaxMultiwayBits", &sorter_max_multiway_bits), CF_UNS("Threads", &sorter_threads), - CF_UNS("ThreadThreshold", &sorter_thread_threshold), - CF_UNS("ThreadChunk", &sorter_thread_chunk), - CF_UNS("RadixThreshold", &sorter_radix_threshold), + CF_U64("ThreadThreshold", &sorter_thread_threshold), + CF_U64("ThreadChunk", &sorter_thread_chunk), + CF_U64("RadixThreshold", &sorter_radix_threshold), CF_END } }; -- 2.39.2