查找表vs if-else

Question

今天我使用查找表而不是if-else读取代码来剪切两个求和的uint8值.地图是i in i={0...255},255 in i={256...511}.我想知道这可能有多大,并尝试使用gprof找到它,

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);
}

Answer 1

那么,既然src被声明为std::vector<uint8_t>,src[i]是永远大于255,这是一个8位无符号整数,最高的可能值.

因此,我的猜测是编译器优化了检查.剩下的只是样板循环,因此基准没有意义.

如果检查没有意义(即检查64而不是255),"优化"的结果可能是高度机器依赖的.分支预测可以(取决于输入数据)在降低分支成本方面做得很好.另一方面,查找表需要(再次取决于输入数据)随机存储器访问并破坏缓存...

Answer 2

除了亚历山大已经说过的事情:

查找表可以大大提高性能.但是,这首先会被创建查找表所花费的时间所抵消.通常你会单独对此进行基准测试

必须记住的另一件事是查找表需要缓存中的空间,因此如果它很大,可能会导致缓存未命中.如果有足够的缓存未命中,则该if方法将比查找表更快.

最后,gprof非常好地识别瓶颈.但我不会将它用于基准测试.请改用计时功能.gprof使用可能严格来说映射到消耗时间的采样,但这里不太精确.