タグから見つける

タグから見つける

職種を選択

事業領域を選択

組織を選択

かつて人々が熱中したベンチマークのお祭り。10億行チャレンジ1BRCについて

目次

データ推進室のsaka1です。

X(旧Twitter)のソフトウェアエンジニアコミュニティをよく見ると、コード最適化を仕事・趣味にする人々のクラスタがあります。 どんなアルゴリズムを使うと効率的か？ どんな実装技法を使うとCPUの性能を絞り出せるか？ スレッド並列？ SIMD？ アセンブリ？ 彼らはありとあらゆる高速化手段に関心があるようです。

1BRCとは？

2024年初頭に、そんなエンジニアたちが一斉に熱中し、タイムラインを埋め尽くした「お祭り」がありました。The One Billion Row Challenge (1BRC)です。

お題はとても単純です。

観測地点と気温の組が10億行並んだテキストファイルが提供される。観測地点ごとに気温の最小・平均・最大を計算し出力する最速のプログラムは？

オリジナルのブログ記事 にあるサンプルテキストは、こんな感じの文字列です。

Hamburg;12.0
Bulawayo;8.9
Palembang;38.8

出力例です。

{Abha=5.0/18.0/27.4, Abidjan=15.7/26.0/34.1, Abéché=12.1/29.4/35.6, Accra=14.7/26.4/33.1, Addis Ababa=2.1/16.0/24.3, Adelaide=4.1/17.3/29.7, ...}

リファレンス環境上で実行時間の短さを競うのがルールでした。このコンテストは当初Javaで行われていましたが、人気が高まると様々な言語での最速実装を試みる大規模なチャレンジに発展していきました。

※ ちなみに英語の解説記事もいくつか出ていて、本記事はそれらと内容が被る部分もあります。興味がある人は記事末尾の関連リンクも参照してみてください。

この記事で紹介すること

この記事では、1BRC参加者たちが開発した興味深い手法のうち、いくつかを取り上げます。特に、CPUの動作やビット演算についてある程度理解している・興味がある人向けの記事になっています。といっても複雑な前提知識は求めません。「CPUの汎用レジスタには8バイト入ると知っている」「ビットシフト演算・XOR演算の挙動がわかる」ぐらいで十分です。

実装の紹介にはPythonを使います。オリジナルの実装はJavaコードなので、面白さの一部は伝わりづらいかもしれず、また低水準のコードが見えづらいとは思うのですが、アルゴリズムとしては読み取りやすくなっている面もあるかと思います。

この記事では次のトピックを扱います：

  • SWAR (SIMD Within A Register)による区切り文字の検出
  • 気温の超高速・分岐命令なしパース

これ以外にもありとあらゆる技法を積み上げた結果、リファレンス環境で実行に数分かかっていたJavaコードは数秒まで高速化されました。実に2桁オーダーの改善ができたことになります。

現代のソフトウェアエンジニアたちの魔術の一端を紹介できれば幸いです。

前提知識と準備

CPUの前提

計算機環境としてはモダンなx86-64 CPUを仮定します。したがってリトルエンディアン・2の補数が前提となります。おそらく多くの現代CPU、例えばARM環境でもほぼ同じ議論が使えるはずです。

レジスタ関連の記法について:

  • レジスタは64ビット（8バイト）を仮定します。Pythonにおけるintは任意精度なので、64ビットであることが実装上重要な箇所では x & 0xffffffffffffffff のようにして64ビットを明記することがあります
  • 64ビット整数の各ビットを、最下位から0ビット目、1ビット目、…63ビット目と表記します
    • 特に0ビット目を最下位ビット(LSB)、63ビット目を最上位ビット(MSB)と表記します
    • MSBは符号ビットでもあります

dump_hex

しばしば整数をバイト列として見たくなることがあるのですが、そういった場合に便利な補助関数を定義しておきます。

def dump_hex(x: int, length=8) -> str:
    return x.to_bytes(length, byteorder='little', signed=True).hex(sep=' ')
