⑴ 怎麼把手機圖片壓縮到200k
背景
在手機上用戶隨手拍一張衣服的照片，去找類似圖片的需求比較明顯，以圖搜圖項目目的就是滿足用戶的這部分需求。
該項目初步預計5個類目，每個類目500萬圖片用於檢索。經過特徵提取，每張圖片可以表示為30976維空間中的一個點，即可以用30976個float值表示，為了便於處理，我們將特徵值乘以100000，在不損失float值精度的情況下，用int32_t存儲圖片特徵。
圖片檢索時需要計算query 圖片和索引圖片的歐式距離，圖片之間計算歐式距離的耗時為50微秒，經過cpu指令集優化(sse)，歐式距離計算耗時減少到13微秒。
在壓縮之前，所有圖片的大小為 3T（ 4 * 30k * 25000000)，每台機器30G內存用於存儲圖片，需要100台機器存儲全量圖片。
需要在計算歐式距離效率不降低的情況下，對圖片進行壓縮，大規模減少機器的佔用。
我們的目標是壓縮到500G左右，即壓縮之後每張圖片20k左右，歐式距離計算耗時為15微秒左右。
歐式距離計算要求耗時在微秒級別，已有的壓縮方法，比如p4delta、valgrind壓縮等在性能上不滿足要求，需要我們根據數據特點自己定製壓縮方法。
成果
目前的壓縮方法單張圖片由120k 壓縮到了平均13k。
歐式距離計算平均耗時為9微秒。
這么靠譜的成果是如何做到的呢？
初步嘗試
bitmap的方法
觀察數據特點，發現平均每張圖片有7000個數為非0值，其他值都為 0。首先想到的是用bitmap表示30976個值在特定的位置是否是0。bitmap需要30976 / 8= 4k個位元組。然後只存儲非0值，需要7k * 4，壓縮之後平均每張圖片大小為32k。壓縮代碼大體如下：
int bitmap_len = size / 8 + 8;
uint64_t *bitmap = (uint64_t*)(cmpr_buf);
int32_t *data = (int32_t*)(cmpr_buf + bitmap_len);
for(unsigned int i=0;i<size;i++) {
if(list[i] != 0) {
data[index++] = list[i];
bitmap[i/64] |= bit_mask_tab[i % 64];
}
}
但是在計算圖片之間的歐式距離時，需要遍歷30976次bitmap，並判斷特定位的值知否為0，即將bitmap和掩碼數組進行與操作，比較耗時，計算耗時在100微秒以上。計算兩個壓縮圖片的歐式距離代碼：
for(i=0; i<size/64; i++) { for(int j=0; j<64; j++) { a = 0; b = 0; if((bitmap1[i] & bit_mask_tab[j])) { a = data1[index1++]; } if((bitmap2[i] & bit_mask_tab[j])) { b = data2[index2++]; } olength += (a - b) * (a - b); } }
採用offset的壓縮方式
我們只保存非0數據的off_set和value，off_set最大值30975，需要用int16_t來保存，value的范圍0~100萬，需要int32_t來表示，採用該方法的話，每個圖片佔用空間為42k （7k * (2 + 4)）。
for(int i=0; i<size; i++) {
if(list[i] != 0) {
index++;
}
}
*(int16_t*) cmpr_buf = index;
int16_t *p_off = (int16_t*)cmpr_buf + 1;
int32_t *p_data = (int32_t*)(((char *)cmpr_buf) + sizeof(int16_t) * index + sizeof(int16_t));
index = 0;
for(int i=0; i<size; i++) {
if(list[i] != 0) {
p_off[index] = i;
p_data[index] = list[i];
index++;
}
}
計算兩個壓縮圖片的歐式距離的時候，採用按照off_set歸並的方法：
while(p_data1<end1 && p_data2 < end2){
if(*p_off1 < *p_off2) {
olength += *p_data1 * *p_data1;
p_data1++;
p_off1++;
} else if(*p_off1 > *p_off2) {
olength += *p_data2 * *p_data2;
p_data2++;
p_off2++;
} else {
olength += (*p_data1 - *p_data2) * (*p_data1 - *p_data2);
p_data1++;
p_data2++;
p_off1++;
p_off2++;
}
}
該方法進行歐式距離的耗時為55微秒，我們認為是if 條件比較耗時，於是嘗試了用位掩碼替代if的方式：
while(p_data1 < end1 && p_data2<end2) {
a = ((*p_off1 - *p_off2) <= 0);
b = ((*p_off2 - *p_off1) <= 0);
tmp1 = -a & *p_data1;
tmp2 = -b & *p_data2;
p_off1 += a;
p_off2 += b;
p_data1 += a;
p_data2 += b;
tmp = tmp1 - tmp2;
olength += tmp * tmp;
}
該方式消除了if 條件判斷，但是耗時為70微秒，性能反而下降了，耗時的原因是cpu的指令增多了。
性能優化
場景分析
兩個壓縮圖片計算 --> 一個壓縮一個非壓縮
目前的優化進入了一個瓶頸，如何才能提升性能到10微秒級別呢？我們回過頭來重新考慮了一下應用場景，在線的場景是query圖片和一系列圖片計算距離，離線的場景是中心點圖片和其他一系列圖片計算距離也就是說都是一個圖片和多個圖片進行距離計算，這時一個圖片不需要進行壓縮，完全可以是非壓縮的，即使該圖片是壓縮也可以先解壓計算歐式距離實際上可以轉化為一個非壓縮圖片和多個壓縮圖片計算歐式距離。對這樣的情況，我們需要重新考慮提升效率的問題。
確定採用off_set壓縮方式
對於計算一個壓縮和一個非壓縮圖片歐式距離的問題，比較bitmap的壓縮方式和off_set的壓縮方式，off_set的壓縮方式有明顯的優勢對於bitmap方式，最耗時的地方仍然是訪問30976次bitmap，然後做與操作，來獲取解壓後的值，遍歷30976次bitmap耗時，至少50微秒以上但是off_set的方式保存了7000個非0數據的off_set，我們只需要遍歷7000次非0 數組就可以計算出歐式距離。
一個壓縮一個非壓縮
做法
首先計算好非壓縮圖片的累加平方和，每次查詢計算多次歐式距離，只計算一次累加平方和。
遍歷壓縮圖片數組，計算該值和另一張非壓縮圖片的對應off_set的差值的平方。
對於壓縮圖片的為0的那些值來說，歐式距離只需要加上非壓縮圖片那些值的平方和。
舉例：
a.非壓縮圖片：[0 2 3 0 4 0 0 5 6 0 0] ，壓縮圖片：[0 0 0 6 6 6 0 0 ]
b.事先計算好非壓縮圖片的特定位之前的所有值的平方和：sqrt[0 4 13 13 29 29 29 54 90 90 90]
c.壓縮的數組為 off[3 4 5]， data[6 6 6 ]
d.遍歷off和data數組
olength += (6 - 0) * (6 - 0) olength += (sqrt[2] - sqrt[0])
olength += (6 - 4) * (6 - 4)olength += (sqrt[3] - sqrt[3])
olength += (6 - 0) * (6 - 0) olength += (sqrt[4] - sqrt[4])
效率：20微秒
該方法只需要遍歷7000次數組， 進行7000次相減 平方操作和 7000次訪問sqrt 數組操作，大大簡化了復雜度。
代碼如下：
data1為壓縮數據，data2為非壓縮數據：
for(int i=0; i<num; i++) {
olength += (data1[i] - data2[off1[i]]) * (data1[i] - data2[off1[i]]);
olength += sqrt[off[i] - 1] - sqrt[off[i-1]];
}