bzip2を読む ブロックソート4

こんにちは、junkawaです。

本記事では、前回に続きブロックソートアルゴリズムの「巡回行列のソート」についてソースコードを交えて紹介します。

前回の記事

bzip2を読む はじめに

bzip2を読む ブロックソート1

bzip2を読む ブロックソート2

bzip2を読む ブロックソート3

前回までのおさらい

ブロックソートアルゴリズムは

　1. 入力データを1字ずつずらして巡回行列を作る
　2. 巡回行列の行をソートする
　3. ソート後の行列の最後の列を出力とする

2. 巡回行列のソートでは、下記の1. 2. を行います。

　1. 先頭の2バイトでソート
　2. 先頭バイトのシンボルの出現頻度が少ない順に下記を行う
　　(3バイト目以降のソート)
　　Step1) 先頭2バイトが異なる値、の行をソート
　　Step2) 先頭2バイトが同じ値、の行をソート
　　Step3) ソート高速化のための情報を更新

本記事では、「先頭2バイトが異なる値、の行をソート」について紹介します。

先頭バイトのシンボルの出現頻度が少ない順(runningOrder[0..255])に、ソート対象としていきます。

ソースコード紹介

mainSort()@blocksort.c L826 〜 L909

  862:    /*--
  863:       The main sorting loop.
  864:    --*/
  865: 

ここからが、巡回行列のソートのメイン処理です。
これまでの、先頭2バイトのループは、ソートの前段階に過ぎない、ということでしょう。

  866:    numQSorted = 0;
  867: 

ソートが完了した行の数。
ここまでで、二文字目までのソートは済んでいるので、三文字目以降のソートが完了した行数が保存されます。

  868:    for (i = 0; i <= 255; i++) {
  869: 

先頭バイトの値の出現頻度が小さい順(runningOrder[0]〜[255])に、ソートを実行します。

  870:       /*--
  871:          Process big buckets, starting with the least full.
  872:          Basically this is a 3-step process in which we call
  873:          mainQSort3 to sort the small buckets [ss, j], but
  874:          also make a big effort to avoid the calls if we can.
  875:       --*/

頻度が一番小さなシンボルから始まる大きなバケット、つまり先頭バイトが同じ行を処理します。

基本的にはこれは3段階のプロセスです。
Step1) 先頭2バイトが異なる値、の行をソート
Step2) 先頭2バイトが同じ値、の行をソート
Step3) ソート高速化のための情報を更新

Step1では、mainQSort3を呼び出して小さなバケット[ss、j]、つまり先頭バイトがssで2バイト目がjである行のソートを行います。

また、できればソート呼び出し(mainQSort3())を避けるために大きな努力をします。

  876:       ss = runningOrder[i];
  877: 

先頭バイトが ss となる行について、三文字目以降をソートする。

  878:       /*--
  879:          Step 1:
  880:          Complete the big bucket [ss] by quicksorting
  881:          any unsorted small buckets [ss, j], for j != ss.  
  882:          Hopefully previous pointer-scanning phases have already
  883:          completed many of the small buckets [ss, j], so
  884:          we don't have to sort them at all.
  885:       --*/

Step 1:
先頭バイトがss、2バイト目がjで、先頭バイトと2バイト目が異なる (j != ss) 行(small buckets)をクイックソートして、先頭バイトがssとなる行(big bucket)のソートを完了します。

うまくいけば、forループのStep 2ポインタスキャンフェーズにより、多くのsmall bucketsがソート完了済みとなります。
ソート完了済みは、ftabにつけるSETMASKフラグで判断します。

  747: #define SETMASK (1 << 21)
  748: #define CLEARMASK (~(SETMASK))

