캐시 정렬 된 링크 목록

Question

데이터 유형 또는 구조체 정렬, 패딩, 패딩 문제 등의 개념에 대해 알고 있습니다. 각 노드가 대략 250 바이트를 차지하는 단일 링크 된 목록을 구현했습니다. 즉 캐시 라인 크기의 약 4 배입니다. 64 바이트. 내 컴퓨터는 Intel 64 비트 아키텍처입니다.

이제 단 하나의 링크 된 목록은 기본적으로 데이터 구조를 추적하는 포인터이므로 많은 캐시 누락이 발생합니다. 캐시 미스를 줄이기 위해 * posix_memalign * 함수를 사용하여 각 데이터 구조 노드를 정렬하여 64 바이트의 경계를 캐시했습니다. 이제 모든 연결된 목록 노드가 캐시에 맞춰집니다.

이렇게하면 링크 된 목록의 메모리 사용량이 현저히 증가하고 실제로 성능이 저하되는 것을 알 수 있습니다. 아무도 잘못 될 가능성을 설명 할 수 있습니까?

Answer 1

나는 당신이 무엇을 사용 malloc을 모르지만이 tcmalloc

// For use by exported routines below that want specific alignments 
// 
// Note: this code can be slow for alignments > 16, and can 
// significantly fragment memory. The expectation is that 
// memalign/posix_memalign/valloc/pvalloc will not be invoked very 
// often. This requirement simplifies our implementation and allows 
// us to tune for expected allocation patterns. 

에서입니다