使用C++中的对象会对性能产生什么影响？

Question

使用C++中的对象会对性能产生什么影响？

c++performancedynamic-programmingcompiler-optimization

4

我有一个用于背包问题的动态规划算法，使用的是C++语言。当它被实现为函数并访问传递给它的变量时，在特定情况下运行需要22秒。但是，当我将其作为类KnapsackInstance的成员函数，并使用该类的数据成员作为变量时，运行时间却增加到了37秒。据我所知，只有访问成员函数才会经过虚表(vtable)，因此我无法解释可能发生的情况。

以下是该函数的代码：

int KnapsackInstance::dpSolve() {
 int i; // Current item number
 int d; // Current weight
 int * tbl; // Array of size weightLeft
 int toret;
 tbl = new int[weightLeft+1];
 if (!tbl) return -1;
 memset(tbl, 0, (weightLeft+1)*sizeof(int));
 for (i = 1; i <= numItems; ++i) {
  for (d = weightLeft; d >= 0; --d) {
   if (profitsWeights.at(i-1).second <= d) {
    /* Either add this item or don't */
    int v1 = profitsWeights.at(i-1).first + tbl[d-profitsWeights.at(i-1).second];
    int v2 = tbl[d];
    tbl[d] = (v1 < v2 ? v2 : v1);
   }
  }
 }
 toret = tbl[weightLeft];
 delete[] tbl;
 return toret;
}

tbl是DP表的一列。我们从第一列开始，一直到最后一列。profitsWeights变量是一对向量，第一个元素是利润，第二个元素是重量。toret是要返回的值。

以下是原始函数的代码：

int dpSolve(vector<pair<int, int> > profitsWeights, int weightLeft, int numItems) {
 int i; // Current item number
 int d; // Current weight
 int * tbl; // Array of size weightLeft
 int toret;
 tbl = new int[weightLeft+1];
 if (!tbl) return -1;
 memset(tbl, 0, (weightLeft+1)*sizeof(int));
 for (i = 1; i <= numItems; ++i) {
  for (d = weightLeft; d >= 0; --d) {
   if (profitsWeights.at(i-1).second <= d) {
    /* Either add this item or don't */
    int v1 = profitsWeights.at(i-1).first + tbl[d-profitsWeights.at(i-1).second];
    int v2 = tbl[d];
    tbl[d] = (v1 < v2 ? v2 : v1);
   }
  }
 }
 toret = tbl[weightLeft];
 delete[] tbl;
 return toret;
}

这是在Debian Lenny上运行的，使用了g++-4.3.2和-O3 -DNDEBUG参数。

谢谢。

- Opt

2

我们需要看到非类函数，才能做出明智的评论。 - anon

2

我觉得我们需要一种比较的方式...另外，你有一个潜在的内存泄漏；如果抛出异常，delete[] tbl 不会被调用。 - Travis Gockel

除了类成员函数与非成员函数的问题之外，如果您的编译器没有为您执行此操作，将profitsWeight.at(i-1)提升到for(d =...)循环之外并将其分配给本地（寄存器）变量可能会有所帮助。 - Dan Blanchard

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jerry Coffin · Accepted Answer

在典型的实现中，成员函数会接收到一个指向实例数据的隐藏参数（this）。因此，对于成员数据的访问通常是通过指针进行的，这可能解释了您所看到的减速现象。

另一方面，只有一个版本的代码很难做出更多的猜测。

在查看了两个代码片段之后，我认为我会像这样编写成员函数：

int KnapsackInstance::dpSolve() {
    std::vector<int> tbl(weightLeft+1, 0);
    std::vector<pair<int, int> > weights(profitWeights);
    int v1;

    for (int i = 0; i <numItems; ++i) 
        for (int d = weightLeft; d >= 0; --d)
            if ((weights[i+1].second <= d) && 
                ((v1 = weights[i].first + tbl[d-weights[i-1].second])>tbl[d]))
                    tbl[d] = v1;
    return tbl[weightLeft];
}