# 메모리 관리와 캐싱 기법

물리 엔진을 최적화할 때 가장 중요한 요소 중 하나는 메모리 관리와 캐싱 기법이다. 메모리 관리는 전체 엔진의 성능과 효율성에 직접적인 영향을 미치며, 적절한 메모리 할당과 해제를 통해 최적의 성능을 유지할 수 있다. 캐싱 기법은 반복적으로 사용되는 데이터를 미리 저장해 두어 성능을 향상시키는 기술이다.

**메모리 관리**

물리 엔진에서 메모리 관리는 다음과 같은 단계로 나뉜다:

1. **메모리 할당 및 해제**:

   * 물리 엔진에서는 객체들이 동적으로 생성되기 때문에 메모리 할당과 해제가 빈번하게 발생한다. 이로 인해 메모리 단편화(Fragmentation)가 발생할 수 있으며, 성능 저하로 이어질 수 있다.
   * 이를 해결하기 위해 메모리 풀(Memory Pool)을 사용한다. 메모리 풀은 미리 정해진 크기의 메모리 블록들을 할당해 두고 재사용하는 기법이다.

   ```cpp
   class MemoryPool {
   public:
       MemoryPool(size_t blockSize, size_t numBlocks);
       ~MemoryPool();

       void* allocate();    // 메모리 블록 할당
       void deallocate(void* p);  // 메모리 블록 해제

   private:
       struct Block {
           Block* next;
       };

       Block* freeBlocks;
       size_t blockSize;
       size_t numBlocks;
       std::vector<char> pool;
   };
   ```
2. **메모리 단편화 방지**:
   * 메모리 단편화는 작고 자주 할당되는 객체로 인해 메모리가 비효율적으로 사용되는 현상이다.
   * 이를 방지하기 위해 각 객체의 크기에 맞는 메모리 풀을 여러 개 운영하여 단편화를 최소화할 수 있다.
   * 또 다른 방법으로는 고정 크기 할당(Fixed-size allocation)을 사용하는 것이다. 이를 통해 메모리 단편화를 줄이고, 할당과 해제를 더 빠르게 수행할 수 있다.
3. **스택 할당 (Stack Allocation)**:

   * 스택 기반 메모리 할당은 임시 데이터를 위한 빠르고 간단한 메모리 관리 방법이다.
   * 함수가 호출될 때마다 스택에 메모리를 할당하고, 함수가 종료되면 자동으로 해제된다.

   ```cpp
   void someFunction() {
       int tempArray[100]; // 스택에 할당된 메모리
       // ...
   } // 함수가 종료되면 메모리 자동 해제
   ```

**캐싱 기법**

캐싱은 다음과 같은 방식을 통해 성능을 향상시킨다:

1. **데이터 지역성(Locality of Reference)**:
   * 메모리에 접근할 때 데이터의 지역성을 고려해 캐시 효율을 높일 수 있다. 여기에는 시간 지역성(Temporal Locality)과 공간 지역성(Spatial Locality)이 있다.
   * 시간 지역성은 자주 사용되는 데이터가 캐시에 남아 있을 가능성이 높다는 것을 의미한다.
   * 공간 지역성은 인접한 메모리 위치가 함께 사용될 가능성이 높다는 것을 의미한다.
2. **스패셜 해싱 (Spatial Hashing)**:

   * 물리 엔진에서 객체의 공간적 위치를 바탕으로 캐싱하는 방법이다.
   * 객체가 차지하는 공간을 해시 테이블에 매핑하여 빠른 검색이 가능한다.

   ```cpp
   struct SpatialHashTable {
       std::unordered_map<int, std::vector<Object*>> table;

       int hashFunction(const Vector& position) const {
           const int p1 = 73856093;
           const int p2 = 19349663;
           const int p3 = 83492791;
           return (int(position.x) * p1) ^ (int(position.y) * p2) ^ (int(position.z) * p3);
       }

       void insert(const Object* obj) {
           int hashValue = hashFunction(obj->position);
           table[hashValue].push_back(obj);
       }

       std::vector<Object*> findNearby(const Vector& position) {
           int hashValue = hashFunction(position);
           return table[hashValue];
       }
   };
   ```
3. **개별 객체 캐싱**:

   * 자주 참조되는 객체의 상태나 결과 값을 캐시하여 매번 계산하지 않고 빠르게 접근할 수 있게 한다.
   * 예를 들어, 기구체(Kinematics) 계산이나 충돌 감지 결과를 캐시할 수 있다.

   ```cpp
   struct CachedObject {
       Vector position;
       Vector velocity;
       bool isCollisionDetected;
       mutable std::optional<CollisionResult> collisionCache;

       CollisionResult detectCollision() const {
           if (!collisionCache.has_value()) {
               collisionCache = performCollisionDetection();
           }
           return collisionCache.value();
       }

   private:
       CollisionResult performCollisionDetection() const {
           // 충돌 감지 알고리즘
       }
   };
   ```

#### 멀티스레딩 최적화

멀티스레딩(Multi-threading)은 다수의 작업을 동시에 수행함으로써 컴퓨팅 리소스를 최대한 활용하는 기법이다. 물리 엔진의 병렬화는 컴퓨팅 성능을 극대화할 뿐만 아니라 프레임 레이트(Frames per Second, FPS)를 높이는 데도 중요한 역할을 한다.

**멀티스레딩 기법**

