I am toying with certain caching algorithm, which is challenging somewhat. Basically, it needs to allocate lots of small objects (double arrays, 1 to 256 elements), with objects accessible through mapped value, map[key] = array. time to initialized array may be quite large, generally more than 10 thousand cpu cycles.
By lots I mean around gigabyte in total. objects may need to be popped/pushed as needed, generally in random places, one object at a time. lifetime of an object is generally long, minutes or more, however, object may be subject to allocation/deallocation several times during duration of program.
What would be good strategy to avoid memory fragmentation, while still maintaining reasonable allocate deallocate speed?
I am using C++, so I can use new and malloc. Thanks.
I know there a similar questions on website, Efficiently allocating many short-lived small objects, are somewhat different, thread safety is not immediate issue for me.
my development platform is Intel Xeon, linux operating system. Ideally I would like to work on PPC linux as well, but it is not the most important for me.
나는 다소 어려운 특정 캐싱 알고리즘을 가지고 놀고 있습니다. 기본적으로 매핑된 값, map[key] = 배열을 통해 액세스할 수 있는 개체와 함께 많은 작은 개체(이중 배열, 1~256개 요소)를 할당해야 합니다. 배열이 초기화되는 데 걸리는 시간은 상당히 클 수 있으며 일반적으로 CPU 주기가 10,000개를 넘습니다.
제비란 총 기가바이트 정도를 의미합니다. 개체는 필요에 따라 일반적으로 무작위 위치에서 한 번에 하나씩 팝/푸시해야 할 수 있습니다. 개체의 수명은 일반적으로 몇 분 이상으로 길지만, 프로그램이 진행되는 동안 개체는 여러 번 할당/할당 취소될 수 있습니다.
합리적인 할당 해제 속도를 유지하면서 메모리 조각화를 방지하는 좋은 전략은 무엇입니까?
저는 C++를 사용하고 있기 때문에 new와 malloc을 사용할 수 있습니다. 감사해요.
나는 웹 사이트에 비슷한 질문이 있다는 것을 알고 있습니다. 많은 단기 작은 개체를 효율적으로 할당하는 것은 다소 다릅니다. 스레드 안전은 나에게 즉각적인 문제가 아닙니다.
내 개발 플랫폼은 Linux 운영 체제인 Intel Xeon입니다. 이상적으로는 PPC Linux에서도 작업하고 싶지만 그것이 나에게 가장 중요한 것은 아닙니다.
Answer
Create a slotted allocator:
Allocator is created with many pages of memory, each of equal size (512k, 256k, the size should be tuned for your use).
The first time an object asks this allocator for memory it allocates a page. Allocating a page consists of removing it from the free list (no search, all pages are the same size) and setting the size of objects that will be allocated on this page. Typically this size calculated by taking the requested size and rounding it up to the nearest power of 2. Subsequent allocations of the same size just require a little bit of pointer math and incrementing the number of objects on the page.
Fragmentation is prevented because slots are all the same size and can be refilled on subsequent allocations. Efficiency is maintained (in some cases improved) because there is no memheader per allocation (which makes a big difference when the allocations are small, once allocations become large this allocator starts to waste almost 50% of available memory).
Both allocations and deallocations can be performed in constant time (no searches of the free list for correct slots). The only tricky part about a deallocation is that you don't typically want a memheader preceding the allocation, so you have to figure out the page and index in the page yourself... It's saturday and I haven't had my coffee so I don't have any good advice about doing that, it's easy enough to figure out from the deallocated address, though.
Edit: This answer is a bit long winded. As usual boost has your back.
슬롯 할당자를 만듭니다.
할당자는 각각 동일한 크기(512k, 256k, 크기는 사용에 맞게 조정해야 함)의 많은 메모리 페이지로 생성됩니다.
객체가 처음으로 이 할당자에게 메모리를 요청할 때 페이지를 할당합니다. 페이지 할당은 사용 가능한 목록에서 페이지를 제거하고(검색 없음, 모든 페이지의 크기가 동일함) 이 페이지에 할당될 개체의 크기를 설정하는 것으로 구성됩니다. 일반적으로 이 크기는 요청된 크기를 가장 가까운 2의 거듭제곱으로 반올림하여 계산됩니다. 동일한 크기의 후속 할당에는 약간의 포인터 계산이 필요하고 페이지의 개체 수를 증가시킵니다.
슬롯의 크기는 모두 동일하고 후속 할당 시 다시 채워질 수 있으므로 조각화가 방지됩니다. 할당당 메모리 헤더가 없기 때문에 효율성이 유지됩니다(어떤 경우에는 향상됨)(할당이 작을 때 큰 차이가 발생합니다. 일단 할당이 커지면 이 할당자는 사용 가능한 메모리의 거의 50%를 낭비하기 시작합니다).
할당과 할당 취소는 모두 일정한 시간에 수행될 수 있습니다(올바른 슬롯에 대한 여유 목록을 검색하지 않음). 할당 취소에 대한 유일한 까다로운 부분은 일반적으로 할당 앞에 멤헤더가 있는 것을 원하지 않기 때문에 페이지와 페이지의 색인을 직접 파악해야 한다는 것입니다... 토요일인데 커피를 마시지 못했기 때문에 그렇게 하는 것에 대한 좋은 조언은 없지만 할당 해제된 주소를 통해 알아내는 것은 충분히 쉽습니다.
편집: 이 답변은 약간 장황합니다. 평소처럼 부스트는 등을 맞댄다.https://stackoverflow.com/questions/2439536/strategy-to-allocate-free-lots-of-small-objects
class Pool
{
private:
struct Link
{ Link * next; };
struct Chunk
{
enum {size = 8*1024-16};
Chunk * next;
char mem[size];
};
private:
Chunk * chunks;
const unsigned int esize;
Link * head;
private:
Pool (const Pool &) { } // copy protection
void operator = (Pool &) { } // copy protection
public:
// sz is the size of elements
Pool(unsigned int sz)
: esize(sz < sizeof(Link*) ? sizeof(Link*) : sz),
head(0), chunks(0)
{ }
~Pool()
{
Chunk * n = chunks;
while(n)
{
Chunk * p = n;
n = n->next;
delete p;
}
}
public:
// allocate one element
void * alloc()
{
if(head == 0)
grow();
Link * p = head;
head = p->next;
return p;
}
// put an element back into the pool
void free(void * b)
{
Link * p = static_cast<Link*>(b);
p->next = head; //put b back as first element
head = p;
}
private:
// make pool larger
void grow()
{
Chunk* n = new Chunk;
n->next = chunks;
chunks = n;
const int nelem = Chunk::size / esize;
char * start = n->mem;
char * last = &start [ (nelem - 1) * esize ];
for(char * p = start; p < last; p += esize) // assume sizeof(Link) <= esize
reinterpret_cast<Link>(p)->next = reinterpret_cast<Link *>(p + esize);
reinterpret_cast<Link *>(last)->next = 0;
head = reinterpret_cast<Link *>(start);
}
};
'코딩 > Memory' 카테고리의 다른 글
#7 [직접구현]small memory object allocator (0) | 2023.11.03 |
---|---|
#5 Why dynamic allocation of small objects in C++ reserves much more memory than actually needed? (0) | 2023.11.02 |
#4 malloc-lab 동적 할당기 구현 (0) | 2023.10.30 |
#3 [직접구현]tcmalloc, malloc 기본 예제 코드 (0) | 2023.10.30 |
#2 mymemory (GitHub) (0) | 2023.10.30 |
I am toying with certain caching algorithm, which is challenging somewhat. Basically, it needs to allocate lots of small objects (double arrays, 1 to 256 elements), with objects accessible through mapped value, map[key] = array. time to initialized array may be quite large, generally more than 10 thousand cpu cycles.
By lots I mean around gigabyte in total. objects may need to be popped/pushed as needed, generally in random places, one object at a time. lifetime of an object is generally long, minutes or more, however, object may be subject to allocation/deallocation several times during duration of program.
What would be good strategy to avoid memory fragmentation, while still maintaining reasonable allocate deallocate speed?
I am using C++, so I can use new and malloc. Thanks.
I know there a similar questions on website, Efficiently allocating many short-lived small objects, are somewhat different, thread safety is not immediate issue for me.
my development platform is Intel Xeon, linux operating system. Ideally I would like to work on PPC linux as well, but it is not the most important for me.
나는 다소 어려운 특정 캐싱 알고리즘을 가지고 놀고 있습니다. 기본적으로 매핑된 값, map[key] = 배열을 통해 액세스할 수 있는 개체와 함께 많은 작은 개체(이중 배열, 1~256개 요소)를 할당해야 합니다. 배열이 초기화되는 데 걸리는 시간은 상당히 클 수 있으며 일반적으로 CPU 주기가 10,000개를 넘습니다.
제비란 총 기가바이트 정도를 의미합니다. 개체는 필요에 따라 일반적으로 무작위 위치에서 한 번에 하나씩 팝/푸시해야 할 수 있습니다. 개체의 수명은 일반적으로 몇 분 이상으로 길지만, 프로그램이 진행되는 동안 개체는 여러 번 할당/할당 취소될 수 있습니다.
합리적인 할당 해제 속도를 유지하면서 메모리 조각화를 방지하는 좋은 전략은 무엇입니까?
저는 C++를 사용하고 있기 때문에 new와 malloc을 사용할 수 있습니다. 감사해요.
나는 웹 사이트에 비슷한 질문이 있다는 것을 알고 있습니다. 많은 단기 작은 개체를 효율적으로 할당하는 것은 다소 다릅니다. 스레드 안전은 나에게 즉각적인 문제가 아닙니다.
내 개발 플랫폼은 Linux 운영 체제인 Intel Xeon입니다. 이상적으로는 PPC Linux에서도 작업하고 싶지만 그것이 나에게 가장 중요한 것은 아닙니다.
Answer
Create a slotted allocator:
Allocator is created with many pages of memory, each of equal size (512k, 256k, the size should be tuned for your use).
The first time an object asks this allocator for memory it allocates a page. Allocating a page consists of removing it from the free list (no search, all pages are the same size) and setting the size of objects that will be allocated on this page. Typically this size calculated by taking the requested size and rounding it up to the nearest power of 2. Subsequent allocations of the same size just require a little bit of pointer math and incrementing the number of objects on the page.
Fragmentation is prevented because slots are all the same size and can be refilled on subsequent allocations. Efficiency is maintained (in some cases improved) because there is no memheader per allocation (which makes a big difference when the allocations are small, once allocations become large this allocator starts to waste almost 50% of available memory).
Both allocations and deallocations can be performed in constant time (no searches of the free list for correct slots). The only tricky part about a deallocation is that you don't typically want a memheader preceding the allocation, so you have to figure out the page and index in the page yourself... It's saturday and I haven't had my coffee so I don't have any good advice about doing that, it's easy enough to figure out from the deallocated address, though.
Edit: This answer is a bit long winded. As usual boost has your back.
슬롯 할당자를 만듭니다.
할당자는 각각 동일한 크기(512k, 256k, 크기는 사용에 맞게 조정해야 함)의 많은 메모리 페이지로 생성됩니다.
객체가 처음으로 이 할당자에게 메모리를 요청할 때 페이지를 할당합니다. 페이지 할당은 사용 가능한 목록에서 페이지를 제거하고(검색 없음, 모든 페이지의 크기가 동일함) 이 페이지에 할당될 개체의 크기를 설정하는 것으로 구성됩니다. 일반적으로 이 크기는 요청된 크기를 가장 가까운 2의 거듭제곱으로 반올림하여 계산됩니다. 동일한 크기의 후속 할당에는 약간의 포인터 계산이 필요하고 페이지의 개체 수를 증가시킵니다.
슬롯의 크기는 모두 동일하고 후속 할당 시 다시 채워질 수 있으므로 조각화가 방지됩니다. 할당당 메모리 헤더가 없기 때문에 효율성이 유지됩니다(어떤 경우에는 향상됨)(할당이 작을 때 큰 차이가 발생합니다. 일단 할당이 커지면 이 할당자는 사용 가능한 메모리의 거의 50%를 낭비하기 시작합니다).
할당과 할당 취소는 모두 일정한 시간에 수행될 수 있습니다(올바른 슬롯에 대한 여유 목록을 검색하지 않음). 할당 취소에 대한 유일한 까다로운 부분은 일반적으로 할당 앞에 멤헤더가 있는 것을 원하지 않기 때문에 페이지와 페이지의 색인을 직접 파악해야 한다는 것입니다... 토요일인데 커피를 마시지 못했기 때문에 그렇게 하는 것에 대한 좋은 조언은 없지만 할당 해제된 주소를 통해 알아내는 것은 충분히 쉽습니다.
편집: 이 답변은 약간 장황합니다. 평소처럼 부스트는 등을 맞댄다.https://stackoverflow.com/questions/2439536/strategy-to-allocate-free-lots-of-small-objects
class Pool
{
private:
struct Link
{ Link * next; };
struct Chunk
{
enum {size = 8*1024-16};
Chunk * next;
char mem[size];
};
private:
Chunk * chunks;
const unsigned int esize;
Link * head;
private:
Pool (const Pool &) { } // copy protection
void operator = (Pool &) { } // copy protection
public:
// sz is the size of elements
Pool(unsigned int sz)
: esize(sz < sizeof(Link*) ? sizeof(Link*) : sz),
head(0), chunks(0)
{ }
~Pool()
{
Chunk * n = chunks;
while(n)
{
Chunk * p = n;
n = n->next;
delete p;
}
}
public:
// allocate one element
void * alloc()
{
if(head == 0)
grow();
Link * p = head;
head = p->next;
return p;
}
// put an element back into the pool
void free(void * b)
{
Link * p = static_cast<Link*>(b);
p->next = head; //put b back as first element
head = p;
}
private:
// make pool larger
void grow()
{
Chunk* n = new Chunk;
n->next = chunks;
chunks = n;
const int nelem = Chunk::size / esize;
char * start = n->mem;
char * last = &start [ (nelem - 1) * esize ];
for(char * p = start; p < last; p += esize) // assume sizeof(Link) <= esize
reinterpret_cast<Link>(p)->next = reinterpret_cast<Link *>(p + esize);
reinterpret_cast<Link *>(last)->next = 0;
head = reinterpret_cast<Link *>(start);
}
};
'코딩 > Memory' 카테고리의 다른 글
#7 [직접구현]small memory object allocator (0) | 2023.11.03 |
---|---|
#5 Why dynamic allocation of small objects in C++ reserves much more memory than actually needed? (0) | 2023.11.02 |
#4 malloc-lab 동적 할당기 구현 (0) | 2023.10.30 |
#3 [직접구현]tcmalloc, malloc 기본 예제 코드 (0) | 2023.10.30 |
#2 mymemory (GitHub) (0) | 2023.10.30 |