C++17 병렬 알고리즘: std::execution::par·par_unseq로 sort·transform·reduce 병렬화할 때 주의점

작성 0xmote · 2026년 7월 7일 · 45분 읽기 · 수정 2026년 10월 2일 고급 실습

들어가며: “정렬하는 동안 코어 하나만 100%를 쓰고 있어요”

#39-3 SIMD와 std::execution에서 std::execution::par 기초를 다뤘다면, 이 글은 C++17 병렬 알고리즘을 집중적으로 다룹니다. std::sort, std::transform, std::reduce 등 기존 STL 알고리즘에 실행 정책만 추가하면 멀티코어를 활용할 수 있습니다. 스레드 풀을 직접 만들 필요 없이, 표준 라이브러리가 알아서 병렬화합니다. 요구 환경: C++17 이상, <execution> 헤더 (MSVC/GCC/Clang 지원)

정렬·변환·집계가 한 코어에 묶이는 상황

대용량 배열 정렬이 병목일 때

상황: std::sort(v.begin(), v.end())는 기본적으로 순차 실행입니다. 데이터가 크면 한 스레드만 풀가동하고 나머지 코어는 유휴 상태입니다. 해결 포인트: std::sort(std::execution::par, v.begin(), v.end())로 바꾸면 내부적으로 여러 스레드가 구간을 나눠 정렬합니다. 가속비는 코어 수와 메모리 대역폭에 따라 다르고, 병합 단계 때문에 코어 수만큼은 나오지 않습니다.

이미지 픽셀 변환이 느릴 때

상황: 픽셀마다 out[i] = gamma_correct(in[i]) 같은 변환을 적용합니다. 200만 픽셀 × 순차 루프 = 한 코어만 사용합니다. 해결 포인트: std::transform(std::execution::par, in.begin(), in.end(), out.begin(), gamma_correct)로 병렬화하면 코어 수만큼 구간을 나눠 처리합니다.

대량 데이터 집계가 병목일 때

상황: std::accumulate는 순서가 보장되지만 병렬화할 수 없습니다. 합계·곱·최대값처럼 결합 법칙이 성립하면 순서를 바꿔도 결과가 같습니다. 해결 포인트: std::reduce(std::execution::par, v.begin(), v.end(), 0.0)로 바꾸면 부분 합을 병렬로 구한 뒤 합칩니다. 부동소수점은 accumulate와 미세하게 다른 결과가 나올 수 있으나, 대량 데이터에서는 허용되는 경우가 많습니다.

ETL 파이프라인에서 변환 단계가 느릴 때

상황: std::transform + std::copy_if 조합을 순차로 실행하면 I/O 대기 후 CPU도 한 코어만 사용합니다. 해결 포인트: std::transform(std::execution::par, ...)로 변환 단계를 병렬화하며, 가능하면 std::transform_reduce로 변환·집계를 한 번에 처리합니다.

스레드 풀 없이 간단히 병렬화하고 싶을 때

상황: std::async를 루프 안에서 호출하면 작업 수만큼 future와 스레드가 생성됩니다. 스레드 풀을 직접 구현하려면 작업 큐·워커·종료 처리 등이 필요합니다. 해결 포인트: std::for_each(std::execution::par, ...) 또는 std::transform(std::execution::par, ...)를 쓰면 라이브러리가 내부적으로 스레드 풀을 관리합니다. 코드 한 줄 추가로 병렬화됩니다.

par_unseq로 SIMD까지 활용하고 싶을 때

상황: std::execution::par는 멀티스레드만 적용합니다. par_unseq는 병렬 + 벡터화(SIMD)를 허용해, 한 스레드 내에서도 4~8개 원소를 한 번에 처리할 수 있습니다. 해결 포인트: 람다가 동기화 프리(락, atomic, 공유 변수 수정 없음)일 때만 par_unseq를 사용합니다. 위반 시 정의되지 않은 동작입니다.

seq·par·par_unseq 정책 비교

정책별 보장과 제약

flowchart TB
    subgraph seq["seq (순차)"]
        S1[원소 1] --> S2[원소 2] --> S3[원소 3] --> S4[...]
    end
    subgraph par["par (병렬)"]
        P1[스레드 1: 구간 A]
        P2[스레드 2: 구간 B]
        P3[스레드 3: 구간 C]
        P4[스레드 4: 구간 D]
    end
    subgraph par_unseq["par_unseq (병렬+SIMD)"]
        U1["스레드 1: SIMD로 8개씩"]
        U2["스레드 2: SIMD로 8개씩"]
    end

정책	설명	멀티스레드	SIMD	요구사항
seq	순차 실행 (기본)	❌	❌	없음
par	멀티스레드 병렬	✅	❌	반복자·함수 스레드 안전
par_unseq	병렬 + 벡터화	✅	✅	동기화 프리 (락·atomic 금지)
unseq (C++20)	단일 스레드 벡터화만	❌	✅	동기화 프리

seq vs par

