Search for rows in a 2D array that contain a given sequence I have a 2d array of m * n dimension (m and n can vary from 1 to 100000). The following snippet of code checks if the sequence exists in the row and stores the index if it exists. The time taken by the following code on 10000*10000 matrix is 650 milliseconds. The sequential version of the code also takes the same time. 

This on Intel Core i7-7560U CPU @ 2.40GHz × 4

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

std::vector&lt;int&gt; lps;

void ComputeLPSArray(std::vector&lt;int&gt; const &amp;pattern) {

    std::vector&lt;int&gt; lps(pattern.size());
    int len = 0;

    lps[0] = 0;

    int i = 1;
    while (i &lt; (int) pattern.size()) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}


int SearchPattern(std::vector&lt;int&gt; const &amp;pattern, std::vector&lt;int&gt; const &amp;row) {
    auto M = (int) pattern.size();
    auto N = (int) row.size();

    int i = 0;
    int j = 0;
    while (i &lt; N) {

        if (pattern[j] == row[i]) {
            j++;
            i++;
        }
        if (j == M) {
            return 1;
        } else if (i &lt; N &amp;&amp; pattern[j] != row[i]) {
            if (j != 0)
                j = lps[j - 1];
            else
                i = i + 1;
        }
    }
    return -1;
}

std::vector&lt;int&gt; SearchSequence(std::vector&lt;std::vector&lt;int&gt;&gt; const &amp;matrix, std::vector&lt;int&gt; const &amp;sequence) {

    ComputeLPSArray(sequence);
    std::vector&lt;int&gt; result(matrix.size());
    unsigned int length = 0;
    std::vector&lt;std::future&lt;int&gt;&gt; f(matrix.size());

    for (unsigned int i = 0; i &lt; matrix.size(); i++) {
        std::vector&lt;int&gt; row = matrix[i];
        f[i] = async(std::launch::async, [sequence, row] { return SearchPattern(sequence, row); });
    }

    for (unsigned int i = 0; i &lt; f.size(); ++i) {
        if (f[i].get() == 1)
            result[length++] = i;
    }

    result.resize(length);

    return result;
}

int main() {

    int m = 25, n = 20; // assume `m` and `n` can vary.
    std::vector&lt;std::vector&lt;int &gt;&gt; matrix(m, std::vector&lt;int&gt;(n));

    for (int i = 0; i &lt; m; ++i) {
        for (int j = 0; j &lt; n; ++j) {
            matrix[i][j] = rand() % 1000;
        }

    }

    std::vector&lt;int&gt; sequence = matrix[24]; // This is purely for testing purpose, actual input(matrix&amp;sequence) is read from files.

    std::vector&lt;int&gt; result;
    result = SearchSequence(matrix, sequence); // This is the ONLY function which needs to be optimised.

    return 0;
}


How do I speed up the search time in this scenario?
I rewrote your SearchSequence function to be as absolutely brain-dead as possible:

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

std::vector&lt;int&gt; SearchSequence(std::vector&lt;std::vector&lt;int&gt;&gt; const &amp;matrix, std::vector&lt;int&gt; const &amp;sequence)
{
    std::vector&lt;int&gt; result;

    for (unsigned int i = 0; i &lt; matrix.size(); i++) {
        auto it = std::search(matrix[i].begin(), matrix[i].end(), sequence.begin(), sequence.end());
        if (it != matrix[i].end()) {
            result.emplace_back(i);
        }
    }
    return result;
}

int main() {

    int m = 25000, n = 25000; // assume `m` and `n` can vary.
    std::vector&lt;std::vector&lt;int &gt;&gt; matrix(m, std::vector&lt;int&gt;(n));

    auto start_time = std::chrono::steady_clock::now();

    for (int i = 0; i &lt; m; ++i) {
        for (int j = 0; j &lt; n; ++j) {
            matrix[i][j] = rand() % 1000;
        }
    }

    std::vector&lt;int&gt; sequence = matrix[9999]; // This is purely for testing purpose, actual input(matrix&amp;sequence) is read from files.

    auto initial_time = std::chrono::steady_clock::now();
    std::cout
        &lt;&lt; "Initializing the array with rand() took: "
        &lt;&lt; std::chrono::duration_cast&lt;std::chrono::milliseconds&gt;(initial_time - start_time).count() &lt;&lt; " ms\n";

    std::vector&lt;int&gt; result = SearchSequence(matrix, sequence); // This is the ONLY function which needs to be optimised.

    auto search_time = std::chrono::steady_clock::now();
    std::cout
        &lt;&lt; "Executing the actual search took: "
        &lt;&lt; std::chrono::duration_cast&lt;std::chrono::milliseconds&gt;(search_time - initial_time).count() &lt;&lt; " ms\n";

    return 0;
}


On my laptop, this prints:

$ clang++ -std=c++14 -O3 ./x.cc
$ ./a.out
Initializing the array with rand() took: 5304 ms
Executing the actual search took: 2 ms

$ clang++ -std=c++14 -O0 ./x.cc
$ ./a.out
Initializing the array with rand() took: 7670 ms
Executing the actual search took: 8 ms


This is single-threaded, with absolutely no cleverness to the search at all — I'm just using the $O(n^2)$ std::search algorithm from the standard library.

I suggest that your business with std::vector&lt;std::future&lt;int&gt;&gt; is completely unnecessary, and that if you're measuring any slowness, it's slowness in initializing the matrix with random numbers.