Performance: repeated sweep through large binary dataset As part of a bigger mcmc sampling algorithm, I'm repeatedly looping through my entire dataset. When the data grows large this becomes a pretty large bottleneck in my algorithm and I'm looking for ways to make it faster.

Some things I'm considering are:


What are the most efficient datatypes? For example, for the variable x I use std::vector&lt; std::vector&lt;bool&gt; &gt; because data are binary; 0 or 1. However, this leads to many type conversions. Is there a better way?
Can I use iterators to loop over the data more efficiently?


All suggestions are welcome!

Edit: the performance critical function does the following:

The goal of the code is to simulate a dataset of size np by ni, while simultaneously evaluating a likelihood ratio. The simulated new data is binary, and created by rlogis(0.0, 1.0) &lt;= val ? 1 : 0. The subsequent evaluation of the ratio happens via acc += theta[i][d] * (x[i][j] -
 xnew) * C[j][d];. These two steps seem optimal from a performance perspective to me; my question is primarily about the surrounding structure.

Code:

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;chrono&gt;

using namespace std; // &lt;-- only here for the example; I don't normally do this

typedef unsigned int uint;
typedef std::vector&lt;double&gt; vec;
typedef std::vector&lt;vec&gt; mat;

// will be replaced by actual random number generator
double rlogis() {
    return rand() % 5 - 2;
}


// improving performance of this function is my goal
double orig(const uint np, const uint ni, const uint nd,
               const mat&amp; theta, const mat&amp; C,
               const vec&amp; delta, const vec&amp; lambdaNew,
               const int d, std::vector&lt;std::vector&lt;bool&gt; &gt;&amp; x) {

    double acc = 0.0;
    bool xnew;
    vec tmp(nd);
    for (uint j = 0; j &lt; ni; ++j) {

        for (uint d2 = 0; d2 &lt; nd; ++d2) {
            tmp[d2] = lambdaNew[d2] * C[j][d2];
        }

        for (uint i = 0; i &lt; np; ++i) {

            double val = delta[j];
            for (uint d2 = 0; d2 &lt; nd; ++d2) {
                val += tmp[d2] * theta[i][d2];
            }

            xnew = rlogis() &lt;= val;
            acc += theta[i][d] * (x[i][j] - xnew) * C[j][d];

        }
    }
    return acc;
}

// wrapper function for timing
int main() {

    // dimensions of the data
    const uint np = 2E4; // this could be larger, easily 1E5
    const uint ni = 200; // this stays constant
    const uint nd = 3;   // could be 4-5, but not 10

    // objects
    std::vector&lt;double&gt; delta(ni);
    std::vector&lt;double&gt; lambdaNew(nd);
    vector&lt; std::vector&lt;double&gt; &gt; theta(np, std::vector&lt;double&gt;(nd));
    vector&lt; std::vector&lt;double&gt; &gt; C(ni, std::vector&lt;double&gt;(nd));
    std::vector&lt; std::vector&lt;bool&gt; &gt; x(np, std::vector&lt;bool&gt;(ni));

    // fill objects with values (exact values are irrelevant)
    srand(1);
    int d = rand() % nd;
    for (uint i = 0; i &lt; np; ++i) {
        for (uint d = 0; d &lt; nd; ++d) {
            theta[i][d] = 2 * rand() - 1;
        }
        for (uint j = 0; j &lt; ni; ++j) {
            x[i][j] = bool(int(rand() + .5));
        }
    }
    for (uint j = 0; j &lt; ni; ++j) {
        delta[j] = 2 * rand() - 1;
        for (uint d = 0; d &lt; nd; ++d) {
            C[j][d] = 2 * rand() - 1;
        }
    }
    for (uint d = 0; d &lt; nd; ++d) {
        lambdaNew[d] = 5 * rand() + 1;
    }

    // start timing
    {
        srand(2);
        auto start = chrono::steady_clock::now();
        auto ans = orig(np, ni, nd, theta, C, delta, lambdaNew, d, x);
        auto time1 = chrono::steady_clock::now() - start;

        cout &lt;&lt; "Orig: " &lt;&lt; ans &lt;&lt; "\n"
             &lt;&lt; "Time: " &lt;&lt; chrono::duration &lt;double, milli&gt; (time1).count() &lt;&lt; " ms\n" &lt;&lt; endl;
    }

    return 0;
}
You did not provide any performance measurements, so every answer here is basically guesswork, but I suspect that the lack of speed you are experiencing could have something to do with std::vector&lt;bool&gt;. 

The problem is that std::vector&lt;bool&gt; is not really what it appears to be. While a vector of any other type actually works in units of bytes, the specialization for bool works with individual bits, packing them as tightly as possible. This is, of course, great if you want to reduce memory usage, but it also is really slow since you have to mask and shift bits around every time you want to access a value. 

For this reason, in combination with the fact that it doesn't behave like a normal vector in certain cases (which are, sadly, not exactly rare), std::vector&lt;bool&gt; is mostly seen as a design flaw in the standard library and does not see much use. 

You should try to replace std::vector&lt;bool&gt; with a similar fitting type, e.g. std::vector&lt;char&gt;, and measure that to determine whether and by how much this alleviates your issue.

If you are not convinced yet, here is a quick-and-dirty benchmark to show just how much slower std::vector&lt;bool&gt; is.