crit-bit 木 (その3)

crit-bit木Ruby で試したものですが、 本番の C 言語の落ち穂拾いをしてみます。

D. J. Bernsteinqhasm の C 言語で記述したソースコードの中に含まれている crit-bit 木 の挿入手続きは次のような goto を使った箇所があります。 ここでは、 挿入したいキーと木の中から見つけた critical bits が一致する文字列で、 共通する接頭ビット列の長さを求めています。 newbyte へ一致するバイト数、 newotherbits へ最初の一致しないビットをゼロにしたビット反転マスク・パターンを求めます。

なお、 両方の文字列が一致するときを特別扱いして、 値 1 で手続きから戻ります。

  uint32 newbyte;
  uint32 newotherbits;
  for (newbyte = 0; newbyte < ulen; ++newbyte) {
    if (p[newbyte] != ubytes[newbyte]) {
      newotherbits = p[newbyte] ^ ubytes[newbyte];
      goto different_byte_found;
    }
  }
  if (p[newbyte] != 0) {
    newotherbits = p[newbyte];
    goto different_byte_found;
  }
  return 1; different_byte_found:
  newotherbits |= newotherbits >> 1;
  newotherbits |= newotherbits >> 2;
  newotherbits |= newotherbits >> 4;
  newotherbits = (newotherbits & ~(newotherbits >> 1)) ^ 255;

ここで、 p は木から探した文字列の先頭バイトへのポインタで、 ubytes はキー文字列の先頭バイトへのポインタです。 両方の文字列ともに、 ゼロ終端であることを前提にしています。 ulen は ubytes が先頭を指している文字列のバイト長です。

これを goto を使わずに、 簡潔な記述に書き直してみます。 まず、 for ループを繰り返す条件は、 p と ubytes の両方の newbyte 位置のバイトが一致するときです。 ただし、 両方共ヌル文字で一致するときは、 両方の文字列が終端まで同一であることを意味しており、 手続きから戻らねばなりません。 そのとき、 newbyte は ulen になっています。

  for (newbyte = 0; p[newbyte] == ubytes[newbyte]; ++newbyte)
    if (newbyte == ulen)
      return 1;
  newotherbits = p[newbyte] ^ ubytes[newbyte]);
  newotherbits |= newotherbits >> 1;
  newotherbits |= newotherbits >> 2;
  newotherbits |= newotherbits >> 4;
  newotherbits = (newotherbits & ~(newotherbits >> 1)) ^ 255;

コンパイラの最適化が賢いなら、 バイトの一致判定が排他的論理和結果のゼロ判定と等価であることを利用して、 4 行目を 1 行目に取り込んでくれるかもしれません。 中間変数が減り、 レジスタ割当が有利になるので、 そうなって欲しいところです。 ですが、 ここでは賢くないコンパイラのために、 可読性を落として、 手作業で最適化向けの記述にしておきます。

  for (newbyte = 0; (newotherbits = p[newbyte] ^ ubytes[newbyte]) == 0; ++newbyte)
    if (newbyte == ulen)
      return 1;
  newotherbits |= newotherbits >> 1;
  newotherbits |= newotherbits >> 2;
  newotherbits |= newotherbits >> 4;
  newotherbits = (newotherbits & ~(newotherbits >> 1)) ^ 255;

テキスト・エディタの interactive 引数指定の正規表現

GNU Emacs の編集コマンドは interactive 特殊形式を持つだけでなく、 この特殊形式で対話時に引数をどのように得るかを指定します。 この仕掛けは、 関数と編集コマンドの差異をなくす働きをします。 エディタの read-eval-print ループからは、 特殊形式を基に引数を作ってコマンドを呼び出します。 一方、 関数やコマンドからは、 この特殊形式を無視し、 コマンドをあたかも通常の関数であるかのように摘要に利用できます。

引数指定は文字列になっています。 その中で、 1 つの引数を 1 文字で指定します。 例えば、 コマンド・プレフィックスから数を得たいときは (interactive "p") と記述します。 ミニバッファを使って文字列を得たいときは s にプロンプトを続けて (interactive "sString ?") と記述します。 ミニバッファから値を得る引数指定のプロンプトを省略することはできません。 また、 プロンプト付き引数指定の後に他の引数指定を続けるときは、 1 つの改行で区切ります。

  (interactive "sString 1 ?\nsString 2 ?")

プロンプトが付かない引数指定も改行で区切ります。 現点 (d) とマーカー (m) の値を引数に受け取る指定は次のようにします。

  (interactive "d\nm")

ここでのローカルな規則の緩和として、 末尾に改行を付けても良いことにしましょう。

  (interactive "sString 1 ?\nsString 2 ?\n")

