2009-05-05 14 views
146

Một số lý do thực sự tốt để mương std::allocator có lợi cho giải pháp tùy chỉnh là gì? Bạn đã chạy qua bất kỳ tình huống nào mà nó hoàn toàn cần thiết cho tính chính xác, hiệu suất, khả năng mở rộng, v.v ...? Bất kỳ ví dụ thực sự thông minh nào?Ví dụ hấp dẫn về trình phân bổ C++ tùy chỉnh?

Trình phân bổ tùy chỉnh luôn là tính năng của Thư viện chuẩn mà tôi không cần nhiều. Tôi chỉ tự hỏi nếu có ai ở đây trên SO có thể cung cấp một số ví dụ hấp dẫn để biện minh cho sự tồn tại của họ.

Trả lời

91

Như tôi đã đề cập đến here, tôi đã nhìn thấy tùy chỉnh STL cấp phát Intel TBB của cải thiện đáng kể hiệu suất của một ứng dụng đa luồng chỉ đơn giản bằng cách thay đổi một đơn

std::vector<T> 

để

std::vector<T,tbb::scalable_allocator<T> > 

(đây là một cách nhanh chóng và cách thuận tiện để chuyển đổi trình cấp phát để sử dụng đống luồng riêng tư tiện lợi của TBB; xem page 7 in this document)

+1

Cảm ơn bạn đã liên kết thứ hai đó. Việc sử dụng các trình phân bổ để thực hiện các luồng riêng tư là thông minh. Tôi thích rằng đây là một ví dụ tốt về nơi các trình phân bổ tùy chỉnh có lợi thế rõ ràng trong một kịch bản không phải là tài nguyên giới hạn (nhúng hoặc bảng điều khiển). – Naaff

+4

Liên kết ban đầu hiện không còn tồn tại, nhưng CiteSeer có PDF: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.8289 –

+1

Tôi phải hỏi: Bạn có thể di chuyển một cách đáng tin cậy như vậy không vào một chủ đề khác? (Tôi đoán là không) – sellibitze

15

Có thể hữu ích khi sử dụng trình phân bổ tùy chỉnh để sử dụng nhóm bộ nhớ thay vì vùng lưu trữ. Đó là một ví dụ trong số nhiều người khác.

Đối với hầu hết các trường hợp, điều này chắc chắn là một tối ưu hóa sớm. Nhưng nó có thể rất hữu ích trong các ngữ cảnh nhất định (thiết bị nhúng, trò chơi, v.v.).

+2

Hoặc khi chia sẻ bộ nhớ đó. – Anthony

7

Tôi chưa viết mã C++ với trình phân bổ STL tùy chỉnh, nhưng tôi có thể tưởng tượng máy chủ web được viết bằng C++, sử dụng trình phân bổ tùy chỉnh để xóa tự động dữ liệu tạm thời cần thiết để trả lời yêu cầu HTTP. Trình phân bổ tùy chỉnh có thể giải phóng tất cả dữ liệu tạm thời cùng một lúc khi phản hồi đã được tạo.

Một trường hợp sử dụng có thể khác cho trình phân bổ tùy chỉnh (mà tôi đã sử dụng) đang viết một bài kiểm tra đơn vị để chứng minh rằng hành vi của hàm không phụ thuộc vào một phần đầu vào của hàm. Trình phân bổ tùy chỉnh có thể lấp đầy vùng bộ nhớ bằng bất kỳ mẫu nào.

+3

Có vẻ như ví dụ đầu tiên là công việc của destructor chứ không phải là cấp phát. – anthropomorphic

+1

Nếu bạn lo lắng về chương trình của bạn tùy thuộc vào nội dung ban đầu của bộ nhớ từ heap, một cách nhanh chóng (tức là qua đêm!) Chạy trong valgrind sẽ cho bạn biết một cách này hay cách khác. – cdyson37

+1

@anthropomorphic: destructor và phân bổ tùy chỉnh sẽ làm việc cùng nhau, các destructor sẽ chạy đầu tiên, sau đó xóa các phân bổ tùy chỉnh, mà sẽ không gọi miễn phí (...) được nêu ra, nhưng miễn phí (...) sẽ được được gọi sau, khi phục vụ yêu cầu đã kết thúc.Điều này có thể nhanh hơn phân bổ mặc định và giảm phân mảnh không gian địa chỉ. – pts

22

