chiến lược để phân bổ/miễn phí rất nhiều đối tượng nhỏ

Question

Tôi đang đùa giỡn với thuật toán bộ nhớ đệm nhất định, đó là thách thức một chút. Về cơ bản, nó cần phân bổ rất nhiều đối tượng nhỏ (mảng kép, 1 đến 256 phần tử), với các đối tượng có thể truy cập thông qua giá trị được ánh xạ, map[key] = array. thời gian để khởi tạo mảng có thể khá lớn, thường là hơn 10 nghìn chu kỳ CPU.

Theo lô tôi có nghĩa là khoảng gigabyte trong tổng số. đối tượng có thể cần phải được bật/đẩy khi cần thiết, thường ở những nơi ngẫu nhiên, một đối tượng tại một thời điểm. tuổi thọ của một đối tượng thường dài, phút hoặc hơn, tuy nhiên, đối tượng có thể phải chịu sự phân bổ/deallocation nhiều lần trong suốt thời gian của chương trình.

Điều gì sẽ là chiến lược tốt để tránh phân mảnh bộ nhớ, trong khi vẫn duy trì tốc độ phân bổ hợp lý phân bổ hợp lý?

Tôi đang sử dụng C++, vì vậy tôi có thể sử dụng mới và malloc. Cảm ơn.

Tôi biết có một câu hỏi tương tự trên trang web, Efficiently allocating many short-lived small objects, có phần khác biệt, an toàn chủ đề không phải là vấn đề ngay lập tức đối với tôi.

nền tảng phát triển của tôi là Intel Xeon, hệ điều hành Linux. Lý tưởng nhất là tôi cũng muốn làm việc trên PPC Linux, nhưng nó không phải là quan trọng nhất đối với tôi.

Answer 1

Tạo một cấp phát rãnh:

cấp phát được tạo ra với nhiều trang của bộ nhớ, mỗi kích thước bằng nhau (512k, 256k, kích thước nên được điều chỉnh để sử dụng).

Lần đầu tiên một đối tượng hỏi trình cấp phát này cho bộ nhớ mà nó phân bổ một trang. Phân bổ một trang bao gồm xóa nó khỏi danh sách miễn phí (không tìm kiếm, tất cả các trang có cùng kích thước) và thiết lập kích thước của các đối tượng sẽ được cấp phát trên trang này. Thông thường kích thước này được tính toán bằng cách lấy kích thước yêu cầu và làm tròn nó lên đến sức mạnh gần nhất của 2. Phân bổ tiếp theo của cùng một kích thước chỉ đòi hỏi một chút toán học con trỏ và tăng số lượng các đối tượng trên trang.

Phân mảnh bị ngăn chặn vì các vị trí có cùng kích thước và có thể được nạp lại trên các phân bổ tiếp theo. Hiệu quả được duy trì (trong một số trường hợp được cải thiện) vì không có memheader cho mỗi phân bổ (tạo nên sự khác biệt lớn khi phân bổ nhỏ, khi phân bổ trở nên lớn, bộ cấp phát này bắt đầu lãng phí gần 50% bộ nhớ có sẵn).

Cả hai phân bổ và deallocations có thể được thực hiện trong thời gian không đổi (không có tìm kiếm của danh sách miễn phí cho các vị trí chính xác). Phần khó khăn duy nhất về một deallocation là bạn không thường muốn một memheader trước phân bổ, vì vậy bạn phải tìm ra các trang và chỉ mục trong trang mình ... Đó là thứ bảy và tôi đã không có cà phê của tôi vì vậy tôi không có bất kỳ lời khuyên tốt về việc đó, thật dễ dàng để tìm ra từ địa chỉ deallocated, mặc dù.

Chỉnh sửa: Câu trả lời này hơi dài. Như thường lệ, boost có lưng của bạn.

Answer 2

Nếu bạn biết kích thước tối đa của mảng, bạn có thể sử dụng trình phân bổ tùy chỉnh. Bạn sẽ phải tự viết lớp cấp phát. Những gì nó cần làm là phân bổ một đoạn lớn của bộ nhớ cùng một lúc và đúc nó vào một danh sách liên kết. Mỗi khi một cá thể đối tượng cần được tạo, bạn xóa đuôi khỏi danh sách. Mỗi khi đối tượng cần được giải phóng, bạn thêm một mục vào danh sách.

EDIT: đây là một ví dụ từ C++ Programming Language Bjarne Stroustrup của , 3rd Edition:

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

Answer 3

Nếu bạn có thể dự đoán kích thước của các đối tượng được phân bổ trước khi bạn có thể sẽ là tốt nhất để đi với một đoạn bộ nhớ được phân bổ tuyến tính và trình phân bổ tùy chỉnh của riêng bạn (như @Kerido đề xuất). Để làm được điều đó, tôi sẽ thêm rằng phương thức hiệu quả nhất sẽ bằng 0 và hoán đổi cho các vị trí trong phân bổ, và không lo lắng về việc phân vùng lại và nén mảng (để lại khoảng trống giữa các phân bổ) để bạn không phải xử lý các chỉ mục và cập nhật bảo trì.

Nếu bạn có thể phân vùng đối tượng của mình trước (nghĩa là bạn biết bạn có các phần tử kích thước không cố định, nhưng nhóm dễ dàng) chia chúng thành các nhóm và sắp xếp các khối bộ nhớ vào mỗi nhóm và hoán đổi các mục vào thích hợp cái xô. Nếu đối tượng của bạn có thể thay đổi kích thước trong suốt cuộc đời của họ có thể trở nên khó khăn để quản lý, hãy xem xét cách tiếp cận này một cách cẩn thận.