Project

General

Profile

Feature #6256 » rubyqisort.patch

MartinBosslet (Martin Bosslet), 04/07/2012 07:36 AM

View differences:

benchmark/bm_sort_int_custom.rb (revision 0)
ary = Array.new(100000) { |i| i }.shuffle!
ary.sort { |x, y| -(x <=> y) }
benchmark/bm_sort_int_sorted.rb (revision 0)
Array.new(1000000) { |i| i }.sort!
benchmark/bm_sort_str_rnd.rb (revision 0)
prng = Random.new(42)
Array.new(100000) { prng.bytes(15) }.sort!
benchmark/bm_sort_int.rb (revision 0)
Array.new(1000000) { |i| i }.shuffle!.sort!
util.c (working copy)
}
#define mmrot3(a,b,c) mmrot3_((a),(b),(c),mmarg)
/* a = b */
static void mmassign_(register char *a, register char *b, mmargdecl)
{
if (a == b) return;
if (mmkind >= 0) {
#if mmcount > 1
if (mmkind > 0) {
register char *t = a + high;
do {
A[0] = B[0];
A[1] = B[1];
#if mmcount > 2
A[2] = B[2];
#if mmcount > 3
A[3] = B[3];
#endif
#endif
a += mmstep; b += mmstep;
} while (a < t);
}
#endif
if (low != 0) { A[0] = B[0];
#if mmcount > 2
if (low >= 2 * sizeof(mmtype)) { A[1] = B[1];
#if mmcount > 3
if (low >= 3 * sizeof(mmtype)) { A[2] = B[2]; }
#endif
}
#endif
}
}
else {
register char *t = a + size;
do { *a++ = *b++;} while (a < t);
}
}
#define mmassign(a, b) mmassign_((a),(b),mmarg)
/* qs6.c */
/*****************************************************/
/* */
......
((*cmp)((b),(c),d)>0 ? (b) : ((*cmp)((a),(c),d)<0 ? (a) : (c))))
typedef int (cmpfunc_t)(const void*, const void*, void*);
static void
ruby_isort(char *l, char *r, cmpfunc_t *cmp, void *d, mmargdecl)
{
char *p, *q, *v, *tmp;
v = ALLOCA_N(char, size);
for(p = l + size; p <= r; p += size) {
if (cmp(p - size, p, d) <= 0)
continue;
mmassign(v, p);
tmp = p - size;
mmassign(p, p - size);
for (q = tmp - size; q >= l && cmp(q, v, d) > 0; q -= size) {
mmassign(q + size, q);
}
mmassign(q + size, v);
}
}
void
ruby_qsort(void* base, const size_t nel, const size_t size, cmpfunc_t *cmp, void *d)
{
......
register int t, eq_l, eq_r; /* eq_l: all items in left group are equal to S */
char *L = base; /* left end of current region */
char *R = (char*)base + size*(nel-1); /* right end of current region */
size_t chklim = 63; /* threshold of ordering element check */
stack_node stack[32], *top = stack; /* 32 is enough for 32bit CPU */
int mmkind;
size_t high, low, n;
......
if ((*cmp)(L,R,d) > 0) mmswap(L,R); goto nxt;
}
n = (R - L + size) / size; /* number of elements */
if (n < 9) { /* Sort small sub problems (9 is empirical) with insertion sort */
ruby_isort(L, R, cmp, d, mmarg);
goto nxt;
}
l = L; r = R;
n = (r - l + size) / size; /* number of elements */
m = l + size * (n >> 1); /* calculate median value */
if (n >= 60) {
......
if ((t = (*cmp)(l,m,d)) < 0) { /*3-5-?*/
if ((t = (*cmp)(m,r,d)) < 0) { /*3-5-7*/
if (chklim && nel >= chklim) { /* check if already ascending order */
char *p;
chklim = 0;
for (p=l; p<r; p+=size) if ((*cmp)(p,p+size,d) > 0) goto fail;
goto nxt;
}
fail: goto loopA; /*3-5-7*/
goto loopA;
}
if (t > 0) {
if ((*cmp)(l,r,d) <= 0) {mmswap(m,r); goto loopA;} /*3-5-4*/
if ((*cmp)(l,r,d) <= 0) {mmswap(m,r); goto loopA;} /*3-5-4*/
mmrot3(r,m,l); goto loopA; /*3-5-2*/
}
goto loopB; /*3-5-5*/
......
if (t > 0) { /*7-5-?*/
if ((t = (*cmp)(m,r,d)) > 0) { /*7-5-3*/
if (chklim && nel >= chklim) { /* check if already ascending order */
char *p;
chklim = 0;
for (p=l; p<r; p+=size) if ((*cmp)(p,p+size,d) < 0) goto fail2;
while (l<r) {mmswap(l,r); l+=size; r-=size;} /* reverse region */
goto nxt;
}
fail2: mmswap(l,r); goto loopA; /*7-5-3*/
mmswap(l,r);
goto loopA;
}
if (t < 0) {
if ((*cmp)(l,r,d) <= 0) {mmswap(l,m); goto loopB;} /*7-5-8*/
(2-2/4)