N要素の分岐しない odd-even mergesort (GCC+Linux/x86_64用) - memologue
(こちらの記事の続き) (ジェネレータを生成) % g++ -O2 -Wall gen_sort.cpp -o gen_sort (8要素向けのソート関数を作成) % ./gen_sort 0 8 > oem_sort_8.s % gcc -c oem_sort8.s (ちゃんと作られたようだ) % nm oem_sort_8.o 0000000000000000 T odd_even_sort8 (テストコード書き) % cat > test.c #include <assert.h> void odd_even_sort8(unsigned int* d); int main() { int i; unsigned int s[] = {7,6,5,4,1,2,3,4}; odd_even_sort8(s); for(i = 0; i < 7; ++i) { assert(s[i] <
4要素の分岐しないソート (GCC用) - memologue
(こちらの記事の続き、おまけです) 「分岐しないソート」の、VC++向けのコードをGCC+Linux向けに修正してみました。 実はC言語によるソートである sort4l() のほうも相当速いので、私の手元の環境だと同じくらいの速度しか出なかった*1んですが、面白いのでオッケー。例えば {1,2,3,4} から生成される順列(24通り)を何百万回か食わすような処理を書いてみると Celeron 2.4GHz & Linux だとアセンブラ版が10%遅く、Athron64 3200+ & Linux/x86_64, gcc -m32 だとアセンブラ版が10%速く、ARM9 200MHz & Linux だと同じ速度でした。 まずx86向けから。 // for GCC + Linux/x86 void sort4(unsigned int *d) { __asm__ ( "mov (%0), %
分岐しないソート (のジェネレータ） - memologue
分岐しない4要素のソート、GCC/Linux/x86,x86_64,arm版 こちらに、「分岐しないソート」という記事があります。短いので読んでいただくほうがよいと思いますが、文章＆アセンブリ言語のコードの内容を要約すると、 4要素のソートは、頑張れば5回の比較と5回の交換でできるよ。さらに、交換を Pentium Pro で追加された命令であるCMOVcc(Conditional Move)で行うことにすれば、「cmp b, a して、 b < a のときだけ b と a をswap」という処理を分岐命令なしで行うことができるから速いよ。 となります。この、「4要素専用・VC++専用の分岐しないソート」を、いつものように(?) GCC向けに書き直してみました。こちら。 分岐しないN要素の odd-even mergesort、GCC/Linux/x86_64版 (x86_64のお勉強がて
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://labs.cybozu.co.jp/blog/kazuho/archives/2008/02/range_coder_sse.php
emit.jp