// seq: 순차 실행 (기본값과 동일)
#include <algorithm>
#include <execution>
#include <vector>
void sort_sequential(std::vector<int>& v) {
    std::sort(std::execution::seq, v.begin(), v.end());
}
// par: 멀티스레드 병렬
void sort_parallel(std::vector<int>& v) {
    std::sort(std::execution::par, v.begin(), v.end());
}

par vs par_unseq

// par: 락 사용 가능 (스레드 안전만 지키면 됨)
std::mutex mtx;
std::for_each(std::execution::par, v.begin(), v.end(), [&mtx](int x) {
    std::lock_guard<std::mutex> lock(mtx);
    shared_result += process(x);
});
// par_unseq: 락·atomic·공유 변수 수정 금지 — 원소별 완전 독립만
std::transform(std::execution::par_unseq, a.begin(), a.end(), b.begin(),
               c.begin(), [](auto x, auto y) { return x * y + 1.0; });

par_unseq 위반 예:

// ❌ UB: par_unseq에서 락 사용
std::mutex m;
std::for_each(std::execution::par_unseq, v.begin(), v.end(), [&m](int x) {
    std::lock_guard<std::mutex> lock(m);  // 정의되지 않은 동작!
    counter++;
});

병렬 sort·transform·reduce 예제

std::execution::par — 병렬 정렬

#include <algorithm>
#include <execution>
#include <vector>
#include <random>
#include <chrono>
#include <iostream>
int main() {
    std::vector<int> v(10'000'000);
    std::mt19937 gen(42);
    std::uniform_int_distribution<> dis(0, 1'000'000);
    for (auto& x : v) x = dis(gen);
    auto start = std::chrono::high_resolution_clock::now();
    std::sort(std::execution::par, v.begin(), v.end());
    auto end = std::chrono::high_resolution_clock::now();
    auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
    std::cout << "Parallel sort: " << ms << " ms\n";
    return 0;
}

컴파일 (Windows MSVC):

cl /EHsc /std:c++17 /O2 /MD parallel_sort.cpp

컴파일 (Linux GCC):

# libstdc++의 병렬 알고리즘은 Intel TBB를 백엔드로 씀 (apt install libtbb-dev)
g++ -std=c++17 -O3 -o parallel_sort parallel_sort.cpp -ltbb
# TBB 헤더가 설치되어 있으면 -ltbb를 빼면 링크 에러가 나고,
# TBB 자체가 없으면 순차 백엔드로 컴파일되어 par를 붙여도 속도 차이가 없음

std::execution::par_unseq — 병렬 + SIMD 변환

#include <algorithm>
#include <execution>
#include <vector>
#include <cmath>
// 감마 보정: out = pow(in, gamma)
void gamma_correct_parallel(const std::vector<float>& in,
                            std::vector<float>& out,
                            float gamma) {
    out.resize(in.size());
    std::transform(std::execution::par_unseq,
                   in.begin(), in.end(),
                   out.begin(),
                   [gamma](float x) { return std::pow(x, gamma); });
}
// 벡터 덧셈 (완전 독립 → par_unseq 적합)
void add_vectors_par_unseq(const std::vector<double>& a,
                            const std::vector<double>& b,
                            std::vector<double>& c) {
    c.resize(a.size());
    std::transform(std::execution::par_unseq,
                   a.begin(), a.end(), b.begin(), c.begin(),
                   [](double x, double y) { return x + y; });
}

병렬 reduce — 합계·내적·최대값

#include <numeric>
#include <execution>
#include <vector>
#include <algorithm>
#include <limits>
// 병렬 합계
double sum_parallel(const std::vector<double>& v) {
    return std::reduce(std::execution::par, v.begin(), v.end(), 0.0);
}
// 병렬 내적 (dot product)
double dot_product_parallel(const std::vector<double>& a,
                            const std::vector<double>& b) {
    return std::transform_reduce(
        std::execution::par,
        a.begin(), a.end(), b.begin(), 0.0,
        std::plus<>(), std::multiplies<>());
}
// 병렬 최대값
int max_parallel(const std::vector<int>& v) {
    return std::reduce(std::execution::par, v.begin(), v.end(),
                       std::numeric_limits<int>::min(),
                       [](int a, int b) { return std::max(a, b); });
}

병렬 for_each — 인덱스 기반 처리

#include <algorithm>
#include <execution>
#include <vector>
#include <numeric>
void process_chunks_parallel(std::vector<int>& data) {
    std::vector<size_t> indices(data.size());
    std::iota(indices.begin(), indices.end(), 0);
    std::for_each(std::execution::par, indices.begin(), indices.end(),
                  [&data](size_t i) {
                      data[i] = data[i] * 2 + 1;  // 독립 연산
                  });
}

병렬 count_if — 조건 만족 개수

#include <algorithm>
#include <execution>
#include <vector>
size_t count_positive_parallel(const std::vector<double>& v) {
    return std::count_if(std::execution::par,
                         v.begin(), v.end(),
                         [](double x) { return x > 0; });
}

