Clojure 디렉터스(Reducers): 시퀀스 없이 병렬로 누적하기

Clojure에서 컬렉션을 다룰 때 우리는 보통 시퀀스 함수를 써요. map, filter 같은 함수가 컬렉션을 하나씩 순서대로, 게으르게 처리하면서 그 사이에 중간 결과를 만들죠. 그런데 잠깐, 이런 함수들은 개념적으로 보면 병렬로 처리해도 되는 경우가 많아요. 매핑과 필터링은 원소끼리 서로 독립적이니까요. 코어가 많아질수록 코드가 자동으로 빨라진다면 얼마나 좋을까요? 바로 그 생각에서 출발한 게 Reducers예요.

출처: Clojure 공식문서

본문

Reducer가 뭐예요?

_리듀서(reducer)_는 **리듀서블 컬렉션(reducible collection)**과 **리듀싱 함수(reducing function)**가 합쳐진 거예요.

리듀서블 컬렉션: 스스로를 reduce할 줄 아는 컬렉션
리듀싱 함수: 리덕션 동안 "무엇을 할지"를 담은 레시피

시퀀스 함수들이 바로 연산을 수행하는 대신, Reducers에서는 새 버전의 함수들이 연산을 직접 하지 않고 리듀싱 함수를 변형만 해요. 실제 실행은 마지막 리덕션 순간까지 미뤄지죠. 그래서 시퀀스에서 볼 수 있는 중간 결과물과 게으른 평가가 사라져요.

여기에 더해, 일부 컬렉션(영속 벡터와 맵)은 **폴더블(foldable)**이에요. 리듀서에 대한 폴드(fold) 연산은 리덕션을 병렬로 수행하는데, 이렇게 진행돼요.

리듀서블 컬렉션을 지정된 단위로 분할 (기본값 512개 원소)
각 분할에 reduce 적용
Java의 fork/join 프레임워크로 각 분할의 결과를 재귀적으로 결합

컬렉션이 폴딩을 지원하지 않으면 병렬이 아닌 일반 reduce로 자동으로 넘어가요.

reduce와 fold

clojure.core.reducers 네임스페이스(여기서는 r로 축약)는 대체 버전의 r/reduce 함수를 제공해요.

(r/reduce f coll)
(r/reduce f init coll)

레듀서 버전의 reduce는 두 가지가 달라요.

맵 컬렉션은 reduce-kv로 리듀스돼요
init을 주지 않으면, 항등값(identity value)을 만들기 위해 f를 인자 없이 호출해요
- 참고: f는 항등값을 만들기 위해 여러 번 호출될 수 있어요.

대부분의 사용자는 r/reduce를 직접 부르지 않아요. 대신 병렬 reduce와 결합을 구현한 r/fold를 쓰는 걸 권장해요. 다만 중간 결과를 적게 만들어내는 즉시(eager) 리덕션이 필요할 때는 r/reduce가 유용할 수 있어요.

(r/fold reducef coll)
(r/fold combinef reducef coll)
(r/fold n combinef reducef coll)

r/fold는 리듀서블 컬렉션을 받아서 대략 n개(기본 512)씩 그룹으로 나눠요. 각 그룹은 reducef로 리듀스되고, 이때 reducef는 각 분할 안에서 항등값을 만들기 위해 인자 없이 호출돼요. 그 결과들이 이제 combinef(기본값은 reducef)로 리듀스되죠. combinef도 인자 없이 호출되면 항등 원소를 만들어야 하는데, 이것도 여러 번 호출돼요. 연산은 병렬로 수행될 수 있고, 결과는 순서를 지켜요.

다음 함수들은 시퀀스 버전과 비슷하게, 리듀서블 또는 폴더블 컬렉션에서 리듀서를 만들어요. r/map, r/mapcat, r/filter, r/remove, r/flatten, r/take-while, r/take, r/drop이에요.

이 함수들 중 어떤 것도 원본 컬렉션을 실제로 변형하지 않아요. 누적된 결과를 얻으려면 r/reduce나 r/fold를 써야 하고, 출력 컬렉션을 만들려면 clojure.core/into로 컬렉션 타입을 고르거나, r/foldcat로 리듀서블·폴더블·시퀀서블·카운트되는 컬렉션을 만들어요.

Reducers 사용하기

+로 합을 구할 때는 fold를 써요.

(require '[clojure.core.reducers :as r])
(r/fold + (r/filter even? (r/map inc [1 1 1 2])))
;=> 6

최종 컬렉션을 만들려면 into를 써요.

(into [] (r/filter even? (r/map inc (range 100000))))

아니면 r/foldcat을 써도 돼요.

(r/foldcat (r/filter even? (r/map inc (range 100000))))

fold에 reduce 함수와 combine 함수를 각각 지정할 수도 있어요.

(defn count-words
  ([] {})
  ([freqs word]
    (assoc freqs word (inc (get freqs word 0)))))

(defn merge-counts
  ([] {})
  ([& m] (apply merge-with + m)))

(defn word-frequency [text]
  (r/fold merge-counts count-words (clojure.string/split text #"\s+")))

언제 써야 하나요?

이 연산들의 리듀서 버전은 이런 경우에 써요.

다단계 변환을 효율적으로 즉시 적용할 때
게으른 시퀀스에서 보이는 dangling I/O 리소스 문제를 피하고 싶을 때

fold는 이런 경우에 써요.

소스 데이터를 메모리에 생성하고 담아둘 수 있을 때
수행할 작업이 순수 연산(I/O나 블로킹이 아닐 때)
데이터 항목 수나 작업량이 "크" 때

Clojure 디렉터스(Reducers): 시퀀스 없이 병렬로 누적하기