@@ -178,6 +178,33 @@ static void mode_unriffle(int *arr, int n)
free(tmp);
}
+static unsigned int prev_pow2(unsigned int n)
+{
+ unsigned int pow2 = 1;
+ while (pow2 * 2 < n)
+ pow2 *= 2;
+ return pow2;
+}
+
+static void unriffle_recursively_skewed(int *arr, int n, int *tmp)
+{
+ if (n > 1) {
+ int pow2 = prev_pow2(n);
+ int rest = n - pow2;
+ unriffle(arr + pow2 - rest, rest * 2, tmp);
+ unriffle_recursively_skewed(arr, pow2, tmp);
+ unriffle_recursively_skewed(arr + pow2, rest, tmp);
+ }
+}
+
+static void mode_unriffle_skewed(int *arr, int n)
+{
+ int *tmp;
+ ALLOC_ARRAY(tmp, n);
+ unriffle_recursively_skewed(arr, n, tmp);
+ free(tmp);
+}
+
#define MODE(name) { #name, mode_##name }
static struct mode {
@@ -191,6 +218,7 @@ static struct mode {
MODE(sort),
MODE(dither),
MODE(unriffle),
+ MODE(unriffle_skewed),
};
static const struct mode *get_mode_by_name(const char *name)
Add a mode that turns a sorted list into adversarial input for a bottom-up mergesort implementation that doubles the length of sorted sublists at each level -- like our llist_mergesort(). While unriffle mode splits the list in half at each recursion step, unriffle_skewed splits it into 2^l items and the rest, with 2^l being the highest power of two smaller than the number of items and thus 2^l >= rest. The rest is unriffled with the tail of the first half to require a merge to compare the maximum number of elements. It complements the unriffle mode, which targets balanced merges. If the number of elements is a power of two then both actually produce the same result, as 2^l == rest == n/2 at each recursion step in that case. Here are the results: $ t/helper/test-tool mergesort test | awk ' $7 > max[$3] {max[$3] = $7; line[$3] = $0} END {for (n in line) print line[n]} ' distribut mode n m get_next set_next compare verdict sawtooth unriffle_skewed 100 128 1184 700 589 OK sawtooth unriffle_skewed 1023 1024 16373 10230 9207 OK sawtooth unriffle 1024 1024 16384 10240 9217 OK sawtooth unriffle_skewed 1025 2048 18454 11275 10241 OK The sawtooth distribution with m>=n produces a sorted list and unriffle_skewed mode turns it into adversarial input for unbalanced merges, which it wins in all cases except for n=1024 -- the resulting list is the same, but unriffle is tested before unriffle_skewed, so its result is selected by the AWK script. Signed-off-by: René Scharfe <l.s.r@web.de> --- t/helper/test-mergesort.c | 28 ++++++++++++++++++++++++++++ 1 file changed, 28 insertions(+) -- 2.33.0