From 0a0199533c874640d913370b62c8a11b8a68bfa0 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 29 Aug 2007 23:10:30 +0200 Subject: [PATCH] So far buggy support for multi-way unification. --- lib/sorter/s-multiway.h | 128 +++++++++++++++++++++++++++++----------- lib/sorter/sorter.h | 6 -- 2 files changed, 95 insertions(+), 39 deletions(-) diff --git a/lib/sorter/s-multiway.h b/lib/sorter/s-multiway.h index 32956e70..097679ac 100644 --- a/lib/sorter/s-multiway.h +++ b/lib/sorter/s-multiway.h @@ -7,21 +7,49 @@ * of the GNU Lesser General Public License. */ -static inline void P(update_tree)(P(key) *keys, int *tree, uns i) +typedef struct P(mwt_node) { + int i; +#ifdef SORT_UNIFY + int eq; +#endif +} P(mwt_node); + +static inline void P(update_tree)(P(key) *keys, P(mwt_node) *tree, uns i) { while (i /= 2) { - if (tree[2*i] < 0) - tree[i] = tree[2*i+1]; - else if (tree[2*i+1] < 0) - tree[i] = tree[2*i]; - else if (P(compare)(&keys[tree[2*i]], &keys[tree[2*i+1]]) <= 0) - tree[i] = tree[2*i]; + P(mwt_node) new; + if (tree[2*i].i < 0) + new = tree[2*i+1]; + else if (tree[2*i+1].i < 0) + new = tree[2*i]; else - tree[i] = tree[2*i+1]; + { + int cmp = P(compare)(&keys[tree[2*i].i], &keys[tree[2*i+1].i]); + if (cmp <= 0) + new = tree[2*i]; + else + new = tree[2*i+1]; +#ifdef SORT_UNIFY + if (!cmp) + new.eq = 1; +#endif + } +#ifdef SORT_UNIFY_XXX // FIXME + /* If we are not unifying, the keys are usually distinct, so this check is pointless */ + if (!memcmp(&tree[i], &new, sizeof(new))) + break; +#endif + tree[i] = new; } } +static inline void P(set_tree)(P(key) *keys, P(mwt_node) *tree, uns i, int val) +{ + tree[i].i = val; + P(update_tree)(keys, tree, i); +} + static void P(multiway_merge)(struct sort_context *ctx UNUSED, struct sort_bucket **ins, struct sort_bucket *out) { uns num_ins = 0; @@ -34,49 +62,83 @@ static void P(multiway_merge)(struct sort_context *ctx UNUSED, struct sort_bucke struct fastbuf *fout = sbuck_write(out); struct fastbuf *fins[num_ins]; - P(key) keys[num_ins]; // FIXME: Tune num_ins according to L1 cache size - int tree[2*n2]; // A complete binary tree, leaves are input streams, each internal vertex contains a minimum of its sons + P(key) keys[num_ins]; + P(mwt_node) tree[2*n2]; // A complete binary tree, leaves are input streams, each internal vertex contains a minimum of its sons for (uns i=1; i<2*n2; i++) - tree[i] = -1; + { + tree[i].i = -1; +#ifdef SORT_UNIFY + tree[i].eq = 0; +#endif + } for (uns i=0; i= 0)) + { + int i = tree[1].i; + if (!tree[1].eq && 0) // FIXME: This does not work for some reason { - tree[n2+i] = i; + /* The key is unique, so let's go through the fast path */ + P(copy_data)(&keys[i], fins[i], fout); + if (unlikely(!P(read_key)(fins[i], &keys[i]))) + tree[n2+i].i = -1; P(update_tree)(keys, tree, n2+i); + continue; + } + + uns m = 0; + key = &keys[i]; + do + { + hits[m] = i; + mkeys[m] = &keys[i]; + mfb[m] = fins[i]; + m++; + P(set_tree)(keys, tree, n2+i, -1); + i = tree[1].i; + if (unlikely(i < 0)) + break; + } + while (!P(compare)(key, &keys[i])); + + P(copy_merged)(mkeys, mfb, m, fout); + + for (uns j=0; j= 0) +#else + + /* Simplified version which does not support any unification */ + while (likely(tree[1].i >= 0)) { - uns i = tree[1]; + uns i = tree[1].i; + P(key) UNUSED key = keys[i]; P(copy_data)(&keys[i], fins[i], fout); if (unlikely(!P(read_key)(fins[i], &keys[i]))) - tree[n2+i] = -1; + tree[n2+i].i = -1; P(update_tree)(keys, tree, n2+i); - } - -#if 0 #ifdef SORT_ASSERT_UNIQUE - ASSERT(comp != 0); + ASSERT(tree[1].i < 0 || P(compare)(&key, &keys[tree[1].i]) < 0); #endif -#ifdef SORT_UNIFY - if (comp == 0) - { - P(key) *mkeys[] = { kin1, kin2 }; - struct fastbuf *mfb[] = { fin1, fin2 }; - P(copy_merged)(mkeys, mfb, 2, fout1); - SWAP(kin1, kprev1, ktmp); - next1 = P(read_key)(fin1, kin1); - run1 = next1 && (P(compare)(kprev1, kin1) LESS 0); - SWAP(kin2, kprev2, ktmp); - next2 = P(read_key)(fin2, kin2); - run2 = next2 && (P(compare)(kprev2, kin2) LESS 0); - kout = kprev2; } -#endif + #endif out->runs++; diff --git a/lib/sorter/sorter.h b/lib/sorter/sorter.h index a0b6b39b..675a3d5b 100644 --- a/lib/sorter/sorter.h +++ b/lib/sorter/sorter.h @@ -200,10 +200,7 @@ static inline void P(copy_merged)(P(key) **keys, struct fastbuf **data UNUSED, u #endif #include "lib/sorter/s-twoway.h" - -#ifndef SORT_UNIFY #include "lib/sorter/s-multiway.h" -#endif #if defined(SORT_HASH_BITS) || defined(SORT_INT) #include "lib/sorter/s-radix.h" @@ -272,10 +269,7 @@ static struct fastbuf *P(sort)( ctx.internal_sort = P(internal); ctx.internal_estimate = P(internal_estimate); ctx.twoway_merge = P(twoway_merge); - -#ifndef SORT_UNIFY ctx.multiway_merge = P(multiway_merge); -#endif sorter_run(&ctx); -- 2.39.2