• http://sourceforge.jp/magazine/10/05/10/0748222

Emacs23.2リリースを知りました。最大バッファサイズが2倍になったようです。デジャブです。23.1の時、バッファサイズが1ビット増えたのに続いてです。

23.1の時、バッファサイズが27ビット長の符号付き整数から28ビット長の符号付き整数に増えました。この秘密はSoftware Designの連載記事「Emacsのトラノマキ」に書いたので、ありえるえりあでの原稿公開(http://dev.ariel-networks.com/articles/emacs/)をお待ちください。

今回どのように1ビットを増やしたのでしょうか。

前提としてなぜ32ビットすべてを整数長に使えないかを説明します。次の理由です。

• オブジェクトのアドレスを8バイト境界に揃えているので、アドレス値として解釈する時、下位3ビットは無視できる
• ポインタが指すオブジェクトの型を、ポインタ値の空いた下位3ビットに載せる
• 整数オブジェクトは、ポインタ値をそのまま整数に解釈する(下位3ビットで整数型と判定できた場合)

初めて聞くと驚くようなハックですが、この技法はRubyやlibc(malloc)にも使われている意外に(?)伝統的な技です。

符号で1ビット、型で3ビット使うので、32ビットのうち残りは28ビットです。これが23.1の時の整数長でした。

ソースコードから関係のある部分のみを引用すると次になります。

/* emacs23.1 */
#define GCTYPEBITS 3
#define TYPEMASK ((((EMACS_INT) 1) << GCTYPEBITS) - 1)
#define XTYPE(a) ((enum Lisp_Type) (((EMACS_UINT) (a)) & TYPEMASK))
#define XINT(a) (((EMACS_INT) (a)) >> GCTYPEBITS)
#define make_number(N) (((EMACS_INT) (N)) << GCTYPEBITS)

GCTYPEBITSの値3が型情報3ビットに該当します。TYPEMASKの値を2進表記すると 111 で、これでマスクすると下位3ビットを得られます(XTYPEマクロ)。XINTとmake_numberマクロは逆のことをやっています。make_numberマクロは3ビット左にシフトしています。下位3ビット空ける処理です。

今回、更に1ビット稼いだ秘密は、3ビット使いながら実は識別している型の数が7つしかなかったことを利用しています。このヒントで答えがわかったら相当のバイナリ脳です。

上記で見たマクロがどう変わったかを見てみます。

/* emacs23.2 */
#define GCTYPEBITS 3
#define TYPEMASK ((((EMACS_INT) 1) << GCTYPEBITS) - 1)
#define XTYPE(a) ((enum Lisp_Type) (((EMACS_UINT) (a)) & TYPEMASK))
#ifdef USE_2_TAGS_FOR_INTS
# define XINT(a) (((EMACS_INT) (a)) >> (GCTYPEBITS - 1))
# define make_number(N) (((EMACS_INT) (N)) << (GCTYPEBITS - 1))

USE_2_TAGS_FOR_INTSの時に1ビット増えます。XTYPEマクロは下位3ビットをマスクする処理で変わっていません。XINTおよびmake_numberマクロのシフトするビット数が2ビットになっています(=GCTYPEBITS - 1)。これで使える数値の長さが1ビット増えます。

下位3ビットで型情報を載せているはずなのに、なぜ2ビットのシフトでいいかと言うと次のようになっているからです。以下の定義は3ビットで識別する型の一覧定義です。適当に改変して引用します。

#ifdef USE_2_TAGS_FOR_INTS
#  define LISP_INT1_TAG 4
#endif

enum Lisp_Type
  {
    /* Integer.  XINT (obj) is the integer value.  */
#ifdef USE_2_TAGS_FOR_INTS
    Lisp_Int0 = 0,
    Lisp_Int1 = LISP_INT1_TAG,
#else
    Lisp_Int = 0,
#endif

    /* Symbol.  XSYMBOL (object) points to a struct Lisp_Symbol.  */
    Lisp_Symbol = 2,

    /* Miscellaneous.  XMISC (object) points to a union Lisp_Misc,
       whose first member indicates the subtype.  */
    Lisp_Misc = 3,

    /* String.  XSTRING (object) points to a struct Lisp_String.
       The length of the string, and its contents, are stored therein.  */
    Lisp_String = LISP_STRING_TAG,

    /* Vector of Lisp objects, or something resembling it.
       XVECTOR (object) points to a struct Lisp_Vector, which contains
       the size and contents.  The size field also contains the type
       information, if it's not a real vector object.  */
    Lisp_Vectorlike = 5,

    /* Cons.  XCONS (object) points to a struct Lisp_Cons.  */
    Lisp_Cons = 6,

    Lisp_Float = 7,
  };

0と4、それぞれ2進数表記すると 000 と 100 のふたつを整数型にしています(Lisp_Int0とLisp_Int1)。元々、3ビットで7種類の識別だったのでひとつ空いていました。

000と100のどちらも整数型と判定するなら、下から3番目のビットは判定に不要です。これでシフトが2ビットで済むようになりました。

ビット演算は男らしくていいですね。