Auction Algorithm Optimization in C++

Question

I have written the following Auction Algorithm implementation in C++ and I am having issues with performance. On my machine a problem size of 500 is solved in about 7 seconds while a similar Matlab version solves the same in about 4-5 seconds. Since C++ should run faster, what are some ways that I can squeeze some more performance out of this code? Are there any blatant pitfalls or bottlenecks which I can avoid?

Note that I am not looking for algorithmic improvements, I am mostly looking for feedback into what is fast C++ and what is not.

#include <iostream>
#include <vector>
#include <limits>
#include <stdlib.h>
#include <math.h>
#include <chrono>
#include <algorithm>
using namespace std;
#define INF numeric_limits<int>::max()
#define VERBOSE false
/* Pre-declare functions to allow arbitry call ordering */
void auction(int N);
void auctionRound(vector<int>* assignment, vector<double>* prices, vector<int> C, double epsilon);
vector<int> makeRandC(int size);
void printMatrix(vector<int> mat, int size);
vector<double> findUnAssig(vector<double>* v);
void vecMax(vector<auto> v, auto* maxVal, int* maxInd);
vector<int> getIndicesWithVal(vector<int> v, int val);
bool hasValue(vector<int> v, int val);
void printVec(vector<auto> v);
vector<double> getVecSubset(vector<double> v, vector<int> subIndices);
void reset(vector<auto>* v, auto val);
void valueMaxSecMax(vector<auto> v1, vector<auto> v2, auto* maxVal, int* maxInd, auto* secMaxVal, int* secMaxInd);
void vecMaxFromSubset(vector<auto> v, vector<int> indices, auto* maxVal, int* maxInd);
int main()
{
 cout << "Please enter a problem size: ";
 int probSize;
 cin >> probSize;
 auction(probSize);
 return 0;
}
void auction(int N)
{
 vector<int> C = makeRandC(N);
 if (VERBOSE)
 {
 cout << "Cost matrix: " << endl;
 printMatrix(C, N);
 }
 /* Begin Time */
 auto t1 = std::chrono::high_resolution_clock::now();
 clock_t start = clock();
 vector<int> assignment(N, INF);
 vector<double> prices(N, 1);
 double epsilon = 1.0;
 int iter = 1;
 while(epsilon > 1.0/N)
 {
 reset(&assignment, INF);
 while (find(assignment.begin(), assignment.end(), INF) != assignment.end())
 {
 iter++;
 auctionRound(&assignment, &prices, C, epsilon);
 }
 epsilon = epsilon * .25;
 }
 clock_t end = clock();
 /* End Time */
 auto t2 = std::chrono::high_resolution_clock::now();
 double timing = std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count();
 double time = (double) (end-start) / CLOCKS_PER_SEC * 1000.0;
 cout << "Num Iterations:\t" << iter << endl;
 cout << "Total time:\t" << timing / 1000.0 << endl;
 cout << "Total CPU time:\t" << time << endl;
 if (VERBOSE)
 {
 cout << endl << endl << "Solution: " << endl;
 for (int i = 0; i < assignment.size(); i++)
 {
 cout << "Person " << i << " gets object " << assignment[i] << endl;
 }
 }
}
void auctionRound(vector<int>* assignment, vector<double>* prices, vector<int> C, double epsilon)
{
 /* Prints the assignment and price vectors */
 if (VERBOSE)
 {
 cout << endl << "Assignment: \t\t";
 printVec(*assignment);
 cout << "prices: \t\t";
 printVec(*prices);
 cout << endl;
 }
 int N = prices->size();
 /* 
 These are meant to be kept in correspondance such that bidded[i] 
 and bids[i] correspond to person i bidding for bidded[i] with bid bids[i]
 */
 vector<int> tmpBidded;
 vector<double> tmpBids;
 vector<int> unAssig;
 /* Compute the bids of each unassigned individual and store them in temp */
 for (int i = 0; i< assignment->size(); i++)
 {
 if (assignment->at(i) == INF)
 {
 unAssig.push_back(i);
 /* Finds the row of our cost matrix corresponding to the ith unassigned person */
 // vector<int> rowInt = getRow(C, i);
 vector<double> row(C.begin() + i*N, C.begin() + (i+1)*N);
 /* 
 Need the best and second best value of each object to this person
 where value is calculated row_{j} - prices{j}
 */
 double optValForI, secOptValForI;
 int optObjForI, secOptObjForI;
 valueMaxSecMax(row, *prices, &optValForI, &optObjForI, &secOptValForI, &secOptObjForI);
 /* Computes the highest reasonable bid for the best object for this person */
 double bidForI = optValForI - secOptValForI + epsilon;
 /* Stores the bidding info for future use */
 tmpBidded.push_back(optObjForI);
 tmpBids.push_back(bidForI);
 }
 }
 /* 
 Each object which has received a bid determines the highest bidder and 
 updates its price accordingly
 */
 for (int j = 0; j < N; j++)
 {
 vector<int> indices = getIndicesWithVal(tmpBidded, j);
 if (indices.size() != 0)
 {
 double highestBidForJ;
 int i_j;
 vecMaxFromSubset(tmpBids, indices, &highestBidForJ, &i_j);
 for (int i = 0; i < assignment->size(); i++)
 {
 if (assignment->at(i) == j)
 {
 if (VERBOSE)
 cout << "Person " << unAssig[i_j] << " was assigned object " << i << " but it will now be unassigned" << endl;
 assignment->at(i) = INF;
 break;
 }
 }
 if (VERBOSE)
 cout << "Assigning object " << j << " to person " << unAssig[i_j]<< endl;
 assignment->at(unAssig[i_j]) = j;
 prices->at(j) = prices->at(j) + highestBidForJ;
 }
 }
}
/*<-------------------------------------- Utility Functions -------------------------------------->*/
vector<int> makeRandC(int size)
{
 srand (time(NULL));
 vector<int> mat(size * size, 2);
 for(int i = 0; i < size; i++)
 {
 for(int j = 0; j < size; j++)
 {
 mat[i + j * size] = rand() % size + 1;
 }
 }
 return mat;
}
void printMatrix(vector<int> mat, int size)
{
 for(int i = 0; i < size; i++)
 {
 for(int j = 0; j < size; j++)
 {
 cout << mat[i + j * size] << "\t";
 }
 cout << endl;
 }
}
void printVec(vector<auto> v)
{
 for(int i = 0; i < v.size(); i++)
 {
 if (v[i] == INF)
 {
 cout << "INF" << "\t";
 }
 else
 {
 cout << v[i] << "\t";
 }
 }
 cout << endl;
}
void vecMax(vector<auto> v, auto* maxVal, int* maxInd)
{
 *maxVal = -INF;
 for (int i = 0; i < v.size(); i++)
 {
 if (v[i] > *maxVal)
 {
 *maxVal = v[i];
 *maxInd = i;
 }
 }
}
void vecMaxFromSubset(vector<auto> v, vector<int> indices, auto* maxVal, int* maxInd)
{
 *maxVal = -INF;
 for (int i = 0; i < indices.size(); i++)
 {
 auto curVal = v[indices[i]];
 if (v[i] > *maxVal)
 {
 *maxVal = curVal;
 *maxInd = indices[i];
 }
 }
}
/* Finds the top two values and indices from the value vector v1 - v2 */
void valueMaxSecMax(vector<auto> v1, vector<auto> v2, auto* maxVal, int* maxInd, auto* secMaxVal, int* secMaxInd)
{
 *maxVal = -INF;
 *secMaxVal = -INF;
 for (int i = 0; i < v1.size(); i++)
 {
 auto curVal = v1[i] - v2[i];
 if (curVal > *maxVal)
 {
 *secMaxVal = *maxVal;
 *secMaxInd = *maxInd;
 *maxVal = curVal;
 *maxInd = i;
 }
 else if (curVal > *secMaxVal)
 {
 *secMaxVal = curVal;
 *secMaxInd = i;
 }
 }
}
/* Returns a vector of indices from v which have the specified value val */
vector<int> getIndicesWithVal(vector<int> v, int val)
{
 vector<int> out;
 for (int i = 0; i < v.size(); i++)
 {
 if (v[i] == val)
 {
 out.push_back(i);
 }
 }
 return out;
}
bool hasValue(vector<int> v, int val)
{
 for (int i = 0; i < v.size(); i++)
 {
 if (v[i] == val)
 {
 return true;
 }
 }
 return false;
}
void reset(vector<auto>* v, auto val)
{
 for (int i = 0; i < v->size(); i++)
 {
 v->at(i) = val;
 }
}

