* (c) 2007--2008 Martin Mares <mj@ucw.cz>
*/
-#include "sherlock/sherlock.h"
-#include "ucw/getopt.h"
-#include "ucw/md5.h"
-#include "ucw/heap.h"
+#include <ucw/lib.h>
+#include <ucw/getopt.h>
+#include <ucw/md5.h>
+#include <ucw/heap.h>
+#include <ucw/time.h>
#include <stdio.h>
#include <stdlib.h>
};
static struct elt *ary, *alt, **ind, *array0, *array1;
-static uns n = 10000000;
+static uint n = 10000000;
static u32 sum;
-static struct elt *alloc_elts(uns n)
+static struct elt *alloc_elts(uint n)
{
return big_alloc(n * sizeof(struct elt));
}
-static void free_elts(struct elt *a, uns n)
+static void free_elts(struct elt *a, uint n)
{
big_free(a, n * sizeof(struct elt));
}
#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 "ucw/sorter/array-simple.h"
+#include <ucw/sorter/array-simple.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 "ucw/sorter/array-simple.h"
+#include <ucw/sorter/array-simple.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)
+ uint cnt[1 << BITS];
+ for (uint sh=0; sh<32; sh+=BITS)
{
bzero(cnt, sizeof(cnt));
- for (uns i=0; i<n; i++)
+ for (uint i=0; i<n; i++)
cnt[(from[i].key >> sh) & ((1 << BITS) - 1)]++;
- uns pos = 0;
- for (uns i=0; i<(1<<BITS); i++)
+ uint pos = 0;
+ for (uint i=0; i<(1<<BITS); i++)
{
- uns c = cnt[i];
+ uint c = cnt[i];
cnt[i] = pos;
pos += c;
}
ASSERT(pos == n);
- for (uns i=0; i<n; i++)
+ for (uint i=0; i<n; i++)
to[cnt[(from[i].key >> sh) & ((1 << BITS) - 1)]++] = from[i];
ASSERT(cnt[(1 << BITS)-1] == n);
tmp=from, from=to, to=tmp;
{
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)
+ uint cnt[1 << BITS], cnt2[1 << BITS];
+ for (uint sh=0; sh<32; sh+=BITS)
{
if (sh)
memcpy(cnt, cnt2, sizeof(cnt));
else
{
bzero(cnt, sizeof(cnt));
- for (uns i=0; i<n; i++)
+ for (uint i=0; i<n; i++)
cnt[(from[i].key >> sh) & ((1 << BITS) - 1)]++;
}
- uns pos = 0;
- for (uns i=0; i<(1<<BITS); i++)
+ uint pos = 0;
+ for (uint i=0; i<(1<<BITS); i++)
{
- uns c = cnt[i];
+ uint c = cnt[i];
cnt[i] = pos;
pos += c;
}
ASSERT(pos == n);
bzero(cnt2, sizeof(cnt2));
- for (uns i=0; i<n; i++)
+ for (uint i=0; i<n; i++)
{
cnt2[(from[i].key >> (sh + BITS)) & ((1 << BITS) - 1)]++;
to[cnt[(from[i].key >> sh) & ((1 << BITS) - 1)]++] = from[i];
static void r1c_sort(void)
{
- uns cnt[256];
+ uint cnt[256];
struct elt *ptrs[256], *x, *lim;
x = ary; lim = ary + n;
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]; }
+#define PTRS(start) x=start; for (uint i=0; i<256; i++) { ptrs[i]=x; x+=cnt[i]; }
PTRS(alt);
x = ary; lim = ary + n;
static void r1c_sse_sort(void)
{
- uns cnt[256];
+ uint cnt[256];
struct elt *ptrs[256], *x, *lim;
ASSERT(sizeof(struct elt) == 16);
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]; }
+#define PTRS(start) x=start; for (uint i=0; i<256; i++) { ptrs[i]=x; x+=cnt[i]; }
PTRS(alt);
x = ary; lim = ary + n;
static void r1d_sort(void)
{
- uns cnt[256];
+ uint cnt[256];
struct elt *ptrs[256], *x, *y, *lim;
ASSERT(!(n % 4));
cnt[x++->key & 255]++;
}
-#define PTRS(start) x=start; for (uns i=0; i<256; i++) { ptrs[i]=x; x+=cnt[i]; }
+#define PTRS(start) x=start; for (uint i=0; i<256; i++) { ptrs[i]=x; x+=cnt[i]; }
PTRS(alt);
x = ary; y = ary+n/2; lim = ary + n/2;
{
struct elt *from = ary, *to = alt;
#define BITS 14
- uns cnt[1 << BITS];
+ uint cnt[1 << BITS];
bzero(cnt, sizeof(cnt));
- for (uns i=0; i<n; i++)
+ for (uint i=0; i<n; i++)
cnt[(from[i].key >> (32 - BITS)) & ((1 << BITS) - 1)]++;
- uns pos = 0;
- for (uns i=0; i<(1<<BITS); i++)
+ uint pos = 0;
+ for (uint i=0; i<(1<<BITS); i++)
{
- uns c = cnt[i];
+ uint c = cnt[i];
cnt[i] = pos;
pos += c;
}
ASSERT(pos == n);
- for (uns i=0; i<n; i++)
+ for (uint i=0; i<n; i++)
to[cnt[(from[i].key >> (32 - BITS)) & ((1 << BITS) - 1)]++] = from[i];
ASSERT(cnt[(1 << BITS)-1] == n);
pos = 0;
- for (uns i=0; i<(1 << BITS); i++)
+ for (uint i=0; i<(1 << BITS); i++)
{
as_sort(cnt[i] - pos, alt+pos);
pos = cnt[i];
#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)
+ auto void r3(struct elt *from, struct elt *to, uint n, uint lev);
+ void r3(struct elt *from, struct elt *to, uint n, uint lev)
{
- uns sh = 32 - lev*BITS;
- uns cnt[BUCKS];
+ uint sh = 32 - lev*BITS;
+ uint cnt[BUCKS];
bzero(cnt, sizeof(cnt));
- for (uns i=0; i<n; i++)
+ for (uint i=0; i<n; i++)
cnt[(from[i].key >> sh) & (BUCKS - 1)]++;
- uns pos = 0;
- for (uns i=0; i<BUCKS; i++)
+ uint pos = 0;
+ for (uint i=0; i<BUCKS; i++)
{
- uns c = cnt[i];
+ uint c = cnt[i];
cnt[i] = pos;
pos += c;
}
ASSERT(pos == n);
- for (uns i=0; i<n; i++)
+ for (uint i=0; i<n; i++)
#if 1
to[cnt[(from[i].key >> 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<BUCKS; i++)
+ for (uint i=0; i<BUCKS; i++)
{
- uns l = cnt[i]-pos;
+ uint l = cnt[i]-pos;
if (lev >= LEVELS || l <= THRESHOLD)
{
as_sort(l, to+pos);
static void mergesort(void)
{
struct elt *from, *to;
- uns lev = 0;
+ uint lev = 0;
if (1)
{
struct elt *x = ary, *z = alt, *last = ary + (n & ~1U);
x = from;
z = to;
last = from + n;
- uns step = 1 << lev;
+ uint step = 1 << lev;
while (x + 2*step <= last)
{
z = mrg(x, x+step, x+step, x+2*step, z);
ary = alt;
}
-static void sampsort(uns n, struct elt *ar, struct elt *al, struct elt *dest, byte *wbuf)
+static void sampsort(uint n, struct elt *ar, struct elt *al, struct elt *dest, byte *wbuf)
{
#define WAYS 256
struct elt k[WAYS];
- uns cnt[WAYS];
+ uint cnt[WAYS];
bzero(cnt, sizeof(cnt));
- for (uns i=0; i<WAYS; i++)
+ for (uint i=0; i<WAYS; i++)
k[i] = ar[random() % n];
as_sort(WAYS, k);
- for (uns i=0; i<n; i++)
+ for (uint i=0; i<n; i++)
{
- uns w = 0;
+ uint w = 0;
#define FW(delta) if (ar[i].key > k[w+delta].key) w += delta
FW(128);
FW(64);
cnt[w]++;
}
struct elt *y = al, *way[WAYS], *z;
- for (uns i=0; i<WAYS; i++)
+ for (uint i=0; i<WAYS; i++)
{
way[i] = y;
y += cnt[i];
}
ASSERT(y == al+n);
- for (uns i=0; i<n; i++)
+ for (uint i=0; i<n; i++)
{
- uns w = wbuf[i];
+ uint w = wbuf[i];
*way[w]++ = ar[i];
}
y = al;
z = ar;
- for (uns i=0; i<WAYS; i++)
+ for (uint i=0; i<WAYS; i++)
{
if (cnt[i] >= 1000)
sampsort(cnt[i], y, z, dest, wbuf);
xfree(aux);
}
-static void sampsort2(uns n, struct elt *ar, struct elt *al, struct elt *dest, byte *wbuf)
+static void sampsort2(uint n, struct elt *ar, struct elt *al, struct elt *dest, byte *wbuf)
{
#define WAYS 256
struct elt k[WAYS];
- uns cnt[WAYS];
+ uint cnt[WAYS];
bzero(cnt, sizeof(cnt));
- for (uns i=0; i<WAYS; i++)
+ for (uint i=0; i<WAYS; i++)
k[i] = ar[random() % n];
as_sort(WAYS, k);
struct elt *k1 = ar, *k2 = ar+1, *kend = ar+n;
byte *ww = wbuf;
while (k2 < kend)
{
- uns w1 = 0, w2 = 0;
+ uint w1 = 0, w2 = 0;
#define FW1(delta) if (k1->key > k[w1+delta].key) w1 += delta
#define FW2(delta) if (k2->key > k[w2+delta].key) w2 += delta
FW1(128); FW2(128);
}
if (k1 < kend)
{
- uns w1 = 0;
+ uint 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<WAYS; i++)
+ for (uint i=0; i<WAYS; i++)
{
way[i] = y;
y += cnt[i];
}
ASSERT(y == al+n);
- for (uns i=0; i<n; i++)
+ for (uint i=0; i<n; i++)
{
- uns w = wbuf[i];
+ uint w = wbuf[i];
*way[w]++ = ar[i];
}
y = al;
z = ar;
- for (uns i=0; i<WAYS; i++)
+ for (uint i=0; i<WAYS; i++)
{
if (cnt[i] >= 1000)
sampsort2(cnt[i], y, z, dest, wbuf);
#define H_LESS(_a,_b) ((_a).key > (_b).key)
struct elt *heap = ary-1;
HEAP_INIT(struct elt, heap, n, H_LESS, HEAP_SWAP);
- uns nn = n;
+ uint nn = n;
while (nn)
- HEAP_DELMIN(struct elt, heap, nn, H_LESS, HEAP_SWAP);
+ HEAP_DELETE_MIN(struct elt, heap, nn, H_LESS, HEAP_SWAP);
#undef H_LESS
}
#define H_LESS(_a,_b) ((_a)->key > (_b)->key)
struct elt **heap = ind-1;
HEAP_INIT(struct elt *, heap, n, H_LESS, HEAP_SWAP);
- uns nn = n;
+ uint nn = n;
while (nn)
- HEAP_DELMIN(struct elt *, heap, nn, H_LESS, HEAP_SWAP);
+ HEAP_DELETE_MIN(struct elt *, heap, nn, H_LESS, HEAP_SWAP);
#undef H_LESS
}
bzero(block, sizeof(block));
sum = 0;
- for (uns i=0; i<n; i++)
+ for (uint i=0; i<n; i++)
{
#if 1
if (!(i % 4))
#else
ary[i].key = i*(~0U/(n-1));
#endif
- for (uns j=1; j<sizeof(struct elt)/4; j++)
+ for (uint j=1; j<sizeof(struct elt)/4; j++)
((u32*)&ary[i])[j] = ROL(ary[i].key, 3*j);
sum ^= ary[i].key;
}
static void chk_ary(void)
{
u32 s = ary[0].key;
- for (uns i=1; i<n; i++)
+ for (uint i=1; i<n; i++)
if (ary[i].key < ary[i-1].key)
die("Missorted at %d", i);
else
{
mk_ary();
ind = xmalloc(sizeof(struct elt *) * n);
- for (uns i=0; i<n; i++)
+ for (uint i=0; i<n; i++)
ind[i] = &ary[i];
}
static void chk_ind(void)
{
u32 s = ind[0]->key;
- for (uns i=1; i<n; i++)
+ for (uint i=1; i<n; i++)
if (ind[i]->key < ind[i-1]->key)
die("Missorted at %d", i);
else
log_init(argv[0]);
int opt;
- uns op = 0;
+ uint op = 0;
while ((opt = cf_getopt(argc, argv, CF_SHORT_OPTS "1", CF_NO_LONG_OPTS, NULL)) >= 0)
switch (opt)
{
array0 = alloc_elts(n);
array1 = alloc_elts(n);
- for (uns i=0; i<n; i++)
+ for (uint i=0; i<n; i++)
array0[i] = array1[i] = (struct elt) { 0 };
- log(L_INFO, "Testing with %u elements", n);
+ msg(L_INFO, "Testing with %u elements", n);
mk_ary();
timestamp_t timer;
init_timer(&timer);
- for (uns i=0; i<5; i++)
+ for (uint i=0; i<5; i++)
{
#if 1
memcpy(alt, ary, sizeof(struct elt) * n);
memcpy(ary, alt, sizeof(struct elt) * n);
#else
- for (uns j=0; j<n; j++)
+ for (uint j=0; j<n; j++)
alt[j] = ary[j];
- for (uns j=0; j<n; j++)
+ for (uint j=0; j<n; j++)
ary[j] = alt[j];
#endif
}
- log(L_DEBUG, "memcpy: %d", get_timer(&timer)/10);
+ msg(L_DEBUG, "memcpy: %d", get_timer(&timer)/10);
-#define BENCH(type, name, func) mk_##type(); init_timer(&timer); func; log(L_DEBUG, name ": %d", get_timer(&timer)); chk_##type()
+#define BENCH(type, name, func) mk_##type(); init_timer(&timer); func; msg(L_DEBUG, name ": %d", get_timer(&timer)); chk_##type()
BENCH(ary, "qsort", qsort(ary, n, sizeof(struct elt), comp));
BENCH(ary, "arraysort", as_sort(n, ary));
projects / libucw.git / blobdiff