欧美人c交zoozooxx,欧美做受xxxxxⅹ性视频,日韩一卡2卡3卡新区乱码来袭

Gonum中內(nèi)積運(yùn)算Plan9匯編代碼如下：

#include "textflag.h"

#define HADDPS_SUM_SUM    LONG $0xC07C0FF2 // @ HADDPS X0, X0

#define X_PTR SI
#define Y_PTR DI
#define LEN CX
#define TAIL BX
#define IDX AX
#define SUM X0
#define P_SUM X1

// func DotUnitary32(x, y []float32) (sum float32)
TEXT ·DotUnitary32(SB), NOSPLIT, $0
  MOVQ    x_base+0(FP), X_PTR  // X_PTR = &x
  MOVQ    y_base+24(FP), Y_PTR // Y_PTR = &y
  PXOR    SUM, SUM             // SUM = 0
 MOVQ    x_len+8(FP), LEN     // LEN = min( len(x), len(y) )
 CMPQ    y_len+32(FP), LEN
   CMOVQLE y_len+32(FP), LEN
   CMPQ    LEN, $0
 JE      dot_end

 XORQ IDX, IDX
   MOVQ Y_PTR, DX
  ANDQ $0xF, DX    // Align on 16-byte boundary for MULPS
 JZ   dot_no_trim // if DX == 0 { goto dot_no_trim }
 SUBQ $16, DX

dot_align: // Trim first value(s) in unaligned buffer  do {
 MOVSS (X_PTR)(IDX*4), X2 // X2 = x[i]
  MULSS (Y_PTR)(IDX*4), X2 // X2 *= y[i]
 ADDSS X2, SUM            // SUM += X2
   INCQ  IDX                // IDX++
   DECQ  LEN
   JZ    dot_end            // if --TAIL == 0 { return }
   ADDQ  $4, DX
    JNZ   dot_align          // } while --DX > 0

dot_no_trim:
 PXOR P_SUM, P_SUM    // P_SUM = 0  for pipelining
   MOVQ LEN, TAIL
  ANDQ $0xF, TAIL      // TAIL = LEN % 16
 SHRQ $4, LEN         // LEN = floor( LEN / 16 )
 JZ   dot_tail4_start // if LEN == 0 { goto dot_tail4_start }

dot_loop: // Loop unrolled 16x  do {
    MOVUPS (X_PTR)(IDX*4), X2   // X_i = x[i:i+1]
  MOVUPS 16(X_PTR)(IDX*4), X3
 MOVUPS 32(X_PTR)(IDX*4), X4
 MOVUPS 48(X_PTR)(IDX*4), X5

 MULPS (Y_PTR)(IDX*4), X2   // X_i *= y[i:i+1]
  MULPS 16(Y_PTR)(IDX*4), X3
  MULPS 32(Y_PTR)(IDX*4), X4
  MULPS 48(Y_PTR)(IDX*4), X5

  ADDPS X2, SUM   // SUM += X_i
   ADDPS X3, P_SUM
 ADDPS X4, SUM
   ADDPS X5, P_SUM

 ADDQ $16, IDX // IDX += 16
  DECQ LEN
    JNZ  dot_loop // } while --LEN > 0

   ADDPS P_SUM, SUM // SUM += P_SUM
    CMPQ  TAIL, $0   // if TAIL == 0 { return }
 JE    dot_end

dot_tail4_start: // Reset loop counter for 4-wide tail loop
    MOVQ TAIL, LEN      // LEN = floor( TAIL / 4 )
  SHRQ $2, LEN
    JZ   dot_tail_start // if LEN == 0 { goto dot_tail_start }

dot_tail4_loop: // Loop unrolled 4x  do {
 MOVUPS (X_PTR)(IDX*4), X2 // X_i = x[i:i+1]
    MULPS  (Y_PTR)(IDX*4), X2 // X_i *= y[i:i+1]
   ADDPS  X2, SUM            // SUM += X_i
 ADDQ   $4, IDX            // i += 4
 DECQ   LEN
  JNZ    dot_tail4_loop     // } while --LEN > 0

dot_tail_start: // Reset loop counter for 1-wide tail loop
 ANDQ $3, TAIL // TAIL = TAIL % 4
    JZ   dot_end  // if TAIL == 0 { return }

dot_tail: // do {
   MOVSS (X_PTR)(IDX*4), X2 // X2 = x[i]
  MULSS (Y_PTR)(IDX*4), X2 // X2 *= y[i]
 ADDSS X2, SUM            // psum += X2
  INCQ  IDX                // IDX++
   DECQ  TAIL
  JNZ   dot_tail           // } while --TAIL > 0

dot_end:
   HADDPS_SUM_SUM        // SUM = \sum{ SUM[i] }
  HADDPS_SUM_SUM
  MOVSS SUM, sum+48(FP) // return SUM
 RET

?Golang如何調(diào)用Plan9匯編呢?

先將匯編函數(shù)保存到后綴為.s的匯編文件中。
然后在同級目錄下新建一個(gè).go文件，在文件中聲明函數(shù)，如以上匯編函數(shù)聲明如下，業(yè)務(wù)代碼直接調(diào)用該函數(shù)即可。