# 実行例
dump_hex(1)   # => '01 00 00 00 00 00 00 00'
dump_hex(2)   # => '02 00 00 00 00 00 00 00'
dump_hex(256) # => '00 01 00 00 00 00 00 00'

この記事では、ダンプ結果の文字列先頭が下位バイトを表す、リトルエンディアンな表記を使います。我々が普段使う整数表記では左側ほど大きな重みの桁ですが、 dump_hex だと逆になっているので注意してください。

この先で用いる演算に対応する関数を定義しておきます。これらはPythonだと複雑なコードですが、x86-64 CPUは1命令で実行できます。関数の中身というよりは、どんな引数に対してどんな結果になるのかに注目してみてください。

tzcnt

tzcnt(trailing zero count)は最下位ビットから連続する0の個数を数えて返します。

# 64ビット版tzcnt
def tzcnt(x: int) -> int:
    if x == 0:
        return 64
    return (x & -x).bit_length() - 1
tzcnt(0b1)    # => 0
tzcnt(0b10)   # => 1
tzcnt(0b100)  # => 2
tzcnt(0b1000) # => 3
tzcnt(0)      # => 64

sar

sar(shift arithmetic right)は算術右シフト命令です。つまり最上位ビットが1になっているならば、シフトで新しく埋めるビットにも1を立てます。

# 算術右シフト（64ビット版）
def sar(val: int, shift: int) -> int:
    val &= 0xffffffffffffffff # 64bitに切り詰める
    # 最上位ビット(符号ビット)が1なら、負の数として扱う
    if val & (1 << 63):
        val -= (1 << 64)
    return val >> shift
dump_hex(sar(0x0fffffffffffffff, 8)) # => 'ff ff ff ff ff ff 0f 00' シフトした場所には0が埋められる
dump_hex(sar(0xffffffffffffffff, 8)) # => 'ff ff ff ff ff ff ff ff' 符号ビットが1ならば1で埋められる

sarによるブロードキャスト

sarを使った面白いテクニックとして、nビット目の値を全体に反映させる（ブロードキャストする）ことができます。例えば3ビット目を全体に反映させたい時、3ビット目を左シフトで最上位ビットに持っていき、シフト量63でsarします。

value = 0b00001000  # 3ビット目が1
# 3ビット目を符号ビット位置(63ビット目)に移動
shifted = value << (63 - 3)
result = sar(shifted, 63)
dump_hex(result)  # => 'ff ff ff ff ff ff ff ff' 全体が3ビット目と同じ1になった

このテクニックがどう役に立つのかわからないと思いますが、以降の節で活躍します。

基本的な実装

1BRCは実行時間を考えずに解くだけなら、それほど難しくありません。素朴なPython実装をするなら以下のようになるでしょう。ただし、これで10億行処理しようとすると、どれだけ時間がかかるか分からないほど遅いはずです。

from dataclasses import dataclass
@dataclass
class Stats:
    min: float
    max: float
    sum: float
    count: int
def process_file(filename: str) -> dict[str, Stats]:
    stats_dict: dict[str, Stats] = {}
    with open(filename, 'r') as f:
        for line in f:
            station, t_str = line.strip().split(';')
            t = float(t_str)
            if station not in stats_dict:
                stats_dict[station] = Stats(
                    min=t,
                    max=t,
                    sum=t,
                    count=1
                )
            else:
                stats = stats_dict[station]
                stats.min = min(stats.min, t)
                stats.max = max(stats.max, t)
                stats.sum += t
                stats.count += 1
    return stats_dict
# 使用例
if __name__ == '__main__':
    results = process_file('measurements.txt')
    # 出力形式: {Abha=5.0/18.0/27.4, ...}
    output = '{' + ', '.join(
        f'{station}={stats.min}/{stats.sum / stats.count:.1f}/{stats.max}'
        for station, stats in sorted(results.items())
    ) + '}'
    print(output)

単純な実装なので、全体の処理の流れが見やすいですね。

  1. テキストファイルを1行ずつ読み出す
  2. 各行から ; を検出して、前半部分（観測地点）と後半部分（気温）に分ける
  3. 気温を浮動小数点数に変換する
  4. 観測地点をキーにして気温を集約する