EDIT: For anyone interested, I implemented JS1's advice and I can now solve the size 500 problem in ~.2 seconds. The updated code can be found here.

EDIT 2: In light of nwp's comment, I compiled the copy-less version of my code with the optimization flag -O3 and I can now solve the size 500 problem in ~.02 seconds.

• nwp: Did you turn on optimizations in your compiler? Chances are unnecessary copies are optimized out without jumping through reference loops and then some.
• evan.oman: I had never thought to use the compiler optimizations. Compiling the original code with the flag -O3 reduced the size 500 run-time to ~1 second. I am not sure how it achieved this improvement, though it seems to have not removed all vector copying

Answer 1

Copying vectors

I ran your program and it was indeed quite slow. After debugging your program for a bit, I realized that you are copying vectors all over the place even though you probably don't mean to. The biggest offender is here, because the vector C is of size \$N^2\$:

void auctionRound(vector<int>* assignment, vector<double>* prices,
 vector<int> C, double epsilon);

When I changed this function to use a reference instead:

void auctionRound(vector<int>* assignment, vector<double>* prices,
 vector<int> &C, double epsilon);

Then your program ran about 7x faster on a 1000 size input.

When I removed all of your vector copies from your functions, including the temporary row vector you create, then I got your program to run around 50x faster on a 1000 size input.

• evan.oman: Fantastic! Thank you very much for the response, that was precisely the issue! Just out of curiosity what tools/methods did you use when you where debugging?
• Emily L.: @evan058 I'd imagine just reading the code. It is a very common mistake among beginner C++ developers and is quite obvious to most C++ developers with more than a few months of experience.
• JS1: @evan058 For this program I didn't use an actual debugger, but I did run your code on various sized inputs to get a sense of the speed of it. Then I looked at your program to find out what could possibly be so slow. At first I thought it was the row vector that you made a copy of, but after "fixing" it to pass in C instead, I made it worse instead of better because it was now copying the whole C instead of just one row. That's when I realized your vectors were being copied instead of being passed by reference.

Answer 2

In methods, pass collections by reference except if you need a copy (ie: for local modification).

ie:

void valueMaxSecMax(vector<auto> v1, vector<auto> v2 ...

should be:

void valueMaxSecMax(vector<auto>& v1, vector<auto>& v2 ...

If you don't want a copy of v1 and v2 each time it's called. (This applies to printMatrix, printVec, vecMax, ...)

This alone should reduce the time by an order of magnitude.