병렬 find — 순서는 그대로, 탐색만 나눠서

std::find에 par를 붙이면 여러 스레드가 구간을 나눠 동시에 훑습니다. 흔한 오해와 달리 결과는 순차 find와 같습니다. 표준은 병렬 버전도 “조건을 만족하는 첫 번째 원소”를 반환하도록 요구하므로, 값이 여러 개 있어도 어느 것이 나올지 흔들리지 않습니다. 대신 구현은 앞쪽 구간에서 이미 찾았으면 뒤쪽 스레드의 탐색을 일찍 접는 식으로 이득을 봅니다. 그래서 목표가 앞쪽에 몰려 있는 데이터에서는 병렬화 효과가 작고, 전체를 거의 다 봐야 하는 경우(없는 값을 찾는 경우 포함)에 효과가 큽니다.

#include <algorithm>
#include <execution>
#include <numeric>
#include <vector>

std::vector<int> v(10'000'000);
std::iota(v.begin(), v.end(), 1);
auto it = std::find(std::execution::par, v.begin(), v.end(), 5'000'000);
// it는 순차 find와 같은 위치를 가리킴 (인덱스 4'999'999)

병렬 파이프라인 — transform + reduce

#include <numeric>
#include <execution>
#include <vector>
#include <cmath>
// 각 원소 제곱 후 합계 (병렬)
double sum_of_squares_parallel(const std::vector<double>& v) {
    return std::transform_reduce(
        std::execution::par,
        v.begin(), v.end(), 0.0,
        std::plus<>(),
        [](double x) { return x * x; });
}
// L2 노름: sqrt(sum(x^2))
double l2_norm_parallel(const std::vector<double>& v) {
    double sum_sq = sum_of_squares_parallel(v);
    return std::sqrt(sum_sq);
}

실행 정책을 받는 알고리즘

C++17은 <algorithm>과 <numeric>의 알고리즘 대부분(약 70개)에 실행 정책을 받는 오버로드를 추가했습니다. 정책 오버로드가 있는 알고리즘은 seq·par·par_unseq(C++20부터 unseq)를 모두 받습니다. 예를 들어 std::sort에 par_unseq를 넘겨도 문법상 문제가 없고, 실제로 벡터화할지는 구현이 정합니다. 반대로 std::accumulate, std::partial_sum처럼 순서가 정의된 알고리즘에는 정책 오버로드가 없고, 대신 std::reduce, std::inclusive_scan 같은 순서 자유 버전이 추가되었습니다.

알고리즘	정책 오버로드	비고
`std::sort`, `std::stable_sort`	✅	랜덤 액세스 반복자 필요
`std::transform`, `std::for_each`	✅
`std::reduce`, `std::transform_reduce`	✅	`accumulate`의 병렬 대응
`std::inclusive_scan`, `std::exclusive_scan`	✅	`partial_sum`의 병렬 대응
`std::count_if`, `std::find_if`, `std::copy_if`	✅	반복자는 최소 forward iterator
`std::accumulate`, `std::partial_sum`	❌	순서가 정의된 알고리즘

병렬 partial_sort — 상위 K개만 정렬

#include <algorithm>
#include <execution>
#include <vector>
// 상위 100개만 정렬 (전체 정렬보다 빠름)
void top_k_parallel(std::vector<int>& v, size_t k) {
    std::partial_sort(std::execution::par,
                      v.begin(), v.begin() + k, v.end());
}

병렬 inclusive_scan — 누적 합 (C++17)

#include <numeric>
#include <execution>
#include <vector>
void prefix_sum_parallel(std::vector<int>& v) {
    std::inclusive_scan(std::execution::par, v.begin(), v.end(), v.begin());
}

병렬 all_of / any_of / none_of

#include <algorithm>
#include <execution>
#include <vector>
bool all_positive_parallel(const std::vector<double>& v) {
    return std::all_of(std::execution::par,
                       v.begin(), v.end(),
                       [](double x) { return x > 0; });
}
bool any_negative_parallel(const std::vector<double>& v) {
    return std::any_of(std::execution::par,
                       v.begin(), v.end(),
                       [](double x) { return x < 0; });
}

병렬 fill_n — 대량 초기화

#include <algorithm>
#include <execution>
#include <vector>
void init_parallel(std::vector<int>& v, int value) {
    std::fill(std::execution::par, v.begin(), v.end(), value);
}

데이터 레이스, par_unseq 락, 부동소수점 reduce 차이: 에러 해결

에러 진단 플로우

flowchart TD
    A[에러 발생] --> B{데이터 레이스?}
    B -->|Yes| C[reduce/transform_reduce 사용]
    B -->|No| D{par_unseq 사용?}
    D -->|Yes| E{락/atomic/공유변수?}
    E -->|Yes| F[par로 변경]
    E -->|No| G[유지]
    D -->|No| H{반복자 무효화?}
    H -->|Yes| I[별도 출력 버퍼 사용]
    H -->|No| J[캡처·예외 검토]

