Branch Prediction: Sorted vs. Shuffled Data

Question 14 / 17 • Correct so far: 0 (0 answered)

Snippet A

Sorted Array

std::size_t filterAboveThreshold(const std::vector<int>& data,
                                  std::vector<int>& out) {
    std::size_t n = 0;
    for (int x : data)
        if (x >= kThreshold) out[n++] = x;
    return n;
}

std::size_t n = filterAboveThreshold(SORTED_DATA, OUTPUT);
Snippet B

Shuffled Array

std::size_t filterAboveThreshold(const std::vector<int>& data,
                                  std::vector<int>& out) {
    std::size_t n = 0;
    for (int x : data)
        if (x >= kThreshold) out[n++] = x;
    return n;
}

std::size_t n = filterAboveThreshold(SHUFFLED_DATA, OUTPUT);
Shared test data (shared-setup) 
constexpr int kArraySize = 32768;
constexpr int kThreshold = 128;

static std::vector<int> generateData() {
    std::mt19937 rng(42);
    std::uniform_int_distribution<int> dist(0, 255);
    std::vector<int> v(kArraySize);
    for (auto& x : v) x = dist(rng);
    return v;
}

static const std::vector<int> SHUFFLED_DATA = generateData();

static std::vector<int> makeSorted() {
    auto v = generateData();
    std::sort(v.begin(), v.end());
    return v;
}

static const std::vector<int> SORTED_DATA = makeSorted();

// Pre-allocated output buffer reused across iterations to avoid allocation cost.
static std::vector<int> OUTPUT(kArraySize);

Which snippet is faster?

Select the correct answer(s)