RecursiveTask와 분할 경계
ForkJoinPool과 RecursiveTask의 실행 구조를 만들고 겹치는 분할 오답·리프 크기·fork·compute·join 순서를 확인합니다.
Fork/Join 프레임워크는 ForkJoinPool이 작업자와 큐를 관리하고 ForkJoinTask가 분할 가능한 계산을 표현합니다.
값이 필요한 작업은 RecursiveTask<V>, 결과 없는 동작은 RecursiveAction을 상속합니다.
중요한 것은 class 이름이 아니라 분할이 전체 입력을 정확히 한 번 덮고, 리프 결과를 결합해 순차 기준과 같은 값을 만드는 것입니다.
midpoint를 양쪽 범위에 포함
양끝을 포함하는 범위 [from, to]를 [from, mid]와 [mid, to]로 나누면 중간점이 중복됩니다.
1~8에 10을 곱해 합친 값은 360입니다. 아래 코드의 분할을 따라가면 wrong-sum=400으로 계산됩니다.
루트 작업의 중간점 4가 양쪽 리프에 반복해서 포함되기 때문입니다.
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
public final class OverlappingForkJoinSplitBug {
private static final class SumTask extends RecursiveTask<Integer> {
private final int from;
private final int to;
private SumTask(int from, int to) {
this.from = from;
this.to = to;
}
@Override
protected Integer compute() {
if (to - from + 1 <= 5) {
int sum = 0;
for (int value = from; value <= to; value++) {
sum += value * 10;
}
return sum;
}
int middle = (from + to) >>> 1;
SumTask left = new SumTask(from, middle);
SumTask right = new SumTask(middle, to);
left.fork();
return right.compute() + left.join();
}
}
public static void main(String[] args) {
try (ForkJoinPool pool = new ForkJoinPool(4)) {
int result = pool.invoke(new SumTask(1, 8));
System.out.println("wrong-sum=" + result);
}
}
}원칙은 반열린 범위 [from, to)를 일관되게 사용하거나, 양끝을 포함하는 범위라면 오른쪽을 mid + 1부터 시작하는 것입니다.
종료 조건도 같은 범위 정의로 계산해야 빈 범위, 무한 재귀, 중복 계산을 피할 수 있습니다.
예시 inclusive 버그 예제의 왼쪽 [1,4]는 100이고 오른쪽 [4,8]은 300입니다. threshold 5 때문에 두 범위가 모두 직접 계산되어 합계 400이며, 4의 항 40이 중복된 오답입니다. 오른쪽 시작을 5로 정하면 260이 되어 360입니다. 인덱스 반열린 [0,4)·[4,8)에서는 숫자 4가 경계로 두 번 적혀도 왼쪽의 실제 인덱스 4는 포함되지 않습니다.
완전한 RecursiveTask 구현
아래 구현은 List<Integer>의 반열린 인덱스 범위를 사용합니다.
범위 크기가 임계값 이하이면 직접 계산하고, 그보다 크면 정확히 둘로 나눕니다. 원문처럼 임계값은 1 이상이어야 크기 1인 범위에서도 재귀가 끝납니다.
왼쪽 작업을 fork해 큐에 공개하고 오른쪽 작업은 현재 작업자가 계산한 뒤 왼쪽 작업을 join합니다.
import java.util.List;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
public final class RecursiveListSumTask {
private static final class SumTask extends RecursiveTask<Integer> {
private final List<Integer> values;
private final int from;
private final int to;
private final int threshold;
private SumTask(List<Integer> values, int from, int to, int threshold) {
this.values = values;
this.from = from;
this.to = to;
this.threshold = threshold;
}
@Override
protected Integer compute() {
int size = to - from;
if (size <= threshold) {
int subtotal = 0;
for (int index = from; index < to; index++) {
subtotal += values.get(index) * 10;
}
return subtotal;
}
int middle = from + size / 2;
SumTask left = new SumTask(values, from, middle, threshold);
SumTask right = new SumTask(values, middle, to, threshold);
left.fork();
int rightResult = right.compute();
return left.join() + rightResult;
}
}
public static void main(String[] args) {
List<Integer> values = List.of(1, 2, 3, 4, 5, 6, 7, 8);
try (ForkJoinPool pool = new ForkJoinPool(4)) {
int result = pool.invoke(new SumTask(values, 0, values.size(), 2));
System.out.println("sum=" + result);
}
}
}아래는 임계값 2에서의 인덱스 범위와 각 원소에 10을 곱한 부분합입니다. 연결선은 분할 관계이며 작업자의 실행 순서는 아닙니다.
인덱스 [0, 8)을 겹치지 않는 네 리프로 나누어 값 1부터 8의 열 배를 한 번씩 더하면 합계 360이 됩니다. 연결선은 범위 분할을 나타내며 작업자의 실행 순서나 동시 실행을 나타내지 않습니다.
겹치지 않는 인덱스 분할
반열린 인덱스 범위의 분할과 부분합
값 1~8에 10을 곱해 더합니다. [from, to)는 인덱스 범위이며, 연결선은 부분합의 분할 관계를 나타냅니다.
인덱스 [0,2)는 저장된 값 1·2의 30, [2,4)는 3·4의 70, [4,6)는 5·6의 110, [6,8)는 7·8의 150입니다. 인덱스와 값이 1씩 다르므로 [0,2)를 값 0·1의 10으로 계산하지 않습니다. 네 리프가 덮는 인덱스는 0부터 7까지 각각 한 번입니다.
pool.invoke(task)는 작업을 제출하고 결과가 완성될 때까지 기다립니다.
compute() 안에서 블로킹 I/O를 수행하면 제한된 작업자가 모두 대기할 수 있으므로 이 구조는 짧고 CPU 중심인 리프에 더 잘 맞습니다.
임계값은 정확성과 별개의 성능 매개변수
임계값이 1이면 리프가 많아져 병렬 실행 기회와 스케줄링 비용이 모두 커집니다.
임계값이 전체 크기 이상이면 작업 하나가 순차로 계산합니다.
임계값을 바꿔도 결과는 같아야 합니다.
다음 확인 프로그램은 리프 수와 최대 깊이를 함께 출력해 분할 구조를 관찰합니다.
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
import java.util.concurrent.atomic.AtomicInteger;
public final class ForkJoinThresholdProbe {
private record Result(long sum, int depth) {}
private static final class ProbeTask extends RecursiveTask<Result> {
private final int from;
private final int to;
private final int threshold;
private final AtomicInteger leaves;
private final int depth;
private ProbeTask(int from, int to, int threshold, AtomicInteger leaves, int depth) {
this.from = from;
this.to = to;
this.threshold = threshold;
this.leaves = leaves;
this.depth = depth;
}
@Override
protected Result compute() {
if (to - from <= threshold) {
leaves.incrementAndGet();
long sum = 0;
for (int value = from; value < to; value++) {
sum += value;
}
return new Result(sum, depth);
}
int middle = from + (to - from) / 2;
ProbeTask left = new ProbeTask(from, middle, threshold, leaves, depth + 1);
ProbeTask right = new ProbeTask(middle, to, threshold, leaves, depth + 1);
left.fork();
Result second = right.compute();
Result first = left.join();
return new Result(first.sum() + second.sum(), Math.max(first.depth(), second.depth()));
}
}
public static void main(String[] args) {
for (int threshold : new int[] {1, 4, 16}) {
AtomicInteger leaves = new AtomicInteger();
try (ForkJoinPool pool = new ForkJoinPool(4)) {
Result result = pool.invoke(new ProbeTask(1, 17, threshold, leaves, 0));
System.out.printf(
"threshold=%d, sum=%d, leaves=%d, depth=%d%n",
threshold, result.sum(), leaves.get(), result.depth());
}
}
}
}원문의 반열린 범위 [1, 17)을 같은 규칙으로 나누면 다음 구조가 됩니다. 깊이는 루트를 0으로 셉니다.
임계값에 따른 리프 수와 재귀 깊이
작업 개수는 바뀌어도 합계는 동일
임계값에 따른 리프 수와 재귀 깊이
값 1~16의 합계는 136입니다. 루트 깊이를 0으로 셀 때, 임계값이 커지면 리프 수와 최대 깊이가 줄어듭니다.
임계값
1
- 리프 수 · 최대 깊이
- 16개 · 깊이 4
- 합계
- 136
임계값
4
- 리프 수 · 최대 깊이
- 4개 · 깊이 2
- 합계
- 136
임계값
16
- 리프 수 · 최대 깊이
- 1개 · 깊이 0
- 합계
- 136
이 표는 분할 구조를 비교합니다. 실행 시간이나 작업 훔치기 횟수의 측정 결과가 아닙니다.
이 확인 프로그램의 AtomicInteger는 계산 결과가 아니라 계측 카운터입니다.
독립 확인: 같은 반열린 규칙과 루트 깊이 0을 쓰되 [1,6)의 값 다섯 개를 분할합니다. threshold 2와 1의 리프 수·최대 깊이·합계를 각각 구하세요. threshold가 0이면 크기 1인 범위도 계속 분할해야 하므로 기존 종료 전제에 맞나요?
풀이 확인
threshold 2는 크기 5→2와 3→1과 2로 분할해 리프 3개·최대 깊이 2·합 15입니다. threshold 1은 각 값 하나씩 리프 5개·최대 깊이 3·합 15입니다. 0은 원문의 1 이상 전제 밖이라 크기 1의 같은 범위가 다시 자식으로 생겨 종료를 보장하지 않습니다. 잘못된 0 실행을 실제 무한 재귀로 시험하지 말고 size/middle 조건을 추적해 판정합니다.
핵심 결과는 각 작업이 반환해 결합합니다.
실측에서는 카운터 자체가 경합을 만들어 시간을 왜곡할 수 있으므로 구조 확인용 실행과 벤치마크 실행을 분리합니다.
RecursiveAction의 적용 범위
배열의 서로 겹치지 않는 구간을 제자리 변환하는 작업처럼 각 리프가 독립 메모리 영역을 소유할 때 RecursiveAction을 사용할 수 있습니다.
같은 원소나 컬렉션 구조를 여러 리프가 바꾸면 데이터 경합이 됩니다.
import java.util.Arrays;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;
public final class DisjointArrayTransformAction {
private static final class DoubleAction extends RecursiveAction {
private final int[] values;
private final int from;
private final int to;
private DoubleAction(int[] values, int from, int to) {
this.values = values;
this.from = from;
this.to = to;
}
@Override
protected void compute() {
if (to - from <= 2) {
for (int index = from; index < to; index++) {
values[index] *= 2;
}
return;
}
int middle = from + (to - from) / 2;
invokeAll(new DoubleAction(values, from, middle), new DoubleAction(values, middle, to));
}
}
public static void main(String[] args) {
int[] values = {1, 2, 3, 4, 5, 6, 7, 8};
try (ForkJoinPool pool = new ForkJoinPool(4)) {
pool.invoke(new DoubleAction(values, 0, values.length));
}
System.out.println(Arrays.toString(values));
}
}fork·join 남용 방지
fork()는 하위 작업을 작업자 큐에 넣어 다른 작업자가 가져갈 기회를 줍니다.
join()은 완료되지 않았으면 기다리거나 도움 실행을 합니다.
모든 하위 작업을 fork하는 방식이 언제나 잘못은 아닙니다. 다만 현재 작업자가 하위 작업 하나를 직접 계산하면 제출 비용을 줄일 수 있으며, 여러 작업을 fork했다면 가장 나중에 만든 작업부터 join하는 방식도 검토합니다.
- 하위 작업 하나를
fork하고 다른 하위 작업을 직접compute한다. join은 의존성이 실제로 필요한 지점까지 늦춘다.- 리프가 너무 작아지지 않도록 임계값을 데이터와 연산량에 맞춘다.
- 결합 연산은 가능하면 결합 법칙을 만족하고 순차 기준과 동일한 결과를 내야 한다.
- 작업이 외부 락을 오래 잡거나 블로킹 호출을 수행하지 않게 한다.
임계값을 CPU 코어 수만으로 계산할 수 있나요?
코어 수만으로는 부족합니다.
원소 하나의 계산 비용, 분할과 객체 생성 비용, 캐시 지역성, 입력 불균형이 모두 영향을 줍니다.
먼저 충분히 큰 리프를 선택하고 여러 대표 입력에서 결과가 같은지 확인한 뒤 벤치마크로 조정합니다.
원본 크기가 작으면 순차 경로를 택하는 전환점도 유용합니다.
연습 문제
반열린 인덱스 범위를 사용해 배열의 최댓값을 찾으세요.
빈 범위를 만들지 않고 임계값 이하에서는 직접 순회하며, 부모 작업은 Math.max로 결과를 결합해야 합니다.
해설 보기
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;
public final class ForkJoinMaximumSolution {
private static final class MaxTask extends RecursiveTask<Integer> {
private final int[] values;
private final int from;
private final int to;
private MaxTask(int[] values, int from, int to) {
this.values = values;
this.from = from;
this.to = to;
}
@Override
protected Integer compute() {
if (to - from <= 3) {
int maximum = values[from];
for (int index = from + 1; index < to; index++) {
maximum = Math.max(maximum, values[index]);
}
return maximum;
}
int middle = from + (to - from) / 2;
MaxTask left = new MaxTask(values, from, middle);
MaxTask right = new MaxTask(values, middle, to);
left.fork();
return Math.max(right.compute(), left.join());
}
}
public static void main(String[] args) {
int[] values = {4, 17, -3, 29, 8, 11, 2};
try (ForkJoinPool pool = new ForkJoinPool(3)) {
int maximum = pool.invoke(new MaxTask(values, 0, values.length));
System.out.println("max=" + maximum);
}
}
}종료 기준은 max=29와 함께 모든 인덱스가 정확히 한 리프에 속하는 것입니다.
빈 배열에 대한 정책은 이 작업 밖에서 예외나 OptionalInt로 명시합니다.
독립 확인: 최댓값 연습의 일곱 값을 [-4,-17,-3,-29,-8,-11,-2]로 바꿉니다. 임계값 3에서 리프 범위·각 최댓값·전체 결과를 구하세요. 리프의 시작값을 무조건 0으로 바꾸면 맞나요? 빈 입력의 values[from]도 안전한가요?
풀이 확인
[0,3)는 -3, [3,5)는 -8, [5,7)는 -2이고 전체 결과는 -2입니다. 초깃값 0은 입력에 없는데 모든 음수보다 커서 오답 0을 남깁니다. 현재 코드의 values[from]은 빈 입력에 유효한 인덱스가 없어 배열 범위 오류입니다. 예제 연습의 빈 범위를 만들지 않는 전제를 유지하고 빈 입력 정책을 호출 경계에서 별도로 결정해야 합니다.