데이터 레이스 — 공유 변수 수정

증상: 간헐적 크래시, 잘못된 결과, ThreadSanitizer 경고.

// ❌ 잘못된 예: 공유 변수에 병렬로 쓰기
int sum = 0;
std::for_each(std::execution::par, v.begin(), v.end(), [&sum](int x) {
    sum += x;  // 데이터 레이스!
});

해결법:

// ✅ reduce 사용 (원소별 독립, 부분 합 후 병합)
int sum = std::reduce(std::execution::par, v.begin(), v.end(), 0);
// 또는 atomic (성능 저하, 꼭 필요할 때만)
std::atomic<int> sum{0};
std::for_each(std::execution::par, v.begin(), v.end(), [&sum](int x) {
    sum.fetch_add(x);  // 동기화 오버헤드 큼
});

공유 변수에 쓰는 경우만 레이스가 아닙니다. 다른 원소를 읽으면서 동시에 원소를 고치는 코드도 똑같이 위험합니다. 아래 코드는 모든 스레드가 v[0]을 읽는데, 그중 한 스레드는 v[0] 자체를 덮어씁니다. 어떤 스레드가 고치기 전 값을 보고 어떤 스레드가 고친 뒤 값을 보는지 정해져 있지 않아 실행마다 결과가 달라집니다.

// ❌ 다른 원소(v[0])에 의존 — 읽기와 쓰기가 섞임
std::for_each(std::execution::par, v.begin(), v.end(), [&v](int& x) { x = v[0] + 1; });

// ✅ 각 원소가 자기 값만 사용
std::for_each(std::execution::par, v.begin(), v.end(), [](int& x) { x = x * 2; });

// ✅ 이웃 값이 필요하면 원본을 따로 두고 읽기 전용으로 참조 (블러 같은 필터)
//    인덱스는 원소 주소로 역산하지 말 것: 병렬 알고리즘은 trivially copyable 원소를 복사해서 넘길 수 있음
const std::vector<int> src = v;
std::vector<std::size_t> idx(src.size() - 2);
std::iota(idx.begin(), idx.end(), 1);
std::for_each(std::execution::par, idx.begin(), idx.end(),
              [&](std::size_t i) { v[i] = (src[i - 1] + src[i] + src[i + 1]) / 3; });  // 쓰기는 v[i]에만

순차 코드에서 v[0] + 1 같은 식이 멀쩡히 돌던 걸 그대로 par로 바꿨다가 테스트 데이터에서는 우연히 맞고 운영 데이터에서만 틀리는 경우가 이 유형입니다. ThreadSanitizer로 한 번 돌려 보면 바로 잡히므로, 병렬 정책을 붙인 커밋에는 TSan 빌드를 함께 돌리는 습관이 가장 싸게 먹힙니다.

par_unseq에서 락 사용

증상: 데드락, 정의되지 않은 동작, 간헐적 크래시.

// ❌ par_unseq에서 mutex 사용 — UB
std::mutex mtx;
std::for_each(std::execution::par_unseq, v.begin(), v.end(), [&mtx](int x) {
    std::lock_guard<std::mutex> lock(mtx);
    process(x);
});

해결법:

// ✅ par만 사용 (락 허용)
std::for_each(std::execution::par, v.begin(), v.end(), [&mtx](int x) {
    std::lock_guard<std::mutex> lock(mtx);
    process(x);
});
// 또는 락 없이 각 스레드별 로컬 결과 수집 후 병합
std::vector<int> results(v.size());
std::transform(std::execution::par_unseq, v.begin(), v.end(), results.begin(),
               [](int x) { return process(x); });

반복자 무효화

증상: 크래시, 잘못된 결과.

// ❌ 병렬 처리 중 컨테이너 수정
std::for_each(std::execution::par, v.begin(), v.end(), [&v](int x) {
    if (x > 0) v.push_back(x);  // 반복자 무효화!
});

해결법:

// ✅ 출력을 별도 컨테이너에
std::vector<int> result;
result.reserve(v.size());
std::mutex mtx;
std::for_each(std::execution::par, v.begin(), v.end(), [&](int x) {
    if (x > 0) {
        std::lock_guard<std::mutex> lock(mtx);
        result.push_back(x);
    }
});
// 또는 copy_if + par
std::vector<int> result(v.size());
auto end = std::copy_if(std::execution::par, v.begin(), v.end(), result.begin(),
                         [](int x) { return x > 0; });
result.erase(end, result.end());

람다의 참조 캡처는 안전한가

병렬 알고리즘은 모든 작업이 끝난 뒤에 반환하는 블로킹 호출이므로, 알고리즘 호출 동안 살아 있는 지역 변수를 [&]로 캡처하는 것은 안전합니다. 위험해지는 것은 std::async나 스레드 풀에 작업을 넘기고 함수가 먼저 반환하는 경우입니다. 병렬 알고리즘에서 신경 쓸 것은 수명이 아니라, 여러 스레드가 그 참조를 통해 같은 데이터를 동시에 수정하지 않는지입니다.

