quadsort simdできるかなかな？（分岐無しソート）

# quadsort simd化検討

quadsortをSIMD化、もうちょっと検討して、こうなった。

ポイントは、A,B,C,D の、A,Dは確定できるけど、それだけだと、CとDの順番保障も必要というところ。

8要素8組のソート(≠ 64要素のソート) で、50 instruction 。
ちゃんと動くなら、まあまあじゃないかなーと。

とりあえず、これでおしまい。ベンチマークとか本当にちゃんとできるのか、とかはさておき。

## ポイント
分岐も何もないので、最悪も最良も平均も計算量O(N)です。データの並びとか一切関係なく、O(N)で処理できます。

## ただし
これ、まだマージソートの一部しかないので、qsortとバトルとか、quicksortとバトルとかできません…
それは予定してないので、ほにゃほにゃ。

```c++:a.cpp
kmtr@ubuntu:~/work/2020/0222_quadsimd$ cat a.cpp
#include <iostream>
#include <immintrin.h>

void simd_sort(int *val)
{
        #define SWAP4(valA,valB,valC,valD) \
        { \
                tmp0 = _mm256_min_epi32 ( valA, valB ); \
                tmp1 = _mm256_max_epi32 ( valA, valB ); \
                tmp2 = _mm256_min_epi32 ( valC, valD ); \
                tmp3 = _mm256_max_epi32 ( valC, valD ); \
                valA = _mm256_min_epi32 ( tmp0, tmp2 ); \
                valD = _mm256_max_epi32 ( tmp1, tmp3 ); \
                tmp4 = _mm256_max_epi32 ( tmp0, tmp2 ); \
                tmp5 = _mm256_min_epi32 ( tmp1, tmp3 ); \
                valB = _mm256_min_epi32 ( tmp4, tmp5 ); \
                valC = _mm256_max_epi32 ( tmp4, tmp5 ); \
        }
        /*
         tmp0 = min(valA, valB);
         tmp1 = max(valA, valB);
         tmp2 = min(valC, valD);
         tmp3 = max(valC, valD);

         outA = min(tmp0, tmp2) = min(valA,valB,valC,valD);
         outD = max(tmp1, tmp3) = max(valA,valB,valC,valD);

         tmp4 = max(tmp0, tmp2) != outA
         tmp5 = min(tmp1, tmp3) != outD
         so
         ( tmp4,tmp5 ) = valB, valC

         outB = min ( tmp4,tmp5 ) = min ( valB, valC )
         outC = max ( tmp4,tmp5 ) = max ( valB, valC )

         */

        __m256i val0, val1, val2, val3;
        __m256i val4, val5, val6, val7;
        __m256i tmp0, tmp1, tmp2, tmp3;
        __m256i tmp4, tmp5;

        val0 = _mm256_load_si256( (__m256i*) val     ) ;
        val1 = _mm256_load_si256( (__m256i*) val + 1 ) ;
        val2 = _mm256_load_si256( (__m256i*) val + 2 ) ;
        val3 = _mm256_load_si256( (__m256i*) val + 3 ) ;
        val4 = _mm256_load_si256( (__m256i*) val + 4 ) ;
        val5 = _mm256_load_si256( (__m256i*) val + 5 ) ;
        val6 = _mm256_load_si256( (__m256i*) val + 6 ) ;
        val7 = _mm256_load_si256( (__m256i*) val + 7 ) ;

        // Step 1
        SWAP4( val0, val1, val2, val3 );
        SWAP4( val4, val5, val6, val7 );

        // Step 2
        SWAP4( val0, val1, val4, val5 );
        SWAP4( val2, val3, val6, val7 );

        // Step 3
        SWAP4( val2, val3, val4, val5 );

        _mm256_store_si256( (__m256i*) val + 0 , val0 ) ;
        _mm256_store_si256( (__m256i*) val + 1 , val1 ) ;
        _mm256_store_si256( (__m256i*) val + 2 , val2 ) ;
        _mm256_store_si256( (__m256i*) val + 3 , val3 ) ;
        _mm256_store_si256( (__m256i*) val + 4 , val4 ) ;
        _mm256_store_si256( (__m256i*) val + 5 , val5 ) ;
        _mm256_store_si256( (__m256i*) val + 6 , val6 ) ;
        _mm256_store_si256( (__m256i*) val + 7 , val7 ) ;

}

int main(int argc, char *argv[] )
{
        __attribute__((aligned(32))) int val[64] ;

        for ( int i=0; i < 64; i++ ){
                std::cin >> val[i];
        }

        std::cout << "[Before]" << std::endl;
        for(int j=0;j<8;j++){
                std::cout << "{" ;
                for(int i=0;i<8;i++){
                        std::cout << val[8 * i + j] << " ";
                }
                std::cout << "}" << std::endl;
        }
        simd_sort(val);

        std::cout << "[After]" << std::endl;
        for(int j=0;j<8;j++){
                std::cout << "{" ;
                for(int i=0;i<8;i++){
                        std::cout << val[8 * i + j] << " ";
                }
                std::cout << "}" << std::endl;
        }
        return 0;
}
```

