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][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

Gprof output

Continued Gprof output

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. After setting optimization flag "-O3"

  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Cody Gray
    Dec 30, 2016 at 9:23
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – JS1
    Dec 30, 2016 at 10:40
  • \$\begingroup\$ @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! \$\endgroup\$
    – Edward
    Dec 30, 2016 at 13:40
  • \$\begingroup\$ @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. \$\endgroup\$ Dec 30, 2016 at 15:49
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Cody Gray
    Dec 30, 2016 at 16:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.