Kylotan의 제안을 반향하지만 가능한 한 낮은 할당 자 수준이 아니라 가능한 경우 데이터 구조 수준 에서이 문제를 해결하는 것이 좋습니다.

다음 Foos은 요소가 연결된 구멍이있는 배열을 사용하여 반복적으로 할당 및 해제를 피할 수있는 간단한 예입니다 ( “할당 자”레벨이 아닌 “컨테이너”레벨에서 해결).

struct FooNode
{
    explicit FooNode(const Foo& ielement): element(ielement), next(-1) {}

    // Stores a 'Foo'.
    Foo element;

    // Points to the next foo available; either the
    // next used foo or the next deleted foo. Can
    // use SoA and hoist this out if Foo doesn't 
    // have 32-bit alignment.
    int next;
};

struct Foos
{
    // Stores all the Foo nodes.
    vector<FooNode> nodes;

    // Points to the first used node.
    int first_node;

    // Points to the first free node.
    int free_node;

    Foos(): first_node(-1), free_node(-1)
    {
    }

    const FooNode& operator[](int n) const
    {
         return data[n];
    }

    void insert(const Foo& element)
    {
         int index = free_node;
         if (index != -1)
         {
              // If there's a free node available,
              // pop it from the free list, overwrite it,
              // and push it to the used list.
              free_node = data[index].next;
              data[index].next = first_node;
              data[index].element = element;
              first_node = index;
         }
         else
         {
              // If there's no free node available, add a 
              // new node and push it to the used list.
              FooNode new_node(element);
              new_node.next = first_node;
              first_node = data.size() - 1;
              data.push_back(new_node);
         }
    }

    void erase(int n)
    {
         // If the node being removed is the first used
         // node, pop it from the used list.
         if (first_node == n)
              first_node = data[n].next;

         // Push the node to the free list.
         data[n].next = free_node;
         free_node = n;
    }
};

이 결과에 영향을주는 것 : 사용 가능한 목록이있는 단일 연결 색인 목록. 인덱스 링크를 사용하면 제거 된 요소를 건너 뛰고, 일정한 시간에 요소를 제거하고, 일정한 시간 삽입으로 사용 가능한 요소를 회수 / 재사용 / 덮어 쓸 수 있습니다. 구조를 반복하려면 다음과 같이하십시오.

for (int index = foos.first_node; index != -1; index = foos[index].next)
    // do something with foos[index]

또한 템플릿을 사용하여 위의 “링크 된 홀 배열”데이터 구조를 일반화 할 수 있으며, 사본 할당에 대한 요구 사항을 피하기 위해 배치 및 신규 및 수동 dtor 호출을 배치하고 요소를 제거 할 때 소멸자를 호출하고 순방향 반복자를 제공하는 등의 작업을 수행 할 수 있습니다. 개념을보다 명확하게 설명하기 위해 예제를 C와 같이 유지하기로 선택했으며 매우 게으 르기 때문입니다.

즉,이 구조는 중간에서 많은 것을 제거하고 삽입 한 후에 공간 위치가 저하되는 경향이 있습니다. 이 시점에서 next링크를 통해 벡터를 따라 앞뒤로 이동할 수 있으며, 동일한 순차 순회 내에 캐시 라인에서 이전에 제거 된 데이터를 다시로드 할 수 있습니다 (이는 데이터 구조 또는 할당 자에서 불가피합니다. 상수 비트 삽입 또는 병렬 비트 세트 또는 removed플래그 와 같은 것을 사용하지 않고 중간부터 공백 ). 캐시 친 화성을 복원하기 위해 다음과 같이 copy ctor 및 swap 메소드를 구현할 수 있습니다.

Foos(const Foos& other)
{
    for (int index = other.first_node; index != -1; index = other[index].next)
        insert(foos[index].element);
}

void Foos::swap(Foos& other)
{
     nodes.swap(other.nodes):
     std::swap(first_node, other.first_node);
     std::swap(free_node, other.free_node);
}

// ... then just copy and swap:
Foos(foos).swap(foos);

이제 새 버전은 캐시 친화적이므로 다시 통과합니다. 또 다른 방법은 별도의 인덱스 목록을 구조에 저장하고 주기적으로 정렬하는 것입니다. 또 다른 방법은 사용 된 인덱스를 나타 내기 위해 비트 세트를 사용하는 것입니다. 이를 통해 항상 비트 세트를 순차적으로 순회해야합니다 (이를 효율적으로 수행하려면 한 번에 64 비트를 확인하십시오 (예 : FFS / FFZ 사용)). 비트 세트는 가장 효율적이고 방해가되지 않으며 요소 당 병렬 비트 만 필요하며 32 비트 next인덱스 를 요구하는 대신 사용되는 비트와 제거 된 비트 를 나타내지 만 잘 작성하는 데 가장 많은 시간이 소요됩니다. 한 번에 하나의 비트를 확인하는 경우 순회 속도가 빠릅니다. 점유 된 인덱스의 범위를 신속하게 결정하려면 한 번에 32 개 이상의 비트 중에서 세트 또는 설정되지 않은 비트를 찾으려면 FFS / FFZ가 필요합니다.

