알고리즘 성능을 1,600,000% 향상시키는 7단계 최적화 과정

이 영상은 '어드벤트 오브 코드 2022'의 문제(긴 문자열에서 14개의 서로 다른 문자 찾기)를 예시로 삼아, 동일한 시간 복잡도 내에서 구현 방식에 따라 성능이 얼마나 극적으로 달라질 수 있는지를 보여줍니다. 해시 세트를 사용하는 가장 기본적인 접근법에서 시작하여 비트 조작, 컴파일러 최적화, 그리고 멀티스레딩을 활용한 극한의 속도 개선 과정을 체계적으로 설명합니다.

• 문제 정의: 14개의 고유 문자 찾기

  • 매우 긴 문자열 속에서 연속된 14개의 문자가 모두 서로 다른 지점을 찾습니다.
  • 해당 지점을 찾으면 그 바로 다음 문자의 위치를 보고합니다.
  • 가장 직관적인 첫 해결책은 해시 세트를 사용하여 14개씩 문자를 넣고 길이를 확인하는 방식입니다.

• 1단계 최적화: 조기 종료 도입 (92% 성능 향상)

  • 14개를 모두 넣은 뒤 확인하는 대신, 문자를 하나씩 삽입합니다.
  • 삽입 과정에서 중복이 발견되는 즉시 프로세스를 중단하고 다음 윈도우로 넘어갑니다.
  • 단순한 조건문 하나만으로 실행 시간을 대폭 단축합니다.

• 2단계 최적화: 해시 세트 대신 벡터(동적 배열) 사용 (8.9배 향상)

  • 이론적으로 해시 세트와 벡터 조회는 모두 상수 시간 복잡도를 가집니다.
  • 하지만 해시 세트는 해시 계산, 인덱싱, 충돌 관리 등의 과정에서 상수 값이 매우 큽니다.
  • 14개 정도의 작은 데이터를 다룰 때는 메모리 참조가 단순한 벡터가 실제 실행 속도 면에서 압도적으로 유리합니다.

• 3단계 최적화: 스택 할당 배열 사용 (26배 향상)

  • 동적으로 할당되는 벡터 대신 고정 크기의 스택 할당 배열을 사용합니다.
  • 힙 메모리 접근을 피하고 캐시 지역성을 극대화하여 속도를 더욱 높입니다.
  • 인덱스를 직접 관리해야 하는 번거로움이 있지만 성능 이득이 큽니다.

• 4단계 최적화: 비트 조작과 비트마스킹 (233배 향상)

  • 배열조차 사용하지 않고 하나의 32비트 정수에 상태를 저장합니다.
  • 아스키 문자의 숫자 값을 이용해 비트를 이동(Shift)시키고 논리합(OR) 연산으로 문자의 출현 여부를 기록합니다.
  • 논리곱(AND) 연산을 통해 중복 여부를 즉시 확인할 수 있습니다.
  • 배니의 알고리즘: 윈도우를 이동할 때 배타적 논리합(XOR)을 사용하여 첫 문자를 제거하고 새 문자를 추가하는 '토글' 방식을 사용해 극도로 효율적인 윈도우 슬라이딩을 구현합니다.

• 5단계 최적화: 역방향 반복과 점프 최적화 (983배 향상)

  • 데이비드 A. 페레즈의 알고리즘: 윈도우 내부를 역방향으로 조사합니다.
  • 중복 문자를 발견하면 그 위치보다 한 칸 앞까지 데이터를 건너뛰며(Jump) 조사 범위를 획기적으로 줄입니다.
  • 모든 문자를 일일이 훑지 않아도 되므로 연산 횟수 자체가 감소합니다.

• 6단계 최적화: SIMD 및 컴파일러 최적화

  • 고정 크기 윈도우를 사용하면 컴파일러가 루프를 펼쳐서(Unrolling) 성능을 높입니다.
  • SIMD(단일 명령 다중 데이터) 기술을 통해 한 번의 명령으로 여러 데이터를 동시에 계산하도록 유도합니다.
  • 어셈블리 단계에서 병렬 처리가 극대화됩니다.

• 7단계 최적화: 멀티스레딩 병렬 처리 (1,606,240% 향상)

  • 작업을 64개의 스레드로 나누어 병렬로 실행합니다.
  • 최종 성능은 초당 617GB의 데이터를 처리하는 수준에 도달합니다.
  • 기초적인 해결책이 초당 3.84MB를 처리하던 것과 비교하면 상상하기 힘든 격차가 발생합니다.

• 결론 및 시사점

  • 빅오 표기법상 동일한 시간 복잡도 내에서도 구현 방식과 하드웨어 이해도에 따라 수백만 배의 성능 차이가 날 수 있습니다.
  • 추상화 수준이 높은 도구(해시 세트 등)보다 로우레벨 접근(비트 조작, 메모리 레이아웃 활용)이 최적화의 핵심입니다.