さらに、 パターンを簡単にするため、 プロンプトなしの引数指定文字 p と、 プロンプト付きの引数指定文字 s の 2 つだけが使えるものとしましょう。

  1. 空行を許す
  2. p にプロンプトを指定しない
  3. p の後に ps を続けるときは改行を 1 つ挟まなければならない
  4. s にプロンプトを指定しなければならない
  5. sプロンプト の後に ps を続けるときは改行を 1 つ挟まなければならない
  6. 末尾に改行があっても良い
  7. 改行を 2 つ以上並べることは禁止

このような規則にマッチする ruby正規表現は簡単なものです。

  INTERACTIVE_PATTERN = %r{
    \A (?: [p] | [s][^\n]+ ) (?: \n (?: [p] | [s][^\n]+ ) )* \n? \z
  }msx

テキスト・エディタの行の折り返し表示 その 4 - キャッシュ更新の改善

行の折り返し表示 その 3」 でテキスト・エディタで長い文書ファイルを開いても、 表示速度が極端に落ちないようにと、 行の折り返し表示のための書記素クラスタ情報をキャッシュすることにしました。 ところが、 キャッシュは良いことばかりではないようで、 キー入力による文字挿入・削除の応答性を改善するために速度を落としている箇所を探してみたところ、 キャッシュ追加時の each ループが原因になっていました。

#@<unshift@>=
  def unshift(value)
    # 問題部分
    each do |e|                                                     # !
      if e.value.last >= value.first && value.last > e.value.first  # !
        delete(e)                                                   # !
      end                                                           # !
    end                                                             # !
    super(value)
  end

このループは、 バッファが改行で終わるとき、 バッファ末尾の書記素クラスタ情報で line.first == line.last になっておりキャッシュに残っていた分を削除するのに必要でした。 他の場合は、 行内の場所 loc に対して、 line.first <= loc < line.last がなりたつので文字挿入・削除時にキャッシュから削除できていました。

改善前

  バッファ          書記素クラスタ情報
  "quick brown\n"   Lines.new(0, 12, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12])
  "fox jumps\n"     Lines.new(12, 22, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
  ""                Lines.new(22, 22, [0])

バッファ末尾を含めて、 すべての書記素クラスタ情報で、 line.first <= loc < line.last がなりたてば、 挿入・削除時にキャッシュから削除できる理屈で、 キャッシュ追加時の余計な重い each ループが不要になります。 そのためには、 擬似的にバッファ末尾を表す制御文字があるかのように書記素クラスタ情報を作れば良いわけです。 つまり、 バッファの正味の文字数は 22 文字なのですが、 擬似末尾制御文字を含めて書記素クラスタを 23 個とします。

改善後

  バッファ          書記素クラスタ情報
  "quick brown\n"   Lines.new(0, 12, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12])
  "fox jumps\n"     Lines.new(12, 22, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
  ""                Lines.new(22, 23, [0, 1])

改善後では、 バッファ末尾が改行で終わってないときも同様に考えて、 擬似的なバッファ末尾文字があるかのように書記素クラスタ情報を作ることにします。 この場合、 バッファの正味の文字数は 21 文字なのですが、 擬似末尾制御文字を含めて書記素クラスタを 22 個とします。

改善後

  バッファ          書記素クラスタ情報
  "quick brown\n"   Lines.new(0, 12, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12])
  "fox jumps"       Lines.new(12, 22, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10])

ギャップ・バッファの作る書記素クラスタ情報 Line は行の折り返しを考慮しません。 求めたいユーザ座標 loc を含む改行文字と改行文字の間を行として、 その中に含まれている書記素クラスタの開始ユーザ座標の相対値をリストアップします。 前のコードではギャップを挟むとき、 文字列に切り出してから書記素クラスタの開始位置を求めていたのですが、 今回はそこも改善し、 文字列切り出しなしで書記素クラスタをたどっていきます。 その場合、 書記素クラスタの途中にギャップが開いている可能性があるので、 ギャップの直前の書記素クラスタを、 ギャップ直後へ移動してから書記素クラスタをもう一度、 同じ文字からたどらせています。 ただし、 この改善による応答性への寄与は小さく、 上の each ループの除去ほどの効果はありません。

Line = Struct.new(:first, :last, :h)

class GapEditor
  GRAPHEME_CLUSTER = %r/\G\X/

  def grapheme_clusters_of_line(loc)
    left = find_first_in_backward("\n", loc, false)
    dol = find_first_in_forward("\n", loc, false)
    line = Line.new(left, dol + 1, [])
    right = (dol < size) ? dol + 1 : dol
    data = @data
    i = left
    if left < @gap_start && @gap_start < right
      gs = @gap_start
      while i < gs
        line.h << i - left
        i = GRAPHEME_CLUSTER.match(data, i).end(0)
      end
      gap_move(left + line.h.last)
      line.h.pop
      i = @gap_start
    end
    gap = right <= @gap_start ? 0 : @gap_end - @gap_start
    i, left_gap, right_gap = i + gap, left + gap, right + gap
    while i < right_gap
      line.h << i - left_gap
      i = GRAPHEME_CLUSTER.match(data, i).end(0)
    end
    while true
      line.h << right - left
      (line.h.last + line.first < line.last) or break
      right += 1
    end
    line
  end

  # 省略