부동소수점 reduce vs accumulate 차이

증상: std::reduce 결과가 std::accumulate와 미세하게 다름.

// accumulate: 순서 보장 (a + b + c + d)
// reduce: 부분 합 병합 ((a+b) + (c+d)) — 결합 순서 비결정
std::vector<float> v(1000000, 0.1f);
float acc = std::accumulate(v.begin(), v.end(), 0.0f);
float red = std::reduce(std::execution::par, v.begin(), v.end(), 0.0f);
// acc != red (부동소수점 누적 오차로 인해)

해결법: 순서가 중요하면 accumulate(순차). 대량 데이터에서 성능이 중요하고 미세 오차가 허용되면 reduce(병렬). Kahan summation이 필요하면 별도 구현.

빈 범위 또는 단일 원소

증상: 일부 구현에서 예외 또는 비정상 동작.

// 빈 벡터
std::vector<int> empty;
std::sort(std::execution::par, empty.begin(), empty.end());  // OK (no-op)
// 단일 원소 — 병렬화 이득 없지만 안전
std::vector<int> single = {42};
std::sort(std::execution::par, single.begin(), single.end());  // OK

해결법: 표준은 빈 범위를 허용합니다. 구현체에 따라 작은 크기에서는 순차로 폴백할 수 있으므로, 임계값(예: 1000 이상) 이상에서만 par를 쓰는 선택적 적용도 가능합니다.

GCC에서 TBB 링크 오류

증상: undefined reference to tbb::... 링크 오류, 또는 par를 붙였는데 전혀 빨라지지 않음. 해결법: GCC의 libstdc++는 병렬 알고리즘의 백엔드로 Intel oneTBB를 씁니다. TBB 헤더가 있으면 TBB를 링크해야 하고, 없으면 순차 백엔드로 조용히 대체됩니다.

sudo apt install libtbb-dev

# CMake
find_package(TBB REQUIRED)
target_link_libraries(myapp PRIVATE TBB::tbb)

MSVC는 표준 라이브러리가 Windows 스레드 풀을 이용해 병렬 알고리즘을 자체 구현하므로 별도 라이브러리가 필요 없습니다. Clang은 libstdc++를 쓰면 GCC와 같고, libc++의 병렬 알고리즘 지원은 버전에 따라 제한적이므로 문서를 확인해야 합니다.

정렬·검색 기준 불일치

증상: std::lower_bound 등으로 찾은 결과가 기대와 다름.

// ❌ 정렬은 name, 검색은 id — UB
std::sort(std::execution::par, users.begin(), users.end(),
          [](const auto& a, const auto& b) { return a.name < b.name; });
auto it = std::lower_bound(users.begin(), users.end(), target_id,
     [](const auto& u, int id) { return u.id < id; });

해결법: 정렬 기준과 검색 기준이 동일해야 합니다.

// ✅ id로 정렬 후 id로 검색
std::sort(std::execution::par, users.begin(), users.end(),
          [](const auto& a, const auto& b) { return a.id < b.id; });
auto it = std::lower_bound(users.begin(), users.end(), target_id,
     [](const auto& u, int id) { return u.id < id; });

커스텀 비교자에서 스레드 안전 위반

증상: 병렬 정렬 시 간헐적 크래시, 잘못된 결과.

// ❌ 비교자가 캡처한 상태를 수정함
int counter = 0;
std::sort(std::execution::par, v.begin(), v.end(),
    [&counter](int a, int b) {
        counter++;  // 데이터 레이스!
        return a < b;
    });

해결법: 비교자·함수 객체는 상태 불변이어야 합니다. 읽기 전용 캡처만 사용합니다.

// ✅ 순수 함수
std::sort(std::execution::par, v.begin(), v.end(),
     [](int a, int b) { return a < b; });

반복자 종류 제한

증상: std::sort(std::execution::par, list.begin(), list.end()) — 컴파일 에러. 원인: std::sort는 RandomAccessIterator가 필요합니다. std::list는 BidirectionalIterator만 제공합니다. 해결법: std::list는 list.sort() 멤버 함수를 사용합니다. 병렬 정렬이 필요하면 std::vector로 복사 후 정렬 후 다시 복사하거나, 다른 자료구조를 사용합니다.

// std::list → vector로 복사 후 병렬 정렬
std::list<int> lst = {3, 1, 4, 1, 5};
std::vector<int> vec(lst.begin(), lst.end());
std::sort(std::execution::par, vec.begin(), vec.end());
lst.assign(vec.begin(), vec.end());

작은 데이터는 seq·독립성 확인 같은 적용 원칙

작은 데이터는 seq 유지

// 100개 미만: 병렬 오버헤드가 이득보다 클 수 있음
if (v.size() < 1000) {
    std::sort(std::execution::seq, v.begin(), v.end());
} else {
    std::sort(std::execution::par, v.begin(), v.end());
}

