Nan-boxing技術介紹，nan-boxing技術

Nan-boxing技術介紹，nan-boxing技術

　　NaN-boxing看起來像英文翻譯的“南拳”，其實它是表示一個無效的double數。NaN-boxing技術：通過一個64位的數字來表示多種數據類型的技術，它通過一個nan浮點數來保存數據，根據IEEE-754浮點數標准，double類型的NAN形式為：
sign
| exponent
|     |
[0][11111111111][yyyyxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx]
                              |      |
                            tag     |
                               payload
　　總共64位，最高位是一個符號位，可能是0也可能是，接下來的11位全部為1，則這個浮點數就是一個NAN，符號位如果為1則表示是一個quiet NAN，如果為1則表示是一個signed NAN。因此一個NAN只需要前面的12位來表示就行了，那麼剩下的52位則可以用來編碼，比如我們用剩下的52位中的前4位來表示一個數據的類型，後面的48位用來表示數據的值或地址。表示類型的4位我們稱為tag，它最多可以用來表示16種類型的數據，後面的48位我們稱為payload，用它來表示實際的數據或數據的地址，對於小於等於32位的數字可以直接存到payload中，對於其它類型的數據可以保存其地址到payload中，因為x86 32位和64位系統中，地址最多不超過47位，所以用48位來保存數據的地址是完全夠用的。
　　為了演示一下nan-boxing的應用，我寫一個簡單的例子來展示一下它是如何存儲數據的，看起來就像一個動態類型。

#pragma once
#include <cstddef>
#include <assert.h>
#include <cstdint>
using namespace std;

enum TypeTag {
    BOOL,
    INT32,
    UINT32,
    UINT64,
    INT64,
    DOUBLE,
    CHAR_ARRAY,
    STRING,
    NIL
};

#define PAYLOAD_MASK 0x00007FFFFFFFFFFFULL
#define NAN_MASK 0x7FF8000000000000ULL
#define TAG_MASK 0xF
#define TAG_SHIFT 47

union Value {
    uint64_t ival;
    double fval;

    Value(double x) : fval(x)
    {
    }

    Value(int v)
    {
        ival = NAN_MASK | ((uint64_t)INT32 << TAG_SHIFT) | (uint64_t)v;
    }
    Value(uint32_t v)
    {
        ival = NAN_MASK | ((uint64_t)UINT32 << TAG_SHIFT) | (uint64_t)v;
    }

    Value(int64_t v)
    {
        ival = static_cast<uint64_t>(v);
    }

    Value(uint64_t v)
    {
        ival = v;
    }

    Value(bool v)
    {
        ival = NAN_MASK | ((uint64_t)BOOL << TAG_SHIFT) | (uint64_t)v;
    }

    Value(const char* v)
    {
        ival = NAN_MASK | ((uint64_t)CHAR_ARRAY << TAG_SHIFT) | (uint64_t)v;
    }

    Value(const string& v)
    {
        ival = NAN_MASK | ((uint64_t)STRING << TAG_SHIFT) | (uint64_t)&v;
    }

    Value(TypeTag tag = NIL, void *payload = nullptr) {
        assert((uint64_t)payload <= PAYLOAD_MASK);
        ival = NAN_MASK | ((uint64_t)tag << TAG_SHIFT) | (uint64_t)payload;
    }

    int toInt() const
    {
        assert(getTag() == INT32);
        return (int)getPayload();
    }

    int64_t toInt64() const
    {
        return (int64_t)ival;
    }

    uint32_t toUInt() const
    {
        assert(getTag() == UINT32);
        return (int)getPayload();
    }

    uint64_t toUInt64() const
    {
        return ival;
    }

    bool toBool() const
    {
        assert(getTag() == BOOL);
        return getPayload() != 0;
    }

    double toDouble() const
    {
        assert(getTag() == DOUBLE);
        return fval;
    }

    char *toCharArray() const
    {
        assert(getTag() == CHAR_ARRAY);
        return (char *)getPayload();
    }

    string& toString() const
    {
        assert(getTag() == STRING);
        return *(string *)getPayload();
    }

    TypeTag getTag() const
    {
        return isPayload() ? DOUBLE : TypeTag((ival >> TAG_SHIFT) & TAG_MASK);
    }

    uint64_t getPayload() const
    {
        assert(!isPayload());
        return ival & PAYLOAD_MASK;
    }

    bool operator<(const Value& other)  const
    {
        return hash()<other.hash();
    }

    bool operator==(const Value& other)  const
    {
        return hash() == other.hash();
    }
private:
    bool isPayload() const
    {
        return (int64_t)ival <= (int64_t)NAN_MASK;
    }

    uint64_t toHashUInt64() const
    {
        assert(getTag() < INT64);
        if (getTag() == UINT64)
            return ival;

        return (uint64_t)getPayload();
    }

    int64_t toHashInt64() const
    {
        assert(getTag() == INT64);
        return toInt64();
    }

    std::size_t hash() const {
        switch (getTag()) {
        case         UINT64:
        case         INT32:
        case         UINT32:
        case           BOOL:
            return std::hash<uint64_t>()(toHashUInt64());
        case         INT64:
            return std::hash<int64_t>()(toHashInt64());
        case DOUBLE:
            return std::hash<double>()(toDouble());
        case STRING:
            return std::hash<std::string>()(toString());
        default:
            throw std::invalid_argument("can not find this type");
        }
    }
};

測試代碼：

void Test()
{
    Value t="a";
    cout << t.toCharArray() << endl;

    Value v = (int)2;
    auto r0 = v.toInt();

    Value v1 = (uint32_t)2;
    auto r1 = v1.toUInt();
    Value v2 = (int64_t)2;
    auto r2 = v2.toInt64();
    Value v3 = (uint64_t)2;
    auto r3 = v3.toUInt64();

    Value v4 = 2.5;
    auto r4 = v4.toDouble();

    string s1 = "a";
    Value v5 = s1;
    auto r5 = v5.toString();
    string s = r5;

    Value b = false;
    bool r = b.toBool();
    b = true;
    r = b.toBool();
}

　　通過nan-boxing技術，Value可以表示多種類型了，比如int double string等類型，這個Value看起來像一個動態類型了。這一切都很簡單，看起來似乎很好，但是這只是我們玩了一個小把戲而已，就是把值或地址放到payload中了，這存在一個很大的問題：即存放在payload中的地址需要保證有效性，如果存放一個臨時變量的地址就悲劇了，尤其是對於非數字類型來說，比如string或者一個自定義類型，這時我們需要在外面保證這些變量的生命周期了，這極大的影響了Value的使用。解決這個問題的辦法有兩個，一個是自定義類型的話就new出來，然後自己去管理其生命周期；另外一個方法是通過一個內存池來創建對象，通過內存池來保持對象地址的有效性。

　　nan-boxing技術最開始是亞馬遜的工程師應用到javascript的引擎中的，luajit和rubyjit也用它作為動態類型來存儲數據，我相信nan-boxing技術還有很多應用場景，比如可以用它來表示json的value等等，本文的目的是拋磚引玉，關於它更多的具體應用我希望更多的人能去深入研究。