C++로 구현한 Conway's Game of Life, 무한 시뮬레이션의 세계로!

HashLife 알고리즘은 Conway's Game of Life의 무한 시뮬레이션(Infinite Simulation)을 가능하게 하는 핵심 기술이다. 이 알고리즘은 게임의 우주를 메모이제이션(Memoization)된 쿼드트리(Quadtree)로 표현하며, 각 노드는 미래의 여러 세대에 걸쳐 자신의 상태를 캐싱한다. 특히, 동일한 하위 패턴은 두 번 이상 계산되지 않도록 하여 계산 중복(Computational Redundancy)을 방지한다. 저자는 $2^n \times 2^n$ 크기의 노드가 $2^{n-2}$ 세대만큼 미래를 계산할 수 있다고 설명하며, 이를 통해 대규모 우주에서도 빠른 시뮬레이션(Fast Simulation)을 가능하게 한다.

저자는 C++23의 기능을 활용하여 코드의 안전성, 가독성, 성능을 향상시켰다. 특히, `LifeNodeArena`를 사용하여 bump-pointer allocator를 구현, 메모리 할당의 효율성을 높였다. 이 arena는 `std::unique_ptr`와 결합된 사용자 정의 삭제자를 사용하여 메모리 관리를 단순화한다. 또한, `std::construct_at`을 활용하여 placement new 호출을 피함으로써 코드의 가독성을 높였다. 이러한 기법들은 메모리 누수(Memory Leak)를 방지하고, 캐시 효율성(Cache Efficiency)을 개선하는 데 기여한다.

HashLife 알고리즘은 기본적으로 2의 거듭제곱으로 진행되지만, 사용자가 임의의 스텝 사이즈를 입력할 수 있도록 하기 위해 GOLDE는 Rokicki의 아이디어를 기반으로 한 알고리즘을 사용한다. 이 알고리즘은 먼저 스텝 사이즈를 2의 거듭제곱으로 분해하고, 각 단계에서 최대 진행 가능한 세대 수만큼 진행한다. 이 과정에서 캐시 효율성(Cache Efficiency)을 위해 노드 크기와 세대 수를 모두 해시 테이블의 키로 사용한다. 이러한 접근 방식은 Golly의 고정된 최대 진행 세대 수를 사용하는 방식보다 유연하며, 정확한 세대(Precise Generation)에 도달할 수 있도록 한다.

GOLDE는 멀티스레딩(Multithreading)을 통해 시뮬레이션과 편집 기능을 동시에 수행할 수 있도록 설계되었다. 이를 위해 각 스레드는 고유한 ID를 기반으로 정적 캐시를 선택하여 사용한다. 이러한 방식은 데이터 레이스(Data Race)를 방지하고, 캐시 효율성(Cache Efficiency)을 유지하면서도 편집 기능과 시뮬레이션 간의 안전한 공유(Safe Sharing)를 가능하게 한다. 또한, `std::jthread`와 `std::stop_token`을 사용하여 시뮬레이션을 안전하게 중단하고, 자원 해제(Resource Release)를 보장한다.