DataType encoding that optimizes for type tests
Summary:
We represent DataType as a 3-of-7 balanced code, still using the lowest bit to mark counted types. See: https://en.wikipedia.org/wiki/Constant-weight_code
## Motivation
Our goal is performance. We want more efficient type checks. We also want to be able to check multiple types, or a type and a bespoke layout index, in one operation.
A **balanced code** is an error-correcting code where every codeword has the same **Hamming weight** - that is, the same number of 1 bits. Every balanced code is an **unordered code** - a code where no codeword's 1 bits are a strict subset of any other codeword's. An unordered code is useful for low-level programming because it is "test"-able. By that, we mean that every codeword `w` can be checked by and-ing with `~w` and checking that ZF is unset. The test operation composes nicely, allowing us to build up encodings with multiple, orthogonal codes and check all of them in one go. On x86, we can also take advantage of the immediate-to-memory variant of this op to save a load instruction.
In DataType alone, we can think of the "counted" low-bit is a simple second code. As an immediate benefit, this encoding allows us to check every type in exactly 2 instructions (test, jmpnz). By contrast, today, varray, vec, and dict type-tests require 4 instructions (load, mask, compare, jmpnz). The faster tests yield an instructions and CPU win.
The performance wins will be even bigger when we use this encoding to optimize BespokeArray layout checks, because we'll convert 5-instruction checks to a simple 2-instruction (test, jmpnz). Basically, a bespoke layout index will become a concatenation of several unordered codes, allowing for efficient tests of arbitrary hierarchy nodes.
## Implementation
We don't need to construct these codewords by hand. I've provided a constexpr function to produce these codewords and used it to keep DataType readable. This function will fail to compile when we run out of codewords. Right now, we still have space for 15 new DataTypes (that is, 15 new counted/uncounted pairs), which is a healthy buffer.
Finally, we need to patch places where we rely on the old encoding. I handled most of them in
D26021832 (https://github.com/facebook/hhvm/commit/
466d56da1c7c7d567393a38193723021e5a82b62),
D26022793 (https://github.com/facebook/hhvm/commit/
faae5a6208f22b33d29ca9e780ad774dc9eed181),
D26142971 (https://github.com/facebook/hhvm/commit/
c0327d935922b19ec5cbc7100ae96c7cd87fd296), and
D26143531. Here's what's left:
1. We change C++ type tests in datatype.h. array-like, "hasPersistentFlavor", and "isNull" are all comparisons. Every data-type-specific check is a simple test op!
1. We change the JIT versions of this logic in irlower-internal-inl. It's simpler, because we can handle all isKnownDataType() cases uniformly.
1. We must use the value of KindOfUninit in our assembly implement of NvGetStr. We create a macro for it (checked by a static_assert).
1. Finally, we fix a super-bogus reinterpret-cast-of-0-to-Variant in the sqlite extension.
Reviewed By: colavitam
Differential Revision:
D26020606
fbshipit-source-id:
1df4a7fa6495adc519b25c1721dae95d645e69a2