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

原文:V8 Internals: How Small is a “Small Integer?”

链接:https://medium.com/fhinkel/v8-internals-how-small-is-a-small-integer-e0badc18b6da

作者:Franziska Hinkelmann

译者:justjavac(迷渡)

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

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

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

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

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

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

左移

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

美高梅注册 1

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

静态转换为无符号整数

  1. static_cast<unsigned int>(-1)

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

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

美高梅注册 2

合在一起

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

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

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

  1. 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 使用最低有效位将所有 Java
值标记为堆栈对象或者 Smis。如果最低有效位是 1,则是指针。如果是 0,则是 Smi。这意味着 32 位整数只能使用 31
位存储 Smi值,因为一位(最低有效位)用作标记。

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

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

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

责任编辑:

相关文章