Sử dụng realloc trong C++

Question

std::realloc là nguy hiểm trong C++ nếu bộ nhớ malloc'd chứa các loại không phải nhóm. Có vẻ như chỉ có vấn đề là std::realloc sẽ không gọi loại destructors nếu nó không thể phát triển bộ nhớ tại chỗ.

Một công việc tầm thường xung quanh sẽ là một hàm try_realloc. Thay vì malloc'ing bộ nhớ mới nếu nó không thể được trồng tại chỗ, nó chỉ đơn giản là sẽ trở về sai. Trong trường hợp đó bộ nhớ mới có thể được cấp phát, các đối tượng được sao chép (hoặc di chuyển) sang bộ nhớ mới, và cuối cùng là bộ nhớ cũ được giải phóng.

Điều này có vẻ vô cùng hữu ích. std::vector có thể tận dụng tối đa điều này, có thể tránh tất cả các bản sao/phân bổ lại.
khả năng chống cháy trước: Về mặt kỹ thuật, đó là hiệu suất Big-O, nhưng nếu tăng trưởng vectơ là cổ chai trong ứng dụng của bạn, tốc độ x2 sẽ tốt hơn ngay cả khi Big-O không thay đổi.

NHƯNG, tôi không thể tìm thấy bất kỳ api nào hoạt động như try_realloc.

Tôi có thiếu gì đó không? Có phải try_realloc không hữu ích như tôi tưởng tượng không? Có một số lỗi ẩn khiến try_realloc không sử dụng được không?

Tốt hơn, Có một số API ít tài liệu hoạt động như try_realloc không?

LƯU Ý: Tôi rõ ràng là trong mã cụ thể của thư viện/nền tảng tại đây. Tôi không lo lắng vì try_realloc vốn đã là một tối ưu hóa.

---

Cập nhật: Sau Steve Jessops bình luận là về việc liệu vector sẽ hiệu quả hơn sử dụng realloc Tôi đã viết lên một bằng chứng của khái niệm để kiểm tra. Các realloc-vector mô phỏng mô hình tăng trưởng của một vector nhưng có tùy chọn để realloc thay thế. Tôi chạy chương trình lên đến một triệu phần tử trong vectơ.

Để so sánh, vector phải cấp phát 19 lần trong khi phát triển thành một triệu phần tử.

Kết quả, nếu realloc-vector là điều duy nhất sử dụng đống kết quả là tuyệt vời, phân bổ 3-4 trong khi phát triển đến kích thước triệu byte.

Nếu realloc-vector được sử dụng cùng với vector tăng trưởng ở tốc độ 66% tốc độ realloc-vector Kết quả kém hứa hẹn, phân bổ 8-10 lần trong quá trình tăng trưởng.

Cuối cùng, nếu realloc-vector được sử dụng cùng với số vector tăng cùng tốc độ, số realloc-vector sẽ phân bổ 17-18 lần. Chỉ tiết kiệm một phân bổ cho hành vi vectơ chuẩn.

Tôi không nghi ngờ rằng một hacker có thể phân bổ kích thước trò chơi để cải thiện khoản tiết kiệm, nhưng tôi đồng ý với Steve rằng nỗ lực to lớn để viết và duy trì người cấp phát đó không hoạt động.

Answer 1

vector thường tăng theo mức tăng lớn. Bạn không thể làm điều đó nhiều lần mà không phải di chuyển, trừ khi bạn sắp xếp cẩn thận mọi thứ để có một lượng lớn các địa chỉ miễn phí ngay trên bộ đệm bên trong của vectơ (có hiệu lực đòi hỏi phải gán toàn bộ các trang), vì rõ ràng bạn không thể có các phân bổ khác sau đó trên cùng một trang). Vì vậy, tôi nghĩ rằng để có được một tối ưu hóa thực sự tốt ở đây, bạn cần nhiều hơn một "cách giải quyết tầm thường" mà có thể tái phân bổ giá rẻ nếu có thể - bạn phải bằng cách nào đó để chuẩn bị cho làm cho có thể, và chi phí chuẩn bị đó bạn giải quyết không gian. Nếu bạn chỉ làm điều đó cho một số vectơ, những cái mà cho biết chúng sẽ trở nên lớn, thì nó khá vô nghĩa, bởi vì chúng có thể chỉ ra với reserve() rằng chúng sẽ trở nên lớn. Bạn chỉ có thể làm điều đó tự động cho tất cả các vectơ nếu bạn có một không gian địa chỉ rộng lớn, để bạn có thể "lãng phí" một phần lớn của nó trên mỗi vectơ.