ソート後のftabは、ftab[65535]が一番大きな値を持ち、その値はnblock以下となります(ptrのインデックス値となるため)。
bzip2-1.0.6では、nblockの最大値は900,000なので、20bitで表現できます。そうすると、SETMACKは 1<<20 でもよいと思いますが、余裕を見て21ビットシフトしているのでしょうか。

  886:       for (j = 0; j <= 255; j++) {

j は2バイト目のシンボルです。シンボル(0〜ss-1、ss+1〜255)に対してソートします。

  887:          if (j != ss) {

Step 1では、先頭バイトssと2バイト目j が異なる行についてソートします。
(ssとjが同じとなる行についてはStep 2でソートします)

  888:             sb = (ss << 8) + j;

sb は、先頭2バイトの値です。

  889:             if ( ! (ftab[sb] & SETMASK) ) {

先頭2バイトがsb となる行がすでにソート済みか確認し、ソート済みでない場合、ソートを行います。

  890:                Int32 lo = ftab[sb]   & CLEARMASK;

先頭2バイトがsbである行の ptr 配列での先頭インデックスを lo にセットします。
CLEARMASKしているのは、ソート完了済みフラグを消して、ftab本来の値を取得するためです。

厳密には、このifブロック内では ftab[sb]にはSETMASKフラグは立っていないのでクリアする必要はないと思います。

  891:                Int32 hi = (ftab[sb+1] & CLEARMASK) - 1;

先頭2バイトがsbである行の ptr 配列での最後のインデックスを hi にセットします。
ftab[sb+1]は、先頭2バイトがsb+1である行の ptr 配列での先頭インデックスなので、それから1を引いた場所は、sbである行の最後のインデックスとなります。
(計数ソートによって先頭2バイトですでにソート済みなので、こうなります)

  892:                if (hi > lo) {

hi > lo とならないのは、下記の場合です

・先頭2バイトがsbとなる行が存在しない場合
　この時、ftab[sb+1] = ftab[sb] のため、hi = lo -1 となり、hi < lo となります

・先頭2バイトがsbとなる行が1つだけの場合
　この時、ftab[sb+1] = ftab[sb] + 1のため、hi = lo となります。

どちらの場合も、ソートする必要はありません。

  893:                   if (verb >= 4)
  894:                      VPrintf4 ( "        qsort [0x%x, 0x%x]   "
  895:                                 "done %d   this %d\n",
  896:                                 ss, j, numQSorted, hi - lo + 1 );

" qsort [0x2, 0x1] done 125 this 10"

と表示された場合、先頭バイトが2、2バイト目が1、ソート済みの行数は125、今回ソートする行数は10 を表します。

  897:                   mainQSort3 ( 
  898:                      ptr, block, quadrant, nblock, 
  899:                      lo, hi, BZ_N_RADIX, budget 
  900:                   );   

メイン処理である、クイックソートを実行します。

詳細は別記事で紹介します。

  901:                   numQSorted += (hi - lo + 1);

ソート済みの行数を更新します。

  902:                   if (*budget < 0) return;

budgetは、ソート中に比較する2つの行の内容が同じ場合(入力データが同じ値や、同じパターンが繰り返される場合など)に、減算されるカウンタです。
初期値は BZ2_blockSort()でセットされ、mainGtU()で減算されます。

同じデータが繰り返される場合、高速化のためにmainSort()ではなくfallbackSort()を使用します。
したがって、budgetが0より小さくなった場合にはmainSort()でのソートをやめ、BZ2_blockSort()まで戻り、fallbackSort()を実行します。1079

  903:                }
  904:             }
  905:             ftab[sb] |= SETMASK;

先頭2バイトがソート完了したことを示すSETMASKフラグを、ftab[sb]にセットします。
hi <= lo となり、ソート不要だった場合も、同様にフラグをセットします。

  906:          }
  907:       }
  908: 

j != ss となる行について、ソートが完了しました。

  909:       AssertH ( !bigDone[ss], 1006 );

bigDone[ss]がTrueの時、アサートを出します。
bigDone[ss]は、Step1、Step2が完了した時に987でTrueにセットされます。
ここでTrueになっているのは問題なので、アサートを実行します。

まとめ

先頭2バイトが異なる値、の行をソート、について概要を紹介しました。次回からは、クイックソートを紹介します。