```plaintext
        SWAP4( val0, val1, val2, val3 );
  40166c:       c4 62 7d 39 c1          vpminsd %ymm1,%ymm0,%ymm8
  401671:       c4 e2 7d 3d c1          vpmaxsd %ymm1,%ymm0,%ymm0
  401676:       c4 e2 6d 39 cb          vpminsd %ymm3,%ymm2,%ymm1
  40167b:       c4 e2 6d 3d d3          vpmaxsd %ymm3,%ymm2,%ymm2
  401680:       c4 e2 3d 39 d9          vpminsd %ymm1,%ymm8,%ymm3
  401685:       c4 62 7d 3d ca          vpmaxsd %ymm2,%ymm0,%ymm9
  40168a:       c4 e2 3d 3d c9          vpmaxsd %ymm1,%ymm8,%ymm1
  40168f:       c4 e2 7d 39 c2          vpminsd %ymm2,%ymm0,%ymm0
  401694:       c4 e2 75 39 d0          vpminsd %ymm0,%ymm1,%ymm2
  401699:       c4 e2 75 3d c0          vpmaxsd %ymm0,%ymm1,%ymm0
        SWAP4( val4, val5, val6, val7 );
  40169e:       c4 e2 5d 39 cd          vpminsd %ymm5,%ymm4,%ymm1
  4016a3:       c4 e2 5d 3d e5          vpmaxsd %ymm5,%ymm4,%ymm4
  4016a8:       c4 e2 4d 39 ef          vpminsd %ymm7,%ymm6,%ymm5
  4016ad:       c4 e2 4d 3d f7          vpmaxsd %ymm7,%ymm6,%ymm6
  4016b2:       c4 e2 75 39 fd          vpminsd %ymm5,%ymm1,%ymm7
  4016b7:       c4 62 5d 3d c6          vpmaxsd %ymm6,%ymm4,%ymm8
  4016bc:       c4 e2 75 3d cd          vpmaxsd %ymm5,%ymm1,%ymm1
  4016c1:       c4 e2 5d 39 e6          vpminsd %ymm6,%ymm4,%ymm4
  4016c6:       c4 e2 75 39 ec          vpminsd %ymm4,%ymm1,%ymm5
  4016cb:       c4 e2 75 3d cc          vpmaxsd %ymm4,%ymm1,%ymm1
        SWAP4( val0, val1, val4, val5 );
  4016d0:       c4 e2 65 39 e2          vpminsd %ymm2,%ymm3,%ymm4
  4016d5:       c4 e2 65 3d d2          vpmaxsd %ymm2,%ymm3,%ymm2
  4016da:       c4 e2 45 39 dd          vpminsd %ymm5,%ymm7,%ymm3
  4016df:       c4 e2 45 3d ed          vpmaxsd %ymm5,%ymm7,%ymm5
  4016e4:       c4 e2 5d 39 f3          vpminsd %ymm3,%ymm4,%ymm6
  4016e9:       c4 e2 6d 3d fd          vpmaxsd %ymm5,%ymm2,%ymm7
  4016ee:       c4 e2 5d 3d db          vpmaxsd %ymm3,%ymm4,%ymm3
  4016f3:       c4 e2 6d 39 d5          vpminsd %ymm5,%ymm2,%ymm2
  4016f8:       c4 e2 65 39 e2          vpminsd %ymm2,%ymm3,%ymm4
  4016fd:       c4 e2 65 3d d2          vpmaxsd %ymm2,%ymm3,%ymm2
        SWAP4( val2, val3, val6, val7 );
  401702:       c4 c2 7d 39 d9          vpminsd %ymm9,%ymm0,%ymm3
  401707:       c4 c2 7d 3d c1          vpmaxsd %ymm9,%ymm0,%ymm0
  40170c:       c4 c2 75 39 e8          vpminsd %ymm8,%ymm1,%ymm5
  401711:       c4 c2 75 3d c8          vpmaxsd %ymm8,%ymm1,%ymm1
  401716:       c4 62 65 39 c5          vpminsd %ymm5,%ymm3,%ymm8
  40171b:       c4 62 7d 3d c9          vpmaxsd %ymm1,%ymm0,%ymm9
  401720:       c4 e2 65 3d dd          vpmaxsd %ymm5,%ymm3,%ymm3
  401725:       c4 e2 7d 39 c1          vpminsd %ymm1,%ymm0,%ymm0
  40172a:       c4 e2 65 39 c8          vpminsd %ymm0,%ymm3,%ymm1
  40172f:       c4 e2 65 3d c0          vpmaxsd %ymm0,%ymm3,%ymm0
        SWAP4( val2, val3, val4, val5 );
  401734:       c4 e2 3d 39 d9          vpminsd %ymm1,%ymm8,%ymm3
  401739:       c4 e2 3d 3d c9          vpmaxsd %ymm1,%ymm8,%ymm1
  40173e:       c4 e2 6d 39 ef          vpminsd %ymm7,%ymm2,%ymm5
  401743:       c4 e2 6d 3d d7          vpmaxsd %ymm7,%ymm2,%ymm2
  401748:       c4 e2 65 39 fd          vpminsd %ymm5,%ymm3,%ymm7
  40174d:       c4 62 75 3d c2          vpmaxsd %ymm2,%ymm1,%ymm8
  401752:       c4 e2 65 3d dd          vpmaxsd %ymm5,%ymm3,%ymm3
  401757:       c4 e2 75 39 ca          vpminsd %ymm2,%ymm1,%ymm1
  40175c:       c4 e2 65 39 d1          vpminsd %ymm1,%ymm3,%ymm2
  401761:       c4 e2 65 3d c9          vpmaxsd %ymm1,%ymm3,%ymm1
```