end

末尾の特別扱いが不要になったので、 キャッシュへの追加時の削除が不要になり、 unshift は Cache クラスのものをそのまま使えるようになります。 キャッシュからの検索に使う条件式も素直になります。

class RangeCache < Cache
  def lookup(loc)
    each do |e|
      r = e.value
      if r.first <= loc && loc < r.last
        touch(e)
        return r
      end
    end
    nil
  end
end

Buffer クラスで、 書記素クラスタ情報 Line をキャッシュするやりかたは、 前のままで変化はありません。 キャッシュにあるときは、 それを使い、 ないときはギャップ・バッファに Line オブジェクトを作ってもらってキャッシュに追加します。

class Buffer
  def grapheme_clusters_of_line(loc)
    line = @line_cache.lookup(loc)
    if line.nil?
      line = content.grapheme_clusters_of_line(loc)
      @line_cache.unshift line
    end
    line
  end

#@<content_insert, content_delete@>

  # 省略
end

文字挿入・削除で、 以前はバッファの内容を更新してからキャッシュとマークを更新していたのですけど、 更新の順番が逆の方が、 デバッグ時の挙動の追跡がわかりやすいことに気がついたので、 逆にしています。

#@<content_insert, content_delete@>=
  def content_insert(dot, str)
    count = str.size
    screen.window_of_buffer_owner(self).each do |win|
      update_mark_insert(win.mark_list, dot, count)
      update_cache(win.layout.cache, dot, 0, count)
    end
    update_mark_insert(@mark_list, dot, count)
    update_cache(@line_cache, dot, 0, count)
    content.insert(dot.point, str)
    dot.point += count
    @revision += 1
    self
  end

  def content_delete(dot, count)
    count_abs = count.abs
    screen.window_of_buffer_owner(self).each do |win|
      update_mark_delete(win.mark_list, dot, count_abs)
      update_cache(win.layout.cache, dot, count_abs, -count_abs)
    end
    update_mark_delete(@mark_list, dot, count_abs)
    update_cache(@line_cache, dot, count_abs, -count_abs)
    content.delete(dot.point, count)
    @revision += 1
    self
  end

#@<update_cache@>

キャッシュの更新は前のままです。 そのままでもバッファ末尾のキャッシュを扱えるようになりました。 次のコードは dot.point をくくりだしただけで、 本質は前と同じです。

#@<update_cache@>=
  def update_cache(cache, dot, count1, count2)
    loc = dot.point
    cache.each do |e|
      if e.value.first <= loc + count1 && loc < e.value.last
        cache.delete(e)
      elsif e.value.first > loc
        e.value.first += count2
        e.value.last += count2
      end
    end
  end

Layout クラスが、 書記素クラスタ情報 Line から行を折り返して、 Grid を作ります。 Line の変更によって、 影響を受けるのは、 現在の Grid がバッファ末尾を含むことをチェックする箇所です。 今度は、 grid.last がバッファ・サイズを越えていることを調べるようにします。

class Layout
  def eos?()
    @grid.last > window.buffer.size
  end

#@<layout@>

  # 省略
end

書記素クラスタ開始位置配列から行の折り返し位置を求める layout クラスは前と同じで良いのですが、 バッファ末尾でも Line の開始位置配列が必ず 2 個以上になったことから、 末尾が 1 個のときを特別扱いしなくて済むようになります。

#@<layout@>=
  def layout(loc)
    tty = window.screen.tty
    buffer = window.buffer
    @grid = @cache.lookup(loc)
    if @grid.nil?
      tab_width = buffer.mode.tab_width
      width = window.size.x
      line = buffer.grapheme_clusters_of_line(loc)
      @grid = Grid.new(line.first, line.last, [[]])
      x = 0
      line.h.each_index do |j|
        loc = line.h[j] + line.first
        len = line.h[j + 1] - line.h[j]
        ch = loc < buffer.size ? buffer[loc] : END_BUFFER
        span = END_BUFFER == ch ? 0 \
             : "\n" == ch ? 0 \
             : "\t" == ch ? tab_width - (x % width) % tab_width
             : ch.ord < 0x20 ? 2
             : tty.wcwidth(ch.ord)
        if x % width + span > width
          x += width - x % width
          @grid.v << []
        end
        @grid.v[-1] << HBox.new(line.h[j], len, span)
        if span > 1
          (span - 1).times {|d| @grid.v[-1] << HBox.new(line.h[j], 0, -(d + 1)) }
        end
        break if END_BUFFER == ch || "\n" == ch
        if x % width + span >= width
          @grid.v << []
        end
        x += span
      end
      @cache.unshift @grid
    end
    self
  end

以上で、 キャッシュの更新を挿入・削除時に完了させることができるようになり、 キャッシュ追加時のループを削除することができました。 しないでも良い無駄な処理をしないで済ますようにデータを構成する大切さを体感できる事例でした。