観測地点ごとの統計量さえ作ってしまえば、あとの表示にかかるコストはわずかです。

最適化①: SWAR (SIMD Within A Register)による区切り文字の検出

さて、前節の テキストファイルを1行ずつ読み出す とは、よく考えると「改行文字 \n を検出する」ことに他なりません。各行では;の検出も必要だったので、1BRCを効率よく解くには、テキストファイル中の特定の1バイト文字を検出する操作を、どこまで効率よく行えるかがポイントの一つです。

Roy van Rijn氏は、この問題に対してSWAR (SIMD Within A Register)と呼ばれる技法を適用しました。 （ ソースコードはこちら ）

発想自体はシンプルです。普通は、ある文字の位置を検出するには、線形探索を使います:

def find_semicolon(input: str):
    i = 0
    while i < len(input):
        if input[i] == ';':
            return i
        i += 1
    return None

ループごとにif文で1バイトずつの比較をしていることになります。しかしCPUの汎用レジスタは長さ8バイトあるので、本来は1ループごとに8バイトの処理をさせると効率的なはずです。言い方を変えると、1バイト単位の処理は効率が悪いのです。

そこで8回のマッチングをまとめて行うために、ASCII文字 ; （0x3b） が8個並んだ整数 0x3b3b3b3b3b3b3b3b を考えます。これと8バイト文字列をまとめてマッチさせると効率的なはずです。

input = int.from_bytes(b"ab;cdefg", 'little')
semicolon_vec = 0x3b3b3b3b3b3b3b3b
xor_vec = input ^ semicolon_vec

バイト単位の全バイト同値判定命令は無いのですが、近い操作としてxor演算を使います。xorは同じビットに対して結果0となるのでした。したがって、もし input のどこかに ; があったなら、 input ^ semicolon_vec の値は ; があるバイト部分についてゼロ(0x00)になるはずです。

; を検出する問題は、0x00を検出する問題に変換されました。これをさらに0x80つまり当該バイトの最上位ビット(MSB)だけ立っている状態に持っていくために、次の演算をします。

found_vec = (xor_vec - 0x0101010101010101) & ~xor_vec & 0x8080808080808080
dump_hex(xor_vec)   # => '5a 59 00 58 5f 5e 5d 5c'
dump_hex(found_vec) # => '00 00 80 00 00 00 00 00'

found_vec は求めたかった状態です。右辺は謎の演算ですが「ハッカーのたのしみ」などでも紹介される、古くから知られるテクニックのようです。

まず - 0x0101010101010101 の部分は、各バイトから1を引く意味です。我々が普段使う十進数の世界で x - 111 が各桁から1を引くのと同じことです。もし、引かれるバイトが0つまり0x00だったら、次のバイトから繰り下がり(borrow)が発生します。

  • そのバイトが 0x00 だったら、繰り下がりが発生して 0xff になっている
  • そのバイトが 非0x00 だったら、バイト内のどこかのビットが1のはずなので、繰り下がりは発生しない

このように場合分けして考えると、検出したい0x00は0xffになっています。

次に考えたいのは、じゃあ ~xor_vec は何かという話です。この部分は引き算の繰り下がり検出のうち都合が悪いパターンを除外するための処理です。もし xor_vec の特定バイトが 0b10000010 のように、MSBおよび別のどこかのビットが立っていたならば、引き算の結果に関係なく元々MSBが1です。引いた結果としてMSBが1になったパターンと区別するためには、元々MSBが1の箇所についてビットを無効化する必要があります。それをするのが & ~xor_vec です。

最後の & 0x8080808080808080 はMSB以外のビットを0にするためのマスクです。

ここまでの一連の変換で「 ; があったバイトのMSBが立っていて他のビットは全て0」なバイト列ができました。

