摘要 Abstract
动态多态语言在运行时对象中必须附加类型等信息,并因此调整值的内存布局以包含这些信息的空间。这使得高效实现IEEE754浮点数变得困难,因为该格式未预留容易访问的空间存储类型信息。目前广泛使用的两种浮点数编码方式——标记指针和NaN boxing都存在缺点:标记指针需要对所有浮点对象进行堆分配,而NaN boxing会增加类型检查以及处理其他对象的运行时开销。本文提出了一种名为自标记的新方法,可以在N位对象中附加易于访问的类型信息的同时保留其全部N位用于数据存储。自标记的核心思想是利用某些比特序列出现频率较高的特性,通过叠加这些频繁出现的序列来在同一N位机器字中同时编码N位数据和类型信息。这种方法的主要应用是分别在64位和32位机器上表示IEEE754 64位和32位浮点数。我们已经在一种JavaScript编译器和两种不同的Scheme编译器中实现了相关的自标记变体,以分析其性能并与其他方法(如标记指针和NaN boxing)进行比较。实验结果表明,该方法在实践中消除了IEEE754浮点数的堆分配,使Scheme中浮点密集型基准测试的执行时间提高了2.4倍,JavaScript中提高了3.6倍,而对其他基准测试的影响可以忽略不计,使其成为标记指针和NaN boxing的良好替代方案。
Dynamic and polymorphic languages must attach information, such as types, to run time objects, and therefore adapt the memory layout of values to include space for this information. It makes it difficult to implement efficiently IEEE754 floating-point numbers as this format does not leave an easily accessible space to store the type information. The two main floating-point number encodings in-use to this day, tagged pointers and NaN-boxing, have drawbacks. Tagged pointers entail a heap-allocation of all float objects, and NaN-boxing puts additional run time costs on type checks and the handling of all other objects. This paper presents self-tagging, a new approach to object tagging that can attach easily accessible type information to N-bit objects while retaining the ability to use all of their N bits for data. At its core, self-tagging exploits the fact that some bit sequences appear with high probability. Superimposing tags with these frequent sequences allows encoding both N-bit data and type within a single N-bit machine word. The main application of this approach is to represent IEEE754 64-bit and 32-bit floating point numbers on 64-bit and 32-bit machines respectively. We have implemented related variants of self-tagging in one JavaScript compiler and two distinct Scheme compilers to analyze their performance and compare them to tagged pointers and NaN-boxing. Our experiments demonstrate that in practice the approach eliminates heap-allocation of IEEE754 floating-point numbers and improves the execution time of float-intensive benchmarks in Scheme by 2.4$\times$, and in JavaScript by 3.6$\times$, with a negligible performance impact on other benchmarks, which makes it a good alternative to both tagged pointers and NaN-boxing.