독립성 확인 후 par_unseq

// 원소 간 독립 + 동기화 없음 → par_unseq
std::transform(std::execution::par_unseq, a.begin(), a.end(), b.begin(),
               [](double x) { return std::sqrt(x); });
// 공유 상태 접근 → par만
std::for_each(std::execution::par, v.begin(), v.end(), [&](int x) {
    std::lock_guard<std::mutex> lock(mtx);
    log(x);
});

출력 버퍼는 resize로 미리 만들기

병렬 알고리즘은 최소 forward iterator를 요구하므로 std::back_inserter 같은 출력 반복자를 쓸 수 없습니다. 출력 컨테이너를 미리 resize해 두고 일반 반복자를 넘깁니다.

std::vector<double> result;
result.resize(input.size());
std::transform(std::execution::par, input.begin(), input.end(),
               result.begin(), transform_fn);

예외 안전성

표준 실행 정책(seq·par·par_unseq)을 쓸 때, 알고리즘에 넘긴 함수에서 예외가 밖으로 새어 나가면 std::terminate가 호출됩니다. 순차 알고리즘처럼 try/catch로 감싸 두면 잡힐 거라고 기대하기 쉽지만 그렇지 않습니다. 예외로 호출자에게 전달되는 것은 알고리즘이 내부 작업 공간을 할당하지 못했을 때의 std::bad_alloc 정도입니다. 그래서 병렬 알고리즘에 넘기는 함수는 예외를 던지지 않게 만들고, 실패는 값으로 기록한 뒤 알고리즘이 끝나고 나서 처리합니다.

// ❌ 순차 코드 습관 그대로: catch에 도달하지 못하고 terminate
try {
    std::for_each(std::execution::par, v.begin(), v.end(), [](int x) {
        if (x < 0) throw std::runtime_error("음수");
    });
} catch (...) { /* 여기 오지 않음 */ }

// ✅ 실패를 플래그(또는 결과 값)로 기록하고 끝난 뒤 처리
std::atomic<bool> has_negative{false};
std::for_each(std::execution::par, v.begin(), v.end(), [&](int x) noexcept {
    if (x < 0) has_negative.store(true, std::memory_order_relaxed);
});
if (has_negative) { /* 에러 처리 */ }

프로파일링 후 적용

// 추측이 아닌 측정
auto start = std::chrono::high_resolution_clock::now();
std::sort(std::execution::par, v.begin(), v.end());
auto end = std::chrono::high_resolution_clock::now();
// 병목이 확인된 부분만 병렬화

연속 메모리 활용

// ✅ std::vector — 연속 메모리, 캐시 친화적
std::vector<double> data(1'000'000);
std::transform(std::execution::par, data.begin(), data.end(), data.begin(),
               [](double x) { return std::sqrt(x); });
// ⚠️ std::deque — 연속이 아님, 병렬 알고리즘은 동작하지만 캐시 효율 낮음

이동 시맨틱 활용

// ✅ 이동으로 불필요한 복사 제거
std::vector<BigObject> process_parallel(std::vector<BigObject> input) {
    std::vector<BigObject> result(input.size());
    std::transform(std::execution::par,
                  std::make_move_iterator(input.begin()),
                  std::make_move_iterator(input.end()),
                  result.begin(),
                  [](BigObject&& obj) { return process(std::move(obj)); });
    return result;
}

조건부 병렬화

#include <algorithm>
#include <execution>
#include <vector>
template <typename It>
void sort_adaptive(It first, It last) {
    constexpr size_t PARALLEL_THRESHOLD = 10'000;
    if (std::distance(first, last) < PARALLEL_THRESHOLD) {
        std::sort(std::execution::seq, first, last);
    } else {
        std::sort(std::execution::par, first, last);
    }
}

sort 벤치마크와 결과 읽는 법

벤치마크 예제 (sort)

#include <algorithm>
#include <execution>
#include <vector>
#include <random>
#include <chrono>
#include <iostream>
int main() {
    const size_t N = 10'000'000;
    std::vector<int> v(N);
    std::mt19937 gen(42);
    std::uniform_int_distribution<> dis(0, 1'000'000);
    for (auto& x : v) x = dis(gen);
    auto seq = v;
    auto par = v;
    auto t1 = std::chrono::high_resolution_clock::now();
    std::sort(std::execution::seq, seq.begin(), seq.end());
    auto t2 = std::chrono::high_resolution_clock::now();
    std::sort(std::execution::par, par.begin(), par.end());
    auto t3 = std::chrono::high_resolution_clock::now();
    auto ms_seq = std::chrono::duration_cast<std::chrono::milliseconds>(t2 - t1).count();
    auto ms_par = std::chrono::duration_cast<std::chrono::milliseconds>(t3 - t2).count();
    std::cout << "seq: " << ms_seq << " ms, par: " << ms_par << " ms, speedup: "
              << (double)ms_seq / ms_par << "x\n";
    return 0;
}

결과를 읽는 법

