Performance Impact When Using Objects in C ++

Question

I have a dynamic programming algorithm for Knapsack in C ++. When it was implemented as a function and access to the variables passed into it, it took 22 seconds for a particular instance. When I made this a member function of my KnapsackInstance class and whether it used variables that are data members of this class, it ran 37 seconds to run. As far as I know, only access to member functions goes through the vtable, so I find it difficult to explain what might happen.

Here is the function code

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 - one column of the DP table. We start from the first column and continue to the last column. The variable profitWeights is a vector of pairs, the first element of which is profit, and the second is weight. toret is the return value.

Here is the source function code: -

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

This was done on Debian Lenny with g ++ - 4.3.2 and -O3 -DNDEBUG enabled

thanks

Answer 1

In a typical implementation, a member function receives a pointer to the instance data as a hidden parameter ( this ). Thus, access to element data is usually done using a pointer that can take into account the slowdown that you see.

On the other hand, it’s hard to do more than guess with just one version of the code.

Having looked at both code snippets, I think that writing a member function is more:

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