func DotUnitary32(x, y []float32) (sum float32)

Gonum的計(jì)算性能怎么樣呢？采用了并行計(jì)算，內(nèi)積運(yùn)算性能是原來的8倍，是滿足要求的，具體測試結(jié)果在2.4章節(jié)中會統(tǒng)一進(jìn)行對比測試。那既然性能滿足要求，是不是就可以了？

因?yàn)镚onum的計(jì)算函數(shù)有限，并不能完全覆蓋到我們需要的一些函數(shù)，如余弦和歐式距離計(jì)算，或者在標(biāo)準(zhǔn)的計(jì)算過程中加一些自定義的計(jì)算公式，Gonum是做不到的。

受到Gonum并行計(jì)算的啟發(fā)，想到是否可以使用SIMD（單指令多數(shù)據(jù)流）指令集來加速計(jì)算。

2.2 SIMD計(jì)算

SIMD單指令流多數(shù)據(jù)流(SingleInstruction Multiple Data,SIMD)是一種采用一個(gè)控制器來控制多個(gè)處理器，同時(shí)對一組數(shù)據(jù)（又稱“數(shù)據(jù)向量”）中的每一個(gè)分別執(zhí)行相同的操作從而實(shí)現(xiàn)空間上的并行性的技術(shù)。在微處理器中，單指令流多數(shù)據(jù)流技術(shù)則是一個(gè)控制器控制多個(gè)平行的處理微元，例如Intel的MMX或SSE以及AMD的3D Now!技術(shù)。

目前Intel處理器支持的SIMD技術(shù)包括MMX,SSE,AVX.，MMX提供了8個(gè)64bit的寄存器進(jìn)行SIMD操作，SSE系列提供了128bit的8個(gè)寄存器進(jìn)行SIMD指令操作，AVX指令則支持256bit的SIMD操作。目前SIMD指令可以有四種方法進(jìn)行使用分別是匯編語言，C++類，編譯器Intrisincs和自動(dòng)矢量化。SIMD intrinsics有些類似于C語言中的函數(shù)，可以被其它的代碼直接調(diào)用，相比匯編語言來說更容易使用。

Intel官網(wǎng)的SIMD intrinsics指令集查詢

https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html

為了使用與SIMD技術(shù)相關(guān)的intrinsics，首先需要包含那些定義了數(shù)據(jù)類型和函數(shù)的頭文件。

#include <mmintrin.h> //MMX   __m64 定義
#include <xmmintrin.h> //SSE(include mmintrin.h)    __m128  定義
#include <emmintrin.h> //SSE2(include xmmintrin.h)  __m128i ,__m128d 類型 定義
#include <pmmintrin.h> //SSE3(include emmintrin.h) 
#include <tmmintrin.h>//SSSE3(include pmmintrin.h) 
#include <smmintrin.h>//SSE4.1(include tmmintrin.h) 
#include <nmmintrin.h>//SSE4.2(include smmintrin.h) 
#include <wmmintrin.h>//AES(include nmmintrin.h) 
#include <immintrin.h>//AVX(include wmmintrin.h)  __m256 ,__m256i ,__m256d 類型定義
#include <intrin.h>//(include immintrin.h) 所有架構(gòu)

關(guān)鍵的SIMD AVX2指令集（256位寄存器），可以利用這些常見的指令進(jìn)行自定義計(jì)算。

__m256（聲明寄存器變量）
_mm256_loadu_ps（加載數(shù)據(jù)到寄存器）
_mm256_mul_ps（寄存器相乘）
_mm256_add_ps（寄存器相加）
_mm256_extractf128_ps（獲取高128位或低128位）
_mm_hadd_ps（水平相加，如x的第1位和第2位相加結(jié)果放在新數(shù)組第1位，y的第1位和第2位相加結(jié)果放在新數(shù)組第2位，然后x和y下標(biāo)移動(dòng)兩位依次重復(fù)以上操作將結(jié)果追加到新數(shù)組后面）
_mm_storeu_ps（取出寄存器值賦值）
_mm_sqrt_ps（開平方）
_mm_log1p_ps（log(1+p)）

查看機(jī)器支持的指令集兩種方式

lscpu // 查看flags標(biāo)志中支持的所有指令集
gcc -mavx2 -dM -E - < /dev/null|egrep AVX  // 查看是否支持AVX
gcc -msse4 -dM -E - < /dev/null|egrep SSE  // 查看是否支持SSE

2.2.1 內(nèi)積距離計(jì)算

使用SIMD AVX2指令進(jìn)行256維向量的內(nèi)積距離計(jì)算，計(jì)算公式如下：

SIMD代碼如下，256位寄存器一次可加載8個(gè)32位浮點(diǎn)數(shù)。