Tôi đang làm việc với một MySQL công cụ torage sử dụng C++ cho mã của nó. Chúng tôi đang sử dụng một cấp phát tùy chỉnh để sử dụng hệ thống bộ nhớ MySQL thay vì cạnh tranh với MySQL cho bộ nhớ. Nó cho phép chúng tôi đảm bảo rằng chúng tôi đang sử dụng bộ nhớ khi người dùng định cấu hình MySQL để sử dụng và không phải là "bổ sung".

69

Một khu vực nơi trình phân bổ tùy chỉnh có thể hữu ích là phát triển trò chơi, đặc biệt là trên bảng điều khiển trò chơi vì chúng chỉ có một lượng bộ nhớ nhỏ và không có trao đổi. Trên các hệ thống như vậy, bạn muốn đảm bảo rằng bạn có quyền kiểm soát chặt chẽ trên từng hệ thống con, do đó một hệ thống không chính thống không thể lấy cắp bộ nhớ từ một hệ thống quan trọng. Những thứ khác như pool allocators có thể giúp giảm phân mảnh bộ nhớ. Bạn có thể tìm thấy một chặng đường dài, giấy chi tiết về chủ đề này tại địa chỉ:

EASTL -- Electronic Arts Standard Template Library

+10

+1 cho liên kết EASTL: "Trong số các nhà phát triển trò chơi, điểm yếu cơ bản nhất [của STL] là thiết kế phân bổ std, và nó là điểm yếu này là yếu tố đóng góp lớn nhất cho việc tạo ra EASTL." – Naaff

5

Tôi đang sử dụng allocators tùy chỉnh ở đây; thậm chí bạn có thể nói rằng nó hoạt động xung quanh quản lý bộ nhớ động tùy chỉnh khác.

Bối cảnh: chúng tôi có quá tải cho malloc, calloc, miễn phí và các biến thể khác nhau của toán tử mới và xóa và mối liên kết vui vẻ làm cho STL sử dụng chúng cho chúng tôi. Điều này cho phép chúng tôi làm những việc như tự động nhóm nhỏ đối tượng, phát hiện rò rỉ, phân bổ điền, điền miễn phí, phân bổ đệm với sentries, liên kết bộ nhớ cache-line cho allocs nhất định, và trì hoãn miễn phí.

Vấn đề là, chúng tôi đang chạy trong môi trường được nhúng - không đủ bộ nhớ để thực hiện tính toán phát hiện rò rỉ đúng cách trong một khoảng thời gian dài. Ít nhất, không phải trong RAM tiêu chuẩn - có một đống RAM khác có sẵn ở nơi khác, thông qua các chức năng phân bổ tùy chỉnh.

Giải pháp: viết phân bổ tùy chỉnh sử dụng vùng mở rộng và sử dụng chỉ trong nội bộ của kiến ​​trúc theo dõi rò rỉ bộ nhớ ... Mọi thứ khác mặc định là quá tải theo dõi rò rỉ mới. Điều này tránh theo dõi theo dõi chính nó (và cung cấp một chút chức năng đóng gói thêm quá, chúng tôi biết kích thước của các nút theo dõi).

Chúng tôi cũng sử dụng tính năng này để giữ dữ liệu lược tả chi phí chức năng, vì lý do tương tự; viết một mục nhập cho mỗi cuộc gọi và trả lại chức năng, cũng như các công tắc chủ đề, có thể nhanh chóng tốn kém. Phân bổ tùy chỉnh lại cung cấp cho chúng ta allocs nhỏ hơn trong vùng bộ nhớ gỡ lỗi lớn hơn.

4

Tôi đang sử dụng trình phân bổ tùy chỉnh để đếm số lượng phân bổ/deallocations trong một phần của chương trình của tôi và đo thời gian cần thiết. Có nhiều cách khác có thể đạt được nhưng phương pháp này rất thuận tiện cho tôi. Nó đặc biệt hữu ích mà tôi có thể sử dụng phân bổ tùy chỉnh cho chỉ một tập con của các thùng chứa của tôi.

3

Một tình huống quan trọng: Khi viết mã phải hoạt động trên các ranh giới mô-đun (EXE/DLL), điều quan trọng là giữ phân bổ và xóa chỉ diễn ra trong một mô-đun.

Nơi tôi chạy vào đây là kiến ​​trúc Plugin trên Windows. Nó là điều cần thiết, ví dụ, nếu bạn vượt qua một std :: string trên ranh giới DLL, rằng bất kỳ reallocations của chuỗi xảy ra từ đống nơi nó bắt nguồn từ, KHÔNG heap trong DLL mà có thể khác nhau *.