[入力: ab;cdefg]
Input: 61 62 3b 63 64 65 66 67
Mask : 3b 3b 3b 3b 3b 3b 3b 3b
------------------------------ XOR
XOR  : 5a 59 00 58 5f 5e 5d 5c  （00の位置がセミコロン）
------------------------------ (x - 0x01..)
SUB  : 59 58 FF 57 5e 5d 5c 5b  （00がFFに、他は単に-1）
------------------------------ & ~XOR & 0x80..
RES  : 00 00 80 00 00 00 00 00  （MSB抽出の完了）

実は;の検出としてはほぼ完了です。前述のように、CPUにはtzcntという「最下位ビットから数えて最初にビットが立っている位置までのビット数」を効率的に計算する命令があります。これを使えばMSBの位置までのビット数が分かるので、バイト数を数えることも容易です。

tzcnt(found_vec)      # => 23 ビット目に ; のMSBが存在する
tzcnt(found_vec) // 8 # =>  2 バイト目に ; が存在する

b"ab;cdefg" の0から数えて2バイト目に ; が確かにありますね。これで検出完了です。

最適化②: 気温の超高速パース

もう一箇所、入力データの処理で重いのが、気温を数値として扱える状態に変換する処理です。ここからは、文字列で書かれた気温を「小数第一位を10倍した整数」に変換するアルゴリズムを見ていきます。

前節までの技法で \n と ; の位置が特定できます。

Hamburg;12.0

この行でいう12.0のメモリ上の位置が特定できることになります。仮に文字列12.0が得られた時に、普通の発想ならば、まずそれを浮動小数点数に変換すると考えるところです。浮動小数点数ならば数値として足したり比較したりする操作が容易です。

t = float(t_input)

これは自然なコードですが、性能面ではあまり効率的ではありません。浮動小数点数のパースは、一般にかなりコストが高い操作として知られています。今回のような極限まで効率的なコードを求める場面では使いたくありません。

@merykitty(Quân Anh Mai)氏はこの問題について、超高速なパーサを発明しました。なんと条件分岐なし(branchless)を実現しています。実装にif文を使いません。 （ ソースコードはこちら ）

このアルゴリズムの大前提として、データが気温である点に注目します。

Hamburg;12.0
Bulawayo;8.9
Palembang;38.8
St. John's;15.2
Cracow;12.6
Bridgetown;26.9
Istanbul;6.2
Roseau;34.4
Conakry;31.2

データを観察すると次のことが分かります。

  • 気温は小数第一位まで記録されている
    • 必ず . があり、その後ろが1文字である点に注意する
  • 気温は100度以上や-100度以下にはならないので、符号部分を除いた値は必ず3文字か4文字になる
    • 3文字の例: 8.9
    • 4文字の例: 34.4
  • 一部の地点は気温マイナスなので - から始まる
    • +から始まることはない

つまり1億や−200のような極端な値はとりません。さらに、文字数は必ず5文字以内だと分かります（4文字パターンに-符号付き）。したがって入力文字列は64ビット整数として扱えます。

input = int.from_bytes(b"12.0", 'little')

ここまでの前提を踏まえ、以降はアルゴリズムをいくつかのステップに分けて説明していきます。

大方針として、浮動小数点数への変換は狙いません。小数第一位までしかないことを利用して、10倍した整数に変換する問題を考えます（要するに固定小数点で扱います）。

  • 文字列 -12.0 を整数 -120 へ
  • 文字列 34.4 を整数 344 へ

整数に変換すれば、以降の処理は全て高速な整数演算で行うことができます。ちなみに1BRCでは浮動小数点数特有の誤差処理まで求められていないので、全ての処理を整数で行ってもレギュレーションを満たせます。

ASCIIコード表

以降の説明で使うので、ASCIIコード表も載せておきます。気温パース問題の性質上、 入力として現れる可能性があるのはこれらの文字だけ です。ちなみに数字は上位4ビットが固定された 0b0011xxxx という形式になっていますね。この性質を使ったコードが以降で現れます。

文字 16進数 2進数
0 30 00110000
1 31 00110001
2 32 00110010
3 33 00110011
4 34 00110100
5 35 00110101
6 36 00110110
7 37 00110111
8 38 00111000
9 39 00111001
- 2d 00101101
. 2e 00101110

ステップ1: 符号の取り出し

