1. Си / Говнокод #25307

    −1

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    38. 38
    39. 39
    40. 40
    41. 41
    42. 42
    43. 43
    44. 44
    45. 45
    46. 46
    47. 47
    48. 48
    49. 49
    50. 50
    51. 51
    52. 52
    53. 53
    54. 54
    55. 55
    56. 56
    57. 57
    58. 58
    59. 59
    60. 60
    61. 61
    62. 62
    63. 63
    64. 64
    65. 65
    66. 66
    67. 67
    68. 68
    69. 69
    70. 70
    71. 71
    72. 72
    73. 73
    74. 74
    void sort8(uint64_t a[8])
{
  uint64_t a0;
  uint64_t a1;
  uint64_t a2;
  uint64_t a3;
  uint64_t a4;
  uint64_t a5;
  uint64_t a6;
  uint64_t a7;
 
  SORT2(a[0], a[1], a0, a1);
  SORT2(a[2], a[3], a2, a3);
  SORT2(a[4], a[5], a4, a5);
  SORT2(a[6], a[7], a6, a7);

  uint64_t a_tmp[8];

  MERGE_2_4(a0, a1, a2, a3, a_tmp[0], a_tmp[1], a_tmp[2], a_tmp[3]);
  MERGE_2_4(a4, a5, a6, a7, a_tmp[4], a_tmp[5], a_tmp[6], a_tmp[7]);

  uint64_t *ptra1 = &a_tmp[0];
  uint64_t *ptra2 = &a_tmp[4];
  
  for (size_t i = 0; i < 4; i++)
  {
    if (*ptra1 < *ptra2)
    {
      a[i] = *ptra1;
      ptra1++;
    }
    else
    {
      a[i] = *ptra2;
      ptra2++;
    }
  }

  for (size_t i = 4; i < 8; i++)
  {
    if (ptra1 == &a_tmp[4])
    {
      while (ptra2 != &a_tmp[8])
      {
        a[i++] = *ptra2;
        ptra2++;
      }
      break;
    }
    
    if (ptra2 == &a_tmp[8])
    {
      while (ptra1 != &a_tmp[4])
      {
        a[i++] = *ptra1;
        ptra1++;
      }
      break;
    }


    if (*ptra1 < *ptra2)
    {
      a[i] = *ptra1;
      ptra1++;
    }
    else
    {
      a[i] = *ptra2;
      ptra2++;
    }

  }
}

    Мерж сорт, специализированный на 8 элементов. Вот доказательство корректности https://paste.debian.net/hidden/cce6d31a/

    Запостил: j123123, 13 Января 2019

    Комментарии (137) RSS

    • ava j123123 13.01.2019 15:02 # +1

      Ах да, макросня для смерживания и сортировки кусков по 2 элемента
      #define SORT2(a, b, a1, b1) \
  do {if (a < b) {a1 = a; b1 = b;} else {a1 = b; b1 = a;};} while (0)

/*
#define SORT2(a, b, a1, b1) \
  do {typeof(a1) temp_var[3] = {a, b, a}; a1 = temp_var[(a > b)]; b1 = temp_var[(a > b)+1];} while (0)
*/