void VecInnerProductAVX2(const float* x, const float* y, float* z) {
    int d = 256;
    __m256 msum1 = _mm256_setzero_ps();
    // 加載數(shù)據(jù)并計(jì)算乘積和累計(jì)和
    while (d >= 8) {
        __m256 mx = _mm256_loadu_ps(x);
        x += 8;
        __m256 my = _mm256_loadu_ps(y);
        y += 8;
        msum1 = _mm256_add_ps(msum1, _mm256_mul_ps(mx, my));
        d -= 8;
    }
     // 將寄存器中的結(jié)果求和并賦值給新數(shù)組返回
    __m128 msum2 = _mm256_extractf128_ps(msum1, 1);
    msum2 = _mm_add_ps(msum2, _mm256_extractf128_ps(msum1, 0));

    msum2 = _mm_hadd_ps(msum2, msum2);
    msum2 = _mm_hadd_ps(msum2, msum2);
     _mm_storeu_ps(z, msum2);
}

2.2.2 歐式距離計(jì)算

使用SIMD AVX2指令進(jìn)行256維向量的歐式距離計(jì)算，計(jì)算公式如下：

SIMD代碼如下：

void VecEuclideanDistanceAVX2(const float* x, const float* y, float* z) {
    int d = 256;
    __m256 msum1 = _mm256_setzero_ps();
    // 加載數(shù)據(jù)并計(jì)算差值平方累計(jì)和
    while (d >= 8) {
        __m256 mx = _mm256_loadu_ps(x);
        x += 8;
        __m256 my = _mm256_loadu_ps(y);
        y += 8;
        __m256 sub = _mm256_sub_ps(mx, my);
        msum1 = _mm256_add_ps(msum1, _mm256_mul_ps(sub, sub));
        d -= 8;
    }
    // 將寄存器中的結(jié)果求和并開平方根，最終結(jié)果賦值給新數(shù)組返回
    __m128 msum2 = _mm256_extractf128_ps(msum1, 1);
    msum2 = _mm_add_ps(msum2, _mm256_extractf128_ps(msum1, 0));

    msum2 = _mm_hadd_ps(msum2, msum2);
    msum2 = _mm_hadd_ps(msum2, msum2);
    _mm_storeu_ps(z, _mm_sqrt_ps(msum2));
}

2.2.3 余弦距離計(jì)算

使用SIMD AVX2指令進(jìn)行256維向量的余弦距離計(jì)算，計(jì)算公式如下：

SIMD代碼如下：

void VecCosineAVX2(const float* x, const float* y, float* z) {
    int d = 256;
    __m256 msum1 = _mm256_setzero_ps();
    __m256 msumx = _mm256_setzero_ps();
    __m256 msumy = _mm256_setzero_ps();
     // 加載數(shù)據(jù)并計(jì)算x和y的內(nèi)積、模長
    while (d >= 8) {
        __m256 mx = _mm256_loadu_ps(x);
        x += 8;
        __m256 my = _mm256_loadu_ps(y);
        y += 8;
        msum1 = _mm256_add_ps(msum1, _mm256_mul_ps(mx, my));
        msumx = _mm256_add_ps(msumx, _mm256_mul_ps(mx, mx));
        msumy = _mm256_add_ps(msumy, _mm256_mul_ps(my, my));
        d -= 8;
    }
    // 將寄存器msum1中的內(nèi)積結(jié)果求和
    __m128 msum2 = _mm256_extractf128_ps(msum1, 1);
    msum2 = _mm_add_ps(msum2, _mm256_extractf128_ps(msum1, 0));
    msum2 = _mm_hadd_ps(msum2, msum2);
    msum2 = _mm_hadd_ps(msum2, msum2);
     // 將寄存器msumx中的x向量模長結(jié)果求和
    __m128 msumx2 = _mm256_extractf128_ps(msumx, 1);
    msumx2 = _mm_add_ps(msumx2, _mm256_extractf128_ps(msumx, 0));
    msumx2 = _mm_hadd_ps(msumx2, msumx2);
    msumx2 = _mm_hadd_ps(msumx2, msumx2);
     // 將寄存器msumy中的y向量模長結(jié)果求和
    __m128 msumy2 = _mm256_extractf128_ps(msumy, 1);
    msumy2 = _mm_add_ps(msumy2, _mm256_extractf128_ps(msumy, 0));
    msumy2 = _mm_hadd_ps(msumy2, msumy2);
    msumy2 = _mm_hadd_ps(msumy2, msumy2);
     // 根據(jù)內(nèi)積、x模長和y模長計(jì)算余弦距離
    __m128 result = _mm_div_ps(msum2, _mm_mul_ps(_mm_sqrt_ps(msumx2), _mm_sqrt_ps(msumy2)));
    _mm_storeu_ps(z, result);
}

一個(gè)寄存器一次加載8個(gè)32位的浮點(diǎn)數(shù)，理論上性能應(yīng)該是原來的8倍，實(shí)際上經(jīng)過測試這個(gè)猜想也得到了驗(yàn)證，詳細(xì)數(shù)據(jù)在2.4節(jié)中給出。

