From 8c661b20faa518f211d54b59ede9127e3b633914 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Thu, 23 Nov 2006 19:06:26 +0100 Subject: [PATCH] Moved tests related to the sorter to debug/sorter/. --- debug/sorter/Makefile | 6 + debug/sorter/NOTES | 65 ++++ debug/sorter/retros.c | 746 ++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 817 insertions(+) create mode 100644 debug/sorter/Makefile create mode 100644 debug/sorter/NOTES create mode 100644 debug/sorter/retros.c diff --git a/debug/sorter/Makefile b/debug/sorter/Makefile new file mode 100644 index 00000000..5e649ca3 --- /dev/null +++ b/debug/sorter/Makefile @@ -0,0 +1,6 @@ +# Testing the new sorter + +DIRS+=debug/sorter +PROGS+=$(addprefix $(o)/debug/sorter/,retros) + +$(o)/debug/sorter/retros: $(o)/debug/sorter/retros.o $(LIBSH) diff --git a/debug/sorter/NOTES b/debug/sorter/NOTES new file mode 100644 index 00000000..f47f7e22 --- /dev/null +++ b/debug/sorter/NOTES @@ -0,0 +1,65 @@ +Users of lib/sorter.h: (WARNING: Obsolete, corresponds to v3.9 or even v3.8) + +centrum/indexer/patch-index.c u32 oid +gather/daemon/expire.c variable complex +gather/daemon/gc.c variable complex +gather/daemon/gc.c variable hash +gather/shepherd/shep-cleanup.c 5 bytes oid 4 min +gather/shepherd/shep-cleanup.c fixed hash 35 min +gather/shepherd/shep-export.c fixed oid 9 min +gather/shepherd/shep-export.c fixed weight +gather/shepherd/shep-plan.c fixed weight + oid in mem +gather/shepherd/shep-plan.c fixed site ptr + complex in mem +gather/shepherd/shep-record.c fixed reducible to int in mem +gather/shepherd/shep-record.c fixed oid in mem +gather/shepherd/shep.c fixed oid +gather/shepherd/shep.c fixed hash +gather/shepherd/shep-cork.c fixed hash + int 20 min +gather/shepherd/shep-feedback.c fixed hash +gather/shepherd/shep-merge.c fixed hash + int +gather/shepherd/shep-merge.c fixed complex (probably can create monotone hashes for that) 38 min +gather/shepherd/shep-recover.c fixed fp + more +gather/shepherd/shep-select.c fixed weight (non-triv) + hash 21 min +indexer/backlinker.c 8 bytes int +indexer/feedback-gath.c fixed hash + complex 7 min +indexer/fpsort.c fixed hash + oid 9 min +indexer/keywords.c fixed complex multi-pass +indexer/labelsort.c variable oid + complex 2:00 +indexer/mergesigns.c fixed complex, but has hashes 1:33 +indexer/mergesums.c fixed hash +indexer/mkgraph.c complex complex (with melding) (probably can be replaced by sorting edges and melding afterwards) 34 min +indexer/psort.c fixed hash + oid 2 min +indexer/reftexts.c fixed hash +indexer/reftexts.c fixed via merges 3:30 +indexer/reftexts.c fixed oid + int +indexer/resolve.c fixed hash 1:00 + 3:45 +indexer/resolve.c fixed masked int 22 min +indexer/ssort.c variable hash (with melding) 1:30 +indexer/wsort.c variable id (with melding) 7:20 +lang/lang-tables.c fixed complex +lang/stem-dict-gen.c variable hash (with melding) + +Users of lib/arraysort.h on big arrays: + +indexer/chewer.c fixed hash + others +indexer/chewer.c u32 id +indexer/lexfreq.c ptr indirect int +indexer/lexorder.c ptr complex +indexer/lexorder.c ptr complex +indexer/lexsort.c ptr complex + +Interface: + +Key structure fixed aligned / fixed unaligned / variable +Data structure none / given by data_len(key) function +Key I/O default (breadb/bwriteb or attempt direct I/O) / user-defined +Data I/O always built-in +Input file / fastbuf / generator function + + delete input ASAP flag +Output file / fastbuf / consumer function +Key comparison comparison function + monotone hash function + preliminary comparison function (?) +Key merging none / guaranteed unique / user-defined merge function: + multi-way merge in memory + 2-way merge on fastbufs diff --git a/debug/sorter/retros.c b/debug/sorter/retros.c new file mode 100644 index 00000000..b0de3a82 --- /dev/null +++ b/debug/sorter/retros.c @@ -0,0 +1,746 @@ +/* + * An experiment with sorting algorithms + */ + +#include "sherlock/sherlock.h" +#include "lib/getopt.h" +#include "lib/md5.h" + +#include +#include +#include +#include +#include + +struct elt { + u32 key; + u32 ballast[3]; +}; + +static struct elt *ary, *alt, **ind, *array0, *array1; +static uns n = 10000000; +static u32 sum; + +static struct elt *alloc_elts(uns n) +{ +#if 0 + return xmalloc(n * sizeof(struct elt)); +#else + uns len = ALIGN_TO(n * sizeof(struct elt), PAGE_SIZE); + void *p = mmap(NULL, len, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, -1, 0); + ASSERT(p != MAP_FAILED); + return p; +#endif +} + +static void free_elts(struct elt *a, uns n) +{ +#if 0 + xfree(a); + (void) n; +#else + uns len = ALIGN_TO(n * sizeof(struct elt), PAGE_SIZE); + munmap(a, len); +#endif +} + +static int comp(const void *x, const void *y) +{ + const struct elt *xx = x, *yy = y; + return (xx->key < yy->key) ? -1 : (xx->key > yy->key) ? 1 : 0; +} + +static int comp_ind(const void *x, const void *y) +{ + const struct elt * const *xx = x, * const *yy = y; + return comp(*xx, *yy); +} + +#define ASORT_PREFIX(x) as_##x +#define ASORT_KEY_TYPE u32 +#define ASORT_ELT(i) a[i].key +#define ASORT_SWAP(i,j) do { struct elt t=a[i]; a[i]=a[j]; a[j]=t; } while (0) +#define ASORT_EXTRA_ARGS , struct elt *a +#include "lib/arraysort.h" + +#define ASORT_PREFIX(x) asi_##x +#define ASORT_KEY_TYPE u32 +#define ASORT_ELT(i) ind[i]->key +#define ASORT_SWAP(i,j) do { struct elt *t=ind[i]; ind[i]=ind[j]; ind[j]=t; } while (0) +#include "lib/arraysort.h" + +static void r1_sort(void) +{ + struct elt *from = ary, *to = alt, *tmp; +#define BITS 8 + uns cnt[1 << BITS]; + for (uns sh=0; sh<32; sh+=BITS) + { + bzero(cnt, sizeof(cnt)); + for (uns i=0; i> sh) & ((1 << BITS) - 1)]++; + uns pos = 0; + for (uns i=0; i<(1<> sh) & ((1 << BITS) - 1)]++] = from[i]; + ASSERT(cnt[(1 << BITS)-1] == n); + tmp=from, from=to, to=tmp; + } + ary = from; +#undef BITS +} + +static void r1b_sort(void) +{ + struct elt *from = ary, *to = alt, *tmp; +#define BITS 8 + uns cnt[1 << BITS], cnt2[1 << BITS]; + for (uns sh=0; sh<32; sh+=BITS) + { + if (sh) + memcpy(cnt, cnt2, sizeof(cnt)); + else + { + bzero(cnt, sizeof(cnt)); + for (uns i=0; i> sh) & ((1 << BITS) - 1)]++; + } + uns pos = 0; + for (uns i=0; i<(1<> (sh + BITS)) & ((1 << BITS) - 1)]++; + to[cnt[(from[i].key >> sh) & ((1 << BITS) - 1)]++] = from[i]; + } + ASSERT(cnt[(1 << BITS)-1] == n); + tmp=from, from=to, to=tmp; + } + ary = from; +#undef BITS +} + +static void r1c_sort(void) +{ + uns cnt[256]; + struct elt *ptrs[256], *x, *lim; + + x = ary; lim = ary + n; + bzero(cnt, sizeof(cnt)); + while (x < lim) + cnt[x++->key & 255]++; + +#define PTRS(start) x=start; for (uns i=0; i<256; i++) { ptrs[i]=x; x+=cnt[i]; } + + PTRS(alt); + x = ary; lim = ary + n; + bzero(cnt, sizeof(cnt)); + while (x < lim) + { + cnt[(x->key >> 8) & 255]++; + *ptrs[x->key & 255]++ = *x; + x++; + } + + PTRS(ary); + x = alt; lim = alt + n; + bzero(cnt, sizeof(cnt)); + while (x < lim) + { + cnt[(x->key >> 16) & 255]++; + *ptrs[(x->key >> 8) & 255]++ = *x; + x++; + } + + PTRS(alt); + x = ary; lim = ary + n; + bzero(cnt, sizeof(cnt)); + while (x < lim) + { + cnt[(x->key >> 24) & 255]++; + *ptrs[(x->key >> 16) & 255]++ = *x; + x++; + } + + PTRS(ary); + x = alt; lim = alt + n; + while (x < lim) + { + *ptrs[(x->key >> 24) & 255]++ = *x; + x++; + } +#undef PTRS +} + +#include + +static inline void sse_copy_elt(struct elt *to, struct elt *from) +{ + __m128i m = _mm_load_si128((__m128i *) from); + _mm_store_si128((__m128i *) to, m); +} + +static void r1c_sse_sort(void) +{ + uns cnt[256]; + struct elt *ptrs[256], *x, *lim; + + ASSERT(sizeof(struct elt) == 16); + ASSERT(!((addr_int_t)alt & 15)); + ASSERT(!((addr_int_t)ary & 15)); + + x = ary; lim = ary + n; + bzero(cnt, sizeof(cnt)); + while (x < lim) + cnt[x++->key & 255]++; + +#define PTRS(start) x=start; for (uns i=0; i<256; i++) { ptrs[i]=x; x+=cnt[i]; } + + PTRS(alt); + x = ary; lim = ary + n; + bzero(cnt, sizeof(cnt)); + while (x < lim) + { + cnt[(x->key >> 8) & 255]++; + sse_copy_elt(ptrs[x->key & 255]++, x); + x++; + } + + PTRS(ary); + x = alt; lim = alt + n; + bzero(cnt, sizeof(cnt)); + while (x < lim) + { + cnt[(x->key >> 16) & 255]++; + sse_copy_elt(ptrs[(x->key >> 8) & 255]++, x); + x++; + } + + PTRS(alt); + x = ary; lim = ary + n; + bzero(cnt, sizeof(cnt)); + while (x < lim) + { + cnt[(x->key >> 24) & 255]++; + sse_copy_elt(ptrs[(x->key >> 16) & 255]++, x); + x++; + } + + PTRS(ary); + x = alt; lim = alt + n; + while (x < lim) + { + sse_copy_elt(ptrs[(x->key >> 24) & 255]++, x); + x++; + } +#undef PTRS +} + +static void r1d_sort(void) +{ + uns cnt[256]; + struct elt *ptrs[256], *x, *y, *lim; + + ASSERT(!(n % 4)); + + x = ary; lim = ary + n; + bzero(cnt, sizeof(cnt)); + while (x < lim) + { + cnt[x++->key & 255]++; + cnt[x++->key & 255]++; + cnt[x++->key & 255]++; + cnt[x++->key & 255]++; + } + +#define PTRS(start) x=start; for (uns i=0; i<256; i++) { ptrs[i]=x; x+=cnt[i]; } + + PTRS(alt); + x = ary; y = ary+n/2; lim = ary + n/2; + bzero(cnt, sizeof(cnt)); + while (x < lim) + { + cnt[(x->key >> 8) & 255]++; + cnt[(y->key >> 8) & 255]++; + *ptrs[x->key & 255]++ = *x; + *ptrs[y->key & 255]++ = *y; + x++, y++; + cnt[(x->key >> 8) & 255]++; + cnt[(y->key >> 8) & 255]++; + *ptrs[x->key & 255]++ = *x; + *ptrs[y->key & 255]++ = *y; + x++, y++; + } + + PTRS(ary); + x = alt; lim = alt + n; + bzero(cnt, sizeof(cnt)); + while (x < lim) + { + cnt[(x->key >> 16) & 255]++; + *ptrs[(x->key >> 8) & 255]++ = *x; + x++; + cnt[(x->key >> 16) & 255]++; + *ptrs[(x->key >> 8) & 255]++ = *x; + x++; + } + + PTRS(alt); + x = ary; lim = ary + n; + bzero(cnt, sizeof(cnt)); + while (x < lim) + { + cnt[(x->key >> 24) & 255]++; + *ptrs[(x->key >> 16) & 255]++ = *x; + x++; + cnt[(x->key >> 24) & 255]++; + *ptrs[(x->key >> 16) & 255]++ = *x; + x++; + } + + PTRS(ary); + x = alt; lim = alt + n; + while (x < lim) + { + *ptrs[(x->key >> 24) & 255]++ = *x; + x++; + *ptrs[(x->key >> 24) & 255]++ = *x; + x++; + } +#undef PTRS +} + +static void r2_sort(void) +{ + struct elt *from = ary, *to = alt; +#define BITS 14 + uns cnt[1 << BITS]; + bzero(cnt, sizeof(cnt)); + for (uns i=0; i> (32 - BITS)) & ((1 << BITS) - 1)]++; + uns pos = 0; + for (uns i=0; i<(1<> (32 - BITS)) & ((1 << BITS) - 1)]++] = from[i]; + ASSERT(cnt[(1 << BITS)-1] == n); + + pos = 0; + for (uns i=0; i<(1 << BITS); i++) + { + as_sort(cnt[i] - pos, alt+pos); + pos = cnt[i]; + } + ary = alt; +#undef BITS +} + +static void r3_sort(void) +{ +#define BITS 10 +#define LEVELS 2 +#define BUCKS (1 << BITS) +#define THRESHOLD 5000 +#define ODDEVEN 0 + + auto void r3(struct elt *from, struct elt *to, uns n, uns lev); + void r3(struct elt *from, struct elt *to, uns n, uns lev) + { + uns sh = 32 - lev*BITS; + uns cnt[BUCKS]; + bzero(cnt, sizeof(cnt)); + for (uns i=0; i> sh) & (BUCKS - 1)]++; + uns pos = 0; + for (uns i=0; i> sh) & (BUCKS - 1)]++] = from[i]; +#else + sse_copy_elt(&to[cnt[(from[i].key >> sh) & (BUCKS - 1)]++], &from[i]); +#endif + pos = 0; + for (uns i=0; i= LEVELS || l <= THRESHOLD) + { + as_sort(l, to+pos); + if ((lev % 2) != ODDEVEN) + memcpy(from+pos, to+pos, l * sizeof(struct elt)); + } + else + r3(to+pos, from+pos, l, lev+1); + pos = cnt[i]; + } + } + + r3(ary, alt, n, 1); + if (ODDEVEN) + ary = alt; + +#undef ODDEVEN +#undef THRESHOLD +#undef BUCKS +#undef LEVELS +#undef BITS +} + +static inline struct elt *mrg(struct elt *x, struct elt *xl, struct elt *y, struct elt *yl, struct elt *z) +{ + for (;;) + { + if (x->key <= y->key) + { + *z++ = *x++; + if (x >= xl) + goto xend; + } + else + { + *z++ = *y++; + if (y >= yl) + goto yend; + } + } + + xend: + while (y < yl) + *z++ = *y++; + return z; + + yend: + while (x < xl) + *z++ = *x++; + return z; +} + +static void mergesort(void) +{ + struct elt *from, *to; + uns lev = 0; + if (1) + { + struct elt *x = ary, *z = alt, *last = ary + (n & ~1U); + while (x < last) + { + if (x[0].key < x[1].key) + *z++ = *x++, *z++ = *x++; + else + { + *z++ = x[1]; + *z++ = x[0]; + x += 2; + } + } + if (n % 2) + *z = *x; + lev++; + } + for (; (1U << lev) < n; lev++) + { + if (lev % 2) + from = alt, to = ary; + else + from = ary, to = alt; + struct elt *x, *z, *last; + x = from; + z = to; + last = from + n; + uns step = 1 << lev; + while (x + 2*step <= last) + { + z = mrg(x, x+step, x+step, x+2*step, z); + x += 2*step; + } + if (x + step < last) + mrg(x, x+step, x+step, last, z); + else + memcpy(z, x, (byte*)last - (byte*)x); + } + if (lev % 2) + ary = alt; +} + +static void sampsort(uns n, struct elt *ar, struct elt *al, struct elt *dest, byte *wbuf) +{ +#define WAYS 256 + struct elt k[WAYS]; + uns cnt[WAYS]; + bzero(cnt, sizeof(cnt)); + for (uns i=0; i k[w+delta].key) w += delta + FW(128); + FW(64); + FW(32); + FW(16); + FW(8); + FW(4); + FW(2); + FW(1); + wbuf[i] = w; + cnt[w]++; + } + struct elt *y = al, *way[WAYS], *z; + for (uns i=0; i= 1000) + sampsort(cnt[i], y, z, dest, wbuf); + else + { + as_sort(cnt[i], y); + if (al != dest) + memcpy(z, y, cnt[i]*sizeof(struct elt)); + } + y += cnt[i]; + z += cnt[i]; + } +#undef FW +#undef WAYS +} + +static void samplesort(void) +{ + byte *aux = xmalloc(n); + sampsort(n, ary, alt, ary, aux); + xfree(aux); +} + +static void sampsort2(uns n, struct elt *ar, struct elt *al, struct elt *dest, byte *wbuf) +{ +#define WAYS 256 + struct elt k[WAYS]; + uns cnt[WAYS]; + bzero(cnt, sizeof(cnt)); + for (uns i=0; ikey > k[w1+delta].key) w1 += delta +#define FW2(delta) if (k2->key > k[w2+delta].key) w2 += delta + FW1(128); FW2(128); + FW1(64); FW2(64); + FW1(32); FW2(32); + FW1(16); FW2(16); + FW1(8); FW2(8); + FW1(4); FW2(4); + FW1(2); FW2(2); + FW1(1); FW2(1); + *ww++ = w1; + *ww++ = w2; + cnt[w1]++; + cnt[w2]++; + k1 += 2; + k2 += 2; + } + if (k1 < kend) + { + uns w1 = 0; + FW1(128); FW1(64); FW1(32); FW1(16); + FW1(8); FW1(4); FW1(2); FW1(1); + *ww++ = w1; + cnt[w1]++; + } + struct elt *y = al, *way[WAYS], *z; + for (uns i=0; i= 1000) + sampsort2(cnt[i], y, z, dest, wbuf); + else + { + as_sort(cnt[i], y); + if (al != dest) + memcpy(z, y, cnt[i]*sizeof(struct elt)); + } + y += cnt[i]; + z += cnt[i]; + } +#undef FW1 +#undef FW2 +#undef WAYS +} + +static void samplesort2(void) +{ + byte *aux = xmalloc(n); + sampsort2(n, ary, alt, ary, aux); + xfree(aux); +} + +static void mk_ary(void) +{ + ary = array0; + alt = array1; + struct MD5Context ctx; + MD5Init(&ctx); + u32 block[16]; + bzero(block, sizeof(block)); + + sum = 0; + for (uns i=0; ikey; + for (uns i=1; ikey < ind[i-1]->key) + die("Missorted at %d", i); + else + s ^= ind[i]->key; + if (s != sum) + die("Corrupted"); + xfree(ind); +} + +int main(int argc, char **argv) +{ + log_init(argv[0]); + + int opt; + uns op = 0; + while ((opt = cf_getopt(argc, argv, CF_SHORT_OPTS "1", CF_NO_LONG_OPTS, NULL)) >= 0) + switch (opt) + { + case '1': + op |= (1 << (opt - '0')); + break; + default: + die("usage?"); + } + + array0 = alloc_elts(n); + array1 = alloc_elts(n); + for (uns i=0; i