#define MERGE_2_4(a0, a1, a2, a3, as0, as1, as2, as3) \
do \
{ \
  if (a0 > a2) \
  { \
    if (a0 > a3) \
    { \
      as0 = a2; \
      as1 = a3; \
      as2 = a0; \
      as3 = a1; \
    } \
    else \
    { \
      if (a1 > a3) \
      { \
        as0 = a2; \
        as1 = a0; \
        as2 = a3; \
        as3 = a1; \
      } \
      else \
      { \
        as0 = a2; \
        as1 = a0; \
        as2 = a1; \
        as3 = a3; \
      } \
    } \
  } \
  else \
  { \
    if (a2 >= a1) \
    { \
      as0 = a0; \
      as1 = a1; \
      as2 = a2; \
      as3 = a3; \
    } \
    else \
    { \
      if (a3 >= a1) \
      { \
        as0 = a0; \
        as1 = a2; \
        as2 = a1; \
        as3 = a3; \
      } \
      else \
      { \
        as0 = a0; \
        as1 = a2; \
        as2 = a3; \
        as3 = a1; \
      } \
    } \
  } \
} while (0)


      Эта херня по итогам уделывает в скорости std::sort, если им сортировать куски по 8 элементов.
      Ответить

    • ava bormand 13.01.2019 15:13 # 0

      А чего последний мёрж не заанроллен?
      Ответить

      • ava j123123 13.01.2019 15:15 # 0

        Компилятор такой цикл должен сам анролльнуть на высокой оптимизации
        Ответить

      • ava j123123 13.01.2019 16:43 # 0

        Хотя вообще да, можно было б запилить еще кроме вот того MERGE_2_4 еще MERGE_4_8 и например MERGE_8_16. Только тут уже кодогенерация нужна, я это руками заебусь делать.
        Ответить

    • ava j123123 13.01.2019 16:05 # 0

      Вот даже бенчмаркалку сделал через /dev/urandom, даже с крестоговном https://paste.debian.net/hidden/4a8b71cf/

      Кто-нибудь сможет быстрее сортировку на восемь uint64_t сделать (можно даже попробовать какое-нибудь SSE, если оно чем-то сможет помочь)? std::sort отстает от этого кода на GCC.
      Ответить

      • ava bormand 13.01.2019 18:34 # +1

        > uint64_t
        Подстраховался от эсэсёбства? :)
        Ответить

      • ava bormand 13.01.2019 19:15 # 0

        Вот такая хуйня медленнее чем твоя?
        void sort2(uint64_t a, uint64_t b, uint64_t& oa, uint64_t& ob) {
    if (a < b) {
        oa = a;
        ob = b;
    } else {
        oa = b;
        ob = a;
    }
}

void sort8(uint64_t a[8]) {
    uint64_t b[8], c[8], d[8], e[8], f[8];
    sort2(a[0], a[1], b[0], b[1]); sort2(a[2], a[3], b[2], b[3]); sort2(a[4], a[5], b[4], b[5]); sort2(a[6], a[7], b[6], b[7]);
    sort2(b[0], b[3], c[0], c[3]); sort2(b[1], b[2], c[1], c[2]); sort2(b[4], b[7], c[4], c[7]); sort2(b[5], b[6], c[5], c[6]);
    sort2(c[0], c[1], d[0], d[1]); sort2(c[2], c[3], d[2], d[3]); sort2(c[4], c[5], d[4], d[5]); sort2(c[6], c[7], d[6], d[7]);
    sort2(d[0], d[7], e[0], e[7]); sort2(d[1], d[6], e[1], e[6]); sort2(d[2], d[5], e[2], e[5]); sort2(d[3], d[4], e[3], e[4]);
    sort2(e[0], e[2], f[0], f[2]); sort2(e[1], e[3], f[1], f[3]); sort2(e[4], e[6], f[4], f[6]); sort2(e[5], e[7], f[5], f[7]);
    sort2(f[0], f[1], a[0], a[1]); sort2(f[2], f[3], a[2], a[3]); sort2(f[4], f[5], a[4], a[5]); sort2(f[6], f[7], a[6], a[7]);
}
        Ответить

        • ava j123123 14.01.2019 00:42 # 0

          Немного быстрее, но там выигрыш идет из-за последней стадии (т.е. последние три строчки с sort2)
          // Вот эти вот три говнострочки
    sort2(a[0], a[1], b[0], b[1]); sort2(a[2], a[3], b[2], b[3]); sort2(a[4], a[5], b[4], b[5]); sort2(a[6], a[7], b[6], b[7]);
    sort2(b[0], b[3], c[0], c[3]); sort2(b[1], b[2], c[1], c[2]); sort2(b[4], b[7], c[4], c[7]); sort2(b[5], b[6], c[5], c[6]);
    sort2(c[0], c[1], d[0], d[1]); sort2(c[2], c[3], d[2], d[3]); sort2(c[4], c[5], d[4], d[5]); sort2(c[6], c[7], d[6], d[7]);
