[자료구조] 시퀀스 컨테이너와 연관 컨테이너 성능 비교요소

시퀀스 컨테이너 VS 연관 컨테이너

 

고려해야할 요소는 다음과 같다

 

1. 이론적 속도 

말 그대로 이론적인 요소이다. 예를 들면, 선형 탐색은 O(n)이 걸리고 비선형 연결 리스트는 O(logn)의 이론적인 개념의 시간 복잡도. 하지만 실제로 성능은 여러가지의 요소의 종합적인 결과이기 때문에 이론적인 속도만 따지면 안된다.

 

2. 캐시 

캐시는 CPU와 메인메모리(RAM) 사이에 있는 고속 임시 저장 공간이다. CPU가 데이터를 접근할 때, 이 캐시를 통해 접근을 최소화 하고 속도를 높힌다.

 

캐시 계층구조

 

L1 캐시 

접근 속도 : 매우빠름(1~3사이클)

크기 :  32KB ~ 128KB(보통 64KB 이하)

분리 여부 : 대부분 명령용, 데이터용으로 분리됨

CPU와 가장 가까운 캐시로 매우 빠르지만 용량이 작음 ( 32KB ~ 128KB )

 

L2 캐시

접근 속도 : 빠름(4~14사이클)

크기 : 128KB ~ 1MB (보통 256KB~512KB)

공유 여부 : 일반적으로 코어마다 독립

특징 : L1 미스 발생 시 L2에서 탐색

 

L3 캐시 

접근 속도 : 느림(20~40사이클)

크기 : 4MB~64MB

공유 여부 : 모든 코어가 공유

 

여러 코어에서 공유하는 캐시 코어간 데이터 교환시 중요한 역할

DRAM보다 훨씬 빠르지만 L1/L2보단 느림

[CPU Register]
     ↓
[L1 Cache] ← 가장 작고 빠름, 자주 쓰는 데이터
     ↓
[L2 Cache] ← 조금 더 크고 느림, L1이 놓친 데이터를 찾음
     ↓
[L3 Cache] ← 모든 코어 공유
     ↓
[Main Memory (RAM)]

 

캐시라인

캐시는 캐시라인이라고 하는 일정 크기의 블록으로 데이터를 저장한다. 예를 들어 한 캐시라인의 크기는 보통 64바이트이다. CPU가 메모리에서 데이터를 요청할 때, 그 데이터뿐만 아니라 해당 데이터 주변의 값들도 함께 가져온다. 이 이유 때문에 인접한 데이터인 시퀀스 컨테이너가 캐시 히트율이 높아 성능이 더 좋다

 

캐시 친화적인 데이터 접근 방식

데이터가 연속으로 저장되거나, 인접한 데이터가 자주 함께 사용되는 경우이다. 이를 통해 효율성을 높일 수 있다.

예를들어 list나 map같은 비연속적인 메모리 구조에서는 데이터를 인덱싱할 때마다 캐시가 미스될 가능성이 높다. 하지만 vector나 array의 경우 연속적인 메모리를 사용하므로, 캐시 친화적이다

 

 

캐시 작동 과정에 이해에 대한 예제

int arr[1000];  // 약 4KB (1000 × 4바이트)

 

이 데이터가 할당되면 스택 or 힙 or 데이터영역에 위치하고 메인메모리 (RAM)에 존재한다.

 

캐시에 올라가는 조건은 CPU가 해당 배열의 원소에 접근하는 순간 그 데이터가 캐시로 불러와 진다.

arr[0] = 1;  // ← 이 시점에 arr[0]이 포함된 캐시 라인(64바이트)이 L1으로 로딩됨

arr[0]에 접근시 그 메모리 주소가 L1캐시에 존재하는지 검사

없으면? L1 캐시미스 

L2 -> L3 -> RAM순으로 탐색한다.

데이터를 찾으면 캐시라인(64바이트)만큼 로드해 L1에 저장 

 

캐시 쓰기 정책

Write-back 캐시

접근하는 데이터는 L1에 쌓이고, 자리가 부족하면 가장 오래된 데이터는 LRU 기준으로 제거 된다. 단, 그 데이터가 수정되었으면 L2로 복사되고 수정되지 않았다면 L1에서 제거된다.

 

여기서 L1 캐시에 들어갈 데이터를 선정하는 알고리즘이 캐시 교체 알고리즘이다. 

 

캐시 교체 알고리즘

FIFO(First In First Out) 가장 먼저 들어온 데이터를 제거

LRU(Least Recently Used) 가장 오래 전에 사용된 데이터를 제거

LFU(Least Frequently Used) 사용횟수가 가장 적은 데이터를 제거

MRU(Most Recently Used) 가장 최근데 사용된 데이터를 제거

Random 임의의 데이터를 제거

Clock 순환 큐 기반, 사용여부 비트로 판단. 성능과 구현의 균형, OS에서 자주 사용

