不確定特異点

広く深く、ところどころ超深く

NaN Boxingというテクニックを知った

mruby のことを調べていたら NaN Boxing というテクニックを知りました。

主に言語処理系等において、整数やポインタや浮動小数点数等、様々な型のデータを一つのオブジェクトとして union で詰め込みたい場合があります。その際、そのオブジェクトがどういう型を持つかを識別するためのタグ情報も必要になりますが、そのまま構造体のメンバとしてタグ情報を持つと、一つのオブジェクトは「データ(union)+タグ情報」となり、タグが付いている分のメモリオーバヘッドが増えてしまいます。

この問題を解決するため、IEEE 754 浮動小数点数の NaN の中にタグを押し込むことにより、メモリサイズを削減するテクニックが使われていて、これを NaN Boxing というようです。つまり、IEEE 754 形式の浮動小数点数仮数部がすべて 1 の場合に NaN と見なされるため、例えば倍精度浮動小数点数だと 0xFFF00000_00000000 よりも大きい数はすべて NaN として扱われるため、0xFFFXXXXX_XXXXXXXX の X の部分は自由に使ってよいことになります。

mruby の include/mruby/boxing_nan.h に以下のような定義がありました。

/* value representation by nan-boxing:
 *   float : FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF FFFFFFFFFFFFFFFF
 *   object: 111111111111TTTT TTPPPPPPPPPPPPPP PPPPPPPPPPPPPPPP PPPPPPPPPPPPPPPP
 *   int   : 1111111111110001 0000000000000000 IIIIIIIIIIIIIIII IIIIIIIIIIIIIIII
 *   sym   : 1111111111110001 0100000000000000 SSSSSSSSSSSSSSSS SSSSSSSSSSSSSSSS
 * In order to get enough bit size to save TT, all pointers are shifted 2 bits
 * in the right direction. Also, TTTTTT is the mrb_vtype + 1;
 */
typedef struct mrb_value {
  union {
    mrb_float f;
    union {
      void *p;
      struct {
        MRB_ENDIAN_LOHI(
          uint32_t ttt;
          ,union {
            mrb_int i;
            mrb_sym sym;
          };
        )
      };
    } value;
  };
} mrb_value;

mrb_value というのが mruby のオブジェクトを表現する型になっていて、浮動小数点数の f とシンボルや整数を表す value が union されてます。mrb_value の上位 32bit に相当する ttt というメンバがタグ情報として利用されるようになっているようです。

#define BOXNAN_SET_VALUE(o, tt, attr, v) do {\
  switch (tt) {\
  case MRB_TT_FALSE:\
  case MRB_TT_TRUE:\
  case MRB_TT_UNDEF:\
  case MRB_TT_FIXNUM:\
  case MRB_TT_SYMBOL: (o).attr = (v); break;\
  default: (o).value.i = 0; (o).value.p = (void*)((uintptr_t)(o).value.p | (((uintptr_t)(v))>>2)); break;\
  }\
  (o).value.ttt = (0xfff00000|(((tt)+1)<<14));\
} while (0)

mrb_value に値をセットするためのマクロだと思いますが、最後の default 項では、value.ttt へセットする際に上位ビットも 0xFFF にセットしていることから、浮動小数点数の NaN 値に影響を与えることなく ttt をタグ情報として埋め込んでいることが見て取れました。