// по сути просто делают четыре сортированных элемента, и еще четыре сортированных элемента.


/// если заменить это на:
    sort2(a[0], a[1], b[0], b[1]); sort2(a[2], a[3], b[2], b[3]); sort2(a[4], a[5], b[4], b[5]); sort2(a[6], a[7], b[6], b[7]); // эта строка без изменений
    
    MERGE_2_4(b[0], b[1], b[2], b[3], d[0], d[1], d[2], d[3]);
    MERGE_2_4(b[4], b[5], b[6], b[7], d[4], d[5], d[6], d[7]);
// то получается чуточку быстрее


          Если последнюю стадию улучшить (наанроллить) в моем варианте, можно быстрей перфоманс сделать.
          Ответить

          • ava j123123 14.01.2019 00:42 # 0

            Вообще, profile guided optimization (PGO) решает:
            user@pc:~/prog/sort_shit$ gcc-7 -O3 -march=native -std=gnu++11 rand_benchmark.cpp  -lstdc++
user@pc:~/prog/sort_shit$ ./a.out 
time = 401513026
user@pc:~/prog/sort_shit$ ./a.out 
time = 405119209
user@pc:~/prog/sort_shit$ ./a.out 
time = 400842337
user@pc:~/prog/sort_shit$ gcc-7 -O3 -march=native -std=gnu++11 -fprofile-generate rand_benchmark.cpp  -lstdc++
user@pc:~/prog/sort_shit$ ./a.out 
time = 463633839
user@pc:~/prog/sort_shit$ gcc-7 -O3 -march=native -std=gnu++11 -fprofile-use -freorder-blocks-and-partition -fprofile-correction -Wcoverage-mismatch rand_benchmark.cpp -lstdc++
user@pc:~/prog/sort_shit$ ./a.out 
time = 376823228
user@pc:~/prog/sort_shit$ ./a.out 
time = 375864788
user@pc:~/prog/sort_shit$ ./a.out 
time = 377222836



            Да, если с PGO оптимизировать обычный std::sort, он оба варианта уделывает по пирфомансу
            user@pc:~/prog/sort_shit$ ./a.out 
time = 140083097
user@pc:~/prog/sort_shit$ ./a.out 
time = 139075303
user@pc:~/prog/sort_shit$ ./a.out 
time = 139685936
user@pc:~/prog/sort_shit$ ./a.out 
time = 139227202
user@pc:~/prog/sort_shit$ ./a.out 
time = 138889191


            https://paste.debian.net/hidden/eadc947e/ - вот код для тестов, если интересно
            Ответить

            • ava j123123 14.01.2019 04:41 # +1

              Поправка - там был баг в заполнении байтиков из /dev/urandom, изза чего там много нулей в массиве было
              // было
    ssize_t result = read(randfd, str, sizeof(str));
    if (result < 0)
    {
      fprintf(stderr, "read err\n");
      exit(-1);
    }

// стало
    size_t randomDataLen = 0;
    while (randomDataLen != sizeof(str) )
    {
      ssize_t result = read(randfd, (char *)str + randomDataLen, sizeof(str) - randomDataLen);
      if (result < 0)
      {
        fprintf(stderr, "read err\n");
        exit(-1);
      }
      randomDataLen += result;
    }


              Теперь std::sort опять проигрывает, даже с PGO. Видимо этот std::sort по дизайну так запилен, чтоб частично сортированнные массивы досортировывать (досортировывать массивы из одних нулей - легко!), а если еще PGO использовать, то тогда вообще супер быстро получается.

              https://paste.debian.net/hidden/368b30a7/
              Ответить

        • ava j123123 14.01.2019 07:49 # +1

          Я провел еще дополнительные исследования. Чистая битонная сортировка (без вклиниваний MERGE_2_4) на clang++-6.0 работает существенно быстрее каких-либо других вариантов

          https://paste.debian.net/hidden/d6c6cd71/ тестовый код

          rm default.profdata default.profraw

