64ビットポインタと浮動小数点数を上手く1つの64ビット値に詰め込む新しい手法“Self-Tagging” (NaN-boxingとかの代替手法)。

https://dl.acm.org/doi/10.1145/3763108

IEEE 754 64ビット浮動小数点数を使う多くのプログラムにおいて、扱う値のほとんどは指数部の上位3ビットが000, 011, 100のいずれかである。そこで浮動小数点数を4ビット左に回転した値としてエンコードすると下位3ビットで浮動小数点数とポインタを判別できる。それ以外の浮動小数点数はヒープに確保してポインタで参照する。

別種1: さらに000の場合は±0.0の場合がほとんどなのでそれを特別なボックス化した値とするとタグは2つにできる(ただし分岐ミスが増えるので遅くなる)。

別種2: 「指数部上位5ビットに1を足して中央3ビットを取ったもの」に注目すると000だけでそれなりに多くの場合をカバーできる。 エンコードは次の式でできる(ここでnはエンコードしたい値で、⊕はmod 2**64の加算で、tagは浮動小数点数に割り当てたいタグで、<<rotは左ビット回転): (n ⊕ ((1 + 2 × tag) << 58)) <<rot 5。

別種3: 別種2において(1 + 2 × tag) << 58ではなく(2 × tag) << 58とした上でtagとtag - 1を浮動小数点数に割り当てるとカバーする範囲を広げられる。その場合32ビット浮動小数点数全てをカバーできるようになる。

あとはx86_64やaarch64における具体的な実装方法とか。

ベンチマークはNaN-boxingやNuN-boxing (初めて知った)と比べて、ポインタ操作はやや速くなるけど浮動小数点数はやや遅くなる感じ? GCが多く発生するようなプログラムだとやや有利かも?

@tadd 既に知ってるかもだけど、NaN-boxingの代替手法の論文が出てる: https://dl.acm.org/doi/10.1145/3763108 概要は返信元ポストにまとめた。