From 7cf300f543b5023ad46a909ed6fde0feba5d1acd Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Mon, 10 Sep 2007 19:31:00 +0200 Subject: [PATCH] Made radix-sorting threshold configurable and let radix-tune-bits help find the optimum. --- debug/sorter/radix-tune-bits.sh | 39 +++++++++++++++++++++++---------- lib/sorter/array.c | 7 +++--- lib/sorter/common.h | 2 +- lib/sorter/config.c | 2 ++ 4 files changed, 34 insertions(+), 16 deletions(-) diff --git a/debug/sorter/radix-tune-bits.sh b/debug/sorter/radix-tune-bits.sh index baab6df8..65098382 100644 --- a/debug/sorter/radix-tune-bits.sh +++ b/debug/sorter/radix-tune-bits.sh @@ -20,7 +20,10 @@ SIZE=$(($SORTBUF/2 - 8192)) log "Decided to benchmark sorting of $SIZE byte data" # Which bit widths we try -WIDTHS="6 7 8 9 10 11 12 13 14" +WIDTHS="0 6 7 8 9 10 11 12 13 14" + +# Which RadixThresholds we try +THRS="100 500 1000 2500 5000" # Which sort-test tests we try TESTS="2,5,8,15" @@ -28,18 +31,33 @@ TESTS="2,5,8,15" # Check various bit widths of the radix sorter rm -f tmp/radix-* for W in $WIDTHS ; do - log "Compiling with $W-bit radix splits" rm -f $BUILD/obj/lib/sorter/sort-test{,.o} - ( cd $BUILD && make CEXTRA="-DFORCE_RADIX_BITS=$W" obj/lib/sorter/sort-test ) - log "Running the tests" - $BUILD/obj/lib/sorter/sort-test -s$SIZE -t$TESTS -v 2>&1 | tee tmp/radix-$W + if [ $W = 0 ] ; then + log "Compiling with no radix splits" + ( cd $BUILD && make obj/lib/sorter/sort-test ) + OPT="-d32" + else + log "Compiling with $W-bit radix splits" + ( cd $BUILD && make CEXTRA="-DFORCE_RADIX_BITS=$W" obj/lib/sorter/sort-test ) + OPT= + fi + for THR in $THRS ; do + log "Testing with RadixThreshold=$THR" + $BUILD/obj/lib/sorter/sort-test -SSorter.RadixThreshold=$THR -s$SIZE -t$TESTS $OPT -v 2>&1 | tee -a tmp/radix-$W + done done -log "Trying with radix-sort switched off" -$BUILD/obj/lib/sorter/sort-test -s$SIZE -t$TESTS -v -d32 2>&1 | tee tmp/radix-0 +echo "thresh" >tmp/radix-thrs +echo "test#" >tmp/radix-tests +for THR in $THRS ; do + for TEST in `echo $TESTS | tr ',' ' '` ; do + echo $THR >>tmp/radix-thrs + echo $TEST >>tmp/radix-tests + done +done -FILES="" -for W in 0 $WIDTHS ; do +FILES="tmp/radix-thrs tmp/radix-tests" +for W in $WIDTHS ; do a=tmp/radix-$W echo >$a.out "$W bits" sed 's/.* \([0-9.]\+\)s internal sorting.*/\1/;t;d' <$a >>$a.out @@ -47,5 +65,4 @@ for W in 0 $WIDTHS ; do done log "These are the results:" -echo "test#,$TESTS" | tr , '\n' >tmp/radix-tests -paste tmp/radix-tests $FILES +paste $FILES diff --git a/lib/sorter/array.c b/lib/sorter/array.c index 838ad98c..26b4a1b5 100644 --- a/lib/sorter/array.c +++ b/lib/sorter/array.c @@ -15,7 +15,6 @@ #include #include -#define ASORT_MIN_RADIX 5000 // FIXME: var? #define ASORT_MIN_SHIFT 2 static void @@ -49,7 +48,7 @@ asort_radix(struct asort_context *ctx, void *array, void *buffer, uns num_elts, for (uns i=0; iquicksort(buffer, n); if (!swapped_output) @@ -216,7 +215,7 @@ rs_finish(struct worker_thread *thr UNUSED, struct work *ww) 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 (w->shift < ASORT_MIN_SHIFT || w->num_elts < sorter_radix_threshold) { w->ctx->quicksort(w->in, w->num_elts); if (w->swap_output) @@ -373,7 +372,7 @@ asort_run(struct asort_context *ctx) 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)) diff --git a/lib/sorter/common.h b/lib/sorter/common.h index deee9e04..f67f9bf9 100644 --- a/lib/sorter/common.h +++ b/lib/sorter/common.h @@ -16,7 +16,7 @@ extern uns sorter_trace, sorter_stream_bufsize; extern uns sorter_debug, sorter_min_radix_bits, sorter_max_radix_bits; extern uns sorter_min_multiway_bits, sorter_max_multiway_bits; -extern uns sorter_threads, sorter_thread_threshold; +extern uns sorter_threads, sorter_thread_threshold, sorter_radix_threshold; extern u64 sorter_bufsize; extern struct fb_params sorter_fb_params; diff --git a/lib/sorter/config.c b/lib/sorter/config.c index 178b1904..75d8fa49 100644 --- a/lib/sorter/config.c +++ b/lib/sorter/config.c @@ -22,6 +22,7 @@ uns sorter_min_multiway_bits; uns sorter_max_multiway_bits; uns sorter_threads; uns sorter_thread_threshold; +uns sorter_radix_threshold = 4096; struct fb_params sorter_fb_params; static struct cf_section sorter_config = { @@ -37,6 +38,7 @@ static struct cf_section sorter_config = { CF_UNS("MaxMultiwayBits", &sorter_max_multiway_bits), CF_UNS("Threads", &sorter_threads), CF_UNS("ThreadThreshold", &sorter_thread_threshold), + CF_UNS("RadixThreshold", &sorter_radix_threshold), CF_END } }; -- 2.39.2