Feature #6256 » rubyqisort.patch
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*/
|