Quản lý bộ nhớ không có nhánh?

Question

Bất cứ ai cũng nghĩ về cách viết một trình quản lý bộ nhớ (trong C++) hoàn toàn miễn phí chi nhánh? Tôi đã viết một hồ bơi, một chồng, một hàng đợi, và một danh sách liên kết (phân bổ từ các hồ bơi), nhưng tôi tự hỏi làm thế nào chính đáng nó là viết một chi nhánh quản lý bộ nhớ chung miễn phí.

Đây là tất cả để giúp tạo một khung thực sự có thể tái sử dụng để làm việc đồng bộ, CPU theo thứ tự và phát triển thân thiện với bộ nhớ cache.

Chỉnh sửa: theo nhánh không có nghĩa là không thực hiện các cuộc gọi hàm trực tiếp hoặc gián tiếp và không sử dụng ifs. Tôi đã nghĩ rằng tôi có thể có thể thực hiện một cái gì đó mà lần đầu tiên thay đổi kích thước yêu cầu bằng không cho các cuộc gọi sai, nhưng đã không thực sự có nhiều hơn thế. Tôi cảm thấy rằng nó không phải là không thể, nhưng khía cạnh khác của bài tập này sau đó là profiling nó trên nói "không thân thiện" bộ vi xử lý để xem nếu nó có giá trị cố gắng cứng như thế này để tránh phân nhánh.

Answer 1

Trong khi tôi không nghĩ rằng đây là một ý tưởng tốt, một giải pháp sẽ có xô trước được phân bổ khác nhau log kích cỡ, ngu ngốc giả:

class Allocator { 

    void* malloc(size_t size) { 
     int bucket = log2(size + sizeof(int)); 
     int* pointer = reinterpret_cast<int*>(m_buckets[bucket].back()); 
     m_buckets[bucket].pop_back(); 
     *pointer = bucket; //Store which bucket this was allocated from 
     return pointer + 1; //Dont overwrite header 
    } 

    void free(void* pointer) { 
     int* temp = reinterpret_cast<int*>(pointer) - 1; 
     m_buckets[*temp].push_back(temp); 
    } 

    vector< vector<void*> > m_buckets; 
}; 

(Bạn sẽ tất nhiên cũng thay thế std::vector bằng một mảng + bộ đếm đơn giản).

CHỈNH SỬA: Để làm điều này mạnh mẽ (ví dụ: xử lý tình huống nơi thùng trống), bạn sẽ phải thêm một số hình thức phân nhánh.

EDIT2: Dưới đây là một nhỏ cành log2 chức năng:

//returns the smallest x such that value <= (1 << x) 
int 
log2(int value) { 
    union Foo { 
     int x; 
     float y; 
    } foo; 
    foo.y = value - 1; 
    return ((foo.x & (0xFF << 23)) >> 23) - 126; //Extract exponent (base 2) of floating point number 
} 

này cho kết quả chính xác cho phân bổ < 33.554.432 byte. Nếu bạn cần phân bổ lớn hơn, bạn sẽ phải chuyển sang tăng gấp đôi.

Đây là số link về cách số dấu phẩy động được thể hiện trong bộ nhớ.

Answer 2

Cách duy nhất tôi biết để tạo phân bổ thật sự không có nhánh là đặt trước tất cả bộ nhớ mà nó có khả năng sẽ sử dụng trước. Nếu không, sẽ luôn có một số mã ẩn ở đâu đó để xem chúng ta có vượt quá dung lượng hiện tại cho dù nó đang ẩn trong một kiểm tra vector không nếu kích thước vượt quá dung lượng được sử dụng để thực hiện nó hoặc thứ gì đó thuộc loại đó.

Dưới đây là một ví dụ thô sơ về phân bổ cố định có phương pháp hoàn toàn không chi nhánh malloc và free.

class FixedAlloc 
{ 
public: 
    FixedAlloc(int element_size, int num_reserve) 
    { 
     element_size = max(element_size, sizeof(Chunk)); 
     mem = new char[num_reserve * element_size]; 

     char* ptr = mem; 
     free_chunk = reinterpret_cast<Chunk*>(ptr); 
     free_chunk->next = 0; 

     Chunk* last_chunk = free_chunk; 
     for (int j=1; j < num_reserve; ++j) 
     { 
      ptr += element_size; 
      Chunk* chunk = reinterpret_cast<Chunk*>(ptr); 
      chunk->next = 0; 
      last_chunk->next = chunk; 
      last_chunk = chunk; 
     } 
    } 

    ~FixedAlloc() 
    { 
     delete[] mem; 
    } 

    void* malloc() 
    { 
     assert(free_chunk && free_chunk->next && "Reserve memory exhausted!"); 
     Chunk* chunk = free_chunk; 
     free_chunk = free_chunk->next; 
     return chunk->mem; 
    } 

    void free(void* mem) 
    { 
     Chunk* chunk = static_cast<Chunk*>(mem); 
     chunk->next = free_chunk; 
     free_chunk = chunk; 
    } 

private: 
    union Chunk 
    { 
     Chunk* next; 
     char mem[1]; 
    }; 
    char* mem; 
    Chunk* free_chunk; 
}; 

Vì nó hoàn toàn không có nhánh, nó chỉ đơn giản là segfaults nếu bạn cố gắng cấp phát bộ nhớ nhiều hơn ban đầu được bảo lưu. Nó cũng có hành vi không xác định cho cố gắng để giải phóng một con trỏ null. Tôi cũng tránh đối phó với sự liên kết vì lợi ích của một ví dụ đơn giản hơn.