The Reduce and Accumulate Algorithms

Deterministic Results with Reduce

How do I ensure deterministic results with non-commutative operators using std::reduce()?

Abstract art representing computer programming

std::reduce() can produce non-deterministic results when used with non-commutative or non-associative operators because it allows elements to be combined in any order, especially in parallel execution.

To ensure deterministic results, consider these strategies:

1. Use std::accumulate()

If you need deterministic results, and your operation is non-commutative, consider using std::accumulate() instead of std::reduce(). std::accumulate() processes elements sequentially from left to right, ensuring a consistent order.

#include <iostream>
#include <numeric>
#include <vector>

int main() {
  std::vector<int> numbers{1, 2, 3, 4, 5};

  int result = std::accumulate(
    numbers.begin(), numbers.end(), 0,
    [](int a, int b) {
      return a - b;  
    });

  std::cout << "Result: " << result;
}
Result: -15

2. Serial Execution Policy

When using std::reduce(), you can specify the std::execution::seq execution policy to enforce serial execution. This ensures elements are combined in a specific order, similar to std::accumulate().

#include <execution>
#include <iostream>
#include <numeric>
#include <vector>

int main() {
  std::vector<int> numbers{1, 2, 3, 4, 5};

  int result = std::reduce(std::execution::seq,
    numbers.begin(), numbers.end(), 0,
    [](int a, int b) {
      return a - b;  
    });

  std::cout << "Result: " << result;
}
Result: -15

3. Custom Reduction Logic

For more complex scenarios, you might need to implement a custom reduction logic that manually controls the order of operations.

This can be done by splitting the data into chunks, processing them individually, and then combining the results in a controlled manner.

#include <iostream>
#include <numeric>
#include <vector>
#include <thread>

void accumulateRange(
  const std::vector<int>& numbers,
  int start, int end, int& result
) {
  result = std::accumulate(
    numbers.begin() + start,
    numbers.begin() + end,
    0,
    [](int a, int b) {
      return a - b; 
    }
  );
}

int main() {
  std::vector<int> numbers{1, 2, 3, 4, 5};
  int result1 = 0, result2 = 0;

  std::thread t1(
    accumulateRange,
    std::ref(numbers),
    0,
    numbers.size() / 2,
    std::ref(result1)
  );

  std::thread t2(
    accumulateRange,
    std::ref(numbers),
    numbers.size() / 2,
    numbers.size(),
    std::ref(result2)
  );

  t1.join();
  t2.join();

  std::cout << "Result 1: " << result1;
  std::cout << "\nResult 2: " << result2;

  int finalResult = result1 - result2; 
  std::cout << "\nFinal Result: " << finalResult;
}
Result 1: -3
Result 2: -12
Final Result: 9

Summary

  • Use the std::accumulate() Algorithm: For non-commutative operations where deterministic results are required.
  • Serial Execution Policy: Apply std::execution::seq with std::reduce() to enforce a specific order.
  • Custom Logic: Implement manual reduction logic to control the order of operations.

These strategies help ensure deterministic results even with non-commutative operations in reduction algorithms.

Answers to questions are automatically generated and may not have been reviewed.

A computer programmer
Part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access

This course includes:

  • 124 Lessons
  • 550+ Code Samples
  • 96% Positive Reviews
  • Regularly Updated
  • Help and FAQ
Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved