Opieram się mocno na internowanych ciągach, jak sugeruje Basile, gdzie wyszukiwanie ciągów przekłada się na 32-bitowy indeks do przechowywania i porównywania. Jest to przydatne w moim przypadku, ponieważ czasami mam setki tysięcy do milionów komponentów z właściwością o nazwie „x”, np. Która wciąż musi być przyjazną dla użytkownika nazwą ciągu, ponieważ jest często dostępna dla skrypterów według nazwy.
Używam trie do wyszukiwania (eksperymentowałem również z, unordered_mapale mój tuning trie wspierany przez pule pamięci przynajmniej zaczął działać lepiej i łatwiej było też zabezpieczyć wątek bez blokowania przy każdym dostępie do struktury), ale nie jest tak szybki do budowy jako tworzenie std::string. Chodzi o to, aby przyspieszyć kolejne operacje, takie jak sprawdzanie równości ciągów, co w moim przypadku sprowadza się do sprawdzenia dwóch liczb całkowitych pod kątem równości i drastycznego zmniejszenia zużycia pamięci.
Wydaje mi się, że jedną z opcji byłoby utrzymywanie pewnego rodzaju rejestru już przydzielonych wartości, ale czy jest nawet możliwe, aby wyszukiwanie rejestru było szybsze niż nadmiarowe przydziały pamięci?
Trudno będzie przeszukać strukturę danych znacznie szybciej niż pojedynczy malloc, np. jeśli masz przypadek, w którym odczytujesz ładunek ciągów znaków z zewnętrznego wejścia, na przykład pliku, wtedy moją pokusą byłoby użycie sekwencyjnego alokatora, jeśli to możliwe. Ma to tę wadę, że nie można zwolnić pamięci pojedynczego łańcucha. Cała pamięć zgromadzona przez alokator musi zostać uwolniona od razu lub wcale. Ale sekwencyjny alokator może być przydatny w przypadkach, w których po prostu musisz przydzielić ładunek niewielkich fragmentów pamięci o zmiennej wielkości w prosty sekwencyjny sposób, tylko po to, aby później to wszystko wyrzucić. Nie wiem, czy ma to zastosowanie w twoim przypadku, czy nie, ale w stosownych przypadkach może to być prosty sposób na naprawienie hotspotu związanego z częstymi alokacjami pamięci (które mogą mieć więcej wspólnego z błędami pamięci podręcznej i błędami strony niż z bazowymi algorytm używany, powiedzmy, malloc).
Przydziały o stałej wielkości są łatwiejsze do przyspieszenia bez ograniczeń sekwencyjnych, które uniemożliwiają zwolnienie określonych fragmentów pamięci do ponownego wykorzystania. Jednak szybsze przydzielanie przydziałów o zmiennej wielkości niż domyślny jest dość trudne. Zasadniczo tworzenie dowolnego rodzaju alokatora pamięci, który jest szybszy niż mallocjest ogólnie wyjątkowo trudny, jeśli nie zastosujesz ograniczeń ograniczających jego zastosowanie. Jednym z rozwiązań jest użycie dzielnika o stałej wielkości, powiedzmy, dla wszystkich ciągów, które mają 8 bajtów lub mniej, jeśli masz ich ładunek, a dłuższe ciągi są rzadkim przypadkiem (dla którego możesz po prostu użyć domyślnego przydziału). Oznacza to, że 7 bajtów jest marnowanych na łańcuchy 1-bajtowe, ale powinno to wyeliminować hotspoty związane z alokacją, jeśli, powiedzmy, w 95% przypadków, twoje łańcuchy są bardzo krótkie.
Innym rozwiązaniem, które właśnie mi przyszło do głowy, jest użycie rozwiniętych połączonych list, które mogą wydawać się szalone, ale mnie wysłuchaj.
Chodzi o to, aby każdy rozwinięty węzeł miał stały rozmiar zamiast zmiennej wielkości. Gdy to zrobisz, możesz użyć niezwykle szybkiego przydziału porcji o stałej wielkości, który gromadzi pamięć, przydzielając porcje o stałej wielkości do połączonych ze sobą łańcuchów o zmiennej wielkości. Nie zmniejszy to zużycia pamięci, będzie się do niej dodawać ze względu na koszt linków, ale możesz grać z rozwiniętym rozmiarem, aby znaleźć równowagę odpowiednią dla twoich potrzeb. Jest to trochę zwariowany pomysł, ale powinien wyeliminować hotspoty związane z pamięcią, ponieważ możesz teraz skutecznie grupować pamięć już przydzieloną w dużych, ciągłych blokach i nadal mieć korzyści z indywidualnego uwalniania ciągów. Oto prosty stary ustalony alokator (ilustracyjny, który zrobiłem dla kogoś innego, pozbawiony puchu związanego z produkcją), z którego możesz swobodnie korzystać:
#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;
}