浮動小数点数とポインタを混在させるテクニック（NaN Boxing）

2023-04-22
#compiler

動的言語内で扱う値の内部表現に関する最適化で、NaN Boxingという方法を知ったのでメモ。

あらまし

動的言語を作るという内容の本でオンラインでも読めてすごくおすすめなCrafting Interpretersの最後の章の最適化の話の中でNaN Boxingについて書かれている。

いわゆる動的言語では変数が型情報を持っているんじゃなくて値自体で型を区別できるようになっている。 普通に実装するには内部表現として型情報とその型に関するデータとして持つことになるが、NaN Boxingではそれをまとめた形で持つようにする。 CPUで扱える１ワード（64ビットint）で表現することで持ち運びやコピーが簡単になり、キャッシュも効いて高速化するという利点がある。

普通のやり方

typedef enum {
  VAL_BOOL,
  VAL_NIL,
  VAL_NUMBER,
  VAL_OBJ
} ValueType;

typedef struct {
  ValueType type;
  union {
    bool boolean;
    double number;
    Obj *obj;
  } as;
} Value;

Value構造体に型の種類を判別するためのValueTypeと、型ごとの情報を共用体asで持つ（Tagged unionと呼ばれる）。 doubleやObjポインタのアライメントがあるので、Valueのサイズは16バイトになる。 これをどうにかしてもっと短縮したい、というエクストリームプレイ。

NaN Boxing

大まかにはdoubleとポインタどちらも64ビット長だけど、どうにかして一つの64ビットで型も判別できるようにした上でさらに値も保持する、というテクニック。

浮動小数点数のフォーマットはIEEE754で決まっていて、符号1ビット|指数部11ビット|仮数部52ビットの計64ビットで構成されている。 普通の数値では指数部は1〜2046（ゲタ1022）だが、NaNは特別で指数部11ビットがすべて1となっている。 ただNaNは無限大と非数にしか使われず仮数部最上位の1ビット以外は使用されないので、それを使う。

64ビット環境のポインタも今の所実際には下位48ビットしか使われてないので、うまく詰め込める（※）。

なので判定手順は

  • もし指数部＋仮数部上位２ビットが１(QNAN)でないなら、数値（浮動小数点数）
  • 全て１なら：下位の値によって
    • 1：nil
    • 2：true
    • 3：false
    • 他：オブジェクトへのポインタ（この場合のみ最上位の符号ビットが立ってる）

実際にテスト

テストコード：ideone.com

抜粋：

typedef uint64_t Value;

#define SIGN_BIT ((uint64_t)0x8000000000000000)
#define QNAN     ((uint64_t)0x7ffc000000000000)

#define IS_NUMBER(value)    (((value) & QNAN) != QNAN)
#define IS_OBJ(value)       (((value) & (QNAN | SIGN_BIT)) == (QNAN | SIGN_BIT))

int main(void) {
  char s[] = "Hello, world!";
  Value str = OBJ_VAL(copyString(s, strlen(s)));

  Value values[] = {
    NIL_VAL,
    FALSE_VAL,
    TRUE_VAL,
    NUMBER_VAL(1.234),
    NUMBER_VAL(-0.789e5),
    NUMBER_VAL(0.0),
    NUMBER_VAL(1.0 / 0.0),
    NUMBER_VAL(-1.0 / 0.0),
    NUMBER_VAL(0.0 / 0.0),
    str,
  };

  for (size_t i = 0; i < sizeof(values) / sizeof(*values); ++i) {
    printValue(values[i]);
    printf("\n");
  }

  return 0;
}
$ cc nan-boxing.c && ./a.out
7ffc000000000001: nil
7ffc000000000002: false
7ffc000000000003: true
3ff3be76c8b43958: 1.234
c0f3434000000000: -78900
0000000000000000: 0
7ff0000000000000: inf
fff0000000000000: -inf
7ff8000000000000: nan
fffc6000003c8050: "Hello, world!"

その他

  • 約10%高速化、との話
  • 環境によってはNaN Boxingが使えない場合に備えて、#ifdefで分岐できるようにしている
  • doubleとの型変換に無理やりキャストじゃなくて、memcpy使うんだぁ…（最適化で消えるらしい）
  • cloxでは整数型はないけど、nilや真偽値のタグをもっと上位に移動させて、整数タグの場合には下位32ビットを使用すれば追加できそう
  • 現行の64ビットアーキテクチャでもハードウェア的にやカーネル的に全アドレスが使用されるわけではなく、アドレスバス（52ビット？）やページテーブル（48ビット？）自体がフルに使うようにはなってないらしい（要出典）

リンク

関連記事

新着記事