The original:
V8 Internals: How Small is a “Small Integer?”


By Franziska Hinkelmann


Translator: JustJavac

When Binary is useful Outside of a coding interview

V8 is Google’s open source JavaScript engine. Chrome, Node.js, and many other applications use V8. If you’ve ever heard a talk about V8, or read an article about V8: Understanding V8’s Bytecode, you’ve probably heard of Smis, small integers. This article takes a closer look at just how big Smis really is by digging into V8’s source code.

According to the spec, JavaScript does not know about integers (except for the recently introduced BigInts). It only knows IEEE floating point numbers. But many operations are based on integers, such as the for loop in the program. All JavaScript engines have a special integer representation. V8 has what are called Smis small integers.

Smis ranges from -2³¹ to 2³¹-1 (2³¹≈2*10⁹) on 64-bit platforms. This may not be obvious if you look at the V8 source code. KSmiMinValue and kSmiMaxValue are defined in include/v8.h as follows:

Static const int kSmiMinValue = (static_cast<unsigned int>(-1)) << (kSmiValueSize -1); static const int kSmiMaxValue = -(kSmiMinValue + 1);Copy the code

How is it equal to minus 2 cubed ¹ and 2 cubed ¹-1? Let’s break down the C++ code above.

Shift to the left

<< is bitwise shift left. Moving to the left means that we move the binary representation of the number to the left and fill the right with zeros. For example, 5<< 3 = 40.

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

You may have noticed that a positive shift to the left is the same as multiplying by 2.

Statically converted to an unsigned integer

static_cast<unsigned int>(-1)
Copy the code

What happens when we convert a negative value to an unsigned integer (that is, a positive number)? All the bits remain the same, but the representation of the values is different. Once converted to an unsigned integer, we can shift the number to the left as a positive number.

So what’s the binary representation of minus one? In the binary complement, -1 is represented by (111… 111)_2 because 2⁶³-2⁶²-2⁶¹-… – 2 squared – creates 2-1 = 1.

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

Put together

If you look at definitions in the V8 source code, you’ll see that kSmiValueSize is defined as 32 on 64-bit computers, so:

KSmiMinValue =(static_cast<unsigned int>(-1)) << (kSmiValueSize -- 1) =(static_cast<unsigned int>(-1)) 111)_2 << (32-1) = (111... 111)_2 << 31 = (11... 1100... 00)_2 // 31 zeros = -2^31Copy the code

Now we can use this result to initialize kMaxValue.

int kSmiMaxValue = -(kSmiMinValue + 1);
Copy the code

KSmiMaxValue = -(-2^31+1) = 2^31-1. V8 defines Smis in the range of -2³¹, 2³¹-1 on 64-bit platforms.

A 32-bit platform

KSmiValueSize = 31 on 32-bit platforms. So let’s change it to 30, and we get kMinValue is equal to minus 2 to the 30. Note, 2³⁰≈10⁹.

Why is Smis smaller in scope on 32-bit platforms? Internally, V8 uses the least significant bits to mark all JavaScript values as stack objects or Smis. If the least significant bit is 1, it is a pointer. If it is 0, it is Smi. This means that 32-bit integers can only use 31 bits to store Smi values, because one (least significant bit) is used as a marker.

V8 uses the least significant bits to mark all values as Smis or heap Pointers.

Smis aren’t as small as you might think, but they can easily be stored in bit-encoded 32-bit or 64-bit integers.

Bonus: Given a non-empty array of integers, one element appears only once and every other element appears twice. Find that unique element. You can use binary representations with O(n) time and O(1) space. Can you find a solution?

PS: a lot of people were interested in the notes for the article, and little sister replied that she used dotted Leuchturm1917 and Pigma Microns.