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)
1
ary = Array.new(100000) { |i| i }.shuffle!
2
ary.sort { |x, y| -(x <=> y) }
3

  
benchmark/bm_sort_int_sorted.rb (revision 0)
1
Array.new(1000000) { |i| i }.sort!
benchmark/bm_sort_str_rnd.rb (revision 0)
1
prng = Random.new(42)
2
Array.new(100000) { prng.bytes(15) }.sort!
3

  
benchmark/bm_sort_int.rb (revision 0)
1
Array.new(1000000) { |i| i }.shuffle!.sort!
2

  
util.c (working copy)
283 283
}
284 284
#define mmrot3(a,b,c) mmrot3_((a),(b),(c),mmarg)
285 285

  
286
/* a = b */
287
static void mmassign_(register char *a, register char *b, mmargdecl)
288
{
289
 if (a == b) return;
290
 if (mmkind >= 0) {
291
#if mmcount > 1
292
   if (mmkind > 0) {
293
     register char *t = a + high;
294
     do {
295
       A[0] = B[0];
296
       A[1] = B[1];
297
#if mmcount > 2
298
       A[2] = B[2];
299
#if mmcount > 3
300
       A[3] = B[3];
301
#endif
302
#endif
303
       a += mmstep; b += mmstep;
304
     } while (a < t);
305
   }
306
#endif
307
   if (low != 0) { A[0] = B[0];
308
#if mmcount > 2
309
     if (low >= 2 * sizeof(mmtype)) { A[1] = B[1];
310
#if mmcount > 3
311
       if (low >= 3 * sizeof(mmtype)) { A[2] = B[2]; }
312
#endif
313
     }
314
#endif
315
   }
316
 }
317
 else {
318
   register char *t = a + size;
319
   do { *a++ = *b++;} while (a < t);
320
 }
321
}
322
#define mmassign(a, b) mmassign_((a),(b),mmarg)
323

  
324

  
286 325
/* qs6.c */
287 326
/*****************************************************/
288 327
/*                                                   */
......
301 340
                       ((*cmp)((b),(c),d)>0 ? (b) : ((*cmp)((a),(c),d)<0 ? (a) : (c))))
302 341

  
303 342
typedef int (cmpfunc_t)(const void*, const void*, void*);
343

  
344
static void
345
ruby_isort(char *l, char *r, cmpfunc_t *cmp, void *d, mmargdecl)
346
{
347
    char *p, *q, *v, *tmp;
348

  
349
    v = ALLOCA_N(char, size);
350

  
351
    for(p = l + size; p <= r; p += size) {
352
	if (cmp(p - size, p, d) <= 0)
353
	    continue;
354

  
355
	mmassign(v, p);
356
	tmp = p - size;
357
	mmassign(p, p - size);
358
	for (q = tmp - size; q >= l && cmp(q, v, d) > 0; q -= size) {
359
	    mmassign(q + size, q);
360
	}
361
	mmassign(q + size, v);
362
    }
363
}
364

  
304 365
void
305 366
ruby_qsort(void* base, const size_t nel, const size_t size, cmpfunc_t *cmp, void *d)
306 367
{
......
308 369
  register int t, eq_l, eq_r;       	/* eq_l: all items in left group are equal to S */
309 370
  char *L = base;                    	/* left end of current region */
310 371
  char *R = (char*)base + size*(nel-1); /* right end of current region */
311
  size_t chklim = 63;                   /* threshold of ordering element check */
312 372
  stack_node stack[32], *top = stack;   /* 32 is enough for 32bit CPU */
313 373
  int mmkind;
314 374
  size_t high, low, n;
......
327 387
      if ((*cmp)(L,R,d) > 0) mmswap(L,R); goto nxt;
328 388
    }
329 389

  
390
    n = (R - L + size) / size;  /* number of elements */
391
    if (n < 9) { /* Sort small sub problems (9 is empirical) with insertion sort */
392
        ruby_isort(L, R, cmp, d, mmarg);
393
    	goto nxt;
394
    }
330 395
    l = L; r = R;
331
    n = (r - l + size) / size;  /* number of elements */
332 396
    m = l + size * (n >> 1);    /* calculate median value */
333 397

  
334 398
    if (n >= 60) {
......
357 421

  
358 422
    if ((t = (*cmp)(l,m,d)) < 0) {                           /*3-5-?*/
359 423
      if ((t = (*cmp)(m,r,d)) < 0) {                         /*3-5-7*/
360
	if (chklim && nel >= chklim) {   /* check if already ascending order */
361
	  char *p;
362
	  chklim = 0;
363
	  for (p=l; p<r; p+=size) if ((*cmp)(p,p+size,d) > 0) goto fail;
364
	  goto nxt;
365
	}
366
	fail: goto loopA;                                    /*3-5-7*/
424
	goto loopA;
367 425
      }
368 426
      if (t > 0) {
369
	if ((*cmp)(l,r,d) <= 0) {mmswap(m,r); goto loopA;}     /*3-5-4*/
427
	if ((*cmp)(l,r,d) <= 0) {mmswap(m,r); goto loopA;}   /*3-5-4*/
370 428
	mmrot3(r,m,l); goto loopA;                           /*3-5-2*/
371 429
      }
372 430
      goto loopB;                                            /*3-5-5*/
......
374 432

  
375 433
    if (t > 0) {                                             /*7-5-?*/
376 434
      if ((t = (*cmp)(m,r,d)) > 0) {                         /*7-5-3*/
377
	if (chklim && nel >= chklim) {   /* check if already ascending order */
378
	  char *p;
379
	  chklim = 0;
380
	  for (p=l; p<r; p+=size) if ((*cmp)(p,p+size,d) < 0) goto fail2;
381
	  while (l<r) {mmswap(l,r); l+=size; r-=size;}  /* reverse region */
382
	  goto nxt;
383
	}
384
	fail2: mmswap(l,r); goto loopA;                      /*7-5-3*/
435
	mmswap(l,r); 
436
        goto loopA;
385 437
      }
386 438
      if (t < 0) {
387 439
	if ((*cmp)(l,r,d) <= 0) {mmswap(l,m); goto loopB;}   /*7-5-8*/