# Memory access pattern

Here is the chunk of the code that hogs the maximum time:

   double m_compute__(int xi, set_type pa_set) {
// no negative or floating numbers to be handled
if (pa_set == 0) { return m_compute__(xi); }

// Bitwise representation of a set of numbers
std::vector<int> pa_vec = as_vector(pa_set);
//  Number of elements in the set
int pa_sz = pa_vec.size();

// Creating a place for storing the key & values
// max_index_[pa_sz] some pre-computed and non-changing value
std::vector<std::vector<int>> vec(max_index_[pa_sz] + 1, std::vector<int>(r_[xi]+1, 0));

int start = m_;
int last = 0;

for (int i = 0; i < m_; ++i) {
int index = 0;
index = D_[i * n_ + pa_vec[0]];
for (int j = 1; j < pa_sz; ++j) { index += r_[pa_vec[j]] * D_[i * n_ + pa_vec[j]]; }
++vec[index][0];
++vec[index][D_[i * n_ + xi] + 1];
start = start < index ? start : index;
last = last > index ? last : index;
}

int qi = 0;
double score = 0.0;
for (; start <= last; ++start) {
double nij = vec[start][0];
if (nij > 1) {
double nijk = -1;
for (int i = 1; i <= r_[xi]; ++i) {
nijk = vec[start][i];
score += (nijk == 0) ? 0 : nijk * (std::log2(nij) - std::log2(nijk));
}
}
if (nij >= 1) { ++qi; }
}
score += cons_ * qi * (r_[xi] - 1);
return score;
}// m_compute__

int n_ = -1;
int m_ = -1;
set_type X_ = 1;

double cons_ = -1;
// vector for storing n_ positive (> 1) numbers and with each number < 127
std::vector<int> r_;
std::vector<data_type> D_;
int max_index_[SET_MAX_SIZE];


D_ is a container used to store table of elements of type signed char (n_ * m_) where m_ represents the number of rows and n_ the number of columns.

Here is the output obtained from using gprof. I am trying to figure out what all changes I can make to improve the performance. Or I am finding it hard to interpret the output of gprof to know where I am losing maximum time and how to improve it.

Compiled using: g++ -std=c++11 -pg test.cpp Profiler output: gprof ./a.out

Compiled using the optimization flags:
g++ -std=c++11 -O3 -pg test.cpp
Profiler output:
gprof ./a.out
But when this "-O3" is used the output of profile does not seems to contain any information.

• The gprof output suggests that you're spending a significant chunk of time in std::vector's operator[]. That doesn't make a lot of sense, since this should be a simple array-indexing operation in an optimized build. You are profiling an optimized build, right? The other possibility is that the arithmetic manipulations are getting folded into the call to operator[] and thus charged against its execution time. std::max and std::min can probably be sped up by eliminating conditional branches, but that's a bit higher-hanging fruit on the performance tree. – Cody Gray Dec 30 '16 at 9:23
• Did you not list the actual function? Why does your function always return 0? What is the purpose of all that computation just to return 0? What are start and last used for? Why is there a vec variable that you modify and then never use? It just seems like this isn't the real code. – JS1 Dec 30 '16 at 10:40
• @JS1: I agreed. If not, here's a suggested optimization: score_type m_compute__(int xi, set_type pa_set) { return 0; } Unless... you're really relying on global variables. ick! – Edward Dec 30 '16 at 13:40
• @JS1 @ick! To keep the function clean and minimal I removed few lines which iterated (only once) over the newly formed vector "vec". And just to keep the code neat, minimalistic and correct, I returned 0. – letsBeePolite Dec 30 '16 at 15:49
• Yes, absolutely! It doesn't have to be -O3; use whatever optimization setting you normally use, whether that's -O3 or -O2 or whatever. The point is, you're profiling debugging code, which gives you meaningless information. The debug version of the runtime libraries probably has a bunch of costly bounds checks for operator[]. As far as max and min, mispredicted branches are expensive, so if the compiler doesn't already do the transformation, removing the branches may speed things up. If the comment didn't make any sense to you, it's an entire answer worth of explanation. – Cody Gray Dec 30 '16 at 16:05