clang++-6.0 -O3 -fno-stack-protector -D_FORTIFY_SOURCE=0 -march=native -std=gnu++11 -fcoverage-mapping -fprofile-instr-generate rand_benchmark.cpp -lstdc++
./a.out
llvm-profdata-6.0 merge -output=default.profdata default.profraw
clang++-6.0 -O3 -march=native -fno-stack-protector -D_FORTIFY_SOURCE=0 -fprofile-instr-use=default.profdata -std=gnu++11 rand_benchmark.cpp -lstdc++
./a.out; ./a.out; ./a.out; ./a.out

          Вывод времени

          time = 154968303
          time = 149922928
          time = 151220900
          time = 150623575


          Для GCC-8 всё сильно медленней:
          gcc-8 -O3 -fno-stack-protector -D_FORTIFY_SOURCE=0 -march=native -std=gnu++11 -fprofile-generate rand_benchmark.cpp -lstdc++
./a.out
gcc-8 -O3 -fno-stack-protector -D_FORTIFY_SOURCE=0 -march=native -std=gnu++11 -fprofile-use -freorder-blocks-and-partition -fprofile-correction -fbranch-target-load-optimize -fbranch-probabilities -Wcoverage-mismatch rand_benchmark.cpp -lstdc++
./a.out; ./a.out; ./a.out; ./a.out;


          time = 381412656
          time = 381636722
          time = 381310683
          time = 379839114
          Ответить

          • ava j123123 14.01.2019 07:56 # 0

            Чтоб докопаться до причин такой разницы, можно сделать
            void __attribute__ ((noinline)) sort8_b(uint64_t a[8])

            (тогда можно будет увидеть саму функцию в ненаанролленом виде).

            И что же мы видим в случае clang?
            _Z7sort8_bPm:                           # @_Z7sort8_bPm
	.cfi_startproc
# %bb.0:
	pushq	%r15
	.cfi_def_cfa_offset 16
	pushq	%r14
	.cfi_def_cfa_offset 24
	pushq	%rbx
	.cfi_def_cfa_offset 32
	.cfi_offset %rbx, -32
	.cfi_offset %r14, -24
	.cfi_offset %r15, -16
	movq	(%rdi), %rax
	movq	8(%rdi), %rcx
	cmpq	%rcx, %rax
	movq	%rcx, %r9
	cmovbq	%rax, %r9
	cmovbq	%rcx, %rax
	movq	16(%rdi), %rsi
	movq	24(%rdi), %rcx
	cmpq	%rcx, %rsi
	movq	%rcx, %r8
	cmovbq	%rsi, %r8
	cmovbq	%rcx, %rsi
	movq	32(%rdi), %r10
	movq	40(%rdi), %rcx
	cmpq	%rcx, %r10
	movq	%rcx, %r11
	cmovbq	%r10, %r11
	cmovbq	%rcx, %r10
	movq	48(%rdi), %rdx
	movq	56(%rdi), %rbx
	cmpq	%rbx, %rdx
	movq	%rbx, %rcx
	cmovbq	%rdx, %rcx
	cmovbq	%rbx, %rdx
	cmpq	%rsi, %r9
	movq	%rsi, %rbx
	cmovbq	%r9, %rbx
	cmovaeq	%r9, %rsi
	cmpq	%r8, %rax

            куча сравнений и условных мувов.


            Что же касается GCC:
            _Z7sort8_bPm:
