태그 보관물: strings

strings

C ++에서 중복 문자열 할당 최적화 합리적 일지

성능이 문제가되는 상당히 복잡한 C ++ 구성 요소가 있습니다. 프로파일 링은 대부분의 실행 시간이 단순히 std::strings에 메모리를 할당하는 데 소비된다는 것을 보여줍니다 .

나는 그 문자열들 사이에 많은 중복성이 있음을 알고 있습니다. 소수의 값은 매우 자주 반복되지만 고유 한 값도 많이 있습니다. 줄은 일반적으로 상당히 짧습니다.

나는 이제 그 빈번한 할당을 어떻게 든 재사용하는 것이 합리적 일지 생각하고 있습니다. 1000 개의 고유 한 “foobar”값에 대한 1000 개의 포인터 대신 하나의 “foobar”값에 대한 1000 개의 포인터를 가질 수 있습니다. 이것이 더 메모리 효율적이라는 사실은 좋은 보너스이지만 여기서 지연 시간이 대부분 걱정됩니다.

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



답변

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;
}


답변

내부 문자열 기계를 원할 수도 있지만 (문자열은 변경할 수 없으므로 const std::string-s를 사용하십시오 ). 당신은 몇 가지 기호를 원할 수 있습니다. 스마트 포인터를 볼 수 있습니다 (예 : std :: shared_ptr ). 또는 C ++ 17의 std :: string_view 조차도 .


답변

옛날에 컴파일러를 만들 때 data-chair (data-bank 대신 DB의 구어체 독일어 번역)를 사용했습니다. 이것은 단순히 문자열의 해시를 만들어 할당에 사용했습니다. 따라서 모든 문자열은 힙 / 스택의 일부 메모리가 아니라이 데이터 의자의 해시 코드입니다. String그러한 클래스로 대체 할 수 있습니다. 그러나 약간의 코드 재 작업이 필요합니다. 물론 이것은 r / o 문자열에만 사용할 수 있습니다.


답변

사용 된 메모리 할당과 실제 메모리가 성능 저하와 어떤 관련이 있는지 확인하십시오.

실제로 메모리를 할당하는 비용은 물론 매우 높습니다. 따라서 std :: string은 작은 문자열에 대해 내부 할당을 이미 사용하고 있으므로 실제 할당량은 처음 가정 한 것보다 적을 수 있습니다. 이 버퍼의 크기가 충분히 크지 않은 경우, 23 개의 문자를 사용하는 Facebook의 문자열 클래스 ( https://github.com/facebook/folly/blob/master/folly/FBString.h ) 에서 영감을받을 수 있습니다. 할당하기 전에 내부적으로

많은 메모리 를 사용 하는 비용 도 주목할 가치가 있습니다. 이것은 아마도 가장 큰 문제 일 것입니다. 컴퓨터에 충분한 RAM이있을 수 있지만, 캐시 크기는 여전히 작아서 아직 캐시되지 않은 메모리에 액세스 할 때 성능이 저하 될 수 있습니다. https://en.wikipedia.org/wiki/Locality_of_reference에서 이에 대해 읽을 수 있습니다.


답변

문자열 작업을 더 빠르게 만드는 대신 문자열 작업 수를 줄이는 것이 또 다른 방법입니다. 예를 들어 문자열을 열거 형으로 바꿀 수 있습니까?

유용 할 수있는 또 다른 접근 방식은 Cocoa에서 사용됩니다. 수백 또는 수천 개의 사전이 있고 대부분 같은 키를 가진 경우가 있습니다. 따라서 사전 키 집합 인 객체를 만들 수 있으며 이러한 객체를 인수로 사용하는 사전 생성자가 있습니다. 사전은 다른 사전과 동일하게 작동하지만 해당 키 세트의 키와 키 / 값 쌍을 추가하면 키가 복제되지 않고 키 세트의 키에 대한 포인터 만 저장됩니다. 따라서 이러한 수천 개의 사전에는 해당 세트에있는 각 키 문자열의 사본 하나만 필요합니다.


답변