Memory access pattern

Question

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.