Go Metrics SDK Tag 校驗性能優化實踐

作者：郭剛平 2023-10-30 16:14:44

本文主要以 Go Metrics SDK 為例，講述對打點 API 的 hot-path 優化的實踐。

背景

Metrics SDK 是與字節內場時序數據庫 ByteTSD 配套的用戶指標打點 SDK，在字節內數十萬服務中集成，應用廣泛，因此 SDK 的性能優化是個重要和持續性的話題。

用戶在使用 SDK API 進行打點時，需要傳入指標對應的 Tag：

tags := []m.T{{Name: "foo", Value: "a"}, {Name: "bar", Value: "b"}}
metric.WithTags(tags...).Emit(m.Incr(1))

SDK 內部需要對用戶傳入的 Tag Value 的合法性進行校驗，IsValidTagValue，是 SDK 中對 Tag Value 進行字符合法性校驗的 util 函數，在對內部一些用戶的業務使用 pprof 拉取 profile 時，發現這兩個函數的 CPU 消耗占整個打點 API 過程的10%~20%，由于該函數發生在打點 API 的 hot-path 上，因此有必要對其進行進一步優化。

圖片

分析

當前實現

我們先看一下 IsValidTagValue 函數內部的實現方式，是否有可優化的點。當前的實現，對于通過 API 傳入的每一個Tag Value，會進行以下操作來判斷其合法性：

先判斷是否是在 Letter、Number 的范圍內，是則直接通過；
存儲所有允許的特殊字符白名單，遍歷 Tag Value 對比其每個字符是否在白名單內。

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
}

該實現的時間復雜度簡單分析如下：

O(n.)n : stringlength

對于全由特殊字符構成的字符串，其時間復雜度是:

O(m * n)n : stringlength, m : whitelistlength

整個字符串的時間復雜度將介于O(n)到O(m * n)之間

問題點

可以看到，從當前實現看，一個主要影響性能的點是白名單列表的循環遍歷對比操作，我們需要考慮可能的優化方式來降低這個操作的時間復雜度。

優化

優化一：使用 Lookup Table，空間換時間

Metrics SDK 所有允許的合法的字符，實際上是 ASCII 的一個子集，也就是說其所有可能的字符最多只有128個，因此，我們可以通過空間換時間的方式，將對白名單的 O(n) 遍歷操作轉換為 O(1) 的查表操作：

提前對這128個字符建立一個包含128個成員的數組，在每一個 offset 上標記對應字符是否合法(合法則標記為1)，這樣就建立了一個快速的 lookup table
對于要校驗的每一個字符，只要將其轉化為數組 offset，直接取數組成員值判斷是否為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 true

Benchmark

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%

優化二：使用 SIMD，提升并行度

基于 Lookup Table 的校驗方式，將字符串校驗的時間復雜度穩定在了O(n)n : stringlength，但有沒有可能進一步減少對字符串每一個字符的遍歷次數，比如一次校驗16個字符？

我們知道，SIMD 指令是循環展開優化的常用思路，那么這里是否可以引入 SIMD 來進一步提升運算并行度和效率？

答案是肯定的，以 intel x86 架構為例，參考其 Intrinsics Guide，在不同的 SIMD 指令集上提供了多個可以實現在不同大小的 lookup table 中查找數據的指令，這些指令可以作為我們加速方案的基礎：

圖片

注：可以通過 cat /proc/cpuinfo 命令來查看機器支持的simd指令集

鑒于 vpermi2b 指令的支持目前不是很普遍的原因，我們考慮使用 pshufb 來實現一個 SIMD 版本，但我們的Lookup Table 需要調整下，因為：

雖然我們基于 bitmap 實現的 Lookup Table 是 128 bits，剛好可以填充 128 bits 的寄存器
但 pshufb 是按字節進行 lookup 的，128 bits 的寄存器支持16字節的 lookup

因此，我們需要將 bitmap lookup table 做一次升維，變成一個16*8 bits 的二維 lookup table，做兩次遞進的行、列 lookup 完成查找，基于該思路，可以實現一次校驗16個字符，大大提升并行度。

整體方案

該方案主要參考這篇文章：SIMDized check which bytes are in a set(http://0x80.pl/articles/simd-byte-lookup.html)

構建 bitmap table

對于一個 ASCII 字符，我們用其低 4bits 作為 lookup table 的 row index，用高 3bits 作為 lookup table 的 column index，這樣對128個 ASCII 字符建立如下的一個二維 bitmap table：

圖片

Lookup 流程

我們先實現一個純 go 語言版本的基于二維 bitmap lookup table 的方案，以便于理解其中的關鍵邏輯：

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

如上代碼示例，可以看到，判斷某個字符合法的關鍵邏輯是：

通過 table[lowerNibble] 獲取table第 lowerNibble 行內容，然后再看其第 upperNibble 個 bit 位是否為0

而 SIMD 版本，即是將上述的每一步操作都使用對應的 SIMD 指令變成對16個字節的并行操作，SIMD 的關鍵操作流程以及和上述 go 代碼的對應關系如下：

圖片

代碼實現

在 go 語言中，想要使用 SIMD，需要寫 plan9 匯編，而編寫 plan9 通常有兩種方式：

手撕，可借助 avo 這樣的工具
C code 轉 plan9，可借助 goat、c2goasm 這樣的工具

這里采用 C code 轉 plan9 的方式，先寫一個 C 版本：

注：由于 goat 工具限制，不能很好的支持 C 代碼中的常量定義，因此以下示例通過函數參數定義用到的 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;
}

通過以下命令轉為 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

對應的 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

先做一個通用的 benchmark，待校驗的 string 長度從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 相當

由于 SIMD 優勢主要體現在長字符串時，因此，我們使用一組長度為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

可以看到，在長 string 上 SIMD 版本表現出非常大的優勢，相對于 arraytable 版本再次提升50%

結論

通過 lookup table + SIMD 的方式優化，字符校驗的整體性能可以提升2~4倍
但由于在 Go 中 plan9 匯編無法內聯，因此在待校驗的字符串較短時不能體現其優勢

責任編輯：龐桂玉來源：字節跳動技術團隊

Metrics SD 數據庫

成人免费xxxxx在线视频软件_久久精品久久久_亚洲国产精品久久久_天天色天天色_亚洲人成一区_欧美一级欧美三级在线观看

Go Metrics SDK Tag 校驗性能優化實踐

背景

分析

當前實現

問題點

優化

優化一：使用 Lookup Table，空間換時間

Benchmark

優化二：使用 SIMD，提升并行度

整體方案

構建 bitmap table

Lookup 流程

代碼實現

Benchmark

結論