설명 된 데이터 구조 유형을 중심으로 내 코드베이스 (ECS 엔진)의 가장 중심 부분 중 일부를 회전하지만 작은 연속 블록 (4 메가 바이트 대신 4 킬로바이트와 같은)을 사용합니다.

더블 프리리스트를 사용하여 삽입 준비가 된 프리 블록 (가득이없는 블록)에 대한 하나의 프리리스트와 해당 블록의 인덱스에 대한 블록 내의 서브 프리리스트로 일정한 시간 삽입 및 제거를 수행합니다. 삽입시 회수 할 수 있습니다.

이 구조의 장단점을 다룰 것입니다. 몇 가지 단점이 있기 때문에 몇 가지 단점부터 시작하겠습니다.

단점

1. 이 구조 std::vector에 순전히 인접한 구조 보다 2 억 개의 요소를 삽입하는 데 약 4 배 더 오래 걸립니다 . 그리고 나는 마이크로 최적화에 꽤 익숙하지만 일반적으로 블록 프리 목록의 맨 위에있는 프리 블록을 검사 한 다음 블록에 액세스하여 블록의 무료 인덱스를 팝해야하기 때문에 개념적으로 더 많은 작업이 있습니다. 빈 목록, 빈 위치에 요소를 쓴 다음 블록이 가득 찼는 지 확인하고 블록 빈 목록에서 블록을 팝하십시오. 여전히 일정 시간 작업이지만로 돌아가는 것보다 훨씬 큰 상수를 사용 std::vector합니다.
2. 인덱싱을위한 추가 산술 및 추가 간접 레이어가 제공되는 임의 액세스 패턴을 사용하여 요소에 액세스하는 경우 약 두 배가 걸립니다.
3. 반복자는 증가 할 때마다 추가 분기를 수행해야하므로 순차 액세스는 반복자 설계에 효율적으로 맵핑되지 않습니다.
4. 일반적으로 요소 당 약 1 비트의 약간의 메모리 오버 헤드가 있습니다. 요소 당 1 비트는별로 소리가 나지 않지만 백만 개의 16 비트 정수를 저장하기 위해 이것을 사용하는 경우 이는 완벽하게 컴팩트 한 배열보다 6.25 % 더 많은 메모리 사용입니다. 그러나 실제로 이것은 예약 된 초과 용량을 제거하기 위해 std::vector압축하지 않는 한 메모리보다 적은 메모리를 사용하는 경향이 있습니다 vector. 또한 나는 일반적으로 그런 조그마한 요소를 저장하는 데 사용하지 않습니다.

찬성

1. for_each블록 내에서 요소의 콜백 처리 범위를 취하는 함수를 사용한 순차 액세스 std::vector는 10 % 차이와 같은 순차 액세스 속도와 거의 비슷 하므로 성능이 가장 중요한 사용 사례에서 효율성이 훨씬 낮습니다. ECS 엔진에 소비되는 대부분의 시간은 순차적 액세스에 있습니다.
2. 블록이 완전히 비워지면 블록을 할당 해제하는 구조로 중간에서 일정한 시간을 제거 할 수 있습니다. 결과적으로 데이터 구조가 필요한 것보다 훨씬 더 많은 메모리를 사용하지 않는 것이 일반적으로 꽤 괜찮습니다.
3. 컨테이너에서 직접 제거되지 않은 요소에 대한 인덱스는 무효화되지 않습니다. 이후 삽입시 자유 목록 접근 방식을 사용하여 구멍을 남기기 때문에 구멍을 남기기 때문입니다.
4. 이 구조가 많은 수의 요소를 보유하고 있어도 메모리 부족에 대해 걱정할 필요가 없습니다. 소형 연속 블록 만 요청하므로 OS가 수많은 연속 사용되지 않는 것을 찾는 데 어려움을 겪지 않기 때문입니다. 페이지.
5. 작업은 일반적으로 개별 블록에 국한되므로 전체 구조를 잠그지 않고 동시성 및 스레드 안전성에 적합합니다.

이제 나에게 가장 큰 장점 중 하나는 다음과 같이이 데이터 구조의 변경 불가능한 버전을 만드는 것이 쉽지 않다는 것입니다.

