병렬 문자 빈도

지침

병렬 연산을 사용해 텍스트에서 문자의 빈도를 세어요.

병렬성이란 순차적으로도 할 수 있는 일을 병렬로 처리하는 것을 말해요. 흔한 예시가 바로 문자의 빈도를 세는 거예요. 병렬성을 활용해 여러 텍스트로 이루어진 목록에서 각 문자의 전체 빈도를 계산해요.

비동기 작업

태스크는 Lean에서 비동기 코드를 작성할 때 쓰는 기본 추상화예요. 가볍고, 다른 스레드에서 병렬로 실행되거나 같은 스레드에서 동시에 실행될 수 있어요.

태스크는 순수할 수도 있고 불순할 수도 있어요. 순수 태스크는 Task.spawn으로 만들어요. Task.spawn은 순수한 계산을 받아요. 불순 태스크는 IO 계산에서 만들어요. 예를 들어 IO.asTask는 IO α를 IO 모나드 안의 Task α로 끌어올려요.

이 연습 문제에서 calculateFrequencies 함수는 모나딕 함수로, IO (Std.TreeMap Char Nat)를 반환해요. 덕분에 IO.asTask로 불순 태스크를 사용할 수 있고, 최종 값을 반환하기 전에 중간 계산을 위한 순수 태스크를 만들 수도 있어요.

데이터 레이스 방지

함수형 언어인 만큼 Lean의 대부분 값은 영속적, 즉 불변이에요. 값을 수정하는 것처럼 보이는 연산도 실제로는 요청한 변경이 반영된 새 값을 만들어요. 덕분에 데이터 레이스 없이 태스크 사이에서 메모리를 안전하게 공유할 수 있는 경우가 많아요.

하지만 모든 자료 구조가 영속적 사용에 똑같이 적합한 것은 아니에요. 예를 들어 Array의 원소 하나를 갱신하려면 보통 배열 전체를 복사해야 해요. Std.HashSet과 Std.HashMap도 마찬가지예요.

이런 자료 구조를 효율적으로 만들기 위해 Lean은 참조 카운팅을 사용해요. 값의 참조가 유일한 동안에는 불필요한 복사를 피하면서 파괴적으로 갱신할 수 있어요.

List, Std.TreeSet, Std.TreeMap 같은 다른 자료 구조는 내부적으로 구조를 공유하도록 설계됐어요. 갱신할 때 바뀌지 않은 노드를 재사용해서, 여러 값이 그 노드에 대한 참조를 공유할 수 있어요. 그래서 구조의 일부를 수정할 때도 보통 값 전체를 복사할 필요가 없어요. 덕분에 태스크 사이에서 공유하기에 특히 알맞아요.

실행 속도 측정

각 테스트의 실행 시간은 IO.monoNanosNow로 나노초 단위로 측정해서 결과와 함께 보여줘요. 여러 접근 방식을 실험해 보고, 런타임 성능에 어떤 영향을 주는지 확인해 봐요.