一、背景及概要
??序列化，是指將數(shù)據(jù)以一種特定的格式轉化為方便計算機經(jīng)網(wǎng)絡傳輸或儲存的格式。
??反序列化，以便在另一臺計算機或者本機上以序列化格式重新得到數(shù)據(jù)的操作。
例如：
?? uint32_t number = 10;
??在計算機中實際儲存為32位數(shù)據(jù):(高)00000000 00000000 00000000 00001010(低)
??為4個Byte數(shù)據(jù)，因此可以將4個Bytes放入char類型(同樣為8bits)的容器string當中，以完成序列化。再將string中的數(shù)據(jù)取出解釋為uint32_t完成反序列化。
??基于此思想，Jeff Dean在Building Software Systems at Google andLessons Learned[1]中提出了VBC編碼以高效地完成uint32_t的序列化與反序列化。本實驗完成了VBC編碼的基本實現(xiàn)和測試速度。
??但由于VBC編碼的decode方式必須忍受分支預測的開銷，因此Jeff Dean提出了一種新的編碼方式Group Varint Encoding，來解決分支預測的問題。
二、實驗方案
實驗設備
實驗概述
1、VBC編碼
??本實驗先將按照如下思路進行了C++程序的編寫并完成單元測試
encode 單個uint32_t
string encode_number(uint32_t n){
char current_byte;
string byte;
while (1) {
current_byte = n & 0x7f;
byte = current_byte + byte;
if (n < 128) break;
n = n >> 7;
}
byte[byte.size()-1] += 128;
return byte;
}
將vector<uint32_t>中所有uint32_t序列化為一個string
string encode(const vector<uint32_t>& in_sequence){
string serialized_integers;
const int size = in_sequence.size();
for (int i = 0; i < size; i++) {
serialized_integers += encode_number(in_sequence[i]);
}
return serialized_integers;
}
反序列化，將string中數(shù)據(jù)decode添加到vector<uint32_t>
vector<uint32_t> decode(const string& serialized_integers){
vector<uint32_t> numbers;
uint32_t current_number = 0;
int index = 0;
while (index < serialized_integers.length()) {
unsigned char current_byte = serialized_integers[index];
uint32_t part = (uint32_t)current_byte;
//對于每一個字節(jié)都要判斷當前字節(jié)是否為uint32_t的最后一個字節(jié)，分支預測開銷大
if (part < 128) {
current_number = (current_number << 7) + part;
}else {
current_number = (current_number << 7) + (part - 128);
numbers.push_back(current_number);
current_number = 0;
}
index++;
}
return numbers;
}
代碼分析
對于encode部分和decode部分，variant byte coding的方法均在每一個Byte上判斷是否屬于是當前整數(shù)的最后一個字節(jié)，因此在分支預測方面的開銷大，每一次分支預測的需要5ns左右的時間，因此提出以下方法Group Variant Encoding。
2、Group Variant Encoding編碼
編碼思想：將每一個uint32_t用2個bits來表示該整數(shù)需要幾個Byte來表示,一個uint32_t為4個字節(jié)正好需要兩個bits來表示。
二進制 ????需要的字節(jié)數(shù)
00???????1
00???????2
00???????3
00???????4
一個uint32_t正好需要四個狀態(tài)來表示
encode 一組uint32_t(數(shù)量<=4)
string encode_single_group(const vector<uint32_t>& integers){
string encoded;
//該組的tag
char tags = 0;
size_t offset = 6;
//對于每一個數(shù)據(jù)進行encode
for(int i = 0; i < integers.size(); i++){
uint32_t number = integers[i];
//每個數(shù)據(jù)有一個子標簽count記錄需要多少個Byte
char count = 0x0;
//為0則不需要取，直接添加至encoded
if(number != 0){
char current_byte = 0xFF;
//當還有字節(jié)可以編碼時：取出字節(jié)-》計數(shù)增加-》加入編碼
while(number != 0){
current_byte = current_byte & number;
count++;
encoded += current_byte;
number = number >> 8;
current_byte = 0xFF;
}
tags = tags | (count-1 << offset);
}else{
encoded += (char)0x00;
tags = tags | (count << offset);
}
offset -= 2;
}
return (tags + encoded);
}
encode接口:將vector<uint32_t>中所有uint32_t序列化為string
string group_varint_encode(const vector<uint32_t> &original_integers){
if(original_integers.empty()) return "";
string encoded;
//分組器
int group_count = 0;
vector<uint32_t> group;
for(int i = 0; i < original_integers.size(); i++){
group_count++;
group.push_back(original_integers[i]);
//若能填滿四個數(shù)據(jù)則編碼
if((group_count & 3) == 0){
encoded += encode_single_group(group);
group_count = 0;
group.clear();
}
}
//若數(shù)據(jù)數(shù)量不為4的倍數(shù)則再單獨編碼
if(group_count != 0) encoded += encode_single_group(group);
return encoded;
}
decode接口：反序列化string為vector<uint32_t>
vector<uint32_t> group_varint_decode(const string& encoded_byte_stream){
if(encoded_byte_stream.empty()) return {};
vector<uint32_t> decoded;
const int len = encoded_byte_stream.length();
int index = 0;
while(index < len{
//取當前tag
char tags = encoded_byte_stream[index++];
int offset = 6;
//對當前組數(shù)據(jù)進行decode(tag后的5～17個Bytes)
//這里對每個字節(jié)有條件判斷
while(offset >= 0 && index < len){
//follow為組內的其中一個數(shù)據(jù)需要的字節(jié)數(shù)
int follow = ((tags >> offset) & 3) + 1;
uint32_t value = 0;
//向后連續(xù)取follow字節(jié)
for(int i = 0; i < follow; i++){
unsigned char* trans = (unsigned char*)&encoded_byte_stream[index++];
value = value | ((uint32_t)*trans << i*8);
}
decoded.push_back(value);
offset -= 2;
}
}
return decoded;
}
代碼分析
在該實現(xiàn)當中注意decode的以下部分
int offset = 6;
//對當前組數(shù)據(jù)進行decode(tag后的5～17個Bytes)
//這里對每個字節(jié)有條件判斷
while(offset >= 0 && index < len)
如果這么編寫代碼，造成的后果是，并沒有達到Group Varint Encoding的核心目的-------減小分支預測的開銷，為了驗證該設想，運用perf分析工具來進行觀察。
#######觀察
#perf record生成一份性能報告
#-e + 性能指標可以對某一具體指標進行測量
#-g 生成具體到每個函數(shù)的性能
#最后是可執(zhí)行文件
#perf report 打開性能測試報告
perf record -e branch-misses -g ./a.out
perf report
可以看到甚至在此實現(xiàn)中，GVE的decode方法的branch-miss的占比甚至比VBC方法還高出了5%,因此需要對上述循環(huán)進行改進。
改進思路
改進思路無非在于，在運用tags時每取2bits都要判斷tags是否結束，即是否該組數(shù)據(jù)處理完成。
那么可以換一種處理方法，在處理前每一次都判斷該tags是否是最后一組tags。
如果對于四個一組的數(shù)據(jù)，順序的連續(xù)取四次，不需要判斷。
而對于最后一組數(shù)據(jù)數(shù)量在1 <= number <= 4,則需要每取一次判斷是否越界。
性能預測
如果處理的數(shù)據(jù)足夠大，那么分支預測的開銷相較于之前，減小了3/4。
改進的decode接口
uint32_t get_value(const string& encoded_byte_stream, const vector<uint32_t>& masks, size_t current_tag, uint32_t* address, int& index){
uint32_t value = 0;
address = (uint32_t*)&encoded_byte_stream[index];
value = *address & masks[current_tag];
index += current_tag + 1;
return value;
}
vector<uint32_t> group_varint_decode(const string& encoded_byte_stream){
if(encoded_byte_stream.empty()) return {};
vector<uint32_t> decoded;
const int len = encoded_byte_stream.length();
int index = 0;
const vector<uint32_t> masks = {0xff, 0xffff, 0xffffff, 0xffffffff};
while(index < len){
//取當前tag
char tags = encoded_byte_stream[index++];
int number = (tags & 3) + ((tags >> 2) & 3) + ((tags >> 4) & 3) + ((tags >> 6) & 3) + 4;
uint32_t* address = (uint32_t*)&encoded_byte_stream[index];
size_t current_tag = (tags >> 6) & 3;
//最后一個
if((index + number) >= len){
decoded.push_back(get_value(encoded_byte_stream,masks, current_tag, address, index));
if(index >= len) break;
current_tag = (tags >> 4) & 3;
decoded.push_back(get_value(encoded_byte_stream,masks, current_tag, address, index));
if(index >= len) break;
current_tag = (tags >> 2) & 3;
decoded.push_back(get_value(encoded_byte_stream,masks, current_tag, address, index));
if(index >= len) break;
current_tag = tags & 3;
decoded.push_back(get_value(encoded_byte_stream,masks, current_tag, address, index));
if(index >= len) break;
}else{
decoded.push_back(get_value(encoded_byte_stream,masks, current_tag, address, index));
current_tag = (tags >> 4) & 3;
decoded.push_back(get_value(encoded_byte_stream,masks, current_tag, address, index));
current_tag = (tags >> 2) & 3;
decoded.push_back(get_value(encoded_byte_stream,masks, current_tag, address, index));
current_tag = tags & 3;
decoded.push_back(get_value(encoded_byte_stream,masks, current_tag, address, index));
}
}
return decoded;
}
三、性能對比
encode對比
圖像分析：
為兩組對照，首先，可以看到，無論是否開啟編譯優(yōu)化O3，GVE方法編碼速度始終高于VBC編碼。
其次，若開啟編譯優(yōu)化O3，GVE方法的性能得到大幅度提升，提升了將近4倍，而VBC編碼的速度也提升了將近7倍，但還是低于未進行編譯優(yōu)化的GVE編碼。
結論：GVE的encode方法在速度上明顯優(yōu)于VBC的encode方法。
decode對比
圖像分析：
從上到下依次為(圖例起名可能引起混淆)：
VBC 未編譯優(yōu)化
GVE 未編譯優(yōu)化 未改進
VBC O3編譯優(yōu)化
GVE O3編譯優(yōu)化 未改進
GVE 未編譯優(yōu)化 改進后
GVE O3編譯優(yōu)化 改進后
? ?首先，無論對于GVE/VBC(未編譯優(yōu)化)還是 GVE/VBC(O3優(yōu)化),兩種方法性能其實相差不遠，均遭受了分支預測所帶來的開銷，表現(xiàn)為曲線貼合緊密。
? ?其次，關注標出數(shù)據(jù)的兩條，黃色和綠色, 表示，在進行改進之后，GVE的性能得到了大幅度的提升，綠色的改進后GVE(O3優(yōu)化)的速度遠遠超過其他版本的曲線，帶來了性能上的優(yōu)勢。
結論：改進編寫方式后的GVE的decode體現(xiàn)了Jeff Dean提出GVE編碼方法的初衷，即避免遭遇分支預測所帶來的性能瓶頸。
四、Conclusion And Future Work
? ?本次實驗運用兩種序列化uint32_t的方法VBC和GVE, 進行了初步的性能測試，以及體會了編碼方式的不同可以在性能上得到了巨大的提升，以及初步使用了perf性能分析工具和數(shù)據(jù)可視化的方法來解決問題。
? ?future work方面，可以看到在最后一張decode性能對比圖中，當數(shù)據(jù)數(shù)量上升時，GVE的decode方法遭遇了性能的嚴重下滑，因此，需要找出為什么會出現(xiàn)這樣的斷層現(xiàn)象，以及如果數(shù)據(jù)進一步增大，該方法性能的體現(xiàn)。找到性能瓶頸并嘗試解決該現(xiàn)象，達到既高效又穩(wěn)定的目標。
引用：
[2]:http://www.ir.uwaterloo.ca/book/addenda-06-index-compression.html