* Điều này phức tạp hơn thực tế, như thể bạn đang liên kết động với CRT, điều này có thể hoạt động tốt. Nhưng nếu mỗi DLL có một liên kết tĩnh đến CRT bạn đang hướng đến một thế giới đau đớn, nơi các lỗi phân bổ ảo liên tục xảy ra.

+0

Nếu bạn vượt qua các đối tượng qua ranh giới DLL, bạn nên sử dụng cài đặt đa luồng (Debug) DLL (/ MD (d)) cho cả hai bên. C++ không được thiết kế với sự hỗ trợ mô-đun. Hoặc bạn có thể che chắn mọi thứ đằng sau giao diện COM và sử dụng CoTaskMemAlloc. Đây là cách tốt nhất để sử dụng các giao diện plugin không bị ràng buộc với một trình biên dịch, STL hoặc nhà cung cấp cụ thể. – gast128

53

Tôi đang làm việc trên bộ cấp phát mmap cho phép vectơ sử dụng bộ nhớ từ tệp được ánh xạ bộ nhớ. Mục đích là để có vectơ sử dụng bộ nhớ trực tiếp trong bộ nhớ ảo được ánh xạ bởi mmap. Vấn đề của chúng tôi là cải thiện việc đọc các tệp thực sự lớn (> 10GB) vào bộ nhớ mà không có bản sao trên trên cao, do đó tôi cần trình phân bổ tùy chỉnh này.

Cho đến bây giờ, tôi có bộ khung phân bổ tùy chỉnh (có nguồn gốc từ std :: allocator), tôi cho rằng đây là điểm bắt đầu tốt để bắt đầu phân bổ của riêng mình. Hãy sử dụng đoạn mã này trong bất cứ cách nào bạn muốn:

#include <memory> 
#include <stdio.h> 

namespace mmap_allocator_namespace 
{ 
     template <typename T> 
     class mmap_allocator: public std::allocator<T> 
     { 
public: 
       typedef size_t size_type; 
       typedef T* pointer; 
       typedef const T* const_pointer; 

       template<typename _Tp1> 
       struct rebind 
       { 
         typedef mmap_allocator<_Tp1> other; 
       }; 

       pointer allocate(size_type n, const void *hint=0) 
       { 
         fprintf(stderr, "Alloc %d bytes.\n", n*sizeof(T)); 
         return std::allocator<T>::allocate(n, hint); 
       } 

       void deallocate(pointer p, size_type n) 
       { 
         fprintf(stderr, "Dealloc %d bytes (%p).\n", n*sizeof(T), p); 
         return std::allocator<T>::deallocate(p, n); 
       } 

       mmap_allocator() throw(): std::allocator<T>() { fprintf(stderr, "Hello allocator!\n"); } 
       mmap_allocator(const mmap_allocator &a) throw(): std::allocator<T>(a) { } 
       template <class U>      
       mmap_allocator(const mmap_allocator<U> &a) throw(): std::allocator<T>(a) { } 
       ~mmap_allocator() throw() { } 
     }; 
} 

Để sử dụng, khai báo một container STL như sau:

using namespace std; 
using namespace mmap_allocator_namespace; 

vector<int, mmap_allocator<int> > int_vec(1024, 0, mmap_allocator<int>()); 

Nó có thể được sử dụng cho ví dụ để đăng nhập bất cứ khi nào bộ nhớ được phân bổ. Điều gì là cần thiết là cấu trúc rebind, khác container vector sử dụng các superclasses phân bổ/deallocate phương pháp.

Cập nhật: Bộ phân bổ ánh xạ bộ nhớ hiện khả dụng tại https://github.com/johannesthoma/mmap_allocator và là LGPL. Hãy sử dụng nó cho các dự án của bạn.

+2

cảm ơn điều này rất hữu ích – stack356

+7

Chỉ cần một người đứng đầu, bắt nguồn từ std :: cấp phát không thực sự là cách thành ngữ để viết phân bổ. Thay vào đó bạn nên nhìn vào allocator_traits, cho phép bạn cung cấp tối thiểu chức năng, và các lớp đặc điểm sẽ cung cấp phần còn lại. Lưu ý rằng STL luôn sử dụng phân bổ của bạn thông qua allocator_traits, không trực tiếp, vì vậy bạn không cần phải tham khảo allocator_traits mình Không có nhiều động lực để lấy được từ std :: allocator (mặc dù mã này có thể là một điểm khởi đầu hữu ích bất kể). –

4

Khi làm việc với GPU hoặc các bộ xử lý khác đôi khi có lợi khi phân bổ cấu trúc dữ liệu trong bộ nhớ chính theo cách đặc biệt . cách đặc biệt cấp phát bộ nhớ này có thể được triển khai trong trình phân bổ tùy chỉnh theo cách thuận tiện.