為什么這些函數(shù)不直接返回結(jié)果，而把結(jié)果存在一個(gè)數(shù)組中呢？若C或C++調(diào)用這些函數(shù)可以直接返回結(jié)果，但是若使用Golang進(jìn)行調(diào)用，需要進(jìn)行一些轉(zhuǎn)換，為什么要這么做？接下來將介紹Golang如何調(diào)用SIMD函數(shù)。

2.3 Golang調(diào)用SIMD

2.3.1 CGO調(diào)用

SIMD函數(shù)是使用C編寫的，Golang調(diào)用C函數(shù)，最容易想到的就是采用Golang提供的CGO方式進(jìn)行C函數(shù)調(diào)用。

/*
#cgo CFLAGS: -mavx2
#include <immintrin.h>

float vecInnerProduct(float* x, float* y) {
   // 此次省略內(nèi)積運(yùn)算過程，返回值可以直接返回，不用放到額外的數(shù)組中
   // _mm_storeu_ps(z, msum2);
   return _mm_cvtss_f32(msum2);
}
*/
import "C"

func VecInnerProductByCGo(userVector []float32, itemVector []float32) float32 {
    // Golang的floa和C的float互轉(zhuǎn)
    return float32(C.vecInnerProduct((*C.float)(&userVector[0]), (*C.float)(&itemVector[0])))
}

CGO這種方式確實(shí)是可以的，但是存在Golang和C之間不同語言的上下文切換，存在性能問題，肯定不能完全發(fā)揮出SIMD所能提升的8倍，經(jīng)過測試，CGO這種方式只能是未優(yōu)化的普通計(jì)算的2倍左右，這種方式不能滿足我們的業(yè)務(wù)需求，詳細(xì)數(shù)據(jù)在2.4節(jié)中給出。

2.3.1 Plan9匯編調(diào)用

Golang是可以直接調(diào)用Plan9匯編的，但是C寫的SIMD函數(shù)怎么轉(zhuǎn)Plan9匯編呢？

在Github上發(fā)現(xiàn)一個(gè)開源的項(xiàng)目c2goasm，它可以將C函數(shù)匯編轉(zhuǎn)成Plan9匯編，c2goasm的本質(zhì)也是調(diào)用asm2plan9s工具將C的匯編轉(zhuǎn)成Plan9匯編。

c2goasm項(xiàng)目地址：https://github.com/minio/c2goasm

asm2plan9s項(xiàng)目地址：https://github.com/minio/asm2plan9s

（1）C轉(zhuǎn)C匯編

可以將SIMD函數(shù)先使用Clang編譯成C的匯編，如將simd.c編譯成simd.s匯編，編譯命令如下：

clang -S -O1 -mavx2 -mfma -masm=intel -mno-red-zone -mstackrealign -mllvm -inline-threshold=1000 -fno-asynchronous-unwind-tables -fno-exceptions -fno-rtti -c simd.c -o simd.s

注意：

GCC優(yōu)化標(biāo)識必須為O1或者Os，否則最終的結(jié)果會不正確，關(guān)于編譯的代碼優(yōu)化標(biāo)識解釋，可以參考：https://blog.csdn.net/liang_baikai/article/details/110137374
安裝clang 7.0.0版本，可執(zhí)行文件在根目錄下的bin目錄，其它版本（高于10.0版本）可能不支持-masm=intel參數(shù)。下載鏈接：https://releases.llvm.org/download.html

SIMD內(nèi)積運(yùn)算的匯編代碼如下：

  .globl        VecInnerProductAVX2     # -- Begin function VecInnerProductAVX2
        .p2align        4, 0x90
        .type        VecInnerProductAVX2,@function
VecInnerProductAVX2:                    # @VecInnerProductAVX2
# %bb.0:
        push        rbp
        mov        rbp, rsp
        and        rsp, -8
        vxorps        xmm0, xmm0, xmm0
        mov        eax, 264
        xor        ecx, ecx
        .p2align        4, 0x90
.LBB1_1:                                # =>This Inner Loop Header: Depth=1
        vmovups        ymm1, ymmword ptr [rdi + rcx]
        vmulps        ymm1, ymm1, ymmword ptr [rsi + rcx]
        vaddps        ymm0, ymm0, ymm1
        add        rcx, 32
        add        eax, -8
        cmp        eax, 15
        ja        .LBB1_1
# %bb.2:
        vextractf128        xmm1, ymm0, 1
        vaddps        xmm0, xmm1, xmm0
        vhaddps        xmm0, xmm0, xmm0
        vhaddps        xmm0, xmm0, xmm0
        vmovups        xmmword ptr [rdx], xmm0
        mov        rsp, rbp
        pop        rbp
        vzeroupper
        ret
.Lfunc_end1:
        .size        VecInnerProductAVX2, .Lfunc_end1-VecInnerProductAVX2
                                        # -- End function

（2）C匯編轉(zhuǎn)Plan9匯編

1. 編譯c2goasm，生成可執(zhí)行文件c2goasm，并添加到PATH路徑。

git clone git@github.com:minio/c2goasm.git
go mod init c2goasm
go build

2. 下載asm2plan9s可執(zhí)行文件，并添加到PATH路徑。

go install github.com/minio/asm2plan9s

