자유 스레딩 Python에서 Advent of Code 예제를 바탕으로 병렬화 성능, 참조 카운팅, 락 경합, 워커 수 조정의 중요성을 살펴봅니다.
Free-threaded Python (PEP-703)는 2024년 10월에 출시되었습니다. 이것은 GIL의 제약 없이 진정한 멀티스레드 실행을 가능하게 합니다.
저는 이전에 Free Threaded Python With Asyncio에서 이것을 다뤘는데, 거기서 사용한 예제는 성능 향상, 혹은 더 나아가 스레드가 “자유롭게 실행되는” 모습을 매우 명확하게 보여주도록 선택된 것이었습니다.
하지만 그것은 실제 문제를 해결하는 코드라고 보기는 어렵습니다. 단지 같은 계산을 반복할 뿐입니다. 저는 이번 12월에 advent of code를 아주 재미있게 하고 있었는데, 이것이 자유 스레딩을 시험해 보기 위한 아주 좋은 테스트베드가 되었습니다.
2024년 day 6에 대한 스포일러가 있습니다! 전체 소스 코드는 여기
Day 6는 병렬화를 사용해 해결할 수 있는 문제의 좋은 예였습니다.
Part 1은 맵에서 경비원의 경로를 추적하는 것이었습니다. 이어서 Part 2에서는 장애물 하나를 놓아서 경비원이 루프를 형성하게 만들 수 있는 위치를 묻습니다.
제 전체 해법은 다음과 같습니다:
from __future__ import annotations
from contextlib import contextmanager
from dataclasses import dataclass
from itertools import pairwise
from pathlib import Path
from typing import Hashable, Iterable, Iterator, Self, assert_never
type Pair = tuple[int, int]
up = 0
right = 1
down = 2
left = 3
def turn(direction: int) -> int:
return (direction + 1) % 4
@dataclass(slots=True)
class Ranges:
"""Traversable location in the map."""
rows: range
cols: range
def __getitem__(self, key: tuple[slice, int] | tuple[int, slice]) -> Iterator[Pair]:
match key:
case int() as r, slice() as cols:
return ((r, c) for c in self.cols[cols])
case slice() as rows, int() as c:
return ((r, c) for r in self.rows[rows])
case _ as other:
assert_never(other)
def walk(self, start: Pair, direction: int) -> Iterator[Pair]:
match direction:
case 0:
return ((row, start[1]) for row in self.rows[start[0] :: -1])
case 2:
return ((row, start[1]) for row in self.rows[start[0] :: 1])
case 3:
return ((start[0], col) for col in self.cols[start[1] :: -1])
case 1:
return ((start[0], col) for col in self.cols[start[1] :: 1])
case _:
assert False
@dataclass(slots=True)
class Grid:
start: Pair
tiles: list[list[bool]]
ranges: Ranges
@classmethod
def from_lines(cls, lines: Iterable[str]) -> Self:
start = None
coord = (0, 0)
rows = []
for r, line in enumerate(lines):
row: list[bool] = []
for c, char in enumerate(line):
coord = (r, c)
if char == "^":
start = coord
row.append(char == "#")
rows.append(row)
assert start is not None
return cls(start, rows, Ranges(range(len(rows)), range(len(rows[0]))))
def __getitem__(self, key: Pair) -> bool:
return self.tiles[key[0]][key[1]]
@contextmanager
def read_lines(path: Path) -> Iterator[Iterator[str]]:
with path.open() as f:
yield (line.rstrip() for line in f)
def walk(grid: Grid, obstruction: Pair | None = None) -> Iterator[Pair]:
direction = up
start = grid.start
yield start
while True:
walk = pairwise(grid.ranges.walk(start, direction))
for prev, curr in walk:
if grid[curr] or curr == obstruction:
direction = turn(direction)
start = prev
break
yield curr
else:
return
def loops[T: Hashable](it: Iterator[T]) -> bool:
visited = set()
for e in it:
if e in visited:
return True
visited.add(e)
return False
if __name__ == "__main__":
with read_lines(Path("inputs") / "d6.txt") as lines:
grid = Grid.from_lines(lines)
path = set(walk(grid))
print("part1", len(path))
candidates = (node for node in path if node != grid.start)
print(
"part2",
sum(1 for node in candidates if loops(pairwise(walk(grid, node)))),
)
여기서 강조하고 싶은 몇 가지 세부 사항이 있습니다: - Grid는 __getitem__을 구현하고 있어서 맵의 위치에 더 직접적으로 접근할 수 있습니다. 예를 들어 grid[1, 2]는 위치 (1, 2)에 접근합니다. - Ranges는 맵에 있는 전체 위치 범위를 나타내며, 한 방향으로 경로를 쉽게 추적할 수 있게 해줍니다. - walk는 이 모든 것을 한데 모으고 장애물을 만났을 때의 로직을 처리합니다.
여기서 우리가 더 관심 있는 것은 Part 2입니다. 경로 상의 모든 위치(제 경우 약 5000개)에 대해 순회하면서, 거기에 장애물을 추가하면 루프가 형성되는지 확인합니다.
Part 2만 시간을 재어 보니 제 11코어 M3 Mac에서 약 4초가 걸렸습니다. 하지만 각 walk는 서로 독립적이고 grid는 수정되지 않고 읽기만 하므로, 병렬화는 간단해야 합니다.
ThreadPoolExecutor를 사용하면 코드의 마지막 부분을 병렬로 실행하도록 다음과 같이 바꿀 수 있습니다:
with ThreadPoolExecutor() as executor:
results = executor.map(
lambda node: loops(pairwise(walk(grid, node))),
candidates,
)
print("part2", sum(1 for r in results if r))
그런데 실행 시간이 거의 두 배로 느려져 약 10초가 되는 것을 보고 저는 충격을 받았습니다.
이런 종류의 동작을 설명할 수 있는 잠재적 이유는 몇 가지가 있습니다.
Python 3.11은 Specialization을 통한 성능 향상과 함께 출시되었습니다.
자유 스레딩 Python은 스레드 코드에서 특수화가 비활성화되어 있습니다. 자세한 내용은 https://peps.python.org/pep-0703/#improved-specialization 를 참고하세요.
하지만 성능 오버헤드는 꽤 작아야 합니다. PEP에 따르면 느려짐은 10% 이내여야 합니다.
GIL의 역할은 객체를 동시 접근으로부터 보호하는 것이었습니다. 이것은 자유 스레딩 Python에서도 여전히 중요하므로, GIL 대신 객체별 락이 있어야 합니다.
이 락들 역시 스레드가 대기하게 만들어 블로킹을 일으킬 수 있습니다.
이것은 스레드보다는 프로세스, sub-interpreters와 더 관련된 문제입니다. Anthony Shaw의 글을 보세요. 따라서 시작 시간으로는 이 느려짐을 설명할 수 없습니다.
제 이론들을 시험하기 위해 가장 먼저 떠오른 생각은 그냥 cProfile을 실행해 보는 것이었습니다.
python -m cProfile d6.py
… 그런데 아무것도 안 됩니다! 프로세스가 멈춘 채로 출력도 나타나지 않습니다. 알고 보니 자유 스레딩 Python 빌드의 cProfile에는 버그가 있었습니다 🤦.
이 때문에 문제는 훨씬 더 어려워졌습니다. 저는 성공 없이 몇 가지 다른 프로파일러 옵션도 시도해 봤습니다. 잠깐 sys.monitoring을 들여다볼까 생각했지만, 프로파일러를 직접 작성하려면 아마 더 많은 조사가 필요할 것 같았습니다.
좋은 프로파일링 없이 할 수 있는 일은 문제를 더 잘 이해하고 여러 가지를 시도해 보는 것뿐입니다.
가장 먼저 확인한 것은 스레드 수에 따른 성능이었습니다. 기본적으로 python은 max_worker 수를 n + 4로 설정하는데, 여기서 n은 시스템 코어 수입니다.
for workers in range(1, 16):
candidates = (node for node in path if node != grid.start)
with timer(f"{workers = }: "):
with ThreadPoolExecutor(max_workers=workers) as executor:
results = executor.map(
lambda node: loops(pairwise(walk(grid, node))),
candidates,
)
print("part2", sum(1 for r in results if r), end="; ")
(advent2024-python) ➜ advent2024-python git:(main) ✗ python d6.py
part1 4883
part2 1655; workers = 1: 4.060725 s elapsed
part2 1655; workers = 2: 4.789434 s elapsed
part2 1655; workers = 3: 5.203642 s elapsed
part2 1655; workers = 4: 5.516271 s elapsed
part2 1655; workers = 5: 6.114952 s elapsed
part2 1655; workers = 6: 7.461776 s elapsed
part2 1655; workers = 7: 7.562252 s elapsed
part2 1655; workers = 8: 8.026832 s elapsed
part2 1655; workers = 9: 8.335291 s elapsed
part2 1655; workers = 10: 8.731357 s elapsed
part2 1655; workers = 11: 9.152564 s elapsed
part2 1655; workers = 12: 9.476967 s elapsed
part2 1655; workers = 13: 9.589462 s elapsed
part2 1655; workers = 14: 9.955716 s elapsed
part2 1655; workers = 15: 9.728167 s elapsed
즉, 여기서는 스레드가 많을수록 성능이 더 나빠집니다. 이것은 어떤 종류의 락 경합이 있다는 강한 신호입니다.
내장 타입은 스레드 안전성을 보장하기 위해 내부 락을 사용합니다.
저는 PEP를 읽어 보았는데 락 방식이 꽤 복잡해 보였습니다. 대부분의 읽기 접근은 “낙관적”입니다. 우리는 list를 읽기만 하므로 이것이 원인일 가능성은 낮습니다. 그래도 의심을 없애기 위해 락이 필요 없는 불변 tuple로 바꿔 봤습니다:
@dataclass(slots=True)
class Grid:
start: Pair
tiles: tuple[tuple[bool, ...], ...]
ranges: Ranges
예상대로 이것은 문제를 해결하지 못했고 성능 저하는 사라지지 않았습니다.
이제 Python 내부 구현을 매우 깊게 파고들게 됩니다. 저는 이 부분이 아주 익숙하지는 않습니다. 그래도 여기에서 다른 사람도 비슷한 성능 문제를 겪었다는 단서를 얻었습니다.
Reference counting은 Python이 가비지 컬렉션을 위해 사용하는 방법입니다. 각 객체가 참조 수 카운터를 저장하고, 그 참조 수가 0이 되었을 때 이를 이용해 가비지 컬렉션을 수행하는 방식입니다.
여기서 더 큰 의미는 객체를 참조하려면 카운터를 증가시켜야 하고, 객체가 여러 스레드에서 참조되면 이것에 락이 필요하다는 점입니다.
자유 스레딩 Python에서는 “biased reference counting””이라 불리는 형태의 참조 카운팅을 사용합니다. 이것은 다른 스레드에서 만들어진 객체보다, 해당 스레드 안에서 생성된 객체의 참조 카운트를 더 빠르게 접근할 수 있게 해줍니다.
전반적으로 이것은 읽기 전용 접근조차 참조 카운팅 때문에 느려질 수 있다는 뜻입니다.
PEP-683을 보세요. 이것 역시 최근의 변화인데, 특정 객체를 불멸로 표시하여 참조 카운팅을 건너뜁니다. 자유 스레딩 Python에도 불멸화가 구현되어 있습니다. 실제로는 True, False, None, 그리고 클래스와 최상위 함수에만 적용됩니다.
제 grid는 이미 boolean을 사용하고 있으므로 이미 불멸 객체를 사용하고 있었습니다. 더 이른 버전에서는 Enum을 사용했는데, 여기서 성능이 확실히 개선되기는 했습니다. 하지만 아주 큰 차이는 아니었습니다. 그래도 다른 상황에서는 성능 문제를 해결할 수도 있습니다.
많은 반복 끝에 마침내 저는 다음 줄을 보게 되었습니다:
if grid[current] or current == obstruction:
여기서는 magic method __getitem__을 사용합니다.
def __getitem__(self, key: Pair) -> bool:
return self.tiles[key[0]][key[1]]
이 메서드는 Grid 객체를 참조하고, 이어서 tiles 속성을 다시 참조합니다.
그리고 이 코드는 walk 함수 안의 이중 루프 내부에 있으므로 아주 자주 호출됩니다!
def walk(grid: Grid, obstruction: Pair | None = None) -> Iterator[Pair]:
...
while True:
...
for prev, curr in walk:
if grid[curr] or curr == obstruction:
...
...
...
제가 직감적으로 여기서 찾았다고 말하고 싶지만, 사실 이것을 찾기 전까지 정말 많은 곳을 살펴봤습니다.
어쨌든 우리는 __getitem__ 호출을 우회할 수 있습니다.
for prev, (r, c) in walk:
if grid.tiles[r][c] or (r, c) == obstruction:
다시 코드를 실행하면:
(advent2024-python) ➜ advent2024-python git:(main) ✗ python d6_threads.py
part1 4883
part2 1655; workers = 1: 3.801581 s elapsed
part2 1655; workers = 2: 3.10458 s elapsed
part2 1655; workers = 3: 2.925348 s elapsed
part2 1655; workers = 4: 2.944652 s elapsed
part2 1655; workers = 5: 3.200314 s elapsed
part2 1655; workers = 6: 4.337672 s elapsed
part2 1655; workers = 7: 4.507129 s elapsed
part2 1655; workers = 8: 4.739261 s elapsed
part2 1655; workers = 9: 4.932432 s elapsed
part2 1655; workers = 10: 5.219045 s elapsed
part2 1655; workers = 11: 5.798776 s elapsed
part2 1655; workers = 12: 6.20557 s elapsed
part2 1655; workers = 13: 6.459673 s elapsed
part2 1655; workers = 14: 6.571967 s elapsed
part2 1655; workers = 15: 6.590083 s elapsed
이것은 실제로 우리가 처음으로 본 긍정적인 성능 향상입니다. 흥미롭게도 높은 스레드 수에서는 여전히 성능이 나빠집니다.
여기서 더 나아가 보면, 우리는 여전히 루프 안에서 grid를 참조하고 있으므로 바깥에서 tiles를 할당할 수 있습니다:
tiles = grid.tiles
while True:
walk = pairwise(ranges.walk(start, direction))
for prev, (r, c) in walk:
if tiles[r][c] or (r, c) == obstruction:
...
다시 한 번:
(advent2024-python) ➜ advent2024-python git:(main) ✗ python d6_threads.py
part1 4883
part2 1655; workers = 1: 3.572743 s elapsed
part2 1655; workers = 2: 2.257732 s elapsed
part2 1655; workers = 3: 1.665534 s elapsed
part2 1655; workers = 4: 1.38678 s elapsed
part2 1655; workers = 5: 1.383013 s elapsed
part2 1655; workers = 6: 2.540588 s elapsed
part2 1655; workers = 7: 3.520335 s elapsed
part2 1655; workers = 8: 4.365446 s elapsed
part2 1655; workers = 9: 5.072404 s elapsed
part2 1655; workers = 10: 5.722957 s elapsed
part2 1655; workers = 11: 6.087521 s elapsed
part2 1655; workers = 12: 6.179896 s elapsed
part2 1655; workers = 13: 6.174642 s elapsed
part2 1655; workers = 14: 6.194982 s elapsed
part2 1655; workers = 15: 6.100845 s elapsed
3, 4, 5개의 worker를 사용할 때 꽤 괜찮은 성능이 나옵니다.
제게는 코어 수와 참조 경합 사이에 어떤 최적 지점이 있는 것처럼 보입니다. 제 기계에서는 4가 꽤 일관되게 좋았습니다. 코어를 더 늘리면 참조 카운트 경합이 시간 측정을 지배하기 시작합니다.
이것이 M3 프로세서의 성능 코어와 효율 코어를 나타내는 신호일 가능성도 있지만, 참조 카운트 경합에서 차이가 얼마나 극적인지 이미 보여주었기 때문에 저는 이 가능성은 더 낮다고 봅니다.
Python에서 자유 스레딩을 볼 때 주의해야 할 핵심 사항은 다음과 같습니다.
성능 측면에서 스레드는 공짜가 아닙니다. 분명히 그 대가를 치러야 합니다. 그리고 동시 접근이 있다는 것은 락으로부터 완전히 자유로울 수 없다는 뜻이기도 합니다.
이 예제에서는 공유 쓰기가 없었습니다. 하지만 이전 테스트를 바탕으로 보면 이런 경우는 극도로 느려질 수 있습니다.
스레드 사이에서 객체를 변경하지 않아도 되도록 구조를 짜는 것이 좋습니다.
피할 수 있는 공유 읽기는 줄여야 한다고 생각합니다. 메모리 접근이 쉬운 점이야말로 멀티스레딩의 가장 큰 장점이기 때문입니다.
“스레드는 공짜가 아니다”라는 생각에서 직접 따라오는 결론은, 상황에 따라 스레드 수를 줄여야 할 수도 있다는 것입니다.
서로 다른 worker thread 수로 코드를 테스트하는 것이 중요합니다.
프로파일링은 매우 중요합니다. cProfile이 고쳐지거나, 아니면 다른 프로파일러가 이런 상황에 도움을 줄 수 있기를 바랍니다.
여기에는 풀어야 할 것이 많지만, 제가 가장 크게 느낀 점은 Python에서 멀티스레딩이 실제로는 꽤나 deceptively difficult하다는 것입니다. 단순한 Python 연산도 성능에 증폭된 영향을 줄 수 있습니다.
프로파일링이 다시 제대로 작동하게 되면 성능 문제를 디버깅하는 일도 더 쉬워질 것이므로, 병렬 문제를 해결하려는 엔지니어들에게 이것이 큰 문제는 아닐 것입니다.
하지만 저는 기존의 멀티스레드 코드가 조금 걱정됩니다. 자유 스레딩 Python 이전에는 GIL이 해제되는 동안 IO bound 작업에 스레드가 사용되었습니다. 언젠가 GIL이 비활성화되고 성능이 몇 배나 더 느려질 수도 있다면, 이것은 큰 도전이 될 것입니다.
저는 점점 sub-interpreters 접근 방식이, 완전히 새로운 동시성 프리미티브와 공유 메모리 데이터 구조를 통해, 많은 장점을 가지고 있다고 생각하게 되었습니다. 현재의 것을 수정하는 대신 새로운 차원의 동시성을 추가한다는 아이디어가 마음에 듭니다. 아마 제 AOC 해법을 sub-interpreters로 구현해 볼지도 모르겠습니다.
마지막으로, 여기서 제가 꽤 많은 노력을 들였음에도 불구하고, GIL을 선택 사항으로 만들기 위해 Python에 엄청난 작업이 들어갔다는 점은 분명히 보입니다. 불멸화부터 편향 참조 카운팅까지, 그리고 제가 다루지 못한 더 많은 것들이 있습니다. 성능 개선의 여지는 분명히 아주 많습니다. 프레임워크 작성자들이 자유 스레딩을 어떻게 활용할지 정말 기대됩니다.