오늘도 집합 연산 이야기.
파이썬 교집합 연산이 STL보다 3배 빠르다.
https://stackoverflow.com/questions/54763112/how-to-improve-stdset-intersection-performance-in-c?fbclid=IwAR0Q9rP6Zs2wD2f8ixWjGPTKlXAzpYq_56spaBKon-fkqJUgBX5nE9n6mTE
파이썬 교집합 연산이 rust 보다 빠르다.
https://stackoverflow.com/questions/35439376/why-is-python-set-intersection-faster-than-rust-hashset-intersection
이것은 파이썬이 빠르다는 이야기는 아니다. 그 언어의 네이티브 구현체의 구현 방식의 차이에서 기인한다.
일단 우리가 처리하고자 하는 집합 연산은 대규모 데이터다 작게는 수메가 크게는 기가를 넘어설 수 있다.
집합을 구성하는 자료구조를 해시맵으로 저장한다고 치자. 해시맵은 논리적으로 O(1)이나 버킷 카디널리티 문제로 분할된 rb-tree로 구현하고 있을 가능성이 크다. 즉, 물리적으로 O(1)과는 거리가 있다. 트리가 등장하면 포인터 추적 연산을 수반한다. 데이터는 물리적으로 산개되어 있으며 캐시의 도움을 받을 가능성이 현저히 떨어진다.
포인터 추적을 물리적인 이터레이터 멤버 함수로 구현하고 있을 수도 있다. 즉, 함수 콜을 수반하며 스택 연산 비용은 물론 CPU는 파이프 스톨을 일으킨다. 이것은 큰 비용이다.
단순 중첩 루프에 의한 데이터 추적을 할 때도 마찬가지다. 연속된 메모리에 위치하지 않은 데이터를 순회하고, 포인터에 의한 간접 참조와 동적 탈출 조건을 수반한다. 이는 역시 CPU와 컴파일러 최적화의 분기 예측을 무력화 시킨다. 역시 파이프 스톨을 유발한다.
한 편으로 데이터가 산개되어 있고 포인터 추적을 한다는 것은 컴파일러가 조기에 SIMD 연산을 포기한다는 뜻이다.
연산 자체도 집합 연산은 최적화가 가능하다. 탐색 후 연산의 루프는 앞의 모든 문제를 일으킨다. 따라서 정렬된 배열에서 연산을 하는 것이 최적이다. 정렬된 배열에서의 집합 연산은 집합 A,B 에서 O(max(len(a), len(b), len(a+b))에서 커버가 된다.
파이썬의 집합 연산이 빠르다는 점은 이런 점들을 고려해서 작성됐을 가능성이 크다. 코드를 열어본 적은 없지만 헿헿헿.
빠른 집합 연산을 구현한다면 먼저 데이터를 최대한 빡빡하게 연속된 메모리에 분포시킨다. 해시셋 방식으로 접근하되, 버킷 충돌시 버킷을 늘릴지 버킷의 하부에 붙일지 결정을 잘해야 한다. 버킷의 하부를 트리보다는 정렬된 배열로 구성한다.
정렬된 배열로 구성할 때에는 삽입 삭제에 매우 불리하다. 탐색의 비용은 비슷하지만 전수 검사에 있어서는 압도적으로 유리하다. SIMD, 캐시, 분기 예측의 도움을 모두 받을 수 있다.
아예 두 벌의 데이터를 만들 수도 있다. 트리와 배열을 모두 만드는 것이다. 트리를 선순위로, 비동기로 배열을 후순위로 만드는 방법이 있고, 연산 발생시에만 온디맨드로 정렬된 배열을 다시 만들어 처리하는 방법이 있을 수 있다. 비동기 방식이라면 OLTP에서 동기화 비용이 문제가 되지만 OLAP이라면 괜찮다. 온디맨드로 연산 발생시 정렬된 배열을 만드는 방식을 쓴다면 쓰레시 홀드 값을 정해두고 대형 데이터 연산시에만 작동하도록 모색할 수 있다. 어찌됐든 malloc의 탄생 이후로 자주 등장하는 데이터 사용 패턴에 대해서는 사전에 준비한 여분의 자료구조를 먼저 리턴하는 것이 장땡이고 준비가 부족할 때 요구불 처리를 동작하도록 하는 쪽이 유리하다.
트리 데이터를 정렬된 배열로 한 벌 더 만드는 일은 생각보다 비용이 적다. rb-tree 등이 이미 리밸런싱을 할 때 바닥좌측부터 정렬이 되어 있기 때문.
연속된 배열을 구성한다는 점에 있어서는 mmap을 동원할 수 있다. 시스템 메모리 이상의 기가 데이터도 문제없이 처리할 수 있다. 메모리에 다 올려둘 필요도 없고 올리고 내리고 GC 만들고 할 일이 없다. huge 페이지나 mmap read-ahead의 지원을 받을 수도 있다. 어쨌든 커널의 지능적인 페이지 관리의 도움을 받으니 대충 개비스콘 짤이다.
아예 데이터 사용 패턴을 예측하여 페이지 폴트를 사전에 유발 시키는 방법도 있다. read-ahead보다 더 멀리 선빵을 치는 방법이다.
https://www.dbpia.co.kr/journal/articleDetail?nodeId=NODE07502902
간만에 잘난 척을 해봤습니다만... 틀린 점이 있을 수 있습니다. 반박시 내가 틀림이니 지적 댓글 바랍니다. 1도 안 맞다. 어디서 부터 지적해야 할지 모르겠다. 어디서 도시괴담을 퍼왔느냐 싶으시면 댓글 달아주시면 조용히 삭제합니다.