Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
OrganizationAdvent CalendarQiitadon (β)
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

simd sortで、bubble sort と quadsort で比較してみると?

More than 1 year has passed since last update.

bubble sortと比較してみる。

基本的に今回比較したいのは「条件分岐を使わずに、simd でソートできること」なので、quick sortとかのアルゴリズムは適応対象外にしかならない(仕方がない)。


56 instructionが必要になる。





だから、28回✕3 = 84 instruction ……


        #define SWAP2(valA,valB) \
        { \
                tmp0 = valA \
                valA = _mm256_min_epi32 ( valA, valB ); \
                valB = _mm256_max_epi32 ( tmp0, valB ); \

SWAP2(val0,val1); // step.1-1
SWAP2(val1,val2); // step.1-2
SWAP2(val2,val3); // step.1-3
SWAP2(val3,val4); // step.1-4
SWAP2(val4,val5); // step.1-5
SWAP2(val5,val6); // step.1-6
SWAP2(val6,val7); // step.1-7 val7 is fixed.

SWAP2(val0,val1); // step.2-1
SWAP2(val1,val2); // step.2-2
SWAP2(val2,val3); // step.2-3
SWAP2(val3,val4); // step.2-4
SWAP2(val4,val5); // step.2-5
SWAP2(val5,val6); // step.2-6 val6 is fixed.

SWAP2(val0,val1); // step.3-1
SWAP2(val1,val2); // step.3-2
SWAP2(val2,val3); // step.3-3
SWAP2(val3,val4); // step.3-4
SWAP2(val4,val5); // step.3-5 val5 is fixed.

SWAP2(val0,val1); // step.4-1
SWAP2(val1,val2); // step.4-2
SWAP2(val2,val3); // step.4-3
SWAP2(val3,val4); // step.4-4 val4 is fixed.

SWAP2(val0,val1); // step.5-1
SWAP2(val1,val2); // step.5-2
SWAP2(val2,val3); // step.5-3 val3 is fixed.

SWAP2(val0,val1); // step.6-1
SWAP2(val1,val2); // step.6-2 val2 is fixed.

SWAP2(val0,val1); // step.7-1 val0 and val1 are fixed.

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away