grafi.jp

学科の課題で書いた。空間消費量が一定というと厳密には嘘で実際は要素数にたいする対数なんだけど、要素数は所詮64bitを超え得ないのだから静的に確保してしまえる。 http://en.wikipedia.org/wiki/Quicksort は割りと参考になった。glibcの実装も参考になった。

分岐命令を極力減らしつつ、それなりにシンプルに書くようにした。ピボットは単に先頭の要素を取っているし、ある程度の深さで別のアルゴリズムに切り替えたりはしていないので、与えられるデータによっては容易に計算量が死ぬ。ランダムデータを相手にするのが一番好条件なんだけど、128MBのランダムデータを昇順にソートするのにqsort()より1.15倍くらい時間がかかった。比較回数は1.35倍くらいだったので、比較回数以外の部分では速く動作しているぽい。

以下コード。あんまり真面目にテストされてないのでおかしな挙動する可能性アリ。コードのライセンスは他と同じく CC0

.global asqsort
.align 4
.lcomm stack, 1024, 8

asqsort:
        ## レジスタ割付 ##
        # R3: 比較呼び出しの引数、比較呼び出しの返り値、分割された左側の長さ
        # R4: 比較呼び出しの引数、分割された右側の長さ
        # R5: 現在見ている左側の要素の内容の一部
        # R6: 現在見ている右側の要素の内容の一部、計算の一時領域
        # R7: スワップのバイト位置
        # R8: 左右のどちらをローカルスタックに入れるか

        # R14: 現在見ている左側の要素のアドレス
        # R15: 現在見ている右側の要素のアドレス(ループ開始時は末尾要素の一つ後ろにセットしている)
        # R16: 左側から進んでいれば0、右側から進んでいれば-1

        # R17: ソート中の配列断片の先頭要素のアドレス
        # R18: ソート中の配列断片のバイト単位の長さ
        # R19: ローカルなスタックの頭のアドレス

        # R20: コンディションレジスタのセーブ場所
        # R21: スタックの底のアドレス
        # R22: 比較関数のエントリポイント
        # R23: 配列一要素のバイト数
        # R24: (R23)/8-1、要素のスワップの際に何回doubleword単位の移動が必要かの判定に使用

        ## 長さが1以下なら去る ##
        cmpdi 4, 1
        blelr-

        ## スタックフレーム生成 ##
        # リンクレジスタ保存
        mflr 0
        std 0, 16(1)
        # 退避すべき汎用レジスタは17個
        # 112+12*8byte16byteにalignしてフレーム生成しつつ上へのポインタを張る
        stdu 1, -208(1)
        # 不揮発性レジスタ退避
        ## stmwは使えないのね…
        std 14, 112(1)
        std 15, 120(1)
        std 16, 128(1)
        std 17, 136(1)
        std 18, 144(1)
        std 19, 152(1)
        std 20, 160(1)
        std 21, 168(1)
        std 22, 176(1)
        std 23, 184(1)
        std 24, 192(1)
        # コンディションレジスタ保存
        mfcr 20

        ## スタックを片持ちしたループに入って実際の処理 ##
        # 初期化
        mr 17, 3
        ld 22, 0(6)
        mulld 18, 4, 5
        mr 23, 5

        ## スワップ条件など
        ### 一要素あたりの大きさの下4bitをcr2に入れて、何byte単位でのスワップを行うか決める
        rotldi 6, 23, 20
        mtcrf 0b00100000, 6
        srdi 24, 23, 3

        ## スタック読み込み
        lis 21, stack@highest
        ori 21, 21, stack@higher
        sldi 21, 21, 32
        oris 21, 21, stack@h
        ori 21, 21, stack@l
        ### 番兵追加
        addi 19, 21, 16

        # ループ実行
        qsortloop:
                # 左右の見ている位置などループ方向を初期化
                add 14, 17, 23
                add 15, 17, 18
                li 16, 0

                ## 比較、およびフラグ更新 ##
                splitloop:
                        # ピボットよりも小さいなら0、小さくないなら-1を比較結果にする
                        # ピボットよりも小さくて、かつ右側を見ているならスワップ
                        # ピボットより小さいなら左側を、小さくないなら右側を見るように変更

                        # 比較関数への引数の設定、ピボットを右にする
                        xor 3, 14, 15
                        and 3, 3, 16
                        xor 3, 3, 14
                        mr 4, 17
                        # 比較関数呼び出し
                        mtctr 22
                        bctrl
                        # 比較結果について、非負を-1に、負を0に変換する
                        srdi 3, 3, 63
                        subi 3, 3, 1
                        # スワップのフラグ設定
                        cmpd cr1, 3, 16
                        # 見ている方向の更新
                        mr 16, 3

                        ble cr1, swapbend
                                ## スワップ ##
                                # まず8byteずつスワップして、次いで4byte2byte1byteとスワップする
                                # 分岐パターンはqsortが呼ばれた時の引数(size)のみに依存するため、
                                # ほぼ分岐予測が成功する?

                                # 現在見ているバイト位置を初期化
                                li 7, 0

                                # 8byteずつスワップ
                                bnl cr2, swapdwend
                                mtctr 24
                                swapdw:
                                        # レジスタにロード
                                        ldx 5, 14, 7
                                        ldx 6, 15, 7
                                        # メモリにストア
                                        stdx 6, 14, 7
                                        stdx 5, 15, 7
                                        # 後ろのバイトに動く
                                        addi 7, 7, 8
                                        # ループ
                                        bdnz swapdw
                                swapdwend:

                                # 4byteスワップ
                                bng cr2, swapwend
                                        # レジスタにロード
                                        lwzx 5, 14, 7
                                        lwzx 6, 15, 7
                                        # メモリにストア
                                        stwx 6, 14, 7
                                        stwx 5, 15, 7
                                        # 後ろのバイトに動く
                                        addi 7, 7, 4
                                swapwend:

                                # 2byteスワップ
                                bne cr2, swaphwend
                                        # レジスタにロード
                                        lhzx 5, 14, 7
                                        lhzx 6, 15, 7
                                        # メモリにストア
                                        sthx 6, 14, 7
                                        sthx 5, 15, 7
                                        # 後ろのバイトに動く
                                        addi 7, 7, 2
                                swaphwend:

                                # 1byteスワップ
                                bns cr2, swapbend
                                        # レジスタにロード
                                        lbzx 5, 14, 7
                                        lbzx 6, 15, 7
                                        # メモリにストア
                                        stbx 6, 14, 7
                                        stbx 5, 15, 7
                                swapbend:

                        # 見ている方向の一つ次の要素に移る
                        and 6, 23, 16
                        sub 14, 14, 6
                        add 14, 14, 23
                        sub 15, 15, 6

                        # ぶつからなければループ
                        cmpd 14, 15
                        blt+ splitloop
                splitloopend:

                # ぶつかったので分割が終わったよ!
                # 右側から左向きに動きながらぶつかった際は、そこにある要素はスワップする相手がいなかったので放置されていた要素なので、
                # 分割の際は右側の要素として扱われるため、必ず左側の見ている位置が一つ先走ることでぶつかることになる

                ## 再帰風呼び出しの制御 ##
                # 配列の長さは3以上のはず

                # 左右のバイト単位での長さを算出
                sub 3, 14, 17
                add 4, 17, 18
                sub 4, 4, 15

                # 左の方が長いなら0、そうでないなら-1
                # 左をピボットの1要素分減らしてから処理するので、「>」で比べることが重要
                sub 8, 4, 3
                srdi 8, 8, 63
                subi 8, 8, 1

                # 左が1要素なら、左にあるのはピボットのみ
                # 右が1要素より大きい長さなら、右側に飛ぶ
                # 右も1要素以下なら、左右ともソート済みなのでスタックをpopして飛ぶ
                cmpd cr0, 3, 23
                cmpd cr1, 4, 23
                crandc 2, 5, 1
                beq qsortsinglesorted
                crnor 0, 5, 1
                blt qsortpopstack

                # 左がピボットのみでないなら、ピボットをスワップして左右の境界に持っていく
                sub 14, 14, 23
                li 7, 0

                bnl cr2, pvswapdwend
                mtctr 24
                pvswapdw:
                        ldx 5, 14, 7
                        ldx 6, 17, 7
                        stdx 6, 14, 7
                        stdx 5, 17, 7
                        addi 7, 7, 8
                        bdnz pvswapdw
                pvswapdwend:

                bng cr2, pvswapwend
                        lwzx 5, 14, 7
                        lwzx 6, 17, 7
                        stwx 6, 14, 7
                        stwx 5, 17, 7
                        addi 7, 7, 4
                pvswapwend:

                bne cr2, pvswaphwend
                        lhzx 5, 14, 7
                        lhzx 6, 17, 7
                        sthx 6, 14, 7
                        sthx 5, 17, 7
                        addi 7, 7, 2
                pvswaphwend:

                bns cr2, pvswapbend
                        lbzx 5, 14, 7
                        lbzx 6, 17, 7
                        stbx 6, 14, 7
                        stbx 5, 17, 7
                pvswapbend:

                sub 3, 3, 23

                # 左右とも1要素より大きい長さなら、短い方をスタックにpushしておいて長い方に飛ぶ
                # 左右とも1要素以下なら、ソート済みなのでスタックをpopしてきて飛ぶ
                # それ以外なら、片方だけソート済みなので、もう片方に飛ぶ
                cmpd cr0, 3, 23
                crand 2, 1, 5
                beq qsortpushstack
                crnor 0, 1, 5
                blt qsortpopstack

                qsortsinglesorted:
                        # 右が1要素以下ならR17を維持、左が1要素以下ならR17をR15で更新
                        xor 15, 15, 17
                        and 15, 15, 8
                        xor 17, 17, 15
                        # 右が1要素以下ならR18をR3で更新、左が1要素以下ならR18をR4で更新
                        xor 18, 3, 4
                        and 18, 18, 8
                        xor 18, 18, 3
                        # ループ
                        b qsortloop

                qsortpushstack:
                        # 右が短ければR17とR15をスワップ
                        xor 17, 17, 15
                        andc 6, 17, 8
                        xor 15, 15, 6
                        xor 17, 17, 15
                        # 右が短ければR3とR4をスワップ
                        # その後R3をR18にコピー(実際にはスワップ後のR3は使わないため端折った動作)
                        xor 3, 3, 4
                        andc 6, 3, 8
                        xor 4, 4, 6
                        xor 18, 3, 4

                        # 長い方をスタックに入れる
                        std 15, 0(19)
                        addi 19, 19, 8
                        std 4, 0(19)
                        addi 19, 19, 8
                        # 短い方を呼び出し
                        ## R17、R18はスワップでセットされている
                        b qsortloop

                qsortpopstack:
                        # スタックからポップ
                        ldu 18, -8(19)
                        ldu 17, -8(19)
                        # スタックを突き抜けてないならループ
                        cmpd 21, 19
                        bne+ qsortloop

        qsortend:
        # ローカルスタックを突き抜けたのでソートが終わったよ!
        ## スタックフレーム破棄 ##
        # コンディションレジスタ復元
        mtcr 20
        # 不揮発性レジスタ復元
        ld 14, 112(1)
        ld 15, 120(1)
        ld 16, 128(1)
        ld 17, 136(1)
        ld 18, 144(1)
        ld 19, 152(1)
        ld 20, 160(1)
        ld 21, 168(1)
        ld 22, 176(1)
        ld 23, 184(1)
        ld 24, 192(1)
        # 親のスタックフレームを辿る
        ld 1, 0(1)
        # リンクレジスタ復元
        ld 0, 16(1)
        mtlr 0
        # 去る
        blr
blog comments powered by Disqus