3. 使用c2goasm工具將SIMD的匯編文件simd.s轉(zhuǎn)成plan9匯編simd_avx2.s 。

c2goasm -a simd.s simd_avx2.s

4. 將SIMD內(nèi)積運(yùn)算的C匯編代碼通過c2goasm轉(zhuǎn)成Plan9匯編如下，默認(rèn)會在函數(shù)名前加一個(gè)下劃線。

TEXT ·_VecInnerProductAVX2(SB), $0-24

    MOVQ x+0(FP), DI
    MOVQ y+8(FP), SI
    MOVQ z+16(FP), DX

    LONG $0xc057f8c5             // vxorps    xmm0, xmm0, xmm0
    LONG $0x000108b8; BYTE $0x00 // mov    eax, 264
    WORD $0xc931                 // xor    ecx, ecx
LBB2_1:
    QUAD $0x0000000f8c10fcc5; BYTE $0x00 // vmovups    ymm1, yword [rdi + rcx]
    QUAD $0x0000000e8c59f4c5; BYTE $0x00 // vmulps    ymm1, ymm1, yword [rsi + rcx]
    LONG $0xc158fcc5             // vaddps    ymm0, ymm0, ymm1
    LONG $0x20c18348             // add    rcx, 32
    WORD $0xc083; BYTE $0xf8     // add    eax, -8
    WORD $0xf883; BYTE $0x0f     // cmp    eax, 15
        JA LBB2_1
    LONG $0x197de3c4; WORD $0x01c1 // vextractf128    xmm1, ymm0, 1
    LONG $0xc058f0c5             // vaddps    xmm0, xmm1, xmm0
    LONG $0xc07cfbc5             // vhaddps    xmm0, xmm0, xmm0
    LONG $0xc07cfbc5             // vhaddps    xmm0, xmm0, xmm0
    LONG $0x4211f8c5; BYTE $0x10 // vmovups    oword [rdx], xmm0
    VZEROUPPER
    RET

asm2plan9s生成以上Plan9匯編指令的源代碼參考：https://github.com/minio/asm2plan9s/blob/master/yasm.go中的函數(shù)toPlan9sYasm。

關(guān)鍵Plan9匯編指令

MOVQ（搬運(yùn)8個(gè)字節(jié)）
BYTE、WORD、LONG、QUAD（將1、2、4、8字節(jié)數(shù)據(jù)放入指令流）
JA (EFLAGS寄存器的標(biāo)志位大于則跳轉(zhuǎn))
VZEROUPPER（YMM寄存器高位置零）

（3）Golang調(diào)用Plan9匯編

需要提前創(chuàng)建一個(gè)與目標(biāo)匯編文件（simd_avx2.s）同名的go文件（如simd_avx2.go），聲明C語言中的函數(shù)（帶下劃線），函數(shù)入?yún)€(gè)數(shù)與原來C源碼中的入?yún)€(gè)數(shù)相等，參數(shù)需要是64位的，若有返回值，返回值的名字不能省略。

//go:noescape
func _VecInnerProductAVX2(x, y, z *float32)

其它業(yè)務(wù)函數(shù)直接調(diào)用該函數(shù)即可，嘗試過這些距離計(jì)算函數(shù)直接返回結(jié)果，最終拿不到結(jié)果，而有些函數(shù)可以直接返回結(jié)果，暫時(shí)還沒有發(fā)現(xiàn)c2goasm轉(zhuǎn)換后的調(diào)用規(guī)律，有興趣的小伙伴可以研究討論。

2.4 對比測試

實(shí)驗(yàn)環(huán)境

運(yùn)行環(huán)境	CPU類型	操作系統(tǒng)	CPU	內(nèi)存
支持AVX2的CVM	Intel Xeon	CentOS Linux release 8.2.2.2004 (Core)	4核	8G

根據(jù)Gonum32、CGO方式調(diào)用SIMD，Golang調(diào)用Plan9匯編SIMD三種計(jì)算方式，對比未優(yōu)化的普通內(nèi)積計(jì)算，計(jì)算能力對比如下圖：

內(nèi)積計(jì)算能力和時(shí)延相比未優(yōu)化的普通內(nèi)積計(jì)算均有提升，結(jié)果如下：

Gonum：8倍
SIMD-Cgo：2倍
SIMD-Plan9匯編：8.7倍

注意：

此處是單協(xié)程測試數(shù)據(jù)，多協(xié)程測試的時(shí)延更低，處理能力更高。
在AMD架構(gòu)的機(jī)器上進(jìn)行相同的測試，和Intel架構(gòu)的機(jī)器測試結(jié)果沒有明顯差異。

對未優(yōu)化的比普通內(nèi)積計(jì)算，CPU資源使用對比如下圖：

從圖中看出，SIMD-Plan9匯編的內(nèi)積運(yùn)算CPU資源使用最低。

另外，對于余弦距離和歐式距離也進(jìn)行了相同測試，測試結(jié)果與內(nèi)積距離的性能提升結(jié)果基本一致。

