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.
std::vector
'soperator[]
. 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 tooperator[]
and thus charged against its execution time.std::max
andstd::min
can probably be sped up by eliminating conditional branches, but that's a bit higher-hanging fruit on the performance tree. \$\endgroup\$ – Cody Gray Dec 30 '16 at 9:23start
andlast
used for? Why is there avec
variable that you modify and then never use? It just seems like this isn't the real code. \$\endgroup\$ – JS1 Dec 30 '16 at 10:40score_type m_compute__(int xi, set_type pa_set) { return 0; }
Unless... you're really relying on global variables. ick! \$\endgroup\$ – Edward Dec 30 '16 at 13:40-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 foroperator[]
. As far asmax
andmin
, 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. \$\endgroup\$ – Cody Gray Dec 30 '16 at 16:05