Lý do tại sao phân bổ tùy chỉnh thông qua thời gian chạy tăng tốc có thể có lợi khi sử dụng tăng tốc như sau:

  1. thông qua phân bổ tùy chỉnh thời gian chạy tăng tốc hoặc lái xe được thông báo về khối bộ nhớ
  2. ngoài các hoạt động hệ thống có thể đảm bảo rằng khối bộ nhớ được phân bổ bị khóa trang (một số gọi là bộ nhớ được ghim), nghĩa là hệ thống con bộ nhớ ảo của hệ điều hành không được di chuyển hoặc xóa trang trong hoặc từ bộ nhớ
  3. nếu 1. và 2. giữ và truyền dữ liệu giữa khối bộ nhớ bị khóa và bộ tăng tốc được yêu cầu, thời gian chạy có thể truy cập trực tiếp dữ liệu trong bộ nhớ chính vì nó biết nó ở đâu và có thể chắc chắn hệ điều hành không di chuyển/loại bỏ nó
  4. điều này sẽ tiết kiệm một bản sao bộ nhớ có thể xảy ra với bộ nhớ được phân bổ theo cách không bị khóa: dữ liệu phải được sao chép trong bộ nhớ chính sang khu vực dàn trang bị khóa với bộ gia tốc có thể khởi tạo việc chuyển dữ liệu (thông qua DMA)
+1

... không được quên các khối bộ nhớ liên kết trang. Điều này đặc biệt hữu ích nếu bạn đang nói chuyện với một trình điều khiển (tức là với FPGA qua DMA) và không muốn những rắc rối và phí tổn của việc tính toán bù đắp trong trang cho các danh sách phân tán DMA của bạn. – Jan

1

Cá nhân tôi sử dụng Loki :: Allocator/SmallObject để tối ưu hóa việc sử dụng bộ nhớ cho các đối tượng nhỏ - nó cho thấy hiệu suất tốt và hiệu suất thỏa mãn nếu bạn phải làm việc với lượng vừa phải. 1 đến 256 byte). Nó có thể lên đến 30 lần hiệu quả hơn so với phân bổ mới/xóa chuẩn C++ nếu chúng ta nói về việc phân bổ số lượng vừa phải của các đối tượng nhỏ có nhiều kích cỡ khác nhau. Ngoài ra, có một giải pháp cụ thể VC gọi là "QuickHeap", nó mang lại hiệu suất tốt nhất có thể (phân bổ và deallocate hoạt động chỉ đọc và ghi địa chỉ của khối được phân bổ/trả lại cho heap, tương ứng lên đến 99. (9)% trường hợp - phụ thuộc vào các thiết lập và khởi tạo), nhưng với chi phí của một chi phí đáng chú ý - nó cần hai con trỏ cho mỗi phạm vi và một phụ cho mỗi khối bộ nhớ mới. Đó là giải pháp nhanh nhất có thể để làm việc với số lượng lớn (10 000 ++) đối tượng được tạo và xóa nếu bạn không cần nhiều kích thước đối tượng (nó tạo ra một nhóm riêng cho từng kích thước đối tượng, từ 1 đến 1023 byte) trong thực hiện hiện tại, do đó, chi phí khởi tạo có thể làm giảm hiệu suất tổng thể, nhưng người ta có thể tiếp tục và phân bổ/deallocate một số đối tượng giả trước khi ứng dụng vào giai đoạn hiệu suất quan trọng (s)).

Vấn đề với việc thực hiện mới/xóa C++ chuẩn là nó thường chỉ là trình bao bọc cho phân bổ miễn phí/malloc C và nó hoạt động tốt cho các khối bộ nhớ lớn hơn, như 1024+ byte. Nó có một chi phí đáng chú ý về hiệu suất và, đôi khi, bộ nhớ thêm được sử dụng để lập bản đồ quá. Vì vậy, trong hầu hết các trường hợp, các trình phân bổ tùy chỉnh được thực hiện theo cách tối đa hóa hiệu suất và/hoặc giảm thiểu lượng bộ nhớ bổ sung cần thiết để phân bổ các đối tượng nhỏ (≤1024 bytes).

2

Đối với bộ nhớ dùng chung, điều quan trọng là không chỉ đầu chứa, mà còn dữ liệu chứa trong bộ nhớ dùng chung được lưu trữ.