まずマイナス符号の処理を考えます。-はもし現れるならば先頭にしかなく、他に先頭に現れるうるのは数字です。ASCIIコード表を見ると、-と数字の違いは4ビット目 00101101 だと分かります。そこで、4ビット目を64ビット全体に「ブロードキャスト」します。

def extract_sign(input: int) -> int:
    inv = ~input
    return sar(inv << 59, 63)
extract_sign(int.from_bytes(b"12.0", 'little'))  # => '00 00 00 00 00 00 00 00'
extract_sign(int.from_bytes(b"-12.0", 'little')) # => 'ff ff ff ff ff ff ff ff'

後続処理の都合で ~input と、あらかじめビットを反転させています。ここまでの操作で、-の有無に反応するマスクを作ることができました。

  • 先頭に-があったとき: extract_sign の結果は 0xffffffffffffffff （全ビットが1）
  • 先頭が-ではなかったとき: extract_sign の結果は 0x00 （全ビットが0）

作ったマスクを使うことで、文字列先頭の - を消去できます。

# "-" がもしあったなら削除する
def strip_sign(input: int) -> int:
    sign_mask = extract_sign(input)
    return input & ~(sign_mask & 0xff)
input = int.from_bytes(b"-12.0", 'little')
dump_hex(input)        # => '2d 31 32 2e 30 00 00 00'
dump_hex(strip_sign(input)) # => '00 31 32 2e 30 00 00 00'

strip_sign 関数では extract_sign が -1 を返したときだけ、先頭 1 バイトを 0 にマスクします（ input & ~(sign_mask & 0xff) ）。これにより - が消え、後続の処理で邪魔にならなくなります。

ステップ2: ピリオド位置を用いたアライメント補正

ステップ1で符号（マイナス）の処理は完了しました。次は数値のアライメント（位置合わせ）です。 入力データはリトルエンディアンで読み込まれているため、例えば 12.3 と 1.2 では、メモリ上のバイト配置が異なります。何番目に1の位があり、何番目に10の位があるか、がズレています。

# "12.3" は "1" (0x31), "2" (0x32), "." (0x2e), "3" (0x33)
dump_hex(int.from_bytes(b"12.3", 'little')) # => '31 32 2e 33 00 00 00 00'
# "1.2"  は "1" (0x31), "." (0x2e), "2" (0x32)
dump_hex(int.from_bytes(b"1.2", 'little'))  # => '31 2e 32 00 00 00 00 00'

※ 繰り返しになりますが、文字列で見たときに一番大きい桁が、バイト並びとして見ると先頭に来ている点に注意します。

このままではステップ3の技法を使うのに都合が悪いので、小数点の位置を基準にして「1の位」「10の位」「100の位」が同じビット位置に来るようにずらす（シフトする）必要があります。

これをif文なしで行うために、ここでもビット演算を使います。 ASCIIコード表を見ると、ピリオド . (0b00101110) と数字 0-9 (0b0011xxxx) の違いは4ビット目です。ここの違いを利用して、ピリオドの位置を特定します。

ピリオドの位置（ビット数）が分かれば、それを元にシフト量を計算し、数字が常に決まった位置に来るように input 全体をずらします。これで "12.3" だろうが "1.2" だろうが、常に「特定の位置に1の位がある」状態を作れます。

# ピリオドは2〜4文字目にしか現れない前提なので
# そのバイト位置についてのみ拾うマスクになっている
DOT_BITS = 0x10101000
def find_dot_pos(input: int) -> int:
    # wordを反転させると、ピリオドの箇所だけ0x10ビットが「1」になる
    # それをマスクして取り出し、tzcntで位置を数える
    return tzcnt(~input & DOT_BITS)
def align_input(input: int) -> int:
    dot_pos = find_dot_pos(input)
    return input << (28 - dot_pos)