綜合計(jì)算能力、時(shí)延和CPU資源等方面，SIMD-Plan9匯編方案綜合性能較優(yōu)，因此可以采用此方案對線上服務(wù)進(jìn)行優(yōu)化。

3 小結(jié)

本文主要介紹了在當(dāng)前的向量檢索業(yè)務(wù)挑戰(zhàn)的背景下，研究了如何在內(nèi)存中進(jìn)行本地向量檢索的探索流程，對探索的多種方案也進(jìn)行了壓測，最終得出了綜合性能較優(yōu)的SIMD-Plan9匯編方案。

但實(shí)際上向量檢索的流程還有前置的向量過濾（可選流程）和后置的檢索結(jié)果排序，這兩個(gè)方面也有進(jìn)一步優(yōu)化的空間，以及整體優(yōu)化后的效果將在下一篇文章《向量檢索研究系列：本地向量檢索（下）》中進(jìn)行詳細(xì)介紹。

向量檢索研究系列：本地向量檢索（下）

1 背景

上一篇文章介紹了如何加快向量相似度計(jì)算，但是一般的向量檢索流程還包括對計(jì)算結(jié)果進(jìn)行排序，以及有必要的話，在計(jì)算相似度之前可以對向量庫中的向量進(jìn)行過濾篩選（可選流程）。

本地向量檢索在過濾和排序這兩個(gè)方面也有進(jìn)一步優(yōu)化的空間，本文將介紹一下過濾方案和排序方案。

2 過濾優(yōu)化

本地向量計(jì)算是先把向量加載內(nèi)存再計(jì)算，經(jīng)過SIMD優(yōu)化，計(jì)算速度快了，但是否還能進(jìn)一步減少待計(jì)算相似度的向量集呢？

舉個(gè)例子，一個(gè)用戶向量本來要和向量集所有1000個(gè)向量進(jìn)行相似度計(jì)算，是否可以在內(nèi)存中通過對向量進(jìn)行屬性過濾，讓用戶向量只需要和向量集中500個(gè)向量進(jìn)行相似度計(jì)算，這樣可以加快總體的向量檢索速度。

2.1 向量過濾

把廣告通過模型轉(zhuǎn)成向量后，向量應(yīng)該關(guān)聯(lián)廣告的一些基本信息，廣告檢索條件是基于這些廣告屬性的，檢索的時(shí)候可以根據(jù)檢索條件在向量關(guān)聯(lián)的廣告信息中進(jìn)行向量的篩選過濾。

廣告信息和檢索條件：

模型版本
冷啟動(dòng)或非冷啟動(dòng)創(chuàng)意
平臺
模板
媒體

基于內(nèi)存進(jìn)行向量過濾暫時(shí)有想到如下三種方案：

方案一：內(nèi)存對象

將廣告信息存儲為對象屬性，向量也是其中一個(gè)屬性，遍歷廣告對象，根據(jù)對象屬性進(jìn)行過濾。

方案二：內(nèi)存Bitmap

每個(gè)廣告屬性的取值都生成一個(gè)Bitmap，廣告ID為下標(biāo)，如平臺屬性中為iOS平臺和安卓平臺各生成一個(gè)bitmap，檢索條件對應(yīng)著多個(gè)bitmap，對這些bitmap進(jìn)行集合運(yùn)算即可得到滿足條件的廣告。bitmap舉例如下：

方案三：內(nèi)存倒排索引

使用兩個(gè)兩層Map結(jié)構(gòu)存儲廣告信息，第一個(gè)Map存儲索引信息，一級Key :“模型版本_冷啟動(dòng)或非冷啟動(dòng)創(chuàng)意”，二級Key :“平臺_模板_媒體”，值為廣告ID列表。第二個(gè)Map存儲向量信息，一級Key :“模型版本”，二級Key ：廣告ID，值為廣告向量。
檢索時(shí)把檢索條件在第一個(gè)Map中查詢到滿足檢索條件的廣告ID列表，再根據(jù)ID列表從第二個(gè)Map中取出對應(yīng)向量列表。
大致結(jié)構(gòu)可以參考2.2中向量存儲方案圖。

對這三種方案的QPS和資源占用情況進(jìn)行了測試，測試結(jié)果如下圖：

QPS：倒排索引 > Bitmap> 對象
CPU資源：Bitmap > 對象 > 倒排索引
時(shí)延（微秒級別，此處沒有展示）：對象 > Bitmap > 倒排索引

100萬數(shù)據(jù)量以下方案三倒排索引的綜合性能較優(yōu)。

2.2 向量存儲

線上倒排索引需要考慮向量存儲，實(shí)現(xiàn)方案分為離線刷入數(shù)據(jù)到Redis和在線從Redis讀取數(shù)據(jù)到內(nèi)存兩個(gè)階段。

在離線刷入數(shù)據(jù)到Redis階段，有兩種刷入方案：

方案一：如下圖左側(cè)所示，使用單個(gè)Hash存儲，Hash的Key和Field存儲條件，Value存儲向量列表，同時(shí)對這些向量列表進(jìn)行zip和base64壓縮，浮點(diǎn)數(shù)的壓縮率不高，僅2倍的壓縮率。因?yàn)橛行V告會在多個(gè)條件中出現(xiàn)，因此向量也會在多個(gè)Filed中出現(xiàn)，所以會存在向量冗余。

