The Biggest Misconception of Computer Science
원본 영상: The Biggest Misconception of Computer Science - Alex Dathskovsky - ACCU 2026
채널: ACCU Conference
개요
이차 시간 알고리즘을 선형 시간 알고리즘으로 바꿨는데 프로그램은 오히려 느려졌다. 강연은 발표자가 첫 직장에서 겪은 이 경험에서 출발한다. 배운 이론대로라면 개선이었지만, 실제 측정 결과는 기대와 달랐다.
발표자가 문제 삼는 것은 시간복잡도 자체가 아니다. 시간복잡도만으로 실제 실행시간까지 판단하는 습관이다. 프로그램의 성능에는 연산의 종류, 데이터 배치, 캐시, 분기 예측, 병렬 처리의 부가 비용이 함께 작용한다.
강연은 복잡도와 자료구조를 되짚은 뒤 CPU의 실행 방식으로 시야를 넓힌다. 마지막에는 두 집합의 차집합 문제를 여러 방식으로 구현하며, 입력 규모와 데이터 표현에 따라 성능의 우열이 어떻게 달라지는지 보여준다.
“벤치마크는 해봤나?”
발표자는 대학을 갓 졸업한 개발자가 기존 코드에서 이차 시간 알고리즘을 발견하는 이야기를 들려준다. 개발자는 이를 비효율적이라고 판단하고, 고민 끝에 선형 시간 알고리즘으로 바꿔 팀장에게 가져간다. 팀장이 던진 질문은 간단하다. “벤치마크는 해봤나?”
측정해보니 새 알고리즘이 기존 구현보다 느렸다. 발표자는 이 개발자가 자신이었다고 밝힌다. 이 경험에서 중요했던 것은 왜 이론적인 개선이 실제 성능 향상으로 이어지지 않았는지 탐구하는 태도였다.
그는 대학에서 알고리즘, 자료구조, 메모리, 운영체제, 스레드를 각각 배웠지만, 이 지식들이 실제 프로그램 안에서 어떻게 연결되는지는 충분히 이해하지 못했다고 돌아본다. 알고리즘을 실행 환경과 분리해서 생각하면 연산 횟수의 증가율만 관리하면 될 것처럼 보인다. 그러나 실제 실행에서는 각 연산이 하는 일과 필요한 데이터의 위치까지 살펴야 한다.
59:05 - CPU, 메모리, 캐시와 분기 특성을 이해하고 구현을 선택해야 한다는 마무리.
이때부터 성능을 묻는 질문도 넓어진다. “몇 번 반복하는가?”에 더해 “반복할 때 무엇을 하는가?”, “데이터는 어디에 있는가?”, “CPU는 무엇을 기다리는가?”를 물어야 한다는 것이다.
복잡도가 설명하는 것과 설명하지 않는 것
연산 횟수와 연산 비용은 다르다
발표자는 배열의 원소를 합산하는 선형 시간 작업과, 반복 횟수는 로그 시간으로 늘어나지만 매번 무거운 함수를 호출하는 작업을 비교한다.
복잡도 표기만 보면 로그 시간 쪽이 유리해 보인다. 하지만 함수 안에서 메모리를 할당하거나 데이터를 읽고 쓰는 비용이 크다면 실제 결과는 달라질 수 있다. 추상적인 연산 한 번이 실제 기계에서도 언제나 같은 비용을 갖는 것은 아니다.
이 비교는 어느 쪽이 항상 빠르다는 결론으로 이어지지 않는다. 내부에서 수행하는 작업을 모른 채 복잡도만으로 실행시간의 우열을 정하기 어렵다는 것이 발표자의 요지다.
자료구조의 성능에는 조건이 붙는다
발표자는 이진 탐색 트리가 한쪽으로 치우치면 연결 리스트와 비슷한 형태가 될 수 있다고 설명한다. 자료구조의 대표적인 복잡도를 기억하는 것만으로는 부족하다. 그 성능이 성립하는 조건과 불리한 경우를 함께 알아야 한다.
다익스트라 알고리즘을 다루는 부분에서는 초기화, 힙에서의 추출, 간선 처리, 우선순위 갱신 등 여러 작업의 비용을 조합한다. 복잡도 분석은 여전히 필요한 도구다. 다만 그 분석이 실제 실행 성능에 영향을 주는 모든 요인을 담고 있지는 않다는 점이 이후 하드웨어 설명으로 이어진다.
강연을 관통하는 문제: 순서를 유지하는 차집합
주어진 두 벡터 A와 B에서, A에 있지만 B에는 없는 원소를 새 벡터에 담는 문제다. 결과는 A의 원래 순서를 유지해야 한다.
가장 단순한 방법은 A의 각 원소에 대해 B를 순회하는 것이다. 같은 값을 찾으면 탐색을 멈추고, 끝까지 찾지 못했을 때만 결과에 추가한다. 구현은 간단하지만 두 벡터를 중첩해서 순회한다.
대안은 B를 std::unordered_set에 넣고, A를 읽으면서 포함 여부를 조회하는 방식이다. A를 순서대로 처리하므로 결과의 순서도 유지된다. 발표자는 이를 복잡도 측면에서 개선하는 해법으로 소개한다.
그러나 해시 조회를 상수 시간으로 설명할 수 있다는 것과, 실제 조회 비용이 작다는 것은 같은 말이 아니다. 해시 집합을 만드는 작업과 메모리 접근에도 비용이 든다. 강연 후반의 비교는 이 차이에 집중한다.
발표자는 같은 작업을 C++의 ranges와 views로 표현하는 방식도 소개한다. 그가 선호하는 표현이지만, 간결한 코드 자체를 별도의 성능 개선으로 제시하지는 않는다. 코드의 표현 방식과 실행 성능은 구분해 살펴야 한다.
분할상환 비용과 개별 호출의 비용
벡터의 push_back은 여유 공간이 있을 때와 없을 때 서로 다른 작업을 수행한다. 공간이 남아 있으면 새 원소를 넣으면 되지만, 용량이 부족하면 더 큰 공간을 마련하고 기존 원소를 옮겨야 한다.
발표자는 이 차이를 분할상환 분석으로 설명한다. 작은 작업을 할 때 비용을 조금씩 저축해두고, 나중에 큰 작업이 발생하면 저축한 비용으로 지불한다는 비유다. 용량을 두 배씩 늘리는 모델에서는 연속된 삽입의 전체 비용을 나누어 삽입당 상수 비용으로 설명할 수 있다.
19:35 - 벡터 용량을 두 배로 늘리는 모델에서 삽입 비용을 계산하는 과정.
그렇다고 재할당 시점의 작업이 사라지는 것은 아니다. 긴 연산열 전체의 비용과 개별 호출에서 실제로 발생하는 비용은 서로 다른 관점이다.
강연은 튜링 기계, P와 NP, 문제 환원으로도 이어진다. 발표자는 스도쿠를 예로 답을 찾는 일과 주어진 답을 확인하는 일이 다를 수 있음을 설명한다. 이후 논의는 다시 실제 컴퓨터로 돌아온다. 문제를 풀 수 있는지, 입력에 따라 작업량이 어떻게 늘어나는지를 이해하는 것에 더해, 그 작업이 어떤 실행 비용을 갖는지도 알아야 한다는 흐름이다.
CPU는 같은 수의 연산도 다르게 처리한다
겹쳐 실행할 수 있는 작업과 기다려야 하는 작업
발표자는 파이프라이닝을 명령어 처리의 여러 단계를 겹쳐 실행하는 방식으로 설명한다. 하지만 메모리 접근이 끝나지 않았거나 다음 명령이 앞선 계산 결과를 필요로 하면 대기가 발생한다. 사용할 수 있는 연산 자원에도 한계가 있다.
비순차 실행은 이런 상황에서 처리 가능한 다른 명령을 먼저 실행해 자원을 활용하는 방식으로 소개된다. 따라서 연산 횟수가 같더라도 작업 사이의 의존성과 자원 사용 방식에 따라 실행시간은 달라질 수 있다.
발표자는 산술 연산의 비용도 비교한다. 부동소수점 값의 일부를 구하는 계산에서 나눗셈과 곱셈을, 정수 계산에서는 나눗셈과 시프트를 비교한다. 그가 제시하는 메시지는 연산 종류에 따라 비용이 다르고, 컴파일러의 최적화도 결과에 영향을 준다는 것이다. 구체적인 성능은 사용하는 CPU에서 측정해야 한다고 강조한다.
분기의 비용은 비교 한 번으로 끝나지 않는다
분기 예측은 조건의 결과를 미리 예상해 다음 작업을 진행하는 방식이다. 발표자는 예측이 맞으면 실행을 이어갈 수 있지만, 틀리면 잘못된 경로에서 진행한 작업을 정리해야 한다고 설명한다.
그는 분기를 줄이는 예로 여러 계산 결과를 먼저 만든 뒤 필요한 값을 선택하는 방식을 소개한다. 추가 계산이 생기더라도 실행 경로를 바꾸는 비용을 줄이면 유리할 수 있다는 설명이다. 이 역시 하드웨어와 실제 생성되는 코드에 따라 판단해야 하는 선택이다.
SIMD와 병렬 처리에도 준비 비용이 있다
SIMD의 계산 속도와 전체 작업의 속도
SIMD는 여러 데이터에 같은 연산을 함께 적용하는 방식으로 소개된다. 발표자는 값을 SIMD 객체에 넣고 계산한 다음, 결과를 출력 배열로 옮기는 흐름을 설명한다.
계산 자체가 빨라도 데이터를 준비하고 결과를 옮기는 비용은 남는다. 발표자는 SIMD를 사용하는 방식에 따라 이 부가 비용이 커질 수 있다고 지적한다. 연산 부분의 속도만으로 전체 작업의 성능을 판단해서는 안 된다는 것이다.
GPU에 관한 설명에서도 작업의 실행 경로가 중요하게 다뤄진다. 발표자는 함께 처리되는 작업들이 서로 다른 분기로 갈라지면 병렬 처리 효율에 영향을 줄 수 있다고 설명한다. 계산을 조금 더 하더라도 경로를 단순하게 만드는 선택이 유리할 수 있다는 점에서, 앞선 분기 설명과 연결된다.
스레드 수와 성능은 비례하지 않는다
발표자는 스레드를 늘리면 성능도 계속 좋아질 것이라는 기대에 의문을 제기한다. 작업을 나누고 관리하는 비용이 있고, 데이터 접근과 캐시 사용 방식도 결과에 영향을 준다.
벡터 원소를 합산하는 비교에서는 단일 스레드 구현이 더 좋은 결과를 보였다고 설명한다. 해당 구현이 컴파일러가 최적화하기 쉬운 형태라는 점을 이유로 들면서도, 입력 규모와 작업 부하에 따라 결과가 달라진다고 덧붙인다.
이 사례의 초점은 병렬 처리가 항상 느리다는 데 있지 않다. 작업을 나누는 비용을 상쇄할 만큼 충분한 계산이 있는지, 데이터가 해당 실행 방식에 적합한지를 함께 살펴야 한다는 것이다.
캐시와 데이터 배치가 만드는 차이
히스토그램: 비슷한 작업, 다른 실행시간
발표자는 히스토그램을 만드는 두 구현을 비교한다. 입력값이 속한 구간을 구한 뒤 해당 카운터를 증가시키는 작업으로, 한쪽은 해시 테이블을, 다른 쪽은 벡터를 사용한다.
그가 제시한 벤치마크에서 해시 테이블 구현은 벡터 구현보다 3.6배 느렸다. 발표자는 이 차이를 데이터의 지역성과 연결해 설명한다.
발표자가 다룬 해시 테이블 구현에서는 필요한 데이터가 메모리의 서로 떨어진 위치에 있을 수 있다. 한 위치의 데이터를 가져와도 다음 작업에 필요한 값이 함께 들어온다는 보장이 약하다.
반면 벡터는 원소가 연속된 공간에 놓인다. 캐시 라인에 인접한 원소들이 함께 들어오면 이후 작업에서 이를 활용할 수 있다. 발표자는 히스토그램의 성능 차이를 이 연속 배치의 효과로 설명한다.
그는 해시 기반 컨테이너 자체를 부정하지 않는다. 조회 복잡도뿐 아니라 메모리 할당, 내부 구조, 접근 패턴에 따른 비용을 알고 사용해야 한다는 입장이다.
차집합을 다시 설계하다
입력 규모에 따라 바뀌는 우열
강연 후반에는 처음의 차집합 문제로 돌아온다. 이제 비교에는 복잡도뿐 아니라 캐시와 데이터 배치도 포함된다.
A에 정수 1만 개, B에 정수 1,000개가 있는 사례에서 발표자는 중첩 반복을 사용하는 단순 구현이 해시 집합 구현보다 빨랐다고 설명한다. 비교에 필요한 데이터를 캐시에서 활용할 수 있었다는 해석이다.
반면 더 큰 입력에서는 단순 구현이 불리해졌다. 작은 입력에서의 캐시 활용 이점이 입력 증가에 따른 비교 횟수까지 상쇄해주지는 못한 것이다.
이 비교는 강연의 출발점에 답한다. 복잡도가 더 좋은 구현이 작은 입력에서도 반드시 빠른 것은 아니며, 작은 입력에서 빠른 구현이 큰 입력에서도 계속 유리한 것은 아니다.
정렬과 이진 탐색
다음 방법은 B를 정렬하고 중복을 제거한 뒤 이진 탐색하는 것이다. A는 원래 순서대로 읽고, B에서 찾지 못한 값만 결과에 넣는다.
이 방식은 검색 데이터와 비교 횟수를 줄일 수 있다. 그러나 발표자의 측정에서는 해시 집합보다 좋은 결과를 얻지 못했다. 그는 탐색 중 여러 메모리 위치를 오가며 데이터를 가져오는 비용을 이유로 설명한다.
여기서 질문이 한 단계 더 나아간다. 탐색 횟수뿐 아니라 검색에 필요한 정보의 크기와 배치도 바꿀 수 있을까?
값 대신 존재 여부를 저장하기
발표자는 값 전체를 보관하는 대신 해당 값이 B에 존재하는지를 바이트로 표시하는 방식을 제시한다. B의 값에 해당하는 위치를 표시해두고, A를 순회하면서 그 표시를 조회한다.
그의 실험에서는 이 방식이 더 빨랐다. 다만 값의 범위가 넓어지면 표시 공간도 커진다. 원소 수가 적더라도 값이 넓게 흩어져 있으면 많은 공간이 필요할 수 있다.
다음 단계는 바이트 대신 비트를 사용하는 비트맵이다. 존재 여부를 더 조밀하게 표현해 필요한 공간을 줄이는 접근이다. 발표자는 이 변경으로 추가 성능 향상을 얻었다고 설명하면서, 강연에서 사용한 고정 크기 비트셋에는 크기를 미리 정해야 한다는 제약이 있다고 덧붙인다.
이 과정에서 바뀌는 것은 반복문의 구조만이 아니다. 같은 판단을 내리기 위해 저장하고 읽어야 하는 정보의 양도 달라진다.
블룸 필터: 확실한 부재와 가능한 존재
발표자는 여러 해시 함수로 비트 위치를 정해 표시하는 블룸 필터도 소개한다. 조회에 필요한 비트 중 하나라도 꺼져 있으면 값이 집합에 없다고 판단할 수 있다. 하지만 비트가 모두 켜져 있다고 해서 실제로 존재한다고 확정할 수는 없다.
차집합 결과를 정확하게 만들기 위해 발표자는 존재 가능성이 있는 값을 실제 B에서도 확인한다. 이때 이진 탐색을 추가하며, 해시 계산과 후속 확인에 비용이 든다고 설명한다.
이 구성에서 블룸 필터는 확실히 없는 값을 먼저 걸러내는 역할을 한다. 나머지 값에는 별도의 확인 작업이 필요하다.
작은 버킷으로 나누고 더 조밀하게 표현하기
마지막 개선은 검색 데이터를 작은 버킷으로 나누는 방식이다. 각 버킷의 값을 정렬하고 중복을 제거한 뒤, 조회할 때 해당 버킷 안에서만 탐색한다. 발표자는 필요한 데이터가 작은 범위에 모이도록 만들어 캐시를 활용하려는 접근으로 설명한다.
이후에는 버킷 내부 표현도 더 조밀하게 바꾼다. 발표자는 바이트를 사용하는 변형에서 약 30%, 이어 비트를 사용하는 변형에서 약 6%의 추가 개선을 얻었다고 말한다.
이 수치는 발표자가 소개한 실험의 결과다. 개선 과정에서 반복되는 방향은 필요한 정보만 보관하고, 한 번의 조회가 접근하는 데이터 범위를 줄이며, 캐시에 들어온 데이터를 활용하도록 구조를 바꾸는 것이다.
마무리: 복잡도와 실행 환경을 함께 보기
발표자의 주장은 복잡도 분석을 버리자는 것이 아니다. 입력 증가에 따른 작업량과 실제 기계가 그 작업을 수행하는 비용을 함께 보자는 것이다.
강연의 사례들은 이 차이를 여러 층위에서 보여준다. 산술 연산마다 실행 비용이 다르고, 분기에는 예측의 영향이 있다. SIMD와 병렬 처리에는 준비와 관리 비용이 따르며, 자료구조의 성능에는 데이터 배치와 캐시 재사용이 작용한다.
차집합 구현을 개선하는 과정에서는 질문 자체가 넓어진다. 비교 횟수를 줄이는 데서 출발해, 판단에 필요한 정보를 얼마나 작게 표현하고 가까이 배치할 수 있는지를 살피게 된다.
발표자는 마지막에 CPU, 메모리, 캐시, 분기 특성을 이해하고 구현을 선택해야 한다고 강조한다. 그 선택이 실제 성능 향상으로 이어졌는지는 벤치마크로 확인해야 한다.