Coś w rodzaju powtórzenia sugestii Kylotana, ale zaleciłbym rozwiązanie tego na poziomie struktury danych, jeśli to możliwe, a nie na niższym poziomie alokatora, jeśli możesz pomóc.
Oto prosty przykład tego, jak można uniknąć Fooswielokrotnego przydzielania i zwalniania za pomocą tablicy z dziurami z połączonymi ze sobą elementami (rozwiązywanie tego na poziomie „kontenera” zamiast na poziomie „alokatora”):
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;
}
};
Coś w tym celu: pojedynczo połączona lista indeksów z darmową listą. Łącza indeksu umożliwiają pomijanie usuniętych elementów, usuwanie elementów w stałym czasie, a także odzyskiwanie / ponowne wykorzystywanie / zastępowanie wolnych elementów z wstawianiem w stałym czasie. Aby wykonać iterację w strukturze, wykonaj następujące czynności:
for (int index = foos.first_node; index != -1; index = foos[index].next)
// do something with foos[index]
I możesz uogólnić powyższy rodzaj struktury danych „połączonej tablicy otworów” za pomocą szablonów, umieszczenia nowego i ręcznego wywołania dtor, aby uniknąć wymogu przypisania kopii, sprawić, by wywoływał destruktory po usunięciu elementów, zapewnia iterator do przodu itp. I postanowiłem zachować przykład bardzo podobny do C, aby jaśniej zilustrować tę koncepcję, a także dlatego, że jestem bardzo leniwy.
To powiedziawszy, ta struktura ma tendencję do degradacji w lokalizacji przestrzennej po usunięciu i wstawieniu wielu rzeczy do / od środka. W tym momencie nextlinki mogą sprawić, że będziesz chodzić tam i z powrotem wzdłuż wektora, ponownie ładując dane wcześniej eksmitowane z linii pamięci podręcznej w ramach tego samego sekwencyjnego przechodzenia (jest to nieuniknione w przypadku dowolnej struktury danych lub alokatora, który umożliwia ciągłe usuwanie bez tasowania elementów podczas odzyskiwania odstępy od środka ze wstawianiem w czasie stałym i bez użycia czegoś takiego jak równoległy zestaw bitów lub removedflaga). Aby przywrócić łatwość obsługi pamięci podręcznej, możesz zaimplementować metodę kopiowania ctor i zamiany w następujący sposób:
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);
Teraz nowa wersja jest znów przyjazna dla pamięci podręcznej, aby przejść. Inną metodą jest przechowywanie osobnej listy indeksów w strukturze i okresowe sortowanie. Innym jest użycie zestawu bitów do wskazania, jakie indeksy są używane. To zawsze będzie wymagać przejścia zestawu bitów w kolejności sekwencyjnej (aby to zrobić skutecznie, sprawdzaj 64 bity na raz, np. Przy użyciu FFS / FFZ). Zestaw bitów jest najbardziej wydajny i nieinwazyjny, wymagając tylko równoległego bitu na element, aby wskazać, które z nich są używane, a które są usuwane zamiast wymagać nextindeksów 32-bitowych , ale najbardziej czasochłonne, aby pisać dobrze (nie będzie bądź szybki na przejście, jeśli sprawdzasz jeden bit na raz - potrzebujesz FFS / FFZ, aby natychmiast znaleźć ustawiony lub nieuzbrojony bit wśród 32+ bitów, aby szybko określić zakres zajętych indeksów).
To połączone rozwiązanie jest na ogół najłatwiejsze do wdrożenia i nieinwazyjne (nie wymaga modyfikacji w Foocelu przechowywania niektórych removedflag), co jest pomocne, jeśli chcesz uogólnić ten kontener do pracy z dowolnym typem danych, jeśli nie przeszkadza ci to 32-bitowe narzut na element.
Czy powinienem utworzyć pulę pamięci do alokacji dynamicznej, czy też nie trzeba się tym przejmować? Co jeśli platforma docelowa to urządzenia mobilne?
potrzeba jest silnym słowem i jestem stronniczy w pracy w obszarach krytycznych pod względem wydajności, takich jak raytracing, przetwarzanie obrazu, symulacje cząstek i przetwarzanie siatki, ale przydzielanie i uwalnianie drobnych obiektów używanych do bardzo lekkiego przetwarzania, takich jak pociski, jest stosunkowo bardzo drogie. oraz cząstki indywidualnie w stosunku do ogólnego przeznaczenia, zmiennej wielkości alokatora pamięci. Biorąc pod uwagę, że powinieneś być w stanie uogólnić powyższą strukturę danych w ciągu jednego lub dwóch dni, aby przechowywać wszystko, co chcesz, myślę, że warto byłoby wymienić takie rozwiązanie, aby całkowicie wyeliminować takie koszty alokacji / dezalokacji stosu za każdą drobną rzecz. Oprócz zmniejszenia kosztów alokacji / dezalokacji, uzyskuje się lepszą lokalizację referencji w porównaniu z wynikami (mniej błędów pamięci podręcznej i błędów strony, tj.).
Jeśli chodzi o to, co Josh wspomniał o GC, nie badałem implementacji GC w C # tak dokładnie jak Java, ale alokatory GC często mają wstępny przydziałto bardzo szybko, ponieważ używa sekwencyjnego alokatora, który nie może zwolnić pamięci od środka (prawie jak stos, nie można usunąć rzeczy ze środka). Następnie opłaca się za drogie koszty faktyczne umożliwienie usuwania pojedynczych obiektów w osobnym wątku poprzez kopiowanie pamięci i czyszczenie poprzednio przydzielonej pamięci jako całości (jak zniszczenie całego stosu jednocześnie podczas kopiowania danych do czegoś bardziej podobnego do struktury powiązanej), ale ponieważ odbywa się to w osobnym wątku, niekoniecznie tak bardzo blokuje wątki aplikacji. Niesie to jednak bardzo znaczący ukryty koszt dodatkowego poziomu pośredniego i ogólnej utraty LOR po początkowym cyklu GC. Jest to kolejna strategia przyspieszenia alokacji - obniż koszt w wątku wywołującym, a następnie wykonaj kosztowną pracę w innym. W tym celu potrzebujesz dwóch poziomów pośrednich, aby odwoływać się do twoich obiektów zamiast jednego, ponieważ w końcu zostaną one potasowane w pamięci między czasem początkowo przydzielonym a po pierwszym cyklu.
Inną strategią w podobnym stylu, która jest nieco łatwiejsza do zastosowania w C ++, jest po prostu nie zawracaj sobie głowy uwalnianiem obiektów w głównych wątkach. Po prostu dodawanie i dodawanie i dodawanie na końcu struktury danych, co nie pozwala na usuwanie rzeczy ze środka. Zaznacz jednak rzeczy, które należy usunąć. Wówczas osobny wątek mógłby zająć się kosztowną pracą tworzenia nowej struktury danych bez usuniętych elementów, a następnie atomową zamianą nowej na starą, np. Znaczną część kosztów zarówno alokacji, jak i zwolnienia elementów można przenieść na oddzielny wątek, jeśli możesz założyć, że żądanie usunięcia elementu nie musi być natychmiast spełnione. To nie tylko sprawia, że uwolnienie jest tańsze, jeśli chodzi o twoje wątki, ale także sprawia, że alokacja jest tańsza, ponieważ możesz użyć znacznie prostszej i głupszej struktury danych, która nigdy nie musi obsługiwać przypadków usuwania od środka. To jest jak pojemnik, który potrzebuje tylkopush_backfunkcja wstawiania, clearfunkcja usuwania wszystkich elementów i swapzamiany zawartości na nowy, kompaktowy pojemnik z wyłączeniem usuniętych elementów; to tyle, jeśli chodzi o mutowanie.