input = int.from_bytes(b"12.3", 'little')
dump_hex(align_input(strip_sign(input)))      # => '00 31 32 2e 33 00 00 00'
input = int.from_bytes(b"-12.3", 'little')
dump_hex(align_input(strip_sign(input)))      # => '00 31 32 2e 33 00 00 00'
input = int.from_bytes(b"1.2", 'little')
dump_hex(align_input(strip_sign(input)))      # => '00 00 31 2e 32 00 00 00'
input = int.from_bytes(b"-3.4", 'little')
dump_hex(align_input(strip_sign(input)))      # => '00 00 33 2e 34 00 00 00'

どの気温の桁数のパターンであっても、4バイト目を小数第一位として、バイトの位置が揃ったフォーマットを作れました。

ちなみに 区切り文字の検出 で触れたのと同じアルゴリズムで . を検出すればいいのでは？ と思うかもしれません。それでも同じ動作の実装は可能なのですが、命令数は増えてしまいます。特定ビットの違いだけで検出が可能だとわかっている場合、今回のアルゴリズムの方が効率的です。

ステップ3: マジックナンバーによる整数変換

ステップ2までで、入力データは常に「指定したビット位置に数字が並ぶ」ように整形されました。

 "12.3" -> '00 31 32 2e 33 00 00 00'
"-12.3" -> '00 31 32 2e 33 00 00 00'
  "1.2" -> '00 00 31 2e 32 00 00 00'
 "-3.4" -> '00 00 33 2e 34 00 00 00'

ここから定数 MAGIC_MULTIPLIER を乗算することで、この文字並びを一気に整数値へ変換します。……そんなことできるの？と思うかもしれませんが可能です。

まず前処理として、数字の整数を表す部分だけを取り出します。ASCII数字は 0b0000xxxx の形をしているので、下位4ビットだけを残すために 0x0f でマスクします。

ASCII_TO_DIGIT_MASK = 0x0f000f0f00
def to_digits(aligned: int) -> int:
    return aligned & ASCII_TO_DIGIT_MASK
input = int.from_bytes(b"12.3", 'little')
aligned = align_input(strip_sign(input))
digits = to_digits(aligned)
dump_hex(digits) # => '00 01 02 00 03 00 00 00'

"12.3" を構成する数字 1, 2, 3がバイト列としても現れました。 ASCII_TO_DIGIT_MASK の値の意味ですが . の位置を基準に整列させたので、末尾から2番目には . があり、残りの箇所は数字です。数字が来る場所には 0x0f を入れています。

そしてここが核心部分である MAGIC_MULTIPLIER を使った演算です。これまでの前処理は、この乗算をするためにあったようなものです。

ASCII_TO_DIGIT_MASK = 0x0f000f0f00
MAGIC_MULTIPLIER = (100 * 0x1000000 + 10 * 0x10000 + 1)
def magic_convert(digits: int) -> int:
    # 掛け算を行うことで、各桁の数字が適切な重み付け（100倍、10倍、1倍）で足し合わされる
    product = digits * MAGIC_MULTIPLIER
    # 必要な合計値は上位ビット（32ビット目付近）に集まるため、シフトして取り出す
    return (product >> 32) & 0x3FF
magic_convert(digits) # => 123

なぜこれで計算できるのでしょうか？ 魔法のように見えますが、ゆっくり考えていけばわかります。

MAGIC_MULTIPLIER は 3つの項からできています。まず100 * 0x1000000 は入力を100倍し、さらに 0x1000000 を掛けていますが、0x1000000は3バイト分のシフトとみなすことができます。

i = 42
# 0x1000000 を掛けるのは3バイト分シフトするのと同じ
dump_hex(i)              # => '2a 00 00 00 00 00 00 00'
dump_hex(i * 0x1000000)  # => '00 00 00 2a 00 00 00 00'

同様に考えていくと MAGIC_MULTIPLIER は、それぞれ3バイトシフト（重み100）、2バイトシフト（重み10）、0バイトシフト（重み1）の3項の和とみなせます。入力データは5バイトあるのでした。これらの掛け算なので、分配法則を考えると、乗算結果としては15個の部分積が出てきます。

部分積それぞれがどのバイト位置に着地し、最終的に4バイト目に集まってくる様子を表にすると、次のようになります。

