자료구조의 최적화 주요 포인트
회사에 들어가기전엔 DB는 그렇게 중점적으로 공부하지 않았고, 로직적 성능을 신경썼었다.
막상 회사오니 서버 부하에 반은 DB부하고 반은 로직 부하였다.
내가 겪은 다양한 부하 케이스와 성능 최적화에 대해서 쭉 정리를 해볼까 한다.
웹 서버들 쪽 성능논하는 얘기를 보면 항상 구조 얘기만 있고, 서버 자체의 로직적인 퍼포먼스 얘기에 대해서는 크게 안보여서 아쉽다싶다.
- 캐시 메모리
- 램
- 하드디스크( 및 SSD)
- 네트워크 전송
분산 DB에 대해서는 지식이나 경험이 크게 없기에,
앞에 얘기 나왔던 DB부하에 대해서 먼저 얘기를 해보면
- 특정 작업을 위해서 DB 쿼리 호출이 여러번 필요한경우 sp사용을 꾀할 수 있다.
- sp 로직은 결국은 DB단에서 직접적으로 움직이는 로직이고
- 코드에서 db호출이 여러번 되는것은 결국
- -> DB접근을 반복적으로 한다는 것이고
- -> 왔다갔다하는 불필요 작업이 발생
- -> 이를 sp호출을 통해 절약할 수 있다.
- 긴 쿼리를 주고 받는 상황에서는 네트워크 비용의 감소 또한 꾀할 수 있다
네트워크 -> 하드디스크 |
단점으론 sp가 관리 포인트가 갈린다는건 결론적으로 유지보수의 어려움이 증가한다.
- 인덱싱은 너무 기본이니 생략..
서버가 단순하고 DB 상하차만을 할수록 대부분 케이스에서 주요 병목 지점은 DB부하가 된다.
DB 부하가 너무 커서 감당이 불가능할때 캐시레이어를 박게 된다.
짜잔 stateful 서버 완성
- disk 접근 부하를 메모리 접근 비용으로 줄이고
- 캐시서버 사망시 롤백이라는 짊을 지는것으로 trade off 관계를 형성 한다.
보조저장장치 -> 램
로직 최적화를 꾀할때는 다양한 방법이 있고, 아이디어 영역이라고 생각하지만 크게 나누면 두 가지라고 생각한다.
- 병목 로직 호출 자체가 없도록 한다. (10번 호출하는 방식을 1번만 호출하거나)
- 돌아가는 코드 자체를 그냥 빠르게 한다. (10번을 빠르게 돌게하거나)
예를들면
기존 스펙에서 한개를 선택해서, 진행하는 로직을 스펙을 N번으로 바꾸는 등의 일이 있다.
이때 작업을 단히 패킷만 N개 던지게 하는 식 or 처리로직을 그냥 for * N만 하게하는식으로 하면서 부하가 발생하는 경우가 생길 수 있다.
이런 식의 작업을 하면서 부하가 생기면 그냥 로직 작성을 애초에 n개를 고려해서 처리하도록 새로 작성하면 된다.
그리고 호출할 필요가 없으면 호출하지 않게 (early return등) 한다던가 하는 방식으로 해당 문제를 근본적으로 고칠 수도있지만,
해당 로직 및 관련 스펙을 빠삭하게 파악하고 있어야 진행할 수 있어 작업이 꽤나 어렵다. (가능한지 부터 견적을 봐야하거나, 로직을 빠삭하게 알지못하면 건들지도 못하거나)
전체 코드 로직을 모르는 상태에서는 2번 방식을 우선적으로 고려하게 되는데
이 중 자료구조에 대해서 좀 깊게 풀어보고자 한다.
자료구조 (시간복잡도의 함정)
- 배열
- 해시테이블 (std::unorderd_~)
- 트리구조 (std::map, set)
자료구조를 논할때 꼭 같이 논해야하는 것이 있다.
캐시메모리 효율과, 메모리 할당 해제 비용이다.
메모리 -> 캐시메모리
메모리 할당 해제비용은 O(1)이라고 퉁치고 넘어가기엔 너무 큰 비용으로
자료구조에서 보통 따지는 시간복잡도는 결국 n의 크기인데 n이 클 수록 이에 대한 영향이 크게 되지만, 많은 경우에 이를 논하기 이전에 대개 단일 연산자체가 병목 지점을 만들 수 있다.
충분히 큰 배열의 메모리 생성 해제 비용이 가장 싸며 캐시 메모리 접근 효율 또한 가장 좋다.
링크드리스트의 맨끝에 삽입하는 insert와 배열의 맨끝에 삽입하는 insert는 둘 다 같은 시간복잡도 O(1)이나 하늘과 땅차이의 성능차이가 존재한다.
초기 메모리를 미리 예측하여 확보할 수도있다.
일반적으로 키밸류 방식 자료구조를 사용할때는 그냥 해시테이블을 사용하는것을 권장된다. (이중 전체 사이즈가 캐시안에 다 박힐정도의 크기면 최적화를 정말 쥐어짜야할땐, 단순 배열로 최적화를 시도해봄직하다)
순회시 정렬 보장이 필요할때 map, set 을 고려할 수 있는데,
트리 구조의 메모리 생성 해제 비용은 가히 최악이다.
시간복잡도를 따지기 이전에 그냥 기본 성능자체가 느리다.
tree구조 map set은 아래 이유가 아니면 마지막의 마지막 선택지로 남겨놔도 괜찮다고 생각한다.
- 정렬을 보장
- 사용 구조가 N이 정말 크고 중간 삽입 삭제가 정말 빈번히 발생
- 위의 케이스에서 전역적으로 접근하는 변수인 경우
저기서 좀 더 빠른 최적화를 꽤 한다면, 배열사용을 고려해볼법하다.
만능 사용은 힘들지만, 배열의 효율은 배열에 들어갈 N과 원소로 들어갈 객체의 size가 작을 수록 효율이 커진다.
가변 배열인 벡터 구조의 경우 처음 생성시에 사이즈를 미리 크게 할당할 수도 있어 추가적인 메모리 비용을 줄여 보일 수도있다.
그러곤 무식하게 보일 수 있지만, 그냥 전체 순회를 한다던가.
정렬이 필요하다면 차라리 필요시점에서 객체를 직접 정렬해서 사용하던가 하는 방식으로도 가능하다. 캐시 미스로 인한 RAM 접근 비용을 꼼꼼히 따져야한다.
경험적으론 리스트 자료구조를 사용해야겠다 판단이 든 케이스는 없었고, 벡터(배열) 메모리 할당을 위한 복사 성능 성능개선을 위해 리스트로 바꾼 케이스는 역으로 성능저하를 불러왔다.
자료구조 선택은 모두 복합적으로 고려해서 선택되어야한다.
- 들어갈 자료의 크기 n
- 삽입 :
- 앞에 들어가는지
- 중간에 들어가는지
- 맨끝에만 들어가는지
- 각각의 빈도
- 삭제
- 맨 앞이 삭제되는지
- 중간이 삭제되는지
- 맨끝에만 삭제되는지
- 각각의 빈도
- 전체 원소의 순회의 비용과 빈도
- 단일 접근 비용과 빈도
- 각각의 케이스에 대한 메모리 할당, 해제 여부
컴퓨터 구조
그래픽스로 가면 컴퓨터 구조까지 따지면서 성능을 따지면서 최적화를 하는 경우도 많이 보는데, 특히 하나의 함수를 몇천번씩 호출하다보니, 그 함수의 최적화 되지않은 코드로직이 크게 영향이 가게된다. 이런 경우에 컴파일 최적화의 결과물까지 신경써서 해야한다.
- 캐시 메모리 접근을 조금 더 신경쓰기
- false sharing 정도 고려, 구조체 크기 64byte 메모리에 맞추기
- 16byte 밑의 객체는 함수 파라미터 전달시 포인터가아닌 단순 복사 전달
- if 로인한 성능 저하 고려
- SIMD 최적화
파일 입출력
단순 파일 파싱하는 일회성 코드작업을 하는데, 복잡한 파일 구조 엑셀 등을 작업하거나, 복잡한 형식으로 파일을 읽어온다거나 할때 파일이 클수록 성능저하가 크게 오는 경우가 생긴다.
많은 경우에 코드 로직적으로 raw 구조로 읽고 필요 변수들을 직접 파싱하는 식으로 변경한다면 시간을 획기적으로 줄일 수 있다.
방식에 따라 50배 100배 넘게 시간 차이가 발생할 수 있는 부분이라
해당 파싱 동작시간이 업무에 영향이 가거나, 이 문제로인해 해당 작업이 가능 불가능을 논해야할정도면 신경써볼법하다.