Duff’s device bubblesort

В продолжение пузырьков, кэшей и предсказателей переходов вариант пузырьковой сортировки а-ля Duff’s device:

    for (i = 0; i < N - 1; i++) {
      register size_t n = ( i + 8 ) / 8;
      register int *src = a + i, *dst = a + i + 1;
      switch((i + 1) % 8 ) {
      case 0:    do {    if (*dst < *src) swap(*dst, *src); dst--; src--;
      case 7:        if (*dst < *src) swap(*dst, *src); dst--; src--;
      case 6:        if (*dst < *src) swap(*dst, *src); dst--; src--;
      case 5:        if (*dst < *src) swap(*dst, *src); dst--; src--;
      case 4:        if (*dst < *src) swap(*dst, *src); dst--; src--;
      case 3:        if (*dst < *src) swap(*dst, *src); dst--; src--;
      case 2:        if (*dst < *src) swap(*dst, *src); dst--; src--;
      case 1:        if (*dst < *src) swap(*dst, *src); dst--; src--;
	} while(--n > 0);
      }
    }

Обновленный код: bubble-duff.zip

На моей машине получаются такие результаты сравнения трех методов:

test1: 48.0096
test2: 33.6773
duff_test: 29.7313
ratio(1/2): 1.43
ratio(1/d): 1.61
ratio(2/d): 1.13

Добавка: Вариант, дающий эффект при включенной оптимизации компилятора (-O2):

    for (i = 1; i < N; i++) {
      n = (i + 7) / 8;
      s = i % 8;
      src = a + (n - 1) * 8;
      switch(s) {
      case 0:    do {    if (src[8] < src[7]) swap(src[8], src[7]);
      case 7:        if (src[7] < src[6]) swap(src[7], src[6]);
      case 6:        if (src[6] < src[5]) swap(src[6], src[5]);
      case 5:        if (src[5] < src[4]) swap(src[5], src[4]);
      case 4:        if (src[4] < src[3]) swap(src[4], src[3]);
      case 3:        if (src[3] < src[2]) swap(src[3], src[2]);
      case 2:        if (src[2] < src[1]) swap(src[2], src[1]);
      case 1:        if (src[1] < src[0]) swap(src[1], src[0]);
	src -= 8;
	} while(--n > 0);
      }
    }

Его результаты c включенной оптимизацией (-O2):

test1: 17.4618
test2: 6.00334
duff_test: 4.6114
ratio(1/2): 2.91
ratio(1/d): 3.79
ratio(2/d): 1.30

Его результаты без оптимизации:

test1: 48.0096
test2: 33.9788
duff_test: 22.2689
ratio(1/2): 1.41
ratio(1/d): 2.16
ratio(2/d): 1.53