Project

General

Profile

Feature #6256 ยป rubyqisort5.patch

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

View differences:

util.c (working copy)
301 301
                       ((*cmp)((b),(c),d)>0 ? (b) : ((*cmp)((a),(c),d)<0 ? (a) : (c))))
302 302

  
303 303
typedef int (cmpfunc_t)(const void*, const void*, void*);
304

  
305
static void
306
ruby_isort(char *l, char *r, cmpfunc_t *cmp, void *d, const size_t size)
307
{
308
    char *p, *q, *v;
309
    size_t i;
310

  
311
    v = ALLOCA_N(char, size);
312

  
313
    for(p = l + size; p <= r; p += size) {
314
	if (cmp(p - size, p, d) <= 0)
315
	    continue;
316

  
317
	memcpy(v, p, size);
318
	i = 1;
319
	for (q = p - 2 * size; q >= l && cmp(q, v, d) > 0; q -= size) {
320
	    i++;
321
	}
322
        memmove(q + 2 * size, q + size, i * size);
323
        memcpy(q + size, v, size);
324
    }
325
}
326

  
304 327
void
305 328
ruby_qsort(void* base, const size_t nel, const size_t size, cmpfunc_t *cmp, void *d)
306 329
{
......
308 331
  register int t, eq_l, eq_r;       	/* eq_l: all items in left group are equal to S */
309 332
  char *L = base;                    	/* left end of current region */
310 333
  char *R = (char*)base + size*(nel-1); /* right end of current region */
311
  size_t chklim = 63;                   /* threshold of ordering element check */
334
  size_t chklim = 9;                    /* threshold of ordering element check */
335
  size_t cutoff = chklim;
312 336
  stack_node stack[32], *top = stack;   /* 32 is enough for 32bit CPU */
313 337
  int mmkind;
314 338
  size_t high, low, n;
......
327 351
      if ((*cmp)(L,R,d) > 0) mmswap(L,R); goto nxt;
328 352
    }
329 353

  
354
    n = (R - L + size) / size;  /* number of elements */
355
    if (n < cutoff) { /* Sort small sub problems (9 is empirical) with insertion sort */
356
        ruby_isort(L, R, cmp, d, size);
357
    	goto nxt;
358
    }
330 359
    l = L; r = R;
331
    n = (r - l + size) / size;  /* number of elements */
332 360
    m = l + size * (n >> 1);    /* calculate median value */
333 361

  
334 362
    if (n >= 60) {
......
366 394
	fail: goto loopA;                                    /*3-5-7*/
367 395
      }
368 396
      if (t > 0) {
369
	if ((*cmp)(l,r,d) <= 0) {mmswap(m,r); goto loopA;}     /*3-5-4*/
397
	if ((*cmp)(l,r,d) <= 0) {mmswap(m,r); goto loopA;}   /*3-5-4*/
370 398
	mmrot3(r,m,l); goto loopA;                           /*3-5-2*/
371 399
      }
372 400
      goto loopB;                                            /*3-5-5*/
......
374 402

  
375 403
    if (t > 0) {                                             /*7-5-?*/
376 404
      if ((t = (*cmp)(m,r,d)) > 0) {                         /*7-5-3*/
377
	if (chklim && nel >= chklim) {   /* check if already ascending order */
405
	if (chklim && nel >= chklim) {   /* check if already descending order */
378 406
	  char *p;
379 407
	  chklim = 0;
380 408
	  for (p=l; p<r; p+=size) if ((*cmp)(p,p+size,d) < 0) goto fail2;
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_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_int.rb (revision 0)
1
Array.new(1000000) { |i| i }.shuffle!.sort!
2