.LFB2309:
	.cfi_startproc
	movq	8(%rdi), %rsi
	pushq	%rbx
	.cfi_def_cfa_offset 16
	.cfi_offset 3, -16
	movq	(%rdi), %r11
	cmpq	%r11, %rsi
	ja	.L83
	movq	%r11, %rax
	movq	%rsi, %r11
	movq	%rax, %rsi
.L83:
	movq	24(%rdi), %rcx
	movq	16(%rdi), %r10
	cmpq	%r10, %rcx
	ja	.L84
	movq	%r10, %rdx
	movq	%rcx, %r10
	movq	%rdx, %rcx
.L84:
	movq	40(%rdi), %rdx
	movq	32(%rdi), %r9
	cmpq	%r9, %rdx
	ja	.L85
	movq	%r9, %rbx
	movq	%rdx, %r9
	movq	%rbx, %rdx
.L85:
	movq	56(%rdi), %rax
	movq	48(%rdi), %r8
	cmpq	%r8, %rax
	ja	.L86
	movq	%r8, %rbx
	movq	%rax, %r8
	movq	%rbx, %rax
.L86:
	cmpq	%r11, %rcx
	ja	.L87
	movq	%r11, %rbx
	movq	%rcx, %r11
	movq	%rbx, %rcx
.L87:
	cmpq	%rsi, %r10
	ja	.L88
	movq	%rsi, %rbx
	movq	%r10, %rsi
	movq	%rbx, %r10
.L88:

            Мы видим кучу меток и условных переходов, тут явно какой-то косяк компилятора. Надо будет в багзиллу GCC ченить накатать по этому поводу.
            Ответить

    • ava j123123 16.01.2019 05:44 # 0

      Вообще, наибыстрейший в среднем алгоритм сортировки, если сортируемые данные это чистый рандом, зависит еще от того, как соотносится время, в среднем затрачиваемое на сравнение с временем, затрачиваемым на перестановку элементов. Ну т.е. если надо сортировать какой-нибудь гипотетический uint1024_t, процедуру сравнения двух таких чисел можно сделать через последовательное сравнение 16-ти 64-битных uint64_t (т.к. 1024/64 = 16)
      int cmp_uint1024_t(uint64_t val1024_a[16], uint64_t val1024_b[16])
{
  for (size_t i = 0; i < 16; i++)
  {
    if (val1024_a[i] < val1024_b[i])
    {
      return B_GREATER_THAN_A;
    }
    else if (val1024_a[i] > val1024_b[i])
    {
      return A_GREATER_THAN_B;
    }
  }
  return A_EQUAL_B; // или тут можно B_GREATER_THAN_A вернуть если в этом случае свап не делается
}


      на случайных данных будет оччень малая вероятность, что на первом же 64-битном куске оба числа будут одинаковы (если быть точным, вероятность эта равна 1/18446744073709551616 - вероятность случайно угадать 64-битное число)

      а процедура обмена двух uint1024_t уже будет достаточно дорогой. Но можно не менять сами uint1024_t, а хранить некий вспомогательный массив индексов
      void sort2(uint64_t val1024_arr[][16], uint8_t index_a[1], uint8_t index_b[1])
{
  int cmp = cmp_uint1024_t( arr[ index_a[0] ], arr[ index_b[0] ] )
  if ((cmp == B_GREATER_THAN_A) || (cmp == A_EQUAL_B))
  {
    return;
  }
  else
  {
    // swap this shit;
    uint8_t tmp;
    tmp = a[0];
    a[0] = b[0];
    b[0] = tmp;
  }
}

      А потом уже в конце можно пораспихивать все эти массивчики через этот говномассив с перестановками, но если мы сортируем большой массив (а не кусочками по 8 штук) то у нас от прыганья по этим индексам будет промахи кэша, в общем тут много чего можно понапридумывать с этим говном
      Ответить

    Добавить комментарий