Như tôi đã hiểu, lý do khái niệm Allocator không có chức năng phân bổ lại là giữ cho nó đơn giản. Nếu std::allocator có chức năng try_realloc, thì mỗi Allocator sẽ phải có một (mà trong hầu hết các trường hợp không thể được triển khai và sẽ chỉ trả về false), hoặc bất kỳ vùng chứa tiêu chuẩn nào sẽ phải chuyên biệt cho std::allocator tận dụng lợi thế của nó. Không có lựa chọn nào là một giao diện Allocator tuyệt vời, mặc dù tôi cho rằng nó sẽ không phải là một nỗ lực lớn đối với những người thực hiện hầu hết tất cả các lớp Allocator chỉ để thêm một hàm không có gì là try_realloc.

Nếu vector chậm do phân bổ lại, deque có thể là một sự thay thế tốt.

Answer 2

Bạn có thể thực hiện một cái gì đó giống như try_realloc bạn đề xuất, sử dụng mmap với MAP_ANONYMOUS và MAP_FIXED và mremap với MREMAP_FIXED.

Sửa: chỉ cần nhận thấy rằng các trang người đàn ông cho mremap thậm chí nói:

mremap() sử dụng bảng trang chương trình Linux. mremap() thay đổi ánh xạ giữa địa chỉ ảo và trang bộ nhớ. Điều này có thể được sử dụng để triển khai hiệu quả realloc (3).

Answer 3

realloc trong C khó có nhiều hơn chức năng tiện lợi; nó có rất ít lợi ích cho hiệu suất/giảm bản sao. Ngoại lệ chính mà tôi có thể nghĩ đến là mã phân bổ mảng lớn sau đó giảm kích thước khi kích thước cần biết - nhưng ngay cả điều này có thể yêu cầu di chuyển dữ liệu trên một số triển khai malloc (những thứ tách biệt khối theo kích thước). của realloc thực hành không tốt.

Miễn là bạn không liên tục tái phân bổ mảng của mình mỗi khi bạn thêm phần tử, nhưng thay vì tăng mảng theo cấp số nhân (ví dụ: 25%, 50% hoặc 100%) bất cứ khi nào bạn hết dung lượng, chỉ cần theo cách thủ công cấp phát bộ nhớ mới, sao chép và giải phóng bộ nhớ cũ sẽ mang lại hiệu năng giống nhau (và giống hệt nhau, trong trường hợp phân mảnh bộ nhớ) để sử dụng realloc. Đây chắc chắn là cách tiếp cận mà C++ STL triển khai sử dụng, vì vậy tôi nghĩ rằng toàn bộ mối quan tâm của bạn là vô căn cứ.

Sửa: Người (hiếm nhưng không phải là chưa từng có) Trường hợp realloc là thực sự hữu ích là cho các khối khổng lồ trên các hệ thống với bộ nhớ ảo, nơi mà các thư viện C tương tác với hạt nhân chuyển nơi ở toàn bộ trang đến địa chỉ mới.Lý do tôi nói điều này hiếm khi là vì bạn cần phải xử lý các khối rất lớn (ít nhất vài trăm kB) trước khi hầu hết các triển khai thậm chí sẽ đi vào lĩnh vực xử lý phân bổ trang chi tiết và có thể lớn hơn nhiều (vài MB có thể) trước khi vào và thoát khỏi kernelspace để sắp xếp lại bộ nhớ ảo thì rẻ hơn là làm bản sao. Tất nhiên try_realloc sẽ không hữu ích ở đây, vì toàn bộ lợi ích đến từ thực tế làm việc di chuyển không tốn kém.