今天,我使用查找表而不是if-else來讀取代碼來剪裁兩個相加的uint8值。該地圖是我在i={0...255}
和255在i={256...511}
。我不知道有多大的這一增益可能,並試圖找到它,使用gprof的,Lookup Table vs if-else
g++ -std=c++0x -pg perfLookup.cpp -O2 -o perfLookup && ./perfLookup && gprof perfLookup |less
與附後的代碼。現在沒有-O2標誌,gprof說lookup()佔用45%,ifelse()佔用48%的執行時間。使用-O2雖然查找()爲56%,而ifelse()爲43%。但是這個基準是否正確?也許很多代碼已經被優化掉了,因爲dst永遠不會被讀取?
#include <iostream>
#include <cstdint>
#include <vector>
void lookup(std::vector<uint8_t> src, int repeat) {
uint8_t lookup[511];
for (int i = 0; i < 256; i++) {
lookup[i] = i;
}
for (int i = 256; i < 512; i++) {
lookup[i] = 255;
}
std::vector<uint8_t> dst(src.size());
for (int i = 0; i < repeat; i++) {
for (int i = 0; i < src.size(); i++) {
dst[i] = lookup[src[i]];
}
}
}
void ifelse(std::vector<uint8_t> src, int repeat) {
std::vector<uint8_t> dst(src.size());
for (int i = 0; i < repeat; i++) {
for (int i = 0; i < src.size(); i++) {
dst[i] = (src[i] > 255) ? 255 : src[i];
}
}
}
int main()
{
int n = 10000;
std::vector<uint8_t> src(n);
for (int i = 0; i < src.size(); i++) {
src[i] = rand() % 510;
}
lookup(src, 10000);
ifelse(src, 10000);
}
更新代碼:
#include <iostream>
#include <cstdint>
#include <cstring>
#include <vector>
#include <algorithm>
// g++ -std=c++0x -pg perfLookup.cpp -O2 -o perfLookup && ./perfLookup && gprof perfLookup |less
std::vector<uint16_t> lookup(std::vector<uint16_t> src, int repeat) {
uint16_t lookup[511];
for (int i = 0; i < 256; i++) {
lookup[i] = i;
}
for (int i = 256; i < 511; i++) {
lookup[i] = 255;
}
std::vector<uint16_t> dst(src.size());
for (int i = 0; i < repeat; i++) {
for (int k = 0; k < src.size(); k++) {
dst[k] = lookup[src[k]];
}
}
return dst;
}
std::vector<uint16_t> ifelse(std::vector<uint16_t> src, int repeat) {
std::vector<uint16_t> dst(src.size());
for (int i = 0; i < repeat; i++) {
for (int k = 0; k < src.size(); k++) {
dst[k] = (src[k] > 255) ? 255 : src[k];
}
}
return dst;
}
std::vector<uint16_t> copyv(std::vector<uint16_t> src, int repeat) {
std::vector<uint16_t> dst(src.size());
for (int i = 0; i < repeat; i++) {
dst = src;
for (int k = 0; k < src.size(); k++) {
if (dst[k] > 255) {
dst[k] = 255;
}
}
}
return dst;
}
std::vector<uint16_t> copyC(std::vector<uint16_t> src, int repeat)
{
uint16_t* dst = (uint16_t *) malloc(sizeof(uint16_t) * src.size()); // Alloc array for dst
for (int i = 0; i < repeat; i++) {
std::memcpy(dst, &src[0], sizeof(uint16_t) * src.size()); // copy src into array
for (int k = 0; k < src.size(); k++) {
if ((dst[k] & 0xFF00) != 0)
dst[k] = 0x00FF;
}
}
free(dst);
return std::vector<uint16_t>();
}
int main()
{
int n = 10000;
std::vector<uint16_t> src(n);
for (int i = 0; i < src.size(); i++) {
src[i] = rand() % 510;
}
std::vector<uint16_t> dst;
dst = lookup(src, 10000);
dst = ifelse(src, 10000);
dst = copyv(src, 10000);
}
請注意,您要衡量的查找表的初始化的基準測試的一部分。通常你分別初始化一個查找表,不要在基準測試中包含它。 – 2011-01-24 15:29:39
我不會將查找表的初始化包含到已測量函數中,因爲在程序執行過程中只能執行一次。 – 2011-01-24 15:30:24
我將對代碼進行一些更改:使用`src`參數並就地執行裁剪 - 注意這已經是一個副本,而不是對原始的引用。從函數中返回該向量,否則編譯器可能會從函數中刪除所有代碼,因爲本地變量從不使用。在測試代碼之外創建並存儲查找表 - 避免添加不會影響結果的操作。 – 2011-01-24 15:54:48