Subscribed unsubscribe Subscribe Subscribe

枕を欹てて聴く

香炉峰の雪は簾を撥げて看る

NaN boxing

C++ JavaScript

書いておかないと将来自分が意味不明になるので, NaN boxingについて.
LuaJITが古くから(wingologさんの素晴らしい記事によると), JSCが前から, SpiderMonkeyはfatvalsで, NaN boxingすることによりJSValを64bitに収めることを行っています.
iv / lv5は以前から32bit SystemにおけるNaN boxingは実装していましたが, 64bit SystemにおけるNaN boxingは行っていませんでした.
しかし先ほど, 64bit NaN boxing in 64bit Systemが入り, 現在, Solaris以外のOSにおいてはsizeof(JSVal)が常に64bitになりました.

というわけでNaN boxing memo. 32bit / 64bitともに.

value representation in javascript implementations -- wingolog
という素晴らしい記事があるのでそちらを参考にしたほうが良いかもしれません. こちらは自分の理解と, 主に実装に落としてのmemo.

NaN boxingとは

doubleの数値NaNは意図的に冗長に作られていて, NaNの空間が非常に広くなっています.
よってNaNを正規化し, 1種類に制限をかけると, 残りのNaNは別の値として使うことができるわけで.
よってこのNaNの空いている部分に例えばpointerを突っ込んだりすることによって, pointer / doubleを64bit以内に収めることができます.

NaNの定義

IEEE 754によると, doubleのformatは以下のようになっています. (Wikipediaより)

 1     11                                52
 +-+-----------+----------------------------------------------------+
 |S|  Exp      |  Fraction                                          |
 +-+-----------+----------------------------------------------------+
 63 62       52 51                                                 0

double全体のsign, 11bitのExp, そして52bitのFraction.
このとき, Expがすべて1, かつFractionが0以外の場合, それはNaNと解釈されます. また, 754rではFractionの最上位bitが1だとQuiet NaN, 0ならSignaling NaNと規定されます.

NaN boxing in 32bit system

Signaling NaNは例外が起こりうるので, ここではQuiet NaN(以下QNaN)だけ考えます. QNaNにすれば自然とFractionも0以外となるので常にNaNです.
ではこの広いNaNの空間を制限し, pointerを埋め込んでいきます.
まず, NaNを1種類のみに制限します. ここではQNaNの最小値, すなわち, signが0, expがすべて1, Fractionの最上位bitが1のbit pattern,

二進表記
0111111111111000 0000000000000000 0000000000000000 0000000000000000
十六進表記
0x7FF8000000000000

をNaNとし, 他の値はNaNではないと考えます.
すると, doubleで表現される数値の範囲が制限されます. 以後, 上32bitの値をみます.
この状態で上32bit, doubleは-Infinityが最大となります. これはsignが1でexpがすべて1の値です. これ以上に大きい値はdoubleでは現れません. (-NaNは+NaNにします. けれど別に-NaNを入れてもそれを正規化して最低の値にしておけば, Fractionの最上位1bit分ふえるだけです.)

1111111111110000 0000000000000000

が最大となります. よって, これ以上の値を上32bitに入れると, それをdoubleでないと認識, tag bitとすることができ, 下32bitが好きに使えるということです.

では適当に, in C++. 32bit systemでのみ動作します. tr1使っていますが, 適当にC++0xとかにしてもらっても構いません. とりあえず32bit Ubuntuで確認.

#include <tr1/cstdint>
#include <tr1/cinttypes>
#include <cmath>
#include <cassert>
#include <string>

template<typename To, typename From>
inline To BitCast(From from) {
  union {
    From from_;
    To to_;
  } value;
  value.from_ = from;
  return value.to_;
}

static const double kNaN = BitCast<double, uint64_t>(UINT64_C(0x7FF8000000000000));
static const uint64_t kPointerTag = UINT64_C(0xFFFFFFFF00000000);

union Layout {
  double number_;
  uint64_t bytes_;
};

template<typename T>
class Val {
 public:
  Val(double val) : layout_() {
    layout_.number_ = (std::isnan(val)) ? kNaN : val;
  }

  Val(T* ptr) : layout_() {
    layout_.bytes_ = kPointerTag | reinterpret_cast<uintptr_t>(ptr);
  }

  bool IsNumber() const {
    return layout_.bytes_ < kPointerTag;
  }

  double GetNumber() const {
    assert(IsNumber());
    return layout_.number_;
  }

  bool IsPtr() const {
    return layout_.bytes_ >= kPointerTag;
  }

  T* GetPtr() const {
    return reinterpret_cast<T*>(static_cast<uintptr_t>(layout_.bytes_ & 0xFFFFFFFF));
  }

 private:
  Layout layout_;
};

int main(int argc, char** argv) {
  {
    std::string str("OK");
    const Val<std::string> val(&str);
    assert(val.IsPtr());
    assert(val.GetPtr() == &str);
  }
  {
    const double num = 200000.04420209;
    const Val<std::string> val(num);
    assert(val.IsNumber());
    assert(val.GetNumber() == num);
  }
  {
    const double num = 1.0 / 0.0;
    const Val<std::string> val(num);
    assert(val.IsNumber());
    assert(val.GetNumber() == num);
  }
  {
    const double num = 0.0 / 0.0;
    const Val<std::string> val(num);
    assert(val.IsNumber());
    assert(std::isnan(val.GetNumber()));
  }
  return 0;
}