그 이후로 부작용이없는 더 많은 함수를 작성하기 위해 모든 종류의 문을 열었으므로 예외 안전성, 스레드 안전성 등을 훨씬 쉽게 달성 할 수 있습니다. 불변성은 내가 쉽게 달성 할 수있는 것으로 나타났습니다. 이 데이터 구조는 후시와 우연히 발생하지만 코드베이스를 훨씬 쉽게 유지 관리 할 수있게되면서 얻을 수있는 가장 큰 이점 중 하나 일 것입니다.

연속되지 않은 어레이에는 캐시 위치가 없으므로 성능이 저하됩니다. 그러나 4M 블록 크기에서는 우수한 캐싱을위한 충분한 로컬 성이있는 것 같습니다.

참조의 지역 성은 4 킬로바이트 블록은 물론 그 크기의 블록에서도 관심을 가질만한 것이 아닙니다. 캐시 라인은 일반적으로 64 바이트입니다. 캐시 누락을 줄이려면 해당 블록을 올바르게 맞추는 데 집중하고 가능한 경우보다 순차적 인 액세스 패턴을 선호하십시오.

랜덤 액세스 메모리 패턴을 순차적으로 변환하는 매우 빠른 방법은 비트 세트를 사용하는 것입니다. 당신이 인덱스의 보트로드를 가지고 있고 그것들이 무작위 순서라고 가정 해 봅시다. 그것들을 쟁기질하고 비트 세트에 비트를 표시 할 수 있습니다. 그런 다음 비트 세트를 반복하고 0이 아닌 바이트를 확인하여 한 번에 64 비트를 확인하십시오. 하나 이상의 비트가 설정된 64 비트 세트가 발견되면 FFS 명령어를 사용하여 설정된 비트를 신속하게 결정할 수 있습니다 . 비트는 인덱스를 순차적으로 정렬하는 것을 제외하고는 어떤 인덱스에 액세스해야하는지 알려줍니다.

이것은 약간의 오버 헤드가 있지만 경우에 따라 가치있는 교환이 될 수 있습니다. 특히이 지수를 여러 번 반복하려는 경우 특히 그렇습니다.

항목에 액세스하는 것은 그리 간단하지 않습니다. 간접적 인 수준이 있습니다. 이것이 최적화됩니까? 캐시 문제가 발생합니까?

아니요, 최적화 할 수 없습니다. 랜덤 액세스는 적어도이 구조에서 더 많은 비용이 듭니다. 특히 일반적인 실행 경로가 순차적 액세스 패턴을 사용하는 경우 블록에 대한 포인터 배열로 높은 시간적 지역성을 얻는 경향이 있기 때문에 캐시 누락을 크게 늘리지 않는 경우가 많습니다.

4M 한계에 도달 한 후 선형 증가가 있기 때문에 일반적으로 할당량보다 더 많은 할당량을 가질 수 있습니다 (예 : 1GB 메모리에 최대 250 개의 할당량). 4M 이후에 추가 메모리가 복사되지 않지만 추가 할당이 많은 양의 메모리를 복사하는 것보다 비용이 많이 드는지 확실하지 않습니다.

실제로는 복사 log(N)/log(2)횟수 가 드물기 때문에 종종 더 빠릅니다. 총 횟수 와 같은 일이 발생 하는 동시에 더러워 지기 쉬운 일반적인 경우를 단순화하는 동시에 배열이 가득 차기 전에 여러 번 요소를 쓸 수 있고 다시 할당 해야하는 경우가 많습니다. 따라서 일반적으로 이러한 유형의 구조를 사용하면 더 빠른 삽입을 얻지 못합니다. 거대 배열을 재 할당하는 값 비싼 희귀 사례를 처리 할 필요가없는 경우에도 일반적인 사례 작업이 더 비싸기 때문입니다.

모든 단점에도 불구 하고이 구조의 주요 매력은 메모리 사용이 줄어들고 OOM에 대해 걱정할 필요가 없으며 무효화되지 않은 동시성 및 불변성이 아닌 인덱스 및 포인터를 저장할 수 있다는 것입니다. 일정한 시간에 물건을 삽입하고 제거하면서 정리하고 포인터와 색인을 구조에 무효화하지 않는 데이터 구조를 갖는 것이 좋습니다.

---

답변