行(Rows): 入力データの各バイト (値は "12.3" を前処理したもの)
列(Cols): 乗数の各項 (シフト量と倍率)
      |  Factor A  |  Factor B  |  Factor C  |
Input |    x 1     |    x 10    |    x 100   |
Byte  | (No Shift) | (Shift 2B) | (Shift 3B) |
------+------------+------------+------------+
 B0   |     B0     |     B2     |     B3     | <- 値は00 (マスク済)
(00)  |    (0)     |    (0)     |    (0)     |    結果は全て0
------+------------+------------+------------+
 B1   |     B1     |     B3     |     B4     | <- 十の位 '1' (値:1)
(01)  |   (Trash)  |   (Trash)  |  Val: 100  |    B4に着地 (1*100)
------+------------+------------+------------+
 B2   |     B2     |     B4     |     B5     | <- 一の位 '2' (値:2)
(02)  |   (Trash)  |  Val: 20   |   (Trash)  |    B4に着地 (2*10)
------+------------+------------+------------+
 B3   |     B3     |     B5     |     B6     | <- 記号 '.' (値:00)
(00)  |    (0)     |    (0)     |    (0)     |    結果は全て0
------+------------+------------+------------+
 B4   |     B4     |     B6     |     B7     | <- 小数位 '3' (値:3)
(03)  |   Val: 3   |   (Trash)  |   (Trash)  |    B4に着地 (3*1)
------+------------+------------+------------+
            |            |            |
            v            v            v
        (B4で合流) + (B4で合流) + (B4で合流) = 123

※ LLMを用いて視覚的に読み取りやすい図を生成しました

例えば "12.3" のうち "2" が前処理された 02 に注目すると MAGIC_MULTIPLIER の項A, B, Cと乗算されますが、もともと2バイト目にあるので

  • 項Aとのシフト結果が2バイト目に落ちる
  • 項Bとのシフト結果が3バイト目に落ちる
  • 項Cとのシフト結果が4バイト目に落ちる

このようになります。同様に 01 や 03 も見ていくと、2バイト目、3バイト目はめちゃくちゃな値になりますが、4バイト目を見ると、100 と 20 と 3 が加算されて、欲しかった 123 が現れているのがわかります。

最後に、ステップ1で保存しておいた符号（マイナスかプラスか）を適用します。符号マスクはもう作ってあるので(x ^ sign_mask) - sign_maskで符号を適用させることができます。sign_maskが全ビット立っているとき、「xorして引く」のはビット反転させて+1に等しいです。これはまさに、元の値の2の補数を取る操作になっています。

まとめとして、以上の一連のコード全体を示します。全体を眺めるだけだとパース処理には全く見えませんが、1つずつ分解して読んでいくと、意味が取れるかなと思います。

DOT_BITS = 0x10101000
MAGIC_MULTIPLIER = (100 * 0x1000000 + 10 * 0x10000 + 1)
def extract_sign(input: int) -> int:
    inv = ~input
    return sar(inv << 59, 63)
def find_dot_pos(input: int) -> int:
    # wordを反転させると、ピリオドの箇所だけ0x10ビットが「1」になる
    # それをマスクして取り出し、tzcntで位置を数える
    return tzcnt(~input & DOT_BITS)
def align_input(input: int) -> int:
    dot_pos = find_dot_pos(input)
    return input << (28 - dot_pos)
def magic_convert(digits: int) -> int:
    # 掛け算を行うことで、各桁の数字が適切な重み付け（100倍、10倍、1倍）で足し合わされる
    product = digits * MAGIC_MULTIPLIER
    return (product >> 32) & 0x3FF
def parse_temperature_fast(input: int) -> int:
    # 符号の検出
    # extract_signは "-" があれば -1 (全ビット1)、なければ 0 を返す
    sign_mask = extract_sign(input)
    # "-" 文字の除去
    # sign_maskの下位1バイト(0xff)を使って "-" (0x2d) を 0x00 にマスクする
    input_no_sign = input & ~(sign_mask & 0xff)
    # アライメント補正
    # ピリオド位置を特定し、数字が常に決まったビット位置に来るようシフト
    aligned = align_input(input_no_sign)
    # マジックナンバーによる整数変換（前処理 + マジックナンバー乗算）
    digits = aligned & ASCII_TO_DIGIT_MASK
    abs_value = magic_convert(digits)
    # 符号の適用 
    return (abs_value ^ sign_mask) - sign_mask