숫자는 CPU 코어 수, 메모리 대역폭, 표준 라이브러리 구현(GCC는 TBB 백엔드 필요, MSVC는 자체 구현)에 따라 크게 달라서 여기 고정값을 적지 않았습니다. 직접 재 보면 대체로 이런 경향이 보입니다.

sort: 연산량이 많아(n log n) 코어 수에 가깝게 빨라지는 편이지만, 병합 단계와 메모리 대역폭 때문에 코어 수만큼은 나오지 않습니다.
transform·reduce: 원소당 연산이 가벼우면 금방 메모리 대역폭 한계에 걸려, 코어를 늘려도 가속비가 일찍 멈춥니다. 원소당 계산이 무거울수록(삼각함수, 복잡한 변환) 병렬 이득이 커집니다.
작은 입력: 수천 개 이하에서는 스레드 분배 비용 때문에 seq가 더 빠른 경우가 흔합니다. 앞의 “작은 데이터는 seq 유지”에 쓴 기준값도 이런 측정으로 정해야 합니다.
GCC에서 -ltbb 없이 빌드하면 par를 붙여도 순차로 돌아 가속비가 1배로 나옵니다. 벤치마크 전에 백엔드가 실제로 연결됐는지 확인하세요.

파이프라인·청크 병렬·Map-Reduce 집계

파이프라인 — transform → filter → reduce

// 1. 변환 (병렬)
std::vector<double> transformed(data.size());
std::transform(std::execution::par, data.begin(), data.end(),
               transformed.begin(), [](double x) { return std::sqrt(x); });
// 2. 필터 (병렬): back_inserter는 병렬 정책과 쓸 수 없으므로 최대 크기로 만들고 잘라냄
std::vector<double> filtered(transformed.size());
auto last = std::copy_if(std::execution::par, transformed.begin(), transformed.end(),
                         filtered.begin(), [](double x) { return x > 0; });
filtered.erase(last, filtered.end());
// 3. 집계 (병렬)
double sum = std::reduce(std::execution::par, filtered.begin(), filtered.end(), 0.0);
// 실제로는 1~3을 transform_reduce 한 번으로 합치면 중간 버퍼가 필요 없다

배치 처리 — 청크 단위 병렬

void process_batch_parallel(const std::vector<Item>& items,
                            std::vector<Result>& results) {
    results.resize(items.size());
    std::transform(std::execution::par,
                   items.begin(), items.end(),
                   results.begin(),
                   [](const Item& item) { return process(item); });
}

std::execution과 스레드 풀 병행

// 병렬 알고리즘: 데이터 중심, 일괄 처리
std::sort(std::execution::par, v.begin(), v.end());
// 스레드 풀: 작업 중심, 비동기 이벤트
pool.submit([&]() { handle_request(req); });

예외 처리 래퍼

template <typename Policy, typename It, typename... Args>
auto safe_parallel_sort(Policy policy, It first, It last, Args&&... args) {
    try {
        std::sort(policy, first, last, std::forward<Args>(args)...);
    } catch (const std::bad_alloc&) {
        // 병렬 실행용 임시 버퍼를 못 잡았을 때만 여기로 옴 → 메모리를 덜 쓰는 순차로 폴백
        std::sort(std::execution::seq, first, last, std::forward<Args>(args)...);
    }
}

이 래퍼가 잡을 수 있는 건 std::bad_alloc뿐입니다. 비교 함수가 던진 예외는 std::terminate로 이어지므로(앞의 “예외 안전성” 참고), 비교자·변환 함수는 애초에 던지지 않게 작성해야 합니다.

Map-Reduce 스타일 집계

// 1단계: 각 청크별 부분 결과 (map)
// 2단계: 부분 결과 병합 (reduce)
struct Stats {
    double sum = 0;
    size_t count = 0;
};
Stats aggregate_parallel(const std::vector<double>& v) {
    return std::transform_reduce(
        std::execution::par,
        v.begin(), v.end(),
        Stats{},
        [](Stats a, Stats b) {
            return Stats{a.sum + b.sum, a.count + b.count};
        },
        [](double x) { return Stats{x, 1}; });
}

병렬 정렬 + 이진 검색 파이프라인

// 대량 데이터 정렬 후 반복 검색
void build_lookup_table(std::vector<std::pair<int, Data>>& table) {
    std::sort(std::execution::par, table.begin(), table.end(),
              [](const auto& a, const auto& b) { return a.first < b.first; });
}
Data lookup(const std::vector<std::pair<int, Data>>& table, int key) {
    auto it = std::lower_bound(table.begin(), table.end(), key,
         [](const auto& p, int k) { return p.first < k; });
    return (it != table.end() && it->first == key) ? it->second : Data{};
}

CPU 코어 수 기반 청크 분할

#include <thread>
#include <algorithm>
#include <execution>
// 라이브러리가 자동으로 처리하지만, 수동 제어가 필요할 때
size_t optimal_chunk_size(size_t total) {
    size_t cores = std::thread::hardware_concurrency();
    return std::max(size_t(1), total / (cores * 4));  // 코어당 4청크
}