1. **작업 분할 (Task Decomposition)**:

   * 작업을 여러 개의 독립적인 부분으로 나누어 각 스레드가 병렬로 처리할 수 있도록 한다.
   * 예를 들어, 충돌 감지, 물리 계산, 렌더링 등을 독립적인 작업으로 나누어 별도 스레드에서 수행할 수 있다.

   ```cpp
   void physicsUpdate() {
       std::vector<std::thread> workers;
       for (int i = 0; i < NUM_THREADS; ++i) {
           workers.emplace_back([=]() {
               processCollision();
               updateRigidBodies();
           });
       }

       for (auto& worker : workers) {
           worker.join();
       }
   }
   ```
2. **데이터 병렬화(Data Parallelism)**:

   * 동일한 작업을 여러 데이터에 대해 병렬로 수행하는 방식이다.
   * 예를 들어, 다수의 객체에 대한 물리 계산을 병렬화하여 속도를 높일 수 있다.

   ```cpp
   void updatePositions(std::vector<RigidBody>& bodies) {
       #pragma omp parallel for
       for (size_t i = 0; i < bodies.size(); ++i) {
           bodies[i].updatePosition();
       }
   }
   ```
3. **동기화 및 상호 배제(Synchronization and Mutexes)**:

   * 다수의 스레드가 공유 자원에 접근할 때, 데이터 일관성을 유지하기 위해 동기화 기법을 사용한다.
   * Mutex나 세마포어(Semaphore)를 사용하여 특정 코드 블록에 대한 상호 배제를 보장할 수 있다.

   ```cpp
   std::mutex mtx;

   void updatePhysics() {
       std::lock_guard<std::mutex> lock(mtx);
       // 공유 자원 접근 코드 블록
   }
   ```
4. **작업 큐(Task Queue)**:

   * 작업을 큐에 넣고 스레드 풀(Thread Pool)이 이를 소비하는 방식이다.
   * 작업 분배와 동기화 문제를 효율적으로 해결할 수 있다.

   ```cpp
   class ThreadPool {
   public:
       ThreadPool(size_t threads);
       ~ThreadPool();

       template<class F>
       void enqueue(F&& f);

   private:
       std::vector<std::thread> workers;
       std::queue<std::function<void()>> tasks;
       std::mutex queueMutex;
       std::condition_variable condition;
       bool stop;

       void workerThread();
   };

   // ThreadPool 생성
   ThreadPool pool(4);

   // 작업 추가
   pool.enqueue([] {
       processPhysics();
   });
   ```
5. **파이프라인 처리(Pipeline Processing)**:

   * 특정 작업을 여러 단계로 나누고 각 단계를 별도 스레드에서 처리하는 방식이다.
   * 하나의 작업이 다음 단계로 넘어가면서 지속적으로 병렬 처리가 이루어진다.

   ```cpp
   void physicsPipeline() {
       std::thread stage1(&performBroadphase);
       std::thread stage2(&performNarrowphase);
       std::thread stage3(&resolveConstraints);

       stage1.join();
       stage2.join();
       stage3.join();
   }
   ```

#### 성능 프로파일링 및 분석

최적화를 제대로 수행하려면 현재 성능 상태를 정확하게 이해해야 한다. 이를 위해 성능 프로파일링 및 분석 도구를 활용하는 것이 중요하다.

**프로파일링 기법**

1. **펑션 타이밍(Function Timing)**:

   * 각 함수의 실행 시간을 측정하여 병목 지점(Bottleneck)을 파악한다.
   * 고해상도 타이머(High-resolution Timer)나 프로파일러를 사용하여 측정한다.

   ```cpp
   #include <chrono>

   void measureExecutionTime() {
       auto start = std::chrono::high_resolution_clock::now();

       // 함수 실행
       someFunction();

       auto end = std::chrono::high_resolution_clock::now();
       std::chrono::duration<double> elapsed = end - start;
       std::cout << "Execution time: " << elapsed.count() << " seconds." << std::endl;
   }
   ```
2. **샘플링 프로파일링(Sampling Profiling)**:
   * 실행 중인 프로그램의 상태를 주기적으로 샘플링하여 함수 호출 빈도를 수집한다.
   * 샘플링 프로파일러는 오버헤드가 적어 실시간 성능 분석에 유리한다.
3. **계측 프로파일링(Instrumentation Profiling)**:

   * 코드 내에 프로파일링 코드를 삽입하여 각 함수 호출 전후로 타이밍 데이터를 수집한다.
   * 정확한 데이터 수집이 가능하지만 오버헤드가 높을 수 있다.

   ```cpp
   #define PROFILE_SCOPE(name) InstrumentationTimer timer##__LINE__(name);

   class InstrumentationTimer {
   public:
       InstrumentationTimer(const char* name) : name(name), startTime(std::chrono::high_resolution_clock::now()) {}
       ~InstrumentationTimer() {
           auto endTime = std::chrono::high_resolution_clock::now();
           std::chrono::duration<double> duration = endTime - startTime;
           std::cout << name << " took " << duration.count() << " s" << std::endl;
       }

   private:
       const char* name;
       std::chrono::time_point<std::chrono::high_resolution_clock> startTime;
   };

   void someFunction() {
       PROFILE_SCOPE("Some Function");
       // 함수 실행 코드
   }
   ```
4. **성능 시각화**:
   * 성능 데이터를 시각화하여 문제 지점을 쉽게 파악할 수 있다.
   * 그래프, 막대 차트, 히트맵 등을 활용한다.
   * 게임 엔진에서는 HUD를 통해 실시간 성능 데이터를 시각화할 수 있다.

#### 맺음말

물리 엔진의 최적화는 성능을 극대화하고 사용자 경험을 향상시키는 핵심 과정이다. 메모리 관리와 캐싱 기법, 멀티스레딩 최적화, 성능 프로파일링 등을 통해 효과적인 최적화를 이룰 수 있다. 다양한 최적화 기법을 적절히 결합하여 최상의 성능을 달성하는 것이 목표이다.