From e65a1a48088af1a5731f64b50ba933f4c29d5040 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Fri, 9 Feb 2007 23:41:58 +0100 Subject: [PATCH] Added a trivial implementation of radix sorting. --- lib/sorter/common.h | 3 +++ lib/sorter/govern.c | 46 ++++++++++++++++++++++++++++++++++++++++-- lib/sorter/s-radix.h | 32 +++++++++++++++++++++++++++++ lib/sorter/sort-test.c | 3 +++ lib/sorter/sorter.h | 8 +++++++- 5 files changed, 89 insertions(+), 3 deletions(-) create mode 100644 lib/sorter/s-radix.h diff --git a/lib/sorter/common.h b/lib/sorter/common.h index bd5ed965..52949657 100644 --- a/lib/sorter/common.h +++ b/lib/sorter/common.h @@ -24,6 +24,7 @@ enum sort_debug { SORT_DEBUG_NO_PRESORT = 1, SORT_DEBUG_NO_JOIN = 2, SORT_DEBUG_KEEP_BUCKETS = 4, + SORT_DEBUG_NO_RADIX = 8, }; struct sort_bucket; @@ -46,6 +47,8 @@ struct sort_context { // Two-way split/merge: merge up to 2 source buckets to up to 2 destination buckets. // Bucket arrays are NULL-terminated. void (*twoway_merge)(struct sort_context *ctx, struct sort_bucket **ins, struct sort_bucket **outs); + // Radix split according to hash function + void (*radix_split)(struct sort_context *ctx, struct sort_bucket *in, struct sort_bucket **outs, uns bitpos, uns numbits); // State variables of internal_sort void *key_buf; diff --git a/lib/sorter/govern.c b/lib/sorter/govern.c index 98b9e9d4..9b8ee774 100644 --- a/lib/sorter/govern.c +++ b/lib/sorter/govern.c @@ -103,7 +103,7 @@ sorter_twoway(struct sort_context *ctx, struct sort_bucket *b) ins[0] = sbuck_new(ctx); if (!sorter_presort(ctx, b, ins[0], join ? : ins[0])) { - SORT_TRACE("Sorted in memory"); + SORT_XTRACE(((b->flags & SBF_SOURCE) ? 1 : 2), "Sorted in memory"); if (join) sbuck_drop(ins[0]); else @@ -163,6 +163,46 @@ sorter_twoway(struct sort_context *ctx, struct sort_bucket *b) clist_insert_after(&ins[0]->n, list_pos); } +static int +sorter_radix_p(struct sort_context *ctx, struct sort_bucket *b) +{ + return b->hash_bits && ctx->radix_split && + !(sorter_debug & SORT_DEBUG_NO_RADIX) && + sbuck_size(b) > (sh_off_t)sorter_bufsize; +} + +static void +sorter_radix(struct sort_context *ctx, struct sort_bucket *b) +{ + uns bits = MIN(b->hash_bits, 4); /* FIXME */ + uns nbuck = 1 << bits; + SORT_XTRACE(2, "Running radix sort on %s with %d bits of %d", F_BSIZE(b), bits, b->hash_bits); + sorter_start_timer(ctx); + + struct sort_bucket *outs[nbuck]; + for (uns i=nbuck; i--; ) + { + outs[i] = sbuck_new(ctx); + outs[i]->hash_bits = b->hash_bits - bits; + clist_insert_after(&outs[i]->n, &b->n); + } + + ctx->radix_split(ctx, b, outs, b->hash_bits - bits, bits); + + u64 min = ~0U, max = 0, sum = 0; + for (uns i=0; ifb = ctx->in_fb; bin->ident = "in"; - bin->size = ctx->in_size; + bin->size = ctx->in_size; /* Sizes should be either sh_off_t or u64, not both; beware of ~0U */ bin->hash_bits = ctx->hash_bits; clist_add_tail(&ctx->bucket_list, &bin->n); SORT_XTRACE(2, "Input size: %s", (ctx->in_size == ~(u64)0 ? (byte*)"unknown" : F_BSIZE(bin))); @@ -200,6 +240,8 @@ sorter_run(struct sort_context *ctx) sbuck_drop(b); else if (b->runs == 1) sorter_join(b); + else if (sorter_radix_p(ctx, b)) + sorter_radix(ctx, b); else sorter_twoway(ctx, b); } diff --git a/lib/sorter/s-radix.h b/lib/sorter/s-radix.h new file mode 100644 index 00000000..c83d6049 --- /dev/null +++ b/lib/sorter/s-radix.h @@ -0,0 +1,32 @@ +/* + * UCW Library -- Universal Sorter: Radix-Split Module + * + * (c) 2007 Martin Mares + * + * This software may be freely distributed and used according to the terms + * of the GNU Lesser General Public License. + */ + +/* FIXME: This is a very trivial implementation so far. Use fbdirect and such things to speed up. */ + +#include + +static void P(radix_split)(struct sort_context *ctx UNUSED, struct sort_bucket *bin, struct sort_bucket **bouts, uns bitpos, uns numbits) +{ + uns nbucks = 1 << numbits; + uns mask = nbucks - 1; + struct fastbuf *in = sbuck_read(bin); + P(key) k; + + struct fastbuf *outs[nbucks]; + bzero(outs, sizeof(outs)); + + while (P(read_key)(in, &k)) + { + uns h = P(hash)(&k); + uns i = (h >> bitpos) & mask; + if (unlikely(!outs[i])) + outs[i] = sbuck_write(bouts[i]); + P(copy_data)(&k, in, outs[i]); + } +} diff --git a/lib/sorter/sort-test.c b/lib/sorter/sort-test.c index 2909599f..5464f744 100644 --- a/lib/sorter/sort-test.c +++ b/lib/sorter/sort-test.c @@ -18,18 +18,21 @@ #include #include #include +#include /*** Time measurement ***/ static void start(void) { + sync(); init_timer(); } static void stop(void) { + sync(); log(L_INFO, "Test took %.3fs", get_timer() / 1000.); } diff --git a/lib/sorter/sorter.h b/lib/sorter/sorter.h index d9ae7a00..98dd8f77 100644 --- a/lib/sorter/sorter.h +++ b/lib/sorter/sorter.h @@ -52,7 +52,7 @@ * SORT_HASH_BITS signals that a monotone hashing function returning a given number of * bits is available. Monotone hash is a function f such that f(x) < f(y) * implies x < y and which is approximately uniformly distributed. - * uns PREFIX_hash(SORT_KEY *a, SORT_KEY *b) + * uns PREFIX_hash(SORT_KEY *a) * * Unification: * @@ -175,6 +175,10 @@ static inline void P(copy_data)(P(key) *key, struct fastbuf *in, struct fastbuf #include "lib/sorter/s-internal.h" #include "lib/sorter/s-twoway.h" +#if defined(SORT_HASH_BITS) || defined(SORT_INT) +#include "lib/sorter/s-radix.h" +#endif + static struct fastbuf *P(sort)( #ifdef SORT_INPUT_FILE byte *in, @@ -223,10 +227,12 @@ static struct fastbuf *P(sort)( #ifdef SORT_HASH_BITS ctx.hash_bits = SORT_HASH_BITS; + ctx.radix_split = P(radix_split); #elif defined(SORT_INT) ctx.hash_bits = 0; while (ctx.hash_bits < 32 && (int_range >> ctx.hash_bits)) ctx.hash_bits++; + ctx.radix_split = P(radix_split); #endif ctx.internal_sort = P(internal); -- 2.39.2