병렬 알고리즘 + 스레드 풀 혼합

// 배치 데이터: std::execution::par (데이터 병렬)
void process_batch(std::vector<Item>& items) {
    std::transform(std::execution::par, items.begin(), items.end(),
                  items.begin(), process_item);
}
// 이벤트 기반 작업: 스레드 풀 (작업 병렬)
void handle_requests(ThreadPool& pool, const std::vector<Request>& reqs) {
    for (const auto& req : reqs) {
        pool.submit([req]() { handle_request(req); });
    }
}

참고 자료

FAQ

Q. 병렬 알고리즘을 언제 적용해야 하나요? A. 프로파일에서 std::sort, std::transform, std::reduce 등이 병목일 때, 대량 데이터(수만~수백만 이상)에서 std::execution::par를 적용합니다. 1000개 미만에서는 오버헤드가 이득보다 클 수 있어 seq를 유지하는 것이 좋습니다. Q. par와 par_unseq 중 뭘 써야 하나요? A. 먼저 par로 병렬화해 효과를 확인합니다. 람다가 완전히 독립적이고(락·atomic·공유 변수 없음) 추가 가속이 필요하면 par_unseq를 시도합니다. par_unseq 위반 시 UB이므로 주의가 필요합니다. Q. std::accumulate를 std::reduce로 바꿔도 되나요? A. 합계·곱·최대값처럼 결합 법칙이 성립하면 reduce로 바꿔도 됩니다. 부동소수점은 accumulate와 미세하게 다른 결과가 나올 수 있으므로, 수치 정확도가 중요한 경우에는 검토가 필요합니다. Q. 병렬 알고리즘을 쓰니 링크 에러가 나요. A. MSVC는 별도 라이브러리 없이 병렬 알고리즘을 지원하므로, 링크 에러가 난다면 /std:c++17 이상으로 빌드했는지와 런타임 라이브러리 설정이 일관적인지부터 확인합니다. TBB 관련 링크 에러는 GCC(libstdc++)에서 나는 문제로, -ltbb 또는 CMake의 TBB::tbb 링크로 해결합니다.

다음 글: C++ 앱의 DB 쿼리 최적화: 인덱스 선택, 실행 계획, 통계 기반 비용 모델

들어가며: “정렬하는 동안 코어 하나만 100%를 쓰고 있어요”

정렬·변환·집계가 한 코어에 묶이는 상황

대용량 배열 정렬이 병목일 때

이미지 픽셀 변환이 느릴 때

대량 데이터 집계가 병목일 때

ETL 파이프라인에서 변환 단계가 느릴 때

스레드 풀 없이 간단히 병렬화하고 싶을 때

par_unseq로 SIMD까지 활용하고 싶을 때

seq·par·par_unseq 정책 비교

정책별 보장과 제약

seq vs par

par vs par_unseq

병렬 sort·transform·reduce 예제

std::execution::par — 병렬 정렬

std::execution::par_unseq — 병렬 + SIMD 변환

병렬 reduce — 합계·내적·최대값

병렬 for_each — 인덱스 기반 처리

병렬 count_if — 조건 만족 개수

병렬 find — 순서는 그대로, 탐색만 나눠서

병렬 파이프라인 — transform + reduce

실행 정책을 받는 알고리즘

병렬 partial_sort — 상위 K개만 정렬

병렬 inclusive_scan — 누적 합 (C++17)

병렬 all_of / any_of / none_of

병렬 fill_n — 대량 초기화

데이터 레이스, par_unseq 락, 부동소수점 reduce 차이: 에러 해결

에러 진단 플로우

데이터 레이스 — 공유 변수 수정

par_unseq에서 락 사용

반복자 무효화

람다의 참조 캡처는 안전한가

부동소수점 reduce vs accumulate 차이

빈 범위 또는 단일 원소

GCC에서 TBB 링크 오류

정렬·검색 기준 불일치

커스텀 비교자에서 스레드 안전 위반

반복자 종류 제한

작은 데이터는 seq·독립성 확인 같은 적용 원칙

작은 데이터는 seq 유지

독립성 확인 후 par_unseq

출력 버퍼는 resize로 미리 만들기

예외 안전성

프로파일링 후 적용

연속 메모리 활용

이동 시맨틱 활용

조건부 병렬화

sort 벤치마크와 결과 읽는 법

벤치마크 예제 (sort)

결과를 읽는 법

파이프라인·청크 병렬·Map-Reduce 집계

파이프라인 — transform → filter → reduce

배치 처리 — 청크 단위 병렬

std::execution과 스레드 풀 병행

예외 처리 래퍼

Map-Reduce 스타일 집계

병렬 정렬 + 이진 검색 파이프라인

CPU 코어 수 기반 청크 분할

병렬 알고리즘 + 스레드 풀 혼합

참고 자료

FAQ

같이 보면 좋은 글