SIMD (Single Instruction Multiple Data) is a technology that uses a single controller to manage multiple processors, executing the same operation on each element of a set of data (also known as a “data vector”), thereby achieving spatial parallelism. It is an important means of program acceleration. This article will briefly introduce some basic knowledge required for using compilers for automatic vectorization in TiFlash.
Introduction to SIMD
SIMD is an important means of program acceleration. The CMU DB group has dedicated two chapters in Advanced Database Systems (vectorization-1, vectorization-2) to the application of SIMD vectorization in databases, highlighting its significance in modern database systems.
Currently, TiFlash supports x86-64 and Aarch64 architectures, with operating system platforms including Linux and MacOS. Due to the constraints of platform ISA and operating system API, different environments may encounter various challenges in implementing SIMD support.
X86-64
Traditionally, we divide the x86-64 platform into four levels:
- x86-64: CMOV, CMPXCHG8B, FPU, FXSR, MMX, FXSR, SCE, SSE, SSE2
- x86-64-v2: (close to Nehalem) CMPXCHG16B, LAHF-SAHF, POPCNT, SSE3, SSE4.1, SSE4.2, SSSE3
- x86-64-v3: (close to Haswell) AVX, AVX2, BMI1, BMI2, F16C, FMA, LZCNT, MOVBE, XSAVE
- x86-64-v4: AVX512F, AVX512BW, AVX512CD, AVX512DQ, AVX512VL
Each level has different extended instruction set support. The current situation is that the target compiled by TiFlash on x86-64 is x86-64-v2, while most home and server CPUs now support x86-64-v3. Due to Intel’s current updates to big.LITTLE architecture, support for x86-64-v4 is relatively chaotic, but newer server models generally include varying degrees of AVX512 support. In AWS’s support matrix, we can see that third-generation Xeon Scalable processors and other models supporting AVX512 have already been adopted in production environments.The costs of the same extended instruction set across different CPU architectures on x86-64 also vary. Generally, we can briefly view the CPI information of related instructions on different microarchitectures in the Intel Intrinsic Guide. For platform-specific optimization, one can read platform-related Tuning Guides and Performance Analysis Papers, INTEL® ADVANCED VECTOR EXTENSIONS, and Intel® 64 and IA-32 Architectures Software Developer Manuals (Software Optimization Reference Manual series) to obtain official recommendations from Intel.How to choose between SSE, AVX/AVX2, and AVX512? In fact, newer technology and wider bit widths do not necessarily yield better results. For example, in section 2.8 of INTEL® ADVANCED VECTOR EXTENSIONS, we can see that mixing traditional SSE and AVX instruction sets can lead to what is known as the SSE-AVX Transition Penalty:
On the other hand, both AVX2 and AVX512 have corresponding Frequency Scaling issues. Cloudflare’s articles On the dangers of Intel’s frequency scaling and Gathering Intel on Intel AVX-512 Transitions analyze this issue. In simple terms, AVX-512 can improve performance in intensive computing, during which CPU frequency decreases, but vectorization itself greatly enhances speed. However, if AVX512 is mixed with ordinary instructions in non-intensive scenarios, we can imagine the performance loss caused by frequency reduction.On Intel platforms, the SIMD instruction sets correspond to registers like XMM, YMM, ZMM, etc. We can use the gdb command:
#!/usr/bin/env bash
args=(-batch -ex "file $1")
while IFS= read -r line;
do
args+=("-ex" "disassemble '$line'")
done < <(nm --demangle $1 | grep $2 | cut -d\ -f3-)
gdb "
${args[@]}" | c++filt
# bash ./this-script.sh tiflash xxx
#!/usr/bin/env bash
# LLDB version
args=(--batch -o "file $1")
while IFS= read -r line;
do
args+=("-o" "disassemble -F intel -n '$line'")
done < <(nm --defined-only --demangle $1 | grep $2 | cut -d\ -f3-)
lldb "
${args[@]}" | c++filt
# bash ./this-script.sh tiflash xxx
Aarch64
In the Arm world, there are also inconsistencies in platform vectorization instruction set support. Arm V8 has currently refined eight versions:
In terms of SIMD, Aarch64 mainly has two or three instruction sets: ASIMD, SVE, and SVE2. ASIMD is already widely used; in fact, GCC/Clang will enable ASIMD support by default. In Arm V8, SVE is generally not implemented in A Profile but is used in specialized CPUs for HPC, etc. In Arm V9, SVE and SVE2 have become standard extended instruction sets.ASIMD describes fixed-length vector operations, operating on 64bit and 128bit registers, functionally similar to the SSE series. SVE, on the other hand, uses variable-length vectors, and vendors can provide ultra-wide registers up to 2048bit. Using a Per-Lane Prediction scheme, the SVE instruction set establishes a programming model that does not require knowledge of the actual register width.
In practical applications, AWS C7g (based on AWS Graviton3) has started to support the SVE instruction set, with a maximum width of 256bit. ASIMD has good implementations on CPUs such as Kunpeng and AWS Graviton2.On AARCH64, common ASIMD-related registers are q0-q15, which sometimes also appear in ASM as v0-v15. SVE uses z0-z15.
SIMD Function Dispatching Scheme
The CD Pipeline of TiFlash generates a unified binary package for each OS/Arch combination for release, so the overall compilation target is relatively general architecture. However, SIMD instruction sets differ across platforms, so we need some schemes to dispatch vectorized functions. Below are two main types of schemes: runtime and load time. Overall, the following conditions can be referenced for selection:
- If you want to support non-Linux targets and the operation itself takes relatively long, not caring about one or two additional branches, runtime dispatch can be used. In this case, TiFlash provides a runtime switch for the corresponding vectorization scheme, making functionality more controllable.
- If the operation is used extremely frequently and branches may affect performance, load time dispatch should be prioritized. TiFlash basically uses Linux in production environments, so only a default version of the function can be provided for MacOS.
Runtime Dispatch
This scheme is relatively simple. In common/detect_features.h, TiFlash provides a scheme to check specific CPU features. We can write a runtime check for functionality and then decide the function entry of the specific implementation scheme. This scheme is suitable for cases where the vectorized operation is known to take a relatively long time, compared to the dispatch cost that can be ignored.Observe the following code:
__attribute__((target("avx512f"))) void test4096_avx512(bool * __restrict a, const int * __restrict b)
{
for (int i = 0; i < 4096; ++i)
{
a[i] = b[i] > 0;
}
}
__attribute__((target("avx2"))) void test4096_avx2(bool * __restrict a, const int * __restrict b)
{
for (int i = 0; i < 4096; ++i)
{
a[i] = b[i] > 0;
}
}
__attribute__((noinline)) void test4096_generic(bool * __restrict a, const int * __restrict b)
{
for (int i = 0; i < 4096; ++i)
{
a[i] = b[i] > 0;
}
}
void test4096(bool * __restrict a, const int * __restrict b)
{
if (common::cpu_feature_flags.avx512f)
{
return test4096_avx512(a, b);
}
if (common::cpu_feature_flags.avx2)
{
return test4096_avx2(a, b);
}
return test4096_generic(a, b);
}
We can see that the function entry is to detect features and call the corresponding platform implementation:
And the specific functions have corresponding vectorization optimizations
In fact, for this kind of dispatching of the same function body, TiFlash has already provided a wrapped macro, and the above code can be written as:
#include <Common/TargetSpecific.h>
TIFLASH_DECLARE_MULTITARGET_FUNCTION(
/* return type */ void,
/* function name */ test4096,
/* argument names */ (a, b),
/* argument list */ (bool * __restrict a, const int * __restrict b),
/* body */ {
for (int i = 0; i < 4096; ++i)
{
a[i] = b[i] > 0;
}
})
IFUNC Dispatching
On Linux, observe the symbol table of Glibc:
We can see that some performance-critical functions are marked with the i symbol. This indicates that these functions are indirect functions: the program can provide multiple implementations of a function, and during the program loading and linking phase, ld determines which specific implementation the target symbol links to. Glibc uses this scheme to decide the implementations of critical functions such as memcpy/memcmp/memset.test4096 can be rewritten as:
void test4096(bool * __restrict a, const int * __restrict b) __attribute__((ifunc("test4096_resolver")));
extern "C" void * test4096_resolver()
{
if (__builtin_cpu_supports("avx512f"))
return reinterpret_cast<void *>(&test4096_avx512);
if (__builtin_cpu_supports("avx2"))
return reinterpret_cast<void *>(&test4096_avx2);
return reinterpret_cast<void *>(&test4096_generic);
}
This scheme reduces the overhead of runtime dispatch but has certain limitations:
- It is only applicable to GNU/Linux platforms
- The resolver of ifunc must be within the current unit. If the resolver is a C++ function, the mangled name must be provided.
- The resolver executes before entering C runtime and C++ runtime, and cannot use TiFlash’s detection functions. On x86_64 platforms, __builtin_cpu_supports can be used; on aarch64, the following scheme can be used:
#include <sys/auxv.h>
#ifndef HWCAP2_SVE2
#define HWCAP2_SVE2 (1 << 1)
#endif
#ifndef HWCAP_SVE
#define HWCAP_SVE (1 << 22)
#endif
#ifndef AT_HWCAP2
#define AT_HWCAP2 26
#endif
#ifndef AT_HWCAP
#define AT_HWCAP 16
#endif
namespace detail
{
static inline bool sve2_supported()
{
auto hwcaps = getauxval(AT_HWCAP2);
return (hwcaps && HWCAP2_SVE2) != 0;
}
static inline bool sve_supported()
{
auto hwcaps = getauxval(AT_HWCAP);
return (hwcaps && HWCAP_SVE) != 0;
}
} // namespace detail
Another interesting example is that if you need to read function variables in the resolver, you may need to manually initialize the environ pointer:
extern char** environ;
extern char **_dl_argv;
char** get_environ() {
int argc = *(int*)(_dl_argv - 1);
char **my_environ = (char**)(_dl_argv + argc + 1);
return my_environ;
}
typedef typeof(f1) * resolve_f() {
environ = get_environ();
const char *var = getenv("TOTO");
if (var && strcmp(var, "ok") == 0) {
return f2;
}
return f1;
}
int f() __attribute__((ifunc("resolve_f")));
Function Multiversioning Dispatch
On x86-64, Clang/GCC actually provides a more convenient implementation scheme for IFUNC:
#include <iostream>
__attribute__((target("avx512f"))) void test4096(bool * __restrict a, const int * __restrict b)
{
std::cout << "using avx512" << std::endl;
for (int i = 0; i < 4096; ++i)
{
a[i] = b[i] > 0;
}
}
__attribute__((target("avx2"))) void test4096(bool * __restrict a, const int * __restrict b)
{
std::cout << "using avx2" << std::endl;
for (int i = 0; i < 4096; ++i)
{
a[i] = b[i] > 0;
}
}
__attribute__((target("default"))) void test4096(bool * __restrict a, const int * __restrict b)
{
std::cout << "using default" << std::endl;
for (int i = 0; i < 4096; ++i)
{
a[i] = b[i] > 0;
}
}
int main() {
bool results[4096];
int data[4096];
for (auto & i : data) {
std::cin >> i;
}
test4096(results, data);
for (const auto & i : results) {
std::cout << i << std::endl;
}
}
Here, we do not need to distinguish between function names and provide a resolver; instead, we directly mark different targets, and the compiler will automatically generate the implementation of ifunc.
Macro Integration
We can use the following code to integrate the IFUNC-based schemes on x86-64 and aarch64:
#ifdef __linux__
#include <sys/auxv.h>
#ifndef HWCAP2_SVE2
#define HWCAP2_SVE2 (1 << 1)
#endif
#ifndef HWCAP_SVE
#define HWCAP_SVE (1 << 22)
#endif
#ifndef AT_HWCAP2
#define AT_HWCAP2 26
#endif
#ifndef AT_HWCAP
#define AT_HWCAP 16
#endif
namespace detail
{
static inline bool sve2_supported()
{
auto hwcaps = getauxval(AT_HWCAP2);
return (hwcaps && HWCAP2_SVE2) != 0;
}
static inline bool sve_supported()
{
auto hwcaps = getauxval(AT_HWCAP);
return (hwcaps && HWCAP_SVE) != 0;
}
} // namespace detail
#endif
#define TMV_STRINGIFY_IMPL(X) #X
#define TMV_STRINGIFY(X) TMV_STRINGIFY_IMPL(X)
#define TIFLASH_MULTIVERSIONED_VECTORIZATION_X86_64(RETURN, NAME, ARG_LIST, ARG_NAMES, BODY) \
struct NAME##TiFlashMultiVersion \
{ \
__attribute__((always_inline)) static inline RETURN inlined_implementation ARG_LIST BODY; \
\
__attribute__((target("default"))) static RETURN dispatched_implementation ARG_LIST \
{ \
return inlined_implementation ARG_NAMES; \
}; \
\
__attribute__((target("avx"))) static RETURN dispatched_implementation ARG_LIST \
{ \
return inlined_implementation ARG_NAMES; \
}; \
\
__attribute__((target("avx2"))) static RETURN dispatched_implementation ARG_LIST \
{ \
return inlined_implementation ARG_NAMES; \
}; \
\
__attribute__((target("avx512f,avx512vl,avx512bw,avx512cd"))) static RETURN dispatched_implementation ARG_LIST \
{ \
return inlined_implementation ARG_NAMES; \
}; \
\
__attribute__((always_inline)) static inline RETURN invoke ARG_LIST \
{ \
return dispatched_implementation ARG_NAMES; \
}; \
};
#define TIFLASH_MULTIVERSIONED_VECTORIZATION_AARCH64(RETURN, NAME, ARG_LIST, ARG_NAMES, BODY) \
struct NAME##TiFlashMultiVersion \
{ \
__attribute__((always_inline)) static inline RETURN inlined_implementation ARG_LIST BODY; \
\
static RETURN generic_implementation ARG_LIST \
{ \
return inlined_implementation ARG_NAMES; \
}; \
\
__attribute__((target("sve"))) static RETURN sve_implementation ARG_LIST \
{ \
return inlined_implementation ARG_NAMES; \
}; \
\
__attribute__((target("sve2"))) static RETURN sve2_implementation ARG_LIST \
{ \
return inlined_implementation ARG_NAMES; \
}; \
\
static RETURN dispatched_implementation ARG_LIST \
__attribute__((ifunc(TMV_STRINGIFY(__tiflash_mvec_##NAME##_resolver)))); \
\
__attribute__((always_inline)) static inline RETURN invoke ARG_LIST \
{ \
return dispatched_implementation ARG_NAMES; \
}; \
}; \
extern "C" void * __tiflash_mvec_##NAME##_resolver() \
{ \
if (::detail::sve_supported()) \
{ \
return reinterpret_cast<void *>(&NAME##TiFlashMultiVersion::sve_implementation); \
} \
if (::detail::sve2_supported()) \
{ \
return reinterpret_cast<void *>(&NAME##TiFlashMultiVersion::sve2_implementation); \
} \
return reinterpret_cast<void *>(&NAME##TiFlashMultiVersion::generic_implementation); \
}
#if defined(__linux__) && defined(__aarch64__)
#define TIFLASH_MULTIVERSIONED_VECTORIZATION TIFLASH_MULTIVERSIONED_VECTORIZATION_AARCH64
#elif defined(__linux__) && defined(__x86_64__)
#define TIFLASH_MULTIVERSIONED_VECTORIZATION TIFLASH_MULTIVERSIONED_VECTORIZATION_X86_64
#else
#define TIFLASH_MULTIVERSIONED_VECTORIZATION(RETURN, NAME, ARG_LIST, ARG_NAMES, BODY) \
struct NAME##TiFlashMultiVersion \
{ \
__attribute__((always_inline)) static inline RETURN invoke ARG_LIST BODY; \
};
#endif
TIFLASH_MULTIVERSIONED_VECTORIZATION(
int,
sum,
(const int * __restrict a, int size),
(a, size),
{
int sum = 0;
for (int i = 0; i < size; ++i) {
sum += a[i];
}
return sum;
}
)
Compiler-Oriented Optimization
LLVM provides a great automatic vectorization guide: Auto-Vectorization in LLVM – LLVM 15.0.0git documentation. You can refer to the chapters in it to understand which common patterns can be used for vectorization. In simple terms, we can think about loop scenarios: can unnecessary control flow be simplified, can opaque function calls be reduced, etc. In addition, it can also be considered that for some simple function definitions, if they will be called in a large number of consecutive times, can we define the function in the header so that the compiler can see it and inline these functions, thereby enhancing the vectorization space.As Donald Knuth said, premature optimization is the root of all evil. There is no need to rewrite some non-performance-critical loops into vectorization-friendly forms just for vectorization. Using a profiler to decide which functions to further optimize is a better choice.
Checking Vectorization Conditions
We use the following parameters to check the vectorization process:
<span>-Rpass-missed='.*vectorize.*'</span>checks why the compiler failed to vectorize successfully<span>-Rpass='.*vectorize.*'</span>checks which vectorizations the compiler has performed
Specifically, in TiFlash, we first extract the compilation instructions of a certain object file
cat compile_commands.json | grep "/VersionFilterBlockInputStream.cpp"
Then, add -Rpass-missed=’.*vectorize.*’ or -Rpass=’.*vectorize.*’ before the compilation instructions to view the relevant information.
Loop Unrolling Pragma
The following pragma can be used to control loop unrolling strategies to assist vectorization
void test1(int * a, int *b, int *c) {
#pragma clang loop unroll(full)
for(int i = 0; i < 1024; ++i) {
c[i] = a[i] + b[i];
}
}
void test2(int * a, int *b, int *c) {
#pragma clang loop unroll(enable)
for(int i = 0; i < 1024; ++i) {
c[i] = a[i] + b[i];
}
}
void test3(int * a, int *b, int *c) {
#pragma clang loop unroll(disable)
for(int i = 0; i < 1024; ++i) {
c[i] = a[i] + b[i];
}
}
void test4(int * a, int *b, int *c) {
#pragma clang loop unroll_count(2)
for(int i = 0; i < 1024; ++i) {
c[i] = a[i] + b[i];
}
}
Vectorization Pragma
The following pragma can suggest clang to perform vectorization.
static constexpr int N = 4096;
int A[N];
int B[N];
struct H {
double a[4];
H operator*(const H& that) {
return {
a[0] * that.a[0],
a[1] * that.a[1],
a[2] * that.a[2],
a[3] * that.a[3],
};
}
};
H C[N];
H D[N];
H E[N];
void test1() {
#pragma clang loop vectorize(enable)
for (int i=0; i < N; i++) {
C[i] = D[i] * E[i];
}
}
void test2() {
for (int i=0; i < N; i++) {
C[i] = D[i] * E[i];
}
}
In fact, on Aarch64, the getDelta in TiFlash is not vectorized by default, while using hints can allow it.If these pragmas want to be used inside macros, they can be changed to _Pragma(“clang loop vectorize(enable)”) form.
Loop Splitting
Reusing the previous example
void x() {
#pragma clang loop vectorize(enable)
for (int i=0; i < N; i++) {
A[i + 1] = A[i] + B[i];
C[i] = D[i] * E[i];
}
}
void y() {
for (int i=0; i < N; i++) {
A[i + 1] = A[i] + B[i];
}
#pragma clang loop vectorize(enable)
for (int i=0; i < N; i++) {
C[i] = D[i] * E[i];
}
}
In function x, vectorization is not performed because there is data dependency in A. In function y, after splitting the two loops, the latter loop can be vectorized. In practical cases, if the scalar operation C[i] = D[i] * E[i] takes relatively long, splitting the loop in this way is quite meaningful.Theoretically
#pragma clang loop distribution(enable)
can automatically handle the corresponding situation, but even using this pragma, clang will still be relatively conservative.
Controlling Vectorization Strategies
Adjusting Unit Vector Size
void test(char *x, char *y, char * z) {
#pragma clang loop vectorize_width(8)
for (int i=0; i < 4096; i++) {
x[i] = y[i] * z[i];
}
}
For example, on Aarch64, vectorize_width(1) means no vectorization, vectorize_width(8) means using 64bit registers, and vectorize_width(16) means using 128bit registers.In addition, you can also use vectorize_width(fixed) or vectorize_width(scalable) to adjust the tendency towards fixed-length and variable-length vectors.
Adjusting Vectorization Batch Size
You can suggest to the compiler to increase the loop batch size during vectorization using interleave_count(4). Increasing the batch size within a certain range can promote processor utilization of superscalar and out-of-order execution for acceleration.
void test(char *x, char *y, char * z) {
#pragma clang loop vectorize_width(8) interleave_count(4)
for (int i=0; i < 4096; i++) {
x[i] = y[i] * z[i];
}
}
Extracting Fixed-Length Loop Units
The following function is used to confirm the first visible column in the column store of the database:
const uint64_t* filterRow(
const uint64_t* data,
size_t length,
uint64_t current_version) {
for(size_t i = 0; i < length; ++i) {
if (data[i] > current_version) {
return data + i;
}
}
return nullptr;
}
It cannot be vectorized because there is a control flow that jumps out inside the loop.In this case, you can manually extract a segment of the loop to help the compiler with automatic vectorization:
const uint64_t* filterRow(
const uint64_t* data,
size_t length,
uint64_t current_version) {
size_t i = 0;
for(; i + 64 < length; i += 64) {
uint64_t mask = 0;
#pragma clang loop vectorize(enable)
for (size_t j = 0; j < 64; ++j) {
mask |= data[i + j] > current_version ? (1ull << j) : 0;
}
if (mask) {
return data + i + __builtin_ctzll(mask);
}
}
for(; i < length; ++i) {
if (data[i] > current_version) {
return data + i;
}
}
return nullptr;
}
(__builtin_ctzll is a compiler built-in function used to calculate the number of trailing zeros in an integer, which can generally be translated efficiently into a single instruction)Related ReadingIn-Depth Analysis of TiFlash丨Blocking Issues in Thread Creation and Release Under Concurrent AccessTiFlash Function Pushdown Must-Know丨Become a TiFlash Contributor in Ten Minutes💡 Tip: Due to WeChat subscription accounts not supporting external link redirection, you can click the end of the article【Read the Original】to visit the official website to view the content linked in blue.