Go Metrics SDK Tag 校驗(yàn)性能優(yōu)化實(shí)踐
背景
Metrics SDK 是與字節(jié)內(nèi)場(chǎng)時(shí)序數(shù)據(jù)庫(kù) ByteTSD 配套的用戶(hù)指標(biāo)打點(diǎn) SDK，在字節(jié)內(nèi)數(shù)十萬(wàn)服務(wù)中集成，應(yīng)用廣泛，因此 SDK 的性能優(yōu)化是個(gè)重要和持續(xù)性的話(huà)題。
用戶(hù)在使用 SDK API 進(jìn)行打點(diǎn)時(shí)，需要傳入指標(biāo)對(duì)應(yīng)的 Tag：
tags := []m.T{{Name: "foo", Value: "a"}, {Name: "bar", Value: "b"}}
metric.WithTags(tags...).Emit(m.Incr(1))SDK 內(nèi)部需要對(duì)用戶(hù)傳入的 Tag Value 的合法性進(jìn)行校驗(yàn)，IsValidTagValue，是 SDK 中對(duì) Tag Value 進(jìn)行字符合法性校驗(yàn)的 util 函數(shù)，在對(duì)內(nèi)部一些用戶(hù)的業(yè)務(wù)使用 pprof 拉取 profile 時(shí)，發(fā)現(xiàn)這兩個(gè)函數(shù)的 CPU 消耗占整個(gè)打點(diǎn) API 過(guò)程的10%~20%，由于該函數(shù)發(fā)生在打點(diǎn) API 的 hot-path 上，因此有必要對(duì)其進(jìn)行進(jìn)一步優(yōu)化。
圖片
分析
當(dāng)前實(shí)現(xiàn)
我們先看一下 IsValidTagValue 函數(shù)內(nèi)部的實(shí)現(xiàn)方式，是否有可優(yōu)化的點(diǎn)。當(dāng)前的實(shí)現(xiàn)，對(duì)于通過(guò) API 傳入的每一個(gè)Tag Value，會(huì)進(jìn)行以下操作來(lái)判斷其合法性：
- 先判斷是否是在 Letter、Number 的范圍內(nèi)，是則直接通過(guò)；
- 存儲(chǔ)所有允許的特殊字符白名單，遍歷 Tag Value 對(duì)比其每個(gè)字符是否在白名單內(nèi)。
var (
// these runes are valid in tag values
whiteListRunes = []rune{'_', '-', '.', '%', ':', ' ', '[', ']', ',', '%',
'/', ':', ';', '<', '=', '>', '@', '~'}
)
func IsValidTagValue(s string) bool {
if len(s) == 0 || len(s) > maxTagLen {
return false
}
for i, r := range s {
if r < minValidChar || r > maxValidChar {
return false
}
if unicode.IsLetter(r) || unicode.IsNumber(r) || isRuneInWhiteList(r) {
continue
}
return false
}
return true
}該實(shí)現(xiàn)的時(shí)間復(fù)雜度簡(jiǎn)單分析如下：
O(n.)n : stringlength
對(duì)于全由特殊字符構(gòu)成的字符串，其時(shí)間復(fù)雜度是:
O(m * n)n : stringlength, m : whitelistlength
整個(gè)字符串的時(shí)間復(fù)雜度將介于O(n)到O(m * n)之間
問(wèn)題點(diǎn)
可以看到，從當(dāng)前實(shí)現(xiàn)看，一個(gè)主要影響性能的點(diǎn)是白名單列表的循環(huán)遍歷對(duì)比操作，我們需要考慮可能的優(yōu)化方式來(lái)降低這個(gè)操作的時(shí)間復(fù)雜度。
優(yōu)化
優(yōu)化一：使用 Lookup Table，空間換時(shí)間
Metrics SDK 所有允許的合法的字符，實(shí)際上是 ASCII 的一個(gè)子集，也就是說(shuō)其所有可能的字符最多只有128個(gè)，因此，我們可以通過(guò)空間換時(shí)間的方式，將對(duì)白名單的 O(n) 遍歷操作轉(zhuǎn)換為 O(1) 的查表操作：
- 提前對(duì)這128個(gè)字符建立一個(gè)包含128個(gè)成員的數(shù)組，在每一個(gè) offset 上標(biāo)記對(duì)應(yīng)字符是否合法(合法則標(biāo)記為
1)，這樣就建立了一個(gè)快速的 lookup table - 對(duì)于要校驗(yàn)的每一個(gè)字符，只要將其轉(zhuǎn)化為數(shù)組 offset，直接取數(shù)組成員值判斷是否為
1即可
image.png
table := [128]uint8{...}
// fill flags
for i := 0; i < 128; i++ {
if unicode.IsNumber(rune(i)) || unicode.IsLetter(rune(i)) || isRuneInWhiteList(rune(i)) {
table[i] = 1
}
}
str := "hello"
for _, char := range []byte(str) {
if r > maxValidChar {
return false
}
if table[char] != 1 {
return false
}
}
return trueBenchmark
goos: linux
goarch: amd64
pkg: code.byted.org/gopkg/metrics_core/utils
cpu: Intel(R) Xeon(R) Platinum 8260 CPU @ 2.40GHz
BenchmarkLookupAlgoValid
BenchmarkLookupAlgoValid/baseline
BenchmarkLookupAlgoValid/baseline-8 2839345 478.9 ns/op
BenchmarkLookupAlgoValid/lookup-arraytable
BenchmarkLookupAlgoValid/lookup-arraytable-8 6673456 167.8 ns/op可以看到，速度提升60%
優(yōu)化二：使用 SIMD，提升并行度
基于 Lookup Table 的校驗(yàn)方式，將字符串校驗(yàn)的時(shí)間復(fù)雜度穩(wěn)定在了O(n)n : stringlength， 但有沒(méi)有可能進(jìn)一步減少對(duì)字符串每一個(gè)字符的遍歷次數(shù)，比如一次校驗(yàn)16個(gè)字符？
我們知道，SIMD 指令是循環(huán)展開(kāi)優(yōu)化的常用思路，那么這里是否可以引入 SIMD 來(lái)進(jìn)一步提升運(yùn)算并行度和效率？
答案是肯定的，以 intel x86 架構(gòu)為例，參考其 Intrinsics Guide，在不同的 SIMD 指令集上提供了多個(gè)可以實(shí)現(xiàn)在不同大小的 lookup table 中查找數(shù)據(jù)的指令，這些指令可以作為我們加速方案的基礎(chǔ)：
圖片
注：可以通過(guò)
cat /proc/cpuinfo命令來(lái)查看機(jī)器支持的simd指令集
鑒于 vpermi2b 指令的支持目前不是很普遍的原因，我們考慮使用 pshufb 來(lái)實(shí)現(xiàn)一個(gè) SIMD 版本，但我們的Lookup Table 需要調(diào)整下，因?yàn)椋?/p>
- 雖然我們基于 bitmap 實(shí)現(xiàn)的 Lookup Table 是 128 bits，剛好可以填充 128 bits 的寄存器
- 但 pshufb 是按字節(jié)進(jìn)行 lookup 的，128 bits 的寄存器支持16字節(jié)的 lookup
因此，我們需要將 bitmap lookup table 做一次升維，變成一個(gè)16*8 bits 的二維 lookup table，做兩次遞進(jìn)的行、列 lookup 完成查找，基于該思路，可以實(shí)現(xiàn)一次校驗(yàn)16個(gè)字符，大大提升并行度。
整體方案
該方案主要參考這篇文章：SIMDized check which bytes are in a set(http://0x80.pl/articles/simd-byte-lookup.html)
構(gòu)建 bitmap table
對(duì)于一個(gè) ASCII 字符，我們用其低 4bits 作為 lookup table 的 row index，用高 3bits 作為 lookup table 的 column index，這樣對(duì)128個(gè) ASCII 字符建立如下的一個(gè)二維 bitmap table：
圖片
Lookup 流程
我們先實(shí)現(xiàn)一個(gè)純 go 語(yǔ)言版本的基于二維 bitmap lookup table 的方案，以便于理解其中的關(guān)鍵邏輯：
table := [16]uint8{}
// fill flags
for i := 0; i < 128; i++ {
if unicode.IsNumber(rune(i)) || unicode.IsLetter(rune(i)) || isRuneInWhiteList(rune(i)) {
lowerNibble := i & 0x0f
upperNibble := i >> 4
table[lowerNibble] |= 1 << upperNibble
}
}
str := "hello"
for _, char := range []byte(str) {
if r > maxValidChar {
return false
}
lowerNibble := uint8(r) & 0x0f
upperNibble := uint8(r) >> 4
if table[lowerNibble]&(1<<upperNibble) == 0 {
return false
}
}
return true如上代碼示例，可以看到，判斷某個(gè)字符合法的關(guān)鍵邏輯是：
- 通過(guò) table[lowerNibble] 獲取table第 lowerNibble 行內(nèi)容，然后再看其第 upperNibble 個(gè) bit 位是否為0
而 SIMD 版本，即是將上述的每一步操作都使用對(duì)應(yīng)的 SIMD 指令變成對(duì)16個(gè)字節(jié)的并行操作，SIMD 的關(guān)鍵操作流程以及和上述 go 代碼的對(duì)應(yīng)關(guān)系如下：
圖片
代碼實(shí)現(xiàn)
在 go 語(yǔ)言中，想要使用 SIMD，需要寫(xiě) plan9 匯編，而編寫(xiě) plan9 通常有兩種方式：
- 手撕，可借助 avo 這樣的工具
- C code 轉(zhuǎn) plan9，可借助 goat、c2goasm 這樣的工具
這里采用 C code 轉(zhuǎn) plan9 的方式，先寫(xiě)一個(gè) C 版本：
注：由于 goat 工具限制，不能很好的支持 C 代碼中的常量定義，因此以下示例通過(guò)函數(shù)參數(shù)定義用到的 sm、hm 常量
#include <tmmintrin.h>
// is_valid_string returns 1 if all chars is in table, returns 0 else.
void is_valid_string(char* table, char* strptr, long strlen, char* sm, char* hm, char* rt) {
__m128i bitmap = _mm_loadu_si128((__m128i*)table);
__m128i shift_mask = _mm_loadu_si128((__m128i*)sm);
__m128i high_mask = _mm_loadu_si128((__m128i*)hm);
size_t n = strlen/16;
for (size_t i = 0; i < n; i++)
{
__m128i input = _mm_loadu_si128((__m128i*)strptr);
__m128i rows = _mm_shuffle_epi8(bitmap, input);
__m128i hi_nibbles = _mm_and_si128(_mm_srli_epi16(input, 4), high_mask);
__m128i cols = _mm_shuffle_epi8(shift_mask, hi_nibbles);
__m128i tmp = _mm_and_si128(rows, cols);
__m128i result = _mm_cmpeq_epi8(tmp, cols);
size_t mask = _mm_movemask_epi8(result);
if (mask != 65535) {
*rt = 0;
return;
}
strptr = strptr + 16;
}
size_t left = strlen%16;
for (size_t i = 0; i < left; i++)
{
size_t lower = strptr[i] & 0x0f;
size_t higher = strptr[i] >> 4;
if ((table[lower] & (1<<higher)) == 0) {
*rt = 0;
return;
}
}
*rt = 1;
return;
}通過(guò)以下命令轉(zhuǎn)為 plan9:
goat is_valid_string.c -03 -mssse3生成的 plan9 代碼如下：
//go:build !noasm && amd64
// AUTO-GENERATED BY GOAT -- DO NOT EDIT
TEXT ·_is_valid_string(SB), $0-48
MOVQ table+0(FP), DI
MOVQ strptr+8(FP), SI
MOVQ strlen+16(FP), DX
MOVQ sm+24(FP), CX
MOVQ hm+32(FP), R8
MOVQ rt+40(FP), R9
WORD $0x8949; BYTE $0xd2 // movq %rdx, %r10
LONG $0x3ffac149 // sarq $63, %r10
LONG $0x3ceac149 // shrq $60, %r10
WORD $0x0149; BYTE $0xd2 // addq %rdx, %r10
LONG $0x0f428d48 // leaq 15(%rdx), %rax
LONG $0x1ff88348 // cmpq $31, %rax
JB LBB0_4
LONG $0x076f0ff3 // movdqu (%rdi), %xmm0
LONG $0x096f0ff3 // movdqu (%rcx), %xmm1
LONG $0x6f0f41f3; BYTE $0x10 // movdqu (%r8), %xmm2
WORD $0x894d; BYTE $0xd0 // movq %r10, %r8
LONG $0x04f8c149 // sarq $4, %r8
WORD $0xc031 // xorl %eax, %eax
LBB0_2:
LONG $0x1e6f0ff3 // movdqu (%rsi), %xmm3
LONG $0xe06f0f66 // movdqa %xmm0, %xmm4
LONG $0x00380f66; BYTE $0xe3 // pshufb %xmm3, %xmm4
LONG $0xd3710f66; BYTE $0x04 // psrlw $4, %xmm3
LONG $0xdadb0f66 // pand %xmm2, %xmm3
LONG $0xe96f0f66 // movdqa %xmm1, %xmm5
LONG $0x00380f66; BYTE $0xeb // pshufb %xmm3, %xmm5
LONG $0xe5db0f66 // pand %xmm5, %xmm4
LONG $0xe5740f66 // pcmpeqb %xmm5, %xmm4
LONG $0xccd70f66 // pmovmskb %xmm4, %ecx
LONG $0xfffff981; WORD $0x0000 // cmpl $65535, %ecx
JNE LBB0_8
LONG $0x10c68348 // addq $16, %rsi
LONG $0x01c08348 // addq $1, %rax
WORD $0x394c; BYTE $0xc0 // cmpq %r8, %rax
JB LBB0_2
LBB0_4:
LONG $0xf0e28349 // andq $-16, %r10
WORD $0xb041; BYTE $0x01 // movb $1, %r8b
WORD $0x294c; BYTE $0xd2 // subq %r10, %rdx
JE LBB0_9
WORD $0xc031 // xorl %eax, %eax
LBB0_7:
LONG $0x1cbe0f4c; BYTE $0x06 // movsbq (%rsi,%rax), %r11
WORD $0x8945; BYTE $0xda // movl %r11d, %r10d
LONG $0x0fe28341 // andl $15, %r10d
LONG $0x04ebc141 // shrl $4, %r11d
LONG $0x0cbe0f42; BYTE $0x17 // movsbl (%rdi,%r10), %ecx
LONG $0xd9a30f44 // btl %r11d, %ecx
JAE LBB0_8
LONG $0x01c08348 // addq $1, %rax
WORD $0x3948; BYTE $0xd0 // cmpq %rdx, %rax
JB LBB0_7
LBB0_9:
WORD $0x8845; BYTE $0x01 // movb %r8b, (%r9)
BYTE $0xc3 // retq
LBB0_8:
WORD $0x3145; BYTE $0xc0 // xorl %r8d, %r8d
WORD $0x8845; BYTE $0x01 // movb %r8b, (%r9)
BYTE $0xc3 // retq對(duì)應(yīng)的 Go Wrapper 代碼如下：
var (
// these runes are valid in tag values
whiteListRunes = []rune{'_', '-', '.', '%', ':', ' ', '[', ']', ',', '%',
'/', ':', ';', '<', '=', '>', '@', '~'}
rcBitTable [16]uint8
smTable [16]int8
hmTable [16]uint8
)
//go:noescape
func _is_valid_string(table unsafe.Pointer, str unsafe.Pointer, len int32, sm, hm unsafe.Pointer, rt unsafe.Pointer)
func init() {
// build tables
for i := 0; i < 128; i++ {
if unicode.IsNumber(rune(i)) || unicode.IsLetter(rune(i)) || isRuneInWhiteList(rune(i)) {
lowerNibble := i & 0x0f
upperNibble := i >> 4
rcBitTable[lowerNibble] |= 1 << upperNibble
}
}
smTable = [16]int8{1, 2, 4, 8, 16, 32, 64, -128, 1, 2, 4, 8, 16, 32, 64, -128}
hmTable = [16]uint8{0x0f, 0x0f, 0x0f, 0x0f, 0x0f, 0x0f, 0x0f, 0x0f, 0x0f, 0x0f, 0x0f, 0x0f, 0x0f, 0x0f, 0x0f, 0x0f}
}
func IsValidTagValueLookup2dBitTableSIMD(s string) bool {
l := len(s)
if l == 0 || len(s) > maxTagLen {
return false
}
sptr := unsafe.Pointer((*reflect.StringHeader)(unsafe.Pointer(&s)).Data)
var rt byte
_is_valid_string(unsafe.Pointer(&rcBitTable), sptr, int32(len(s)), unsafe.Pointer(&smTable), unsafe.Pointer(&hmTable), unsafe.Pointer(&rt))
return rt != 0
}Benchmark
- 先做一個(gè)通用的 benchmark，待校驗(yàn)的 string 長(zhǎng)度從1 ~ 20不等：
goos: linux
goarch: amd64
pkg: code.byted.org/gopkg/metrics_core/utils
cpu: Intel(R) Xeon(R) Platinum 8260 CPU @ 2.40GHz
BenchmarkLookupAlgoValid
BenchmarkLookupAlgoValid/baseline
BenchmarkLookupAlgoValid/baseline-8 2574217 510.5 ns/op
BenchmarkLookupAlgoValid/lookup-arraytable
BenchmarkLookupAlgoValid/lookup-arraytable-8 6347204 193.7 ns/op
BenchmarkLookupAlgoValid/lookup-2d-bittable-simd
BenchmarkLookupAlgoValid/lookup-2d-bittable-simd-8 6133671 185.2 ns/op可以看到，SIMD 版本在平均水平上與 arraytable 相當(dāng)
- 由于 SIMD 優(yōu)勢(shì)主要體現(xiàn)在長(zhǎng)字符串時(shí)，因此，我們使用一組長(zhǎng)度為20左右的 string，再次 benchmark:
goos: linux
goarch: amd64
pkg: code.byted.org/gopkg/metrics_core/utils
cpu: Intel(R) Xeon(R) Platinum 8260 CPU @ 2.40GHz
BenchmarkLookupAlgoValidLong
BenchmarkLookupAlgoValidLong/baseline
BenchmarkLookupAlgoValidLong/baseline-8 3523198 356.4 ns/op
BenchmarkLookupAlgoValidLong/lookup-arraytable
BenchmarkLookupAlgoValidLong/lookup-arraytable-8 8434142 153.3 ns/op
BenchmarkLookupAlgoValidLong/lookup-2d-bittable-simd
BenchmarkLookupAlgoValidLong/lookup-2d-bittable-simd-8 13621970 87.29 ns/op可以看到，在長(zhǎng) string 上 SIMD 版本表現(xiàn)出非常大的優(yōu)勢(shì)，相對(duì)于 arraytable 版本再次提升50%
結(jié)論
- 通過(guò) lookup table + SIMD 的方式優(yōu)化，字符校驗(yàn)的整體性能可以提升2~4倍
- 但由于在 Go 中 plan9 匯編無(wú)法內(nèi)聯(lián)，因此在待校驗(yàn)的字符串較短時(shí)不能體現(xiàn)其優(yōu)勢(shì)