方案二：如下圖右側(cè)所示，使用一個(gè)Hash存儲索引條件和廣告ID列表，用多個(gè)單獨(dú)的Key/value存儲廣告ID和對應(yīng)的向量。若在Redis把這些單獨(dú)的向量Key用一個(gè)Hash進(jìn)行存儲，則會出現(xiàn)大Key，請求這些大Key會導(dǎo)致某些節(jié)點(diǎn)壓力過高，響應(yīng)速度變慢，而使用單獨(dú)的Key存儲可以分散請求壓力，提高后臺服務(wù)請求Redis速度。

后臺服務(wù)從Redis讀取向量數(shù)據(jù)到內(nèi)存，實(shí)驗(yàn)10萬個(gè)廣告，使用方案二，存儲向量需要內(nèi)存270M，存儲倒排索引3M。如果線上4個(gè)版本的向量進(jìn)行AB實(shí)驗(yàn)，則內(nèi)存總占用約1G。

Redis中多個(gè)單獨(dú)的Key和Value讀到內(nèi)存后被存儲在一個(gè)兩層的Map中。

綜合刷入數(shù)據(jù)和讀取數(shù)據(jù)兩個(gè)階段，兩種方案的優(yōu)缺點(diǎn)如下：

方案一

優(yōu)點(diǎn)：查詢Redis次數(shù)少
缺點(diǎn)：解析復(fù)雜、冗余向量內(nèi)存占用大、不便增量更新

方案二

優(yōu)點(diǎn)：解析簡單、內(nèi)存占用小、方便增量更新
缺點(diǎn)：查詢Redis次數(shù)比方案一要多

因此方案二的Redis存儲方式更有利于線上服務(wù)存儲和更新廣告向量。

3 排序優(yōu)化

向量過濾和相似度計(jì)算完之后，對結(jié)果取TopK的排序是否耗時(shí)？能否優(yōu)化？

3.1 全量排序

把Golang官方的排序算法（快排+堆排序+插入排序）時(shí)間和SIMD相似度計(jì)算時(shí)間進(jìn)行對比，如下圖：

可見，排序運(yùn)算時(shí)間 > 內(nèi)積運(yùn)算時(shí)間，Golang默認(rèn)的排序算法不滿足需求。

向量是浮點(diǎn)數(shù)數(shù)組，內(nèi)積計(jì)算的結(jié)果是浮點(diǎn)數(shù)，浮點(diǎn)數(shù)結(jié)果排序方案對比：

Go官方排序（快排+堆排序+插入排序）
堆排序（TopK問題常用算法）
浮點(diǎn)數(shù)基數(shù)排序（非比較型排序）
并行浮點(diǎn)數(shù)基數(shù)排序（分而治之）

基數(shù)排序常用于整數(shù)排序，基于浮點(diǎn)數(shù)的基數(shù)排序也是本小節(jié)的重點(diǎn)，其改造核心思想如下：

浮點(diǎn)數(shù)轉(zhuǎn)二進(jìn)制分段
多次分桶排序
處理負(fù)數(shù)

浮點(diǎn)數(shù)基數(shù)排序的大致流程如下，可參考下圖數(shù)字表標(biāo)識順序：

將待排序的浮點(diǎn)數(shù)轉(zhuǎn)成二進(jìn)制，并分成多段。
將所有浮點(diǎn)數(shù)的第1段映射到桶里面，段的二進(jìn)制位數(shù)決定了桶的大小，如8位二進(jìn)制段對應(yīng)的桶大小為256。
在桶里面確定浮點(diǎn)數(shù)的相對位置。
根據(jù)這個(gè)相對位置再進(jìn)行浮點(diǎn)數(shù)第2段排序，重復(fù)步驟2~3。
直至所有分段都分桶完成并確定元素相對位置后已經(jīng)得到浮點(diǎn)數(shù)的大致順序，因?yàn)樨?fù)數(shù)帶符號位，最高位為1，負(fù)數(shù)會在數(shù)組的后面，需要將負(fù)數(shù)反轉(zhuǎn)至數(shù)組頭部即可得到最終排序好的浮點(diǎn)數(shù)數(shù)組。

上面提到需要對浮點(diǎn)數(shù)的二進(jìn)制進(jìn)行分段，到底分多少段比較合適呢？

根據(jù)算法流程，得出時(shí)間復(fù)雜度公式：O(d*(n+2^(32/d))+n)，其中d為浮點(diǎn)數(shù)分段個(gè)數(shù)，n為待排序數(shù)據(jù)量，括號中三個(gè)時(shí)間的相加，分別代表著分桶、確定元素相對位置、將原數(shù)組元素按順序放到新數(shù)組中。32表示是32位的浮點(diǎn)數(shù)。

