Float Self-Tagging（浮点自标记）

导读

这篇论文研究动态语言运行时中浮点数的表示问题：传统指针标记（pointer tagging）方案难以直接用于需要全部 64 位的浮点数。作者提出 float self-tagging，利用浮点数自身高位比特的分布规律，让相当一部分浮点数可以不加装箱（boxed）地以立即数形式存储，从而减少堆分配。

HN 关注点：是因为它与 NaN boxing / NaN tagging 等语言实现中的经典技巧直接相关，讨论焦点是这种方案是否真的比现有生产级实现更快。

关键词　浮点数表示pointer taggingNaN boxing动态语言实现

HN 评论精选

这几条评论里：质疑 2　补充 2

补充详细科普了论文核心思路：利用浮点数自身高位比特模式做自标记

我很喜欢这篇聪明又奇特的论文，简单总结一下。在许多动态语言中，有些值存放在堆上（boxed）并以指针表示，另一些则以立即数（unboxed）表示。指针标记是常见做法：用值的低位比特表示类型，某些类型是立即数，其他则是 boxed。标记位有固定值，不能存数据，比如你可能只有 61 位整数立即数而非 64 位。但浮点数需要全部 64 位，很难用这个策略（有个叫 NaN boxing 的技巧利用了浮点表示中大量的 NaN，详见论文）。作者的洞察是：假设用三位标记、011 表示浮点，随机情况下某些浮点数的低位恰好是 011，这些就可以直接作为带标记的立即数表示。当然概率很低，但可以用多个标记值提高几率。低位不是好选择，那高位呢？大多数浮点数的高位模式只有少数几种……

pavpanchekha查看英文原文

I loved this clever, weird, awesome paper, so a short summary. In many dynamic languages some values are stored on the heap ("boxed") and represented as a pointer, while others are represented as an immediate value ("unboxed" or "immediate"). Pointer tagging is a common way to do that: the low bit of the value tells you the value's type, and some types are immediate while others are boxed. Naturally, the tag bits have a fixed value, so can't be used to store data. So for example your language might offer 61-bit integer immediates instead of 64-bit integers; the other three bits are used for tags. Possibly, larger integers are stored on the heap and treated as a different type (for example Python 2.X had separate int and long types for these cases). However, it's hard to use this strategy for floats, because floats need all 64 bits (or 32 bits for single-precision, same difference). There's a trick called "NaN boxing" which makes use of the large number of NaNs in the float representation, but read the paper if you want more on that. The authors' insight is that, suppose you have a three-bit tag and 011 is the tag for floats. By totally random chance, _some_ floats will end in 011; you can represent those as immediates with those tag bits. Obviously, that's unlikely, though you can raise the chances by using, like, 010, 011, 100, and 101 all as float tags. Still, the low bits are a bad choice. But what about high bits? Most floats have one of a couple high bit patterns, because most floats are either 0 or between, say, 1e-100 and 1e100. Floats outside that range can be boxed but since they're really rare it's not a big cost to box them. So basically, we use high bits as our tag bits and map all the common float prefixes to float tags. This allows unboxing the vast majority of floats, which leads to big speedups on float-heavy benchmarks. A personal note: I've been working in numerics and floating-point for a decade now and have had to deal with float boxing both from a research point of view (lots of runtime analysis systems for floats), from a user point of view (using unboxed float vectors for significant speedup in my own software), and from a teaching point of view (discussing boxing in my compilers class, using NaN-boxing as an example of cleverness). This idea is so simple, so crazy, so stupid, and works so well, but I never thought of it. Bravo to the authors.

补充提出一个改进变体：用七个指数高位做标记，可省去旋转并支持 16 个标记

很酷的方案！一个问题：标记位似乎没有技术原因不能用整个指数位范围吧？只是 2048 个标记会导致分支太多。我想到一个变体：用最高的七个指数位代替三位，这样可以直接读 double 的最高字节，省去旋转操作。读出最高字节后减 16 并屏蔽符号位，若结果大于 15 则是未装箱的 double，否则低四位可用作替代标记（16 个标记）。这相当于把 2⁻⁷⁶⁷..2⁻⁵¹¹ 的指数范围映射为 boxed double，其余 15/16 的 double（包括 subnormal、零、所有 NaN 编码和无穷）都是未装箱的。当然这是即兴想法，可能有疏漏。

vanderZwan查看英文原文

Really cool solution! One question: maybe I missed it, but there's no technical reason the tag bits could not use the entire range of exponent bits, no? Other than the fact that having up to 2048 tags would be ridiculously branchy, I guess. Here's a variation I just thought of, which probably has a few footguns I'm overlooking right now: use the seven highest exponent bits instead of three. Then we can directly read the most significant byte of a double, skipping the need for a rotation altogether. After reading the most significant byte, subtract 16 (or 0b00010000) from it, then mask out the sign. To test for unboxed doubles, test if the resulting value is bigger than 15. If so, it is an unboxed double, otherwise the lower four bits of the byte are available as alternative tags (so 16 tags). Effectively, we adjusted the exponent range 2⁻⁷⁶⁷..2⁻⁵¹¹ into the 0b(0)0000000 - 0b(0)0001111 range and made them boxed doubles. Every other double, which is 15/16th of all possible doubles, is now unboxed. This includes subnormals, zero, all NaN encodings (so it even can exist in superposition with a NaN or NuN tagging system I guess?) and both infinities. To be clear, this is off the top of my head so maybe I made a few crucial mistakes here.

质疑质疑论文中关于栈地址超过 48 位的说法，与 x86-64 Linux 实际情况不符

论文说 NaN-tagging 会阻碍依赖栈分配的优化，因为栈使用的高地址无法放进 48 位。这说法有问题：在传统 x86-64 上所有指针都 fit 在 48 位内，栈也不例外。虽然架构后来扩展到 56 位指针，但据我所知 Linux 等系统默认在用户空间禁用（内核文档明确说默认不分配超过 47 位的虚拟地址空间）。栈地址怎么会超过 47 位？文档过时了吗？

comex查看英文原文

> For instance, NaN-tagging prevents (or largely complicates) optimizations relying on stack allocations. The stack uses high memory addresses that do not fit in 48 bits unless encoded relative to the location of the stack segment. Er, what? The paper says they tested on a Xeon CPU, so x86-64, running Linux. On traditional x86-64, all pointers fit in 48 bits, period. Stack memory is no exception. More recently the architecture was extended to allow 56-bit pointers, but my impression is that Linux (like other OSes) keeps them disabled by default in userspace. According to the documentation [1]: > Not all user space is ready to handle wide addresses. [..] To mitigate this, we are not going to allocate virtual address space above 47-bit by default. So how would the stack end up above 47 bits? Is the documentation out of date? [1] https://docs.kernel.org/arch/x86/x86_64/5level-paging.html

质疑JavaScriptCore 开发者质疑：对比对象是稻草人，未证明比生产级 NuN tagging 更快

我怀疑这实际上并不比 NaN（他们称之为 NuN）tagging 更快。他们给出的编解码代码序列比我预期的 NuN tagging 要差。要说服我，他们应该与生产级的 NuN tagging 实现做对比——做对它涉及 x86 上古怪的寄存器分配技巧和 arm 上极其小心的指令选择。他们似乎用了一个非常不标准的 JS NaN tagging 实现作为稻草人对比。（来源：我在 JavaScriptCore 中写了大量 NuN tagging 优化，但不是该技术的发明者。）

pizlonator查看英文原文

I doubt this is actually faster than NaN or why they call NuN tagging. The code sequences they cite for encoding and decoding are worse than what I expect NuN tagging to give you. If they want to convince me that their thing is faster, they should do a comparison against a production implementation of NuN tagging. Note that the specifics of getting it right involve wacky register allocation tricks on x86 and super careful instruction selection on arm. It seems that they use some very nonstandard JS implementation of NaN tagging as a strawman comparison. (Source: I wrote a lot of the NuN tagging optimizations in JavaScriptCore, but I didn’t invent the technique.)

历次讨论

2024Hacker News 讨论帖87 分 · 50 评
2024Hacker News 讨论帖170 分 · 2 评

HN 二十年，最值得读的论文。

朋友分享的书单

专题阅读路线

本周最多人读

我的书单

必读 30 篇

论文库

这些论文是怎么挑出来的

全量扫一遍

只留论文本身

写导读、译评论

Float Self-Tagging（浮点自标记）

导读

HN 评论精选

相关资源

历次讨论

同领域还值得读

Google 的软件工程（2017）

Peter Naur：编程作为理论构建 (1985)

SciPy 1.0：Python 科学计算的基础算法

Lisp 的历史（1979）

使用 NumPy 进行数组编程

打赏支持

关注向阳乔木