이 링크 된 솔루션은 일반적으로 구현하기 가장 쉽고 방해가되지 않습니다 ( 플래그 Foo를 저장하기 위해 수정 할 필요가 없음 removed). 요소 당 오버 헤드.

동적 할당을 위해 메모리 풀을 만들어야합니까, 아니면 이것을 귀찮게 할 필요가 없습니까? 대상 플랫폼이 모바일 장치 인 경우 어떻게합니까?

필요 는 강력한 단어이며 레이트 레이싱, 이미지 처리, 입자 시뮬레이션 및 메쉬 처리와 같은 성능이 매우 중요한 영역에서 일하는 편견이 있지만 총알과 같은 매우 가벼운 처리에 사용되는 조그마한 객체를 할당하고 해제하는 것은 비교적 비용이 많이 듭니다. 및 범용의 가변 크기 메모리 할당기에 대해 개별적으로 파티클을 포함한다. 원하는 데이터를 저장하기 위해 하루나 이틀 안에 위의 데이터 구조를 일반화 할 수 있어야한다고 생각할 때마다 이러한 힙 할당 / 할당 비용을 하나의 작은 물건에 대해 지불하는 것을 제거하는 것이 가치있는 교환이라고 생각합니다. 할당 / 할당 비용을 줄이는 것 외에도 결과를 통과하는 참조의 지역성이 향상됩니다 (캐시 누락 및 페이지 오류 감소).

Josh가 GC에 대해 언급 한 바에 따르면, C #의 GC 구현을 Java와 거의 비슷하게 연구하지는 않았지만 GC 할당자는 종종 초기 할당이 있습니다.그것은 중간에서 메모리를 확보 할 수없는 순차적 할당자를 사용하기 때문에 매우 빠릅니다 (거의 스택과 마찬가지로 중간에서 물건을 삭제할 수는 없습니다). 그런 다음 실제로 메모리를 복사하고 이전에 할당 된 메모리를 전체적으로 제거하여 개별 스레드에서 개별 객체를 제거 할 수있게하는 비용이 많이 듭니다 (데이터를 링크 된 구조와 같은 것으로 복사하는 동시에 전체 스택을 한 번에 파괴 함). 그러나 별도의 스레드에서 수행되기 때문에 응용 프로그램의 스레드가 너무 많이 정지되지는 않습니다. 그러나 이는 초기 GC주기 이후 추가적인 수준의 간접적 인 비용과 LOR의 일반적인 손실에 대한 막대한 숨겨진 비용을 부담합니다. 그러나 할당 속도를 높이는 또 다른 전략입니다. 호출 스레드에서 더 저렴하게 만든 다음 다른 스레드에서 값 비싼 작업을 수행하십시오. 이를 위해서는 처음 할당 한 시간과 첫 번째주기 이후에 메모리에서 셔플이 발생하기 때문에 하나를 대신하여 두 가지 수준의 간접 참조가 필요합니다.

비슷한 맥락에서 C ++에 적용하기가 쉬운 또 다른 전략은 주 스레드에서 객체를 해제하지 않아도됩니다. 중간에서 물건을 제거 할 수없는 데이터 구조 끝에 추가, 추가 및 추가를 계속하십시오. 그러나 제거해야 할 사항을 표시하십시오. 그러면 별도의 스레드가 제거 된 요소없이 새 데이터 구조를 작성하는 고가의 작업을 처리 한 다음 새 요소를 기존의 요소와 원자 적으로 교환 할 수 있습니다. 요소 제거 요청이 즉시 충족 될 필요가 없다고 가정 할 수있는 경우 별도의 스레드. 스레드에 관한 한 여유가 줄어들뿐만 아니라 할당이 더 저렴합니다. 중간에서 제거 사례를 처리 할 필요가없는 훨씬 단순하고 멍청한 데이터 구조를 사용할 수 있기 때문입니다. 그것은 단지 필요한 컨테이너와 같습니다.push_back삽입을위한 clear기능 , 모든 요소를 ​​제거하고, swap제거 된 요소를 제외한 새로운 소형 용기로 내용물을 교환 하는 기능 ; 그것이 돌연변이가 진행되는 한 그것입니다.

답변