浮點(diǎn)數(shù)分段數(shù)	時(shí)間復(fù)雜度	待排序數(shù)量的合適取值范圍
1	2n+2^32	n > 2,147,418,112
2	4n+2^17	32512 < n <= 2,147,418,112
4	8n+2^10	124 < n <= 32512
8	16n+2^7	4 < n <= 124
16	32n+2^6	1 =< n <= 4
32	64n+2^6	0

注意：這僅是理論上的估算值，對分段趨勢的一個(gè)大概判斷。同時(shí)也在代碼層面對分2段、4段、8段進(jìn)行了測試，其排序時(shí)間對比如下圖：

可以看出，數(shù)據(jù)量越大，分段數(shù)越少排序越快，這和表格中的分段趨勢估算一致。在5萬數(shù)據(jù)量以下，分4段的效果最好，大于5萬時(shí)，分2段的效果較好。

數(shù)據(jù)量非常大的時(shí)候是否能并行排序？

并行浮點(diǎn)數(shù)基數(shù)排序思想：

多協(xié)程分批排序后各取TopK
子結(jié)果匯總后再取TopK

對于上面提到的幾種排序算法進(jìn)行了測試，同樣也和SIMD內(nèi)積運(yùn)算時(shí)間進(jìn)行對比，其測試結(jié)果如下：

上圖中各排序方案性能：并行浮點(diǎn)數(shù)基數(shù)排序 > 浮點(diǎn)數(shù)基數(shù)排序 > Golang官方排序 > 堆排序

浮點(diǎn)數(shù)基數(shù)排序是Golang官方排序的4~5倍，并行浮點(diǎn)數(shù)基數(shù)排序是Golang官方排序的1~11倍。并行浮點(diǎn)數(shù)基數(shù)排序在數(shù)據(jù)量比較小的時(shí)候反而性能沒有浮點(diǎn)數(shù)基數(shù)排序好，因?yàn)椴⑿幸泊嬖谛阅軗p耗。

此時(shí)可以看出浮點(diǎn)數(shù)基數(shù)排序時(shí)間已經(jīng)比SIMD相似度計(jì)算時(shí)間要短，已經(jīng)滿足我們的業(yè)務(wù)需求。

3.2 局部排序

前面提到的排序都是對全量的數(shù)據(jù)進(jìn)行排序，然后對結(jié)果取TopK，如果只對部分?jǐn)?shù)據(jù)進(jìn)行排序拿到TopK結(jié)果，不關(guān)心其它數(shù)據(jù)順序，因此可以考慮對現(xiàn)有排序算法進(jìn)行局部排序改造。

局部排序改造思想

方案一：冒泡排序

冒泡排序每次循環(huán)都會找到一個(gè)最大或最小的數(shù)值，循環(huán)TopK次就可以找到最終的TopK結(jié)果，退出算法即可。
時(shí)間復(fù)雜度：O(n*k)

方案二：快速排序.

利用二分法的思想，對于每次找到支點(diǎn)pivot時(shí)，判斷pivot位置若大于TopK，則在pivot的左半部分繼續(xù)遞歸，若pivot位置小于TopK，則在pivot的右半部分繼續(xù)遞歸，直至pivot等于TopK退出遞歸，數(shù)組的前TopK個(gè)數(shù)就是最終的TopK結(jié)果。
時(shí)間復(fù)雜度：O(n*logn)

方案三：堆排序

取出數(shù)組的前TopK個(gè)數(shù)構(gòu)建的一個(gè)小頂堆，然后遍歷原數(shù)組第TopK之后所有的數(shù)，依次和堆頂進(jìn)行比較，若比堆頂大，則插入堆中，進(jìn)行堆調(diào)整。遍歷完之后的堆即可TopK結(jié)果。
時(shí)間復(fù)雜度：O(n*logk)

對這幾種局部排序在不同的數(shù)據(jù)量下取TopK（k=1000）進(jìn)行了測試，結(jié)果如下：

算法\數(shù)據(jù)量	2000	1萬	2萬	5萬	10萬	100萬
冒泡排序TopK	2.3μs	12μs	114μs	205.087ms	321.765ms	2530ms
快速排序TopK	1403μs	8505μs	17135μs	43.705ms	88.822ms	883ms
堆排序TopK	59μs	246μs	335μs	0.436ms	0.551ms	1.364ms

從表格中可以得出以下結(jié)論：

冒泡排序在2萬數(shù)據(jù)量以下，其排序時(shí)間比其它局部排序要短。
快速排序的整體性能不佳，從其時(shí)間復(fù)雜度可以得知原因。
堆排序的性能比較穩(wěn)定，在5萬及以上的數(shù)據(jù)量時(shí)，其排序性能比較好
堆排序?qū)Ρ戎暗母↑c(diǎn)數(shù)基數(shù)排序和并行浮點(diǎn)數(shù)基數(shù)排序，在10萬以下數(shù)據(jù)量時(shí)，性能相差不大，在10萬數(shù)據(jù)量時(shí)還是堆排序的性能較優(yōu)。

根據(jù)當(dāng)前的業(yè)務(wù)數(shù)據(jù)量和數(shù)據(jù)增長趨勢，選擇堆排序的局部排序算法比較合適