input = int.from_bytes(b"12.3", 'little')
parse_temperature_fast(input) # => 123

補足: なぜ「分岐なし」を強調するのか

気温のパース部分は条件分岐命令を一切使わない（branchlessな）実装になっています。実は現代のCPU環境では、条件分岐がないことは大きなメリットになります。

現代のCPUはアウトオブオーダー実行などの仕組みにより、シングルスレッドプログラムであっても命令列をできるだけ並列に処理しようとします（興味がある方は「命令レベル並列性」といった単語で調べてみてください）。CPUはこれから実行される命令列を予測し、投機的に並列実行します。

コード中に条件分岐が登場すると、CPUはその分岐先を予測しなければなりません。もし予測が外れると、その先読みの結果は捨てることになってしまい、実行効率が下がります（分岐予測ミス）。

もちろん現代のCPUの分岐予測は非常に優秀とされますが、それでも「分岐そのものがない」方が確実に高速です。そのため、少々トリッキーでも、条件分岐なしで気温を整数へ変換するアルゴリズムはパフォーマンス向上に効くというわけです。

一連の技法から見えること

1BRCはあくまで技術チャレンジではあるのですが、筆者は少しだけ一般化できる部分もあると感じています。

これだけシンプルな問題であっても最適化の余地は大きい

テキストを上から読んでパースし、足し合わせるような単純な処理であっても、技巧を凝らせば性能を2桁改善できます。「テキストスキャンだしI/Oバウンドでしょ？」といった予想を大きく裏切っています。

ギリギリまで高速化するには問題に特化したアルゴリズム・実装が必要

特に気温のパース部分は、今回のフォーマットに合わせた特殊なアルゴリズム・実装になっています。一般的な解法から進んで、特化させることで最適化余地を作っているわけです。再利用性が高いとは言い難いでしょう。

一般的なアプリケーションでは、ここまでやらなくてもいい（かも）

典型的なアプリケーション開発では、これらの技法を適用するのは費用対効果が合わないかもしれません。しかし、世の中で広く使われるライブラリならばギリギリまで最適化する合理性が出てくるでしょう。

筆者としては、経済的合理性とは別の「技術力によるチャレンジを楽しむ」空気を味わえたのが印象的でした。

まとめ

この記事では次のことを紹介しました。

  • 1BRCというお祭りがあったこと
  • その中で用いられた、SWARや特化パーサといった興味深い低水準の技芸について

これらは1BRCで行われた取り組みのごく一部です。興味があればぜひ関連リンク先の実装も覗いてみてください。

関連リンク

本家ページ

解説記事など

お知らせRECRUIT TECH CONFERENCE 2026を開催します！（オンライン配信／参加無料）

リクルート主催の技術カンファレンス。
第3回目となる今回は「AI×プロダクト開発」をテーマに、急速な技術進化の中で生まれた多様な領域のナレッジから、技術者の活躍を引き出す土壌づくりまで、豊富なセッションをお届けします。是非お気軽にご参加ください！

お申し込みはこちら

RECRUIT TECH CONFERENCE 2026

  • 開催日時
    2026年2月27日（金） 12:00~19:30 （オンライン配信／途中入退場自由）
  • 社外ゲスト
    和田 卓人 氏（タワーズ・クエスト株式会社 取締役社長）／岡野原 大輔 氏（株式会社Preferred Networks 共同創業者 代表取締役社長） ※ご登壇順

記事内容及び組織や事業・職種などの名称は、編集・執筆当時のものです。

執筆者プロフィール

saka1 ソフトウェアエンジニア

2023年リクルート入社後、Webバックエンドやデータエンジニアの領域のお仕事をしています。

キャリア採用の関連職種ページはこちら

関連職種の採用情報
詳しくはこちら

関連組織の特設ページはこちら