Công cụ phân bổ Boost::Interprocess là một ví dụ tốt. Tuy nhiên, như bạn có thể đọc here allone này không đủ, để làm cho tất cả các container STL chia sẻ bộ nhớ tương thích (Do các phép chiếu khác nhau trong các quy trình khác nhau, con trỏ có thể "ngắt").

3

Một ví dụ về thời gian tôi đã sử dụng chúng đã hoạt động với các hệ thống nhúng bị ràng buộc rất tài nguyên.Cho phép nói rằng bạn có 2k ram miễn phí và chương trình của bạn phải sử dụng một số bộ nhớ đó. Bạn cần lưu trữ các chuỗi 4-5 ở đâu đó mà không có trong ngăn xếp và bạn cần có quyền truy cập rất chính xác vào nơi những thứ này được lưu trữ, đây là tình huống mà bạn có thể muốn viết trình phân bổ của riêng mình. Việc triển khai mặc định có thể phân mảnh bộ nhớ, điều này có thể không được chấp nhận nếu bạn không có đủ bộ nhớ và không thể khởi động lại chương trình của mình.

Một dự án mà tôi đang làm là sử dụng AVR-GCC trên một số chip được hỗ trợ thấp. Chúng tôi đã lưu trữ 8 chuỗi có độ dài thay đổi nhưng với độ dài tối đa đã biết. standard library implementation of the memory management là một wrapper mỏng xung quanh malloc/miễn phí mà theo dõi nơi để đặt các mục bằng cách thêm vào trước mỗi khối được cấp phát bộ nhớ với một con trỏ chỉ qua cuối của phần được cấp phát bộ nhớ đó. Khi phân bổ một bộ nhớ mới, bộ cấp phát chuẩn phải đi qua từng phần của bộ nhớ để tìm khối tiếp theo có sẵn khi kích thước bộ nhớ được yêu cầu sẽ phù hợp. Trên nền tảng máy tính để bàn, điều này sẽ rất nhanh đối với một vài mục này nhưng bạn phải ghi nhớ rằng một số các bộ vi điều khiển này rất chậm và nguyên thủy trong so sánh. Ngoài ra vấn đề phân mảnh bộ nhớ là một vấn đề lớn có nghĩa là chúng tôi thực sự không có lựa chọn nào khác ngoài cách tiếp cận khác.

Vì vậy, những gì chúng tôi đã làm là triển khai memory pool riêng của chúng tôi. Mỗi khối bộ nhớ đủ lớn để phù hợp với trình tự lớn nhất mà chúng ta cần trong đó. Các khối bộ nhớ có kích thước cố định được phân bổ này trước thời hạn và đánh dấu khối bộ nhớ nào hiện đang được sử dụng. Chúng tôi đã làm điều này bằng cách giữ một số nguyên 8 bit trong đó mỗi bit đại diện nếu một khối nhất định được sử dụng. Chúng tôi giao dịch sử dụng bộ nhớ ở đây vì đã cố gắng làm cho toàn bộ quá trình nhanh hơn, mà trong trường hợp của chúng tôi là hợp lý vì chúng tôi đã đẩy chip vi điều khiển này gần với khả năng xử lý tối đa của nó.

Có một số lần khác tôi có thể thấy viết trình phân bổ tùy chỉnh của riêng bạn trong ngữ cảnh của hệ thống nhúng, ví dụ: nếu bộ nhớ cho chuỗi không nằm trong ram chính như thường lệ trên these platforms.

2

liên kết bắt buộc để CppCon 2015 talk Andrei Alexandrescu về allocators:

https://www.youtube.com/watch?v=LIb3L4vKZ7U

Những điều tốt đẹp là chỉ đặt ra cho họ làm cho bạn nghĩ đến ý tưởng về cách bạn sẽ sử dụng chúng :-)

1

Trong mô phỏng đồ họa, tôi đã thấy các trình phân bổ tùy chỉnh được sử dụng cho

  1. Ràng buộc căn chỉnh std::allocator không trực tiếp ủng hộ.
  2. Giảm thiểu phân mảnh bằng cách sử dụng các nhóm riêng biệt cho thời gian sống ngắn (chỉ khung này) và phân bổ lâu dài.
1

Cách đây không lâu, tôi thấy giải pháp này rất hữu ích đối với tôi: Fast C++11 allocator for STL containers. Nó hơi tăng tốc độ STL container trên VS2017 (~ 5x) cũng như trên GCC (~ 7x). Nó là một phân bổ mục đích đặc biệt dựa trên bộ nhớ. Nó có thể được sử dụng với các container STL chỉ nhờ vào cơ chế mà bạn đang yêu cầu.