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

junkawa@Chromebookで始める開発日記

2018年5月28日 03:16

こんにちは、junkawaです。

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

これまでの記事

https://note.mu/junkawashima/m/m3adbdc56f010

前回までのおさらい

ブロックソートでは巡回行列のソートが必要です。

Step1、Step2では、先頭シンボルがssから始まる行についてソートが完了しました。

Step3では、次回以降のループでStep1のソート時の比較処理を高速にするための準備を行います。

ソースコード紹介

mainSort()@blocksort.c
https://github.com/junkawa/bzip2/blob/master/bzip2-1.0.6/blocksort.c#L485
https://github.com/junkawa/bzip2/blob/master/bzip2-1.0.6/blocksort.c#L948
〜
https://github.com/junkawa/bzip2/blob/master/bzip2-1.0.6/blocksort.c#L1011

  948:       /*--
  949:          Step 3:
  950:          The [ss] big bucket is now done.  Record this fact,
  951:          and update the quadrant descriptors.  Remember to
  952:          update quadrants in the overshoot area too, if
  953:          necessary.  The "if (i < 255)" test merely skips
  954:          this updating for the last bucket processed, since
  955:          updating for the last bucket is pointless.
  956:

ssから始まる行([ss] big bucket])のソートがStep1、Step2で完了しました。

bigDone[ss] にソート完了を記録します。

また、quadrantを更新します。block[nblock]〜block[nblock+BZ_N_OVERSHOOT-1](OVERSHOOT領域)の比較時に使用するquadrantも忘れずに更新します。

Step3は、次回以降のループのStep1のクイックソートを高速化するための処理です。
したがって、i = 255の時はループの最後なのでStep3の処理は不要となります。

  957:          The quadrant array provides a way to incrementally
  958:          cache sort orderings, as they appear, so as to 
  959:          make subsequent comparisons in fullGtU() complete
  960:          faster.  For repetitive blocks this makes a big
  961:          difference (but not big enough to be able to avoid
  962:          the fallback sorting mechanism, exponential radix sort).
  963:

quadrantは、巡回行列のソート結果の順番をキャッシュします。
quadrantを使うことで、mainGtU()(旧名 fullGtU())で後続する比較をより高速に完了できます。

同じシンボルやパターンを繰り返す入力データブロックの場合、quadrantを使うことで大きな違い(より高速になる)をもたらします。

ただし、同じシンボルやパターンを繰り返す入力では、fallbackSort()の指数基数ソートの方がquadrantを使うよりも有効です。

  964:          The precise meaning is: at all times:
  965: 
  966:             for 0 <= i < nblock and 0 <= j <= nblock
  967: 
  968:             if block[i] != block[j], 
  969: 
  970:                then the relative values of quadrant[i] and 
  971:                     quadrant[j] are meaningless.
  972:

block[i]とblock[j]が異なるシンボルの場合、quadrantは使用できません。
quadrantは先頭シンボルが同じ行同士の比較にだけ使えます。

quadrantにセットする998行目の qValは、ssから始まる行の中でのソート結果の順番なのでptr上のbbStartからの差分(相対的な値)であり、絶対的な値(ptr上のインデックス)ではありません。

  973:                else {

以降の処理は、block[i] と block[j]が同じ場合です。

この場合、quadrantを使用して比較ができます。

  974:                   if quadrant[i] < quadrant[j]
  975:                      then the string starting at i lexicographically
  976:                      precedes the string starting at j
  977:

quadrant[i] < quadrant[j] の時、行番号iの行は、行番号jの行より辞書順で先になります。

  978:                   else if quadrant[i] > quadrant[j]
  979:                      then the string starting at j lexicographically
  980:                      precedes the string starting at i
  981:

quadrant[i] > quadrant[j] の時、行番号jの行は、行番号iの行より辞書順で先になります。

  982:                   else
  983:                      the relative ordering of the strings starting
  984:                      at i and j has not yet been determined.

quadrant[i] == quadrant[j] の時、行番号jの行と行番号iの行の順序は決定できません。

これが起こるのは、bbSizeが65535以上の場合などです。詳しくは後述します。

  985:                }
  986:       --*/
  987:       bigDone[ss] = True;
  988:

Step1、Step2で、ssから始まる行のソートが完了したので、bigDone[ss] = True として記録しています。bigDoneはStep2で使用されます。

  989:       if (i < 255) {

i=255の時にStep3を行わないようにしています。

  990:          Int32 bbStart  = ftab[ss << 8] & CLEARMASK;
  991:          Int32 bbSize   = (ftab[(ss+1) << 8] & CLEARMASK) - bbStart;

bbStartは、ssから始まる行のptr上での先頭インデックス。
bbSizeは、ssから始まる行の数。

  992:          Int32 shifts   = 0;
  993: 
  994:          while ((bbSize >> shifts) > 65534) shifts++;
  995:

bbSizeを65535未満にビットシフトするためのshiftsの算出。
998行目で、65535(16bit)に収めるためにshiftsを使用します。

bbSize=65535の時は、shifts=1になります。

  996:          for (j = bbSize-1; j >= 0; j--) {
  997:             Int32 a2update     = ptr[bbStart + j];
  998:             UInt16 qVal        = (UInt16)(j >> shifts);
  999:             quadrant[a2update] = qVal;

a2Updateは、ssから始まる行の行番号(ブロック番号)です。

図はss=3、bbStart=510、bbSize=180の場合です。

bbSizeが65535未満なので、994行目のshiftsは0のままです。

996行目のfor文では、j = bbSize-1 なので、jの初期値は179となります。
jは、3から始まる行のソート結果の順番になります。

例)
j = 0 の時、ptr [ bbStart + 0] は、3から始まる行で一番小さい行の行番号です。
j = bbSize -1 の時、ptr [ bbStart + bbSize-1] は、3から始まる行で一番大きい行の行番号です

997行目のa2update = ptr[bbStart+j]には、3から始まる行の行番号がソート結果の大きい順(ptr上で後ろから前に)に入ります。

998行目のqVal = (j>>shifts)は、j が16bitに収まらない値の場合、16bitに収めるための処理です。quadrantがUInt16の配列のためです。ここでUInt32の配列にしなかったのはメモリ使用量の削減のためでしょうか。
UInt32にする場合のメモリ使用量の増加は約900kB*2で、約1.8MB。2018年現在では特に問題ないサイズだと思いますが何か理由があるのでしょうか。

999行目では、quadrant[ a2update] = qvalとしています。
quadrant配列のインデックスは行番号(ブロック番号)a2updateで、入る値は行番号a2updateの行が、3から始まる行の中でソート結果が何番目かという値です。

quadrantの使われ方

quadrantはmainGtU()で使用されます。
https://github.com/junkawa/bzip2/blob/master/bzip2-1.0.6/blocksort.c#L347

  412:       c1 = block[i1]; c2 = block[i2];
  413:       if (c1 != c2) return (c1 > c2);
  414:       s1 = quadrant[i1]; s2 = quadrant[i2];
  415:       if (s1 != s2) return (s1 > s2);

mainGtU()はStep1のクイックソートから呼び出される関数で、2つの行の大小比較を行う関数です。

2つの行の各文字block[i1]とblock[i2]の比較結果が同じだった場合に、quadrant[i1]、quadrant[i2]を比較します。

block[i1](=block[i2])から始まる行がソート済みだった場合、行番号i1と行番号i2の大小関係はptr上ですでに決まっています。

quadrant[i1]、quadrant[i2]には、ptr上でのソート結果が何番目か、つまり大小関係がセットされています。

quadrantを使って行番号i1と行番号i2を比較することで、block[i1]、block[i2]以降の文字を比較することなく、比較結果をここで得ることができます。

block[i1](=block[i2])から始まる行が未ソートの場合、quadrant[i1]、quadrant[i2]はどちらも0なので、i1++、i2++して、次の文字を比較します。

備考1

quadrantの比較は、同じシンボルssから始まる行同士でのみ行なえます。

414、415行目でquadrantを使うのは、c1==c2時で、同じシンボルから始まる行同士の比較になっているので、問題ないです。

備考2

quadrantが決まれば、かなり高速に比較ができます。なので、Step 1ではrunningOrder()を使って頻度の低いssから始まる行を先にソートすることで、なるべく速くquadrantが埋まるようにし、後のソートを高速化する戦略を取っていると思われます。

bbSizeが65535以上の場合

図はss=3、bbStart=510、bbSize=70000の場合です。
bbSizeが70000なので、994行目の whileループにより、shiftsは1となります。

図のように、j が 70519 と 70518 の時、どちらも qVal は 35259 となります。

mainGtU()で、quadrantを比較した際に同じ値だった場合は、次の文字を比較することになります。quadrantはあくまで高速化のための比較なので、quadrantが同じ場合でも、1文字ずつblock[i1]とblock[i2]を比較していけば、正しい比較結果が得られます。

 1000:             if (a2update < BZ_N_OVERSHOOT)
 1001:                quadrant[a2update + nblock] = qVal;
 1002:          }

ブロック番号a2updateがBZ_N_OVERSHOOT未満の場合に、quadrantのOVERSHOOT領域にもソート結果の順番(qVal)をセットしています。

上記の図において、ptr[679] が 10 の時、quadrant[10]とquadrant[nblock+10] の両方に 679 をセットしている箇所の処理です。

これはmainGtU()にて、block[0]からblock[BZ_N_OVERSHOOT-1]を比較する代わりに、block[nblock]からblock[nblock+BZ_N_OVERSHOOT-1]までを比較することがあるため、その場合に対応する quadrant の値のセットです。

BZ_N_OVERSHOOT は 34 @ bzlib_private.h #L189 です。
https://github.com/junkawa/bzip2/blob/master/bzip2-1.0.6/bzlib_private.h#L189

 1003:          AssertH ( ((bbSize-1) >> shifts) <= 65535, 1002 );
 1004:       }
 1005:

(bbSize-1)>>shifts が 16bitの範囲を超えた時(65535より大きい時)にアサートします。

 1006:    }
 1007:

868行目のfor文の終端です。
次回のループでは、今回のssの次に出現頻度の低い ss (runningOrder順) で、Step1、Step2、Step3 を行います。

 1008:    if (verb >= 4)
 1009:       VPrintf3 ( "        %d pointers, %d sorted, %d scanned\n",
 1010:                  nblock, numQSorted, nblock - numQSorted );

blockは入力データブロック数、numQSortedはStep1でソートされた行数、nblock-numQSortedはStep2でソートされた行数となります。

 1011: }

mainSort() の終端です。

まとめ

これでmainSort()のブロックソート全ての処理を紹介できました。

次回は、mainSort()の呼び出し元の処理を紹介します。

呼び出し元では、mainSort()実行前の準備や、mainSort()実行後に逆ブロックソート変換に必要な情報を算出する処理を紹介します。

その後の記事で、入力ブロックデータ数が10,000バイト未満の場合や、同じシンボル、パターンが続いた場合のブロックソート実装であるfallbackSort()について紹介します。

ご覧下さりありがとうございます。いただいたサポートは図書館への交通費などに使わせていただきます。

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

これまでの記事

前回までのおさらい

ソースコード紹介

まとめ

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