작은 물체를 할당/무료로 만드는 전략

StackOverflow https://stackoverflow.com/questions/2439536

문제

나는 특정 캐싱 알고리즘으로 놀고 있습니다. 기본적으로 맵핑 된 값을 통해 액세스 할 수있는 객체를 사용하여 많은 작은 물체 (이중 배열, 1 ~ 256 요소)를 할당해야합니다. map[key] = array. 초기화 된 배열까지의 시간은 상당히 클 수 있으며 일반적으로 10,000 CPU 사이클 이상일 수 있습니다.

많은 사람들은 총 기가 바이트 주위를 의미합니다. 객체는 필요에 따라, 일반적으로 임의의 장소에서 한 번에 하나의 물체 씩 튀어 나오거나 밀어야 할 수도 있습니다. 물체의 수명은 일반적으로 길고 몇 분 이상이지만, 객체는 프로그램 기간 동안 여러 번 할당/거래를받을 수 있습니다.

합리적인 할당 할당 속도를 유지하면서 메모리 파편화를 피하기위한 좋은 전략은 무엇입니까?

C ++를 사용하고 있으므로 새롭고 Malloc을 사용할 수 있습니다. 감사.

웹 사이트에 비슷한 질문이 있다는 것을 알고 있습니다. 많은 짧은 작은 물체를 효율적으로 할당합니다, 다소 다르면, 스레드 안전은 즉각적인 문제가 아닙니다.

내 개발 플랫폼은 인텔 Xeon, Linux 운영 체제입니다. 이상적으로는 PPC Linux에서도 작업하고 싶지만 가장 중요하지는 않습니다.

도움이 되었습니까?

해결책

슬롯 형 할당자를 만듭니다.

할당자는 많은 메모리 페이지로 만들어졌으며 각각 동일한 크기 (512k, 256k, 크기는 사용하도록 조정해야 함).

객체가 처음 으로이 할당 자에게 메모리를 요청하면 페이지가 할당됩니다. 페이지를 할당하는 것은 무료 목록에서 제거하고 (검색 없음, 모든 페이지가 같은 크기입니다)이 페이지에 할당 될 객체의 크기를 설정하는 것으로 구성됩니다. 일반적 으로이 크기는 요청 된 크기를 가져 와서 가장 가까운 2의 전력으로 반올림하여 계산되었습니다. 같은 크기의 후속 할당은 약간의 포인터 수학이 필요하고 페이지의 객체 수를 증가시킵니다.

슬롯은 모두 같은 크기이며 후속 할당에서 리필 될 수 있기 때문에 단편화가 방지됩니다. 할당 당 memheader가 없기 때문에 효율성이 유지됩니다 (일부 경우 개선) (할당이 작을 때 큰 차이를 만듭니다. 일단 할당이 커지면이 할당자는 사용 가능한 메모리의 거의 50%를 낭비하기 시작합니다).

할당 및 거래는 일정한 시간에 수행 될 수 있습니다 (정확한 슬롯에 대한 무료 목록의 검색 없음). 거래에 대한 유일한 까다로운 부분은 일반적으로 할당 앞에 멤버를 원하지 않기 때문에 페이지를 파악하고 페이지를 직접 알아 내야한다는 것입니다 ... 토요일에 커피를 마시지 않았습니다. 그래도 좋은 조언이 없지만, 거래 된 주소에서 알아 내기가 쉽습니다.

편집 :이 답변은 약간 길다. 평소와 같이 후원 등이 있습니다.

다른 팁

할당 된 물체의 크기를 미리 예측할 수 있다면 아마도 선형 할당 된 메모리 덩어리와 자신의 사용자 정의 할당 자 (@Kerido가 제안한대로)와 함께 이동하는 것이 가장 좋습니다. 그에 따라 가장 효율적인 방법은 할당 내 위치를 제로하고 스왑하는 것이며, 배열을 반복하고 압축하는 것에 대해 걱정하지 않아 (할당 사이에 데드 스페이스를 남겨두기) 인덱스 업데이트 및 색인을 처리 할 필요가 없습니다. 유지.

객체를 미리 분할 할 수 있다면 (즉, 고정되지 않은 크기 요소가 있지만 그룹은 쉽게 그룹을 알 수 있음) 메모리 덩어리를 각 버킷에 구사하고 항목을 적절한 버킷으로 바꾸십시오. 물체가 수명 동안 크기를 변경할 수있는 경우 관리하기가 까다로울 수 있으므로이 접근 방식을주의 깊게 고려하십시오.

배열의 최대 크기를 알고 있다면 사용자 정의 할당자를 사용할 수 있습니다. 할당 수업을 직접 작성해야합니다. 그것이해야 할 일은 한 번에 큰 메모리 덩어리를 할당하여 링크 된 목록에 캐스팅하는 것입니다. 객체 인스턴스를 만들 때마다 목록에서 꼬리를 삭제합니다. 객체를 풀어야 할 때마다 목록에 항목을 추가합니다.

편집 : 여기 Bjarne Stroustrup 's의 샘플이 있습니다. C ++ 프로그래밍 언어, 3 판:

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);
  }
};
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top