Basile이 제안한 것처럼 문자열을 조회하고 저장하기 위해 32 비트 인덱스로 변환하는 인터네 이닝 된 문자열에 크게 의존합니다. 예를 들어, “x”라는 속성을 가진 수십만에서 수백만 개의 컴포넌트를 가지고 있기 때문에 제 경우에는 유용합니다.

검색을 위해 trie를 사용합니다 (또한 실험 unordered_map했지만 메모리 풀로 백업 된 조정 된 trie는 적어도 성능이 향상되기 시작했으며 구조에 액세스 할 때마다 잠금하지 않고 스레드 안전을 쉽게 만들었습니다). 생성으로 건설에 대한 빠른 std::string. 요점은 문자열 동등성 검사와 같은 후속 작업의 속도를 높이는 것입니다. 제 경우에는 두 정수가 동일한 지 검사하고 메모리 사용량을 크게 줄입니다.

한 가지 옵션은 이미 할당 된 값의 레지스트리를 유지 관리하는 것이지만 중복 메모리 할당보다 레지스트리 조회를 더 빠르게 할 수 있습니까?

단일 데이터보다 훨씬 빠르게 데이터 구조를 검색하기가 어렵습니다. malloc예를 들어 파일과 같은 외부 입력에서 문자열의 보트로드를 읽는 경우 가능한 경우 순차적 할당자를 사용하는 것이 좋습니다. 개별 문자열의 메모리를 비울 수 없다는 단점이 있습니다. 할당 자에 의해 풀링 된 모든 메모리는 한 번에 해제되거나 전혀 해제되지 않아야합니다. 그러나 순차 할당자는 작은 가변 크기의 메모리 덩어리의 보트로드를 똑바로 순차적으로 할당하고 나중에 나중에 모두 던져 버릴 경우에 편리 할 수 ​​있습니다. 이것이 귀하의 경우에 해당되는지 여부는 알 수 없지만 적용 가능한 경우 빈번한 작은 메모리 할당과 관련된 핫스팟을 수정하는 쉬운 방법이 될 수 있습니다 (캐시 누락 및 페이지 결함과 관련이있을 수 있음) 에 의해 사용되는 알고리즘 malloc).

고정 된 크기의 할당은 순차적 할당 기 제약 조건없이 속도를 높이기 때문에 나중에 재사용 할 특정 메모리 청크를 해제 할 수 없습니다. 그러나 기본 할당 자보다 가변 크기 할당을 더 빠르게 만드는 것은 매우 어렵습니다. 기본적으로 malloc적용 범위를 좁히는 제약 조건을 적용하지 않으면 일반적으로 매우 힘든 메모리 할당 기보다 훨씬 빠릅니다 . 한 가지 해결책은 고정 크기 할당자를 사용하는 것입니다. 예를 들어, 보트로드가 있고 긴 문자열이 드문 경우 (기본 할당자를 사용할 수있는 경우) 8 바이트 이하의 모든 문자열입니다. 즉, 1 바이트 문자열에 7 바이트가 낭비된다는 것을 의미하지만 95 %의 시간에 문자열이 매우 짧은 경우 할당 관련 핫스팟을 제거해야합니다.

방금 나에게 일어난 또 다른 해결책은 미쳐 들리지만 내 말을들을 수있는 풀린 링크 목록을 사용하는 것입니다.

여기서 아이디어는 언 롤링 된 각 노드를 가변 크기 대신 고정 크기로 만드는 것입니다. 그렇게 할 때, 메모리를 풀링하는 매우 빠른 고정 크기의 청크 할당자를 사용하여 서로 연결된 가변 크기 문자열에 고정 크기의 청크를 할당 할 수 있습니다. 메모리 사용을 줄이지는 않지만 링크 비용으로 인해 추가되는 경향이 있지만 풀린 크기로 재생하여 필요에 맞는 균형을 찾을 수 있습니다. 그것은 괴상한 아이디어이지만 이제는 대량의 연속 블록에 이미 할당 된 메모리를 효과적으로 풀링하고 여전히 문자열을 개별적으로 해제 할 수있는 이점을 가지므로 메모리 관련 핫스팟을 제거해야합니다. 다음은 내가 쓸 수있는 간단한 고정 고정 할당 자 (생산 관련 보풀이없는 다른 사람을 위해 만든 그림)입니다.

#ifndef FIXED_ALLOCATOR_HPP
#define FIXED_ALLOCATOR_HPP

class FixedAllocator
{
public:
    /// Creates a fixed allocator with the specified type and block size.
    explicit FixedAllocator(int type_size, int block_size = 2048);

    /// Destroys the allocator.
    ~FixedAllocator();

    /// @return A pointer to a newly allocated chunk.
    void* allocate();

    /// Frees the specified chunk.
    void deallocate(void* mem);

private:
    struct Block;
    struct FreeElement;

    FreeElement* free_element;
    Block* head;
    int type_size;
    int num_block_elements;
};

#endif

#include "FixedAllocator.hpp"
#include <cstdlib>

struct FixedAllocator::FreeElement
{
    FreeElement* next_element;
};

struct FixedAllocator::Block
{
    Block* next;
    char* mem;
};

FixedAllocator::FixedAllocator(int type_size, int block_size): free_element(0), head(0)
{
    type_size = type_size > sizeof(FreeElement) ? type_size: sizeof(FreeElement);
    num_block_elements = block_size / type_size;
    if (num_block_elements == 0)
        num_block_elements = 1;
}

FixedAllocator::~FixedAllocator()
{
    // Free each block in the list, popping a block until the stack is empty.
    while (head)
    {
        Block* block = head;
        head = head->next;
        free(block->mem);
        free(block);
    }
    free_element = 0;
}

void* FixedAllocator::allocate()
{
    // Common case: just pop free element and return.
    if (free_element)
    {
        void* mem = free_element;
        free_element = free_element->next_element;
        return mem;
    }

    // Rare case when we're out of free elements.
    // Create new block.
    Block* new_block = static_cast<Block*>(malloc(sizeof(Block)));
    new_block->mem = malloc(type_size * num_block_elements);
    new_block->next = head;
    head = new_block;

    // Push all but one of the new block's elements to the free stack.
    char* mem = new_block->mem;
    for (int j=1; j < num_block_elements; ++j)
    {
        void* ptr = mem + j*type_size;
        FreeElement* element = static_cast<FreeElement*>(ptr);
        element->next_element = free_element;
        free_element = element;
    }
    return mem;
}

void FixedAllocator::deallocate(void* mem)
{
    // Just push a free element to the stack.
    FreeElement* element = static_cast<FreeElement*>(mem);
    element->next_element = free_element;
    free_element = element;
}

답변