⑴ 怎么把手机图片压缩到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]];
}