もちろん, 現在はtag bitを0xFFFFFFFFにしたのですが, doubleの最大値はもっと少ないので, その間の分はいくらでもtagとして使えます. いろんな種類のptrをtagで分岐して入れても大丈夫ですし, int32tagを作って, 下32bitにint32_tを入れてもいいですね.
また, 下32bitについてpointerの値をいじっていません. そのため, conservativeなGCでもpointerと認識できる値のまま残されています.

NaN boxing in 64bit system

もちろん, 64bitについても気になります. でも64bit pointerが64bit全域を使うのであれば, どうやってもboxingはできません. heapからとったptrの場合, alignmentの都合上, 下3bit程度がありますが, doubleとのtagとしては少なすぎます.
しかし, JSC / SpiderMonkeyは実装しています. ではどうやるのか.
結論としては, 64bit pointerといっても, 64bitの空間は莫大, 実際には64bit fullには使っていません. pointerの値は, 上16bitを使っておらず, これが0になっています. x86-64 - Wikipedia, the free encyclopedia
(ただしSolaris除く) https://bugzilla.mozilla.org/show_bug.cgi?id=577056 iv / lv5ではSolarisの場合は128bit JSValにします.

16bitあれば十分です. 先程のdoubleの最大値を確認すれば,

1111111111110000 0000000000000000

と上16bitがまだ隙間があるので, ぜんぜん大丈夫ですね.

しかし, ここで考慮しなければいけないことがあります. それはptrの値に対して16bit例えば,

1111111111110001

とtagを打つとすると, ptrをmodifyしてしまうことになるのです. 別に普通にする分にはclearして取り出せばいいのですが, これではconservative GCなどを使う場合にpointerの値を見つけられません. ではどうするのか?

結論は簡単, doubleの最大値のbit patternが

1111111111110000

なのであれば, 1増やしてもoverflowすることはありません. よってdoubleを格納するときに0x0001000000000000, 上16bitが

0000000000000001

の値を足して格納します. するとdoubleのbit patternのrange(上16bit)は,

0000000000000001 => 1111111111110001

となり, 0000000000000000が使えるようになります. これをpointerのtagとして利用すれば, pointerをmodifyすることなく(もとから上16bitは0なので)格納することができ, conservative GCも安心というわけです. これは上のwingologさんの素晴らしい記事ではfavor pointersとして解説されており, JSCの方式です.
一方普通に16bitを使い, doubleはそのままで, それ以上の値をtagにしてpointerをmodify, 格納するのがfavor doublesの方式で, LuaJIT, SpiderMonkeyなどの方式です.

では適当に, in C++. 64bit system (Solaris除く) でのみ動作します. tr1使っていますが, 適当にC++0xとかにしてもらっても構いません. とりあえず64bit MacOSX Lionで確認.

#include <tr1/cstdint>
#include <tr1/cinttypes>
#include <cmath>
#include <cassert>
#include <string>

template<typename To, typename From>
inline To BitCast(From from) {
  union {
    From from_;
    To to_;
  } value;
  value.from_ = from;
  return value.to_;
}

static const uint64_t kNumberMask = UINT64_C(0xFFFF000000000000);
static const uint64_t kDoubleOffset = UINT64_C(0x0001000000000000);
static const uint64_t kNaNWithOffset = UINT64_C(0x7FF8000000000000) + kDoubleOffset;

template<typename T>
class Val {
 public:
  Val(double val) : layout_() {
    layout_.bytes_ = (std::isnan(val)) ? kNaNWithOffset : (BitCast<uint64_t>(val) + kDoubleOffset);
  }

  Val(T* ptr) : layout_() {
    layout_.pointer_ = ptr;
  }

  bool IsNumber() const {
    return layout_.bytes_ & kNumberMask;
  }

  double GetNumber() const {
    assert(IsNumber());
    return BitCast<double, uint64_t>(layout_.bytes_ - kDoubleOffset);
  }

  bool IsPtr() const {
    return !(layout_.bytes_ & kNumberMask);
  }

  T* GetPtr() const {
    return layout_.pointer_;
  }

 private:
  union {
    T* pointer_;
    uint64_t bytes_;
  } layout_;
};

int main(int argc, char** argv) {
  {
    std::string str("OK");
    const Val<std::string> val(&str);
    assert(val.IsPtr());
    assert(val.GetPtr() == &str);
  }
  {
    const double num = 200000.04420209;
    const Val<std::string> val(num);
    assert(val.IsNumber());
    assert(val.GetNumber() == num);
  }
  {
    const double num = 1.0 / 0.0;
    const Val<std::string> val(num);
    assert(val.IsNumber());
    assert(val.GetNumber() == num);
  }
  {
    const double num = 0.0 / 0.0;
    const Val<std::string> val(num);
    assert(val.IsNumber());
    assert(std::isnan(val.GetNumber()));
  }
  return 0;
}

doubleの使っていないtagを使ってもいいし, pointerの下3bitの値を使ってtagを打ち, それに別の値を突っ込んでもいいですね(pointer以外).
また, DoubleOffsetをあふれるギリギリにして, Doubleのrangeを0xFFFFFFFFまで持っていけば, 下の方の連続領域をtagに使えます.
ただし, pointerは一種類しか入りません(きちんとtagを持った状態では. dirtyなものでいいならtagを打てるが, pointerがmodifyされるのでconservative GCが回収できなくなります. よってpointerを汚さず様々な種類のものを入れたければ, 共通の親をつくりそのpointerを格納して, member functionで分岐する形になります)

結論

というわけで32bitでも64bitでもJSValの値はpointerをmodifyせず64bitに入るのでした. (Solaris除く)
bugを見つけたら是非教えてください...

Remove all ads