深入 V8 引擎:“小整数”到底有多小?

1,607 阅读3分钟
原文链接: zhuanlan.zhihu.com
原文:V8 Internals: How Small is a “Small Integer?”
作者:Franziska Hinkelmann
译者:justjavac(迷渡)

原文副标题:“When binary is useful outside of a coding interview”


V8 是谷歌的开源 JavaScript 引擎。Chrome,Node.js 和许多其他应用程序都使用了 V8 引擎。如果你曾经听过关于 V8 的演讲,或者读过关于 V8 的文章:Understanding V8’s Bytecode(中文:理解 V8 的字节码),你一定听说过 Smis小整数。本文通过深入 V8 的源代码,具体研究一下 Smis 到底有多大。

根据规范,JavaScript 并不知道整数(除了最近引入的 BigInts)(中文: BigInt:JavaScript 中的任意精度整数)。它只知道 IEEE 浮点数。但是许多操作都是基于整数,比如程序中的 for 循环。所有 JavaScript 引擎都有一个特殊的整数表示方式。V8 有所谓的 Smis 小整数。

Smis 在 64 位平台上的范围是 -2³¹ 到 2³¹-1(2³¹≈2*10⁹)。如果你查看 V8 源码,这可能并不是非常明显。kSmiMinValuekSmiMaxValueinclude/v8.h 中定义如下:

static const int kSmiMinValue = 
  (static_cast<unsigned int>(-1)) << (kSmiValueSize — 1);
static const int kSmiMaxValue = -(kSmiMinValue + 1);

它是如何等于 -2³¹ 和 2³¹-1 的呢?让我们将上面的 C++ 代码分解一下。

左移

<< 是按位左移运算。左移意味着我们将数字的二进制表示移到左边,并用零填充右边。例如,5<< 3 = 40

5 &amp;lt;&amp;lt; 3 = 40

您可能已经注意到了,正数的左移与乘以 2 相同。

静态转换为无符号整数

static_cast<unsigned int>(-1)

当我们将负值转换为无符号整数(即正数)时会发生什么?所有的二进制位保持不变,但值的表示却不同了。转换为无符号整数后,我们就可以把这个数作为正数来进行左移运算了。

那么 -1 的二进制表示是什么呢?在二进制补码中,-1 表示为 (111...111)_2 因为 2⁶³-2⁶²-2⁶¹- … -2²-2¹–1 = 1。

Three-bit signed integer in two&amp;#39;s complement representation.

放在一起

如果您查看 V8 源代码中的 definitions,您会发现在 64 位计算机上 kSmiValueSize 被定义为 32,于是:

kSmiMinValue =(static_cast<unsigned int>(-1)) << (kSmiValueSize — 1)
             = (111...111)_2 << (32-1) 
             = (111...111)_2 << 31
             = (11...1100...00)_2  // 31个零
             = -2^31

现在我们可以使用这个结果来对 kMaxValue 进行初始化。

int kSmiMaxValue = -(kSmiMinValue + 1);

显而易见,kSmiMaxValue = -(-2^31+1) = 2^31-1。在 64 位平台上 V8 对 Smis 定义的范围是 [-2³¹,2³¹-1]。

32 位平台

在 32 位平台上 kSmiValueSize = 31。所以我们把它换为 30,计算得到 kMinValue = -2^30。注意,2³⁰≈10⁹。

为什么 Smis 在 32 位平台上的范围要小一点呢?在引擎 内部,V8 使用最低有效位将所有 JavaScript 值标记为堆栈对象或者 Smis。如果最低有效位是 1,则是指针。如果是 0,则是 Smi。这意味着 32 位整数只能使用 31 位存储 Smi 值,因为一位(最低有效位)用作标记。

V8 使用最低有效位将所有值标记为 Smis 或堆指针。

其实 Smis 并没有你想象的那么小,但它们很容易以按位编码的方式来存储到 32 位或 64 位整数中。

附加题:给定一个非空的整数数组,其中某个元素只出现了一次,其余每个元素都出现了两次。找到那个唯一元素。您可以使用二进制表示方式,时间复杂度为 O(n),空间复杂度为 O(1),你能找到解决方案吗?

PS:很多人对文章的笔记感兴趣,小姐姐回复说,她使用的是 dotted Leuchturm1917Pigma Microns