저는 보조 버퍼 힙과 같은 캐시를 잊어 버리는 데이터 구조에 대해 최근에 읽었습니다. 이러한 데이터 구조는 가장 최근에 액세스 한 요소를 캐시 메모리에 보관하여 후속 액세스가 더 빠르기 때문에 작동합니다.캐시를 잊어 버리는 데이터 구조와 동적 언어 - 효과적입니까?
이러한 데이터 구조의 대부분은 C/C++와 같은 저수준 언어로 구현됩니다. 이러한 데이터 구조를 Python과 같은 동적 언어로 이식하는 것이 가치가 있습니까? 아니면 가상 시스템에서 실행하는 오버 헤드로 인해 이러한 데이터 구조의 모든 성능 이점이 손상됩니까? 후자와 같이 보이지만 누군가가 실제로 그것에 경험이 있는지를 물어볼 것이라고 생각했습니다.
C (또는 C++)에서는 각 데이터 구조의 정확한 크기를 세부적으로 제어 할 수 있습니다. 또한 스토리지 할당을 세부적으로 제어 할 수 있습니다. 결국 new 메서드를 확장 할 수 있으며 malloc을 직접 사용하고 그렇지 않으면 메모리를 구조화하여 공간 지역성을 만듭니다.
대부분의 동적 언어 (파이썬과 같은)에서는 정확한 크기와 위치를 제어 할 수 없습니다.
파이썬에서는 일시적인 지역성이 있지만 공간적 지역성이 거의 없거나 전혀 없습니다.
결과의 간단한 메모를 통해 시간의 지역성이 향상 될 수 있습니다. 이것은 사람들이 흔히 메모 알고리즘 (시간적 지역성)을 핵심 알고리즘과 분리하는 메모 작성자를 포함하는 일반적인 속도 향상입니다.
충분한 제어 권한이 있다고 생각하지 않기 때문에 C 또는 C++ 캐시를 인식하지 못하는 구현이 동적 언어로 변환되지 않는다고 생각합니다. 대신, 속도 향상을 위해 메모를 활용하십시오. 캐시 잊기 알고리즘의 주요 포인트
하나는 (어쨌든 메모리 페이징의 다음 단계의 크기를 알 수 없기 때문에) 객체의 크기는별로 중요하지 않습니다, 그래서 정확한 크기를 알지 못하는 것은 중요하지 않습니다. 어떤 시점에서, 1 개 이상의 객체 크기가 다음 메모리 블록 크기에 "적합"합니다. (참고 : 객체의 크기를 모르는 것은 캐시 인식 구현에서 중요한 문제입니다.)
또한 대부분의 VM 메모리 할당자는 생성 공간의 끝에 할당하므로 모든 객체를 동시에 할당하면 ok를 시작할 수 있습니다. 불행하게도, 캐시를 모르는 일부 알고리즘은 VM을 사용하여 일반적으로 불가능한 메모리 레이아웃을 변경할 수 있다고 가정합니다.
또 다른 큰 문제는 대부분의 VM 기반 구현에서 객체에 대한 참조를 사용한다는 것입니다. 그래서 세 개의 문자열을 가진 객체는 실제로 4 개의 객체 (객체 자체와 3 개의 문자열 객체)입니다. 이 4 개의 객체가 서로 옆에 할당되지 않으면 알고리즘 분석이 중단됩니다.
압축 가비지 수집기 및 VM이 자유롭게 수행 할 수있는 기타 "최적화"를 추가하면 필요한 알고리즘과 이러한 알고리즘에 대한 현재 연구 상태 사이에 큰 차이가 있습니다.
파이썬에서 numpy 배열을 사용하면 크기와 위치를 직접 제어 할 수 있습니다. – ArekBulski