Optimal 앞으로 가장 멀리 사용될 데이터를 제거하지만 이론적일 뿐이고 실제 구현은 불가(미래 예측)

 

 

 

3. 분기 예측

현대 CPU 성능 최적화에서 매우 중요한 개념. 이 개념을 이해하면, 왜 단순한 코드가 더 빠르고 선형탐색이 이진 탐색보다 빠를 수 있는지도 알 수 있다.

 

현대 CPU는 파이프라인과 명령어 병렬실행 구조를 사용해 빠르게 동작한다. 하지만 if, for, while, switch 같은 분기(Branch)명령이 나오면 문제가 된다.

 

예시

if (x > 0)
    doA();
else
    doB();

이 경우 CPU는 x>0의 결과가 나올 때 까지 기다리지 않고 미리 doA(), doB()를 실행한다. 이걸 분기 예측 이라고한다.

 

CPU가 잘 못 예측했을 때 파이프라인에 적재된 명령을 전부 무효화하고 다시 실행해야한다. 이걸 분기 예측 실패라고하고 성능에 지대한 영향을 끼친다. 파이프라인이 길수록 피해가 더 크고, 예측 실패 시 수십 클럭이 낭비될 수 있음

 

예제 : 패턴이 일정한 분기 vs 불규칙한 분기

for (int i = 0; i < 1000000; ++i)
{
    if (i % 2 == 0)
        sum += arr[i];
}

이 경우 만약 arr 배열이 arr[1] = 1, arr[2] = 2... 이런식으로 정렬되어 있다면, 컴파일러는 분기문의 결과를 FTFTFT...로 예측할 수 있어 분기 예측 성공률이 높다. 하지만 arr[1] = 45437, arr[2] = 45... 처럼 랜덤하게 배치되어있다면, 컴파일러가 분기문의 결과를 예측하기 어렵다. 따라서 분기 예측 성공률이 낮아 성능이 낮아진다.

 

 

분기 예측 실패의 대표적인 예

for (int i = 0; i < 1000000; ++i)
{
    if (arr[i] == target) // 불규칙한 값
        return i;
}

이 경우 target에 의한 조건 예측이 어려워 분기 예측 실패율이 높고 성능이 저하된다.

 

 

 

실 조건 set VS vector

std::set + 노드 탐색

많은 비교연산, 분기가 많아서 예측실패 시 성능이 급감한다.

 

std::vector + linear search

메모리가 연속이고 분기가 거의 없거나 간단한 패턴이기 때문에 캐시 및 분기 예측 친화적이다. 실제로 작은 데이터 에서는 vector + linear search가 map보다 빠르다

 

 

4. 명령어 구조

" 2010년 이후로 거의 모든 프로세서가 RISC 구조를 따라가므로 대량의 데이터 검색이라도 선형탐색이 가장 빠르다."

 

RISC 구조

RISC는 단순하고 예측 가능한 명령어이다.

- 적고 단순한 명령어

- 모든 명령어가 거의 동일한 시간에 실행 ( 일반적으로 1 클럭)

- 파이프라인 최적화에 유리

- 루프, 반복문, 순차적 코드에 매우 강함

- CPU파이프라인/분기 예측/프리패치가 효율적으로 동작- 선형탐색에서 매우 최적화된 실행이 가능

 

반면, 이진 탐색(tree 기반 탐색)은 분기가 많고 예측하기 어렵다. 특히 캐시 미스발생 시 페널티가 크고, 분기 예측 실패 시 파이프라인을 갈아야한다.

 

하지만 선형탐색처럼 명령 흐름이 단순하고 일정한 루프는 RISC에서 CPU가 전력을 발휘하는 영역이다.

 

 

현대 CPU 최적화 방향

현대 CPU(RISC기반) 에서는 예측 가능성이 성능의 핵심이다. 따라서 분기 예측 실패시 리스크가 큰 트리탐색은 리스크가 크다.

 

현대의 CSIC ( 인텔, AMD)도 내부적으로는 RISC방식으로 동작한다.

CSIC는 복잡한 명령어를 집합으로 갖는 구조인데 (한 명령으로 여러 연산수행) 내부는 단순하고 빠른 RISC 스타일이 훨씬 최적화에 유리하다.

 

따라서 성능 최적화를 하려면 RISC철학에 맞는 코드 패턴(예측 가능한 흐름, 순차접근)을 따라야한다.

 

 

5. 데이터 패턴

 

예제 : 순차 vs 임의 접근 비교

#include <iostream>
#include <chrono>
#include <vector>
#include <random>
#include <numeric>

using namespace std;

const int N = 10000000;
int* arr = new int[N];

int main()
{
    // 순차 접근
    auto start = chrono::high_resolution_clock::now();
    long long sum = 0;
    for (int i = 0; i < N; ++i)
        sum += arr[i];
    auto end = chrono::high_resolution_clock::now();
    cout << "Linear time: " << chrono::duration<double>(end - start).count() << "s\n";

    // 임의 접근
    vector<int> indices(N);
    iota(indices.begin(), indices.end(), 0);
    random_shuffle(indices.begin(), indices.end());

    start = chrono::high_resolution_clock::now();
    sum = 0;
    for (int i = 0; i < N; ++i)
        sum += arr[indices[i]];
    end = chrono::high_resolution_clock::now();
    cout << "Random time: " << chrono::duration<double>(end - start).count() << "s\n";

    return 0;
}

 

 

랜덤한 접근일 경우 순차 접근 보다 성능이 떨어지는걸 볼 수 있다.  비약적이긴 하지만 시퀀스 컨테이너 vs 연관 컨테이너의 차이이다. 

 

 

 

번외) vector, list, set 탐색 실행 성능 비교

#include <iostream>
#include <chrono>
#include <vector>
#include <random>
#include <numeric>
#include <thread>
#include <list>
#include <set>

using namespace std;

const int N = 10000;
int* arr = new int[N];

list<int> lst;
set<int> Set;

void findelementvec(const int* arr, long long& result, int start, int end)
{
    result = 0;
    for (int i = start; i < end; ++i)
    {
        if (arr[i] == 4325) break;
    }
}


void findelementlist(list<int>* lst, long long& result)
{
    auto it = lst->begin();

    while (it != lst->end())
    {
        if (*it == 4325) break;
        ++it;
    }
}


int main()
{
    for (int i = 0; i < N; ++i)
        lst.push_back(i);

    for (int i = 0; i < N; ++i)
        arr[i] = i;

    for (int i = 0; i < N; ++i)
        Set.insert(i);
    
    // 벡터시간 계산
    long long r1 = 0, r2 = 0;
    long long total = r1 + r2;
    auto start = chrono::high_resolution_clock::now();
     r1 = 0;
     findelementvec(arr, r1, 0, N);

    auto end = chrono::high_resolution_clock::now();
    cout << "vector normal time: " << chrono::duration<double>(end - start).count() << "s\n";
    
    // 리스트 시간계산
    auto startlist = chrono::high_resolution_clock::now();
    r1 = 0;
    findelementlist(&lst, r1);

    auto endlist = chrono::high_resolution_clock::now();
    cout << "list normal time: " << chrono::duration<double>(endlist - startlist).count() << "s\n";

    // 셋 시간계산
    auto startSet = chrono::high_resolution_clock::now();
    r1 = 0;
    Set.find(4325);

    auto endSet = chrono::high_resolution_clock::now();
    cout << "set normal time: " << chrono::duration<double>(endSet - startSet).count() << "s\n";

	return 0;
}

 

 

처음실행 했을 때

vector > set > list (실행시간 빠르기)

vector가 가장 빠르다. 여러이유가 있지만 아래에서 더 보기로 하고 좀 더 흥미로운 결과가 있다.

 

 

두번째 실행했을 때

set > vector >list (실행시간 빠르기)

 

두번째 부터 set이 빨라지는 이유

 

초기 실행시는 vector는 연속된 메모리 공간에 저장되므로 L1/L2캐시에 한번에 원소가 프리패칭되지만, set은 노드기반 구조이기 때문에 많은 캐시 미스를 유발하기 때문이다. 이 때문에 처음 실행했을 때는 vector가 더 빠르다.

 

두번째 실행 시, set의 탐색 경로가 이미 캐시에 로드되었으므로 자주 접근되는 노드들이 L1/L2 캐시에 올라가 트리 탐색 비용이 감소한다. vector는 여전히 빠르지만 set의 캐시 히트율이 증가하면서 상대적으로 우위가 생긴다.

 

하지만

이것은 단일 기능 프로그램이여서 set이 빠른것이고 다중 프로그램과 같이 여러 메모리를 캐시에 올려야하는 게임이나 렌더링 엔진, 서버의 경우 계속해서 캐시에 메모리가 올라갔다가 내려오므로 set의 캐시 히트율이 떨어지면서 결과적으로는 set이 더 성능이 떨어진다. 원소를 찾기 위해서 해야하는 연산이 적어도 말이다.

 

데이터가 1만 이하이면 vector가 더 낫고, 이 이상 많아지면 set이 유리한데 vector는 다중 기능 시스템에서 캐시 친화성 때문에 더 유리하다.

 

따라서 복잡한 다기능 프로그램에서는 vector가 set보다 일관되고 예측가능한 성능을 낸다. 또한 여기서는 쓰레드를 이용한 병렬 탐색도 사용하지 않았기 때문에 vector는 개선될 여지가 아주 많다. 즉 힘을 숨긴 상태인데 학교 1짱인 경우이다.