Làm cách nào để tránh phân mảnh heap?

Question

Tôi hiện đang làm việc trên một dự án xử lý hình ảnh y tế, cần một lượng bộ nhớ lớn. Có điều gì tôi có thể làm để tránh phân mảnh đống và tăng tốc độ truy cập dữ liệu hình ảnh đã được tải vào bộ nhớ không?

Ứng dụng đã được viết bằng C++ và chạy trên Windows XP.

EDIT: Ứng dụng thực hiện một số tiền xử lý với dữ liệu hình ảnh, như định dạng lại, tính toán bảng tra cứu, trích xuất hình ảnh phụ cần quan tâm ... Ứng dụng cần khoảng 2 GB RAM trong quá trình xử lý, trong đó khoảng 1 , 5 GB có thể được sử dụng cho dữ liệu hình ảnh.

Answer 1

Nếu bạn đang xử lý ảnh y tế, có khả năng bạn đang phân bổ các khối lớn cùng một lúc (hình ảnh 512x512, 2 byte cho mỗi pixel). Phân mảnh sẽ cắn bạn nếu bạn phân bổ các đối tượng nhỏ hơn giữa phân bổ bộ đệm hình ảnh.

Viết trình phân bổ tùy chỉnh không nhất thiết phải khó cho trường hợp sử dụng cụ thể này. Bạn có thể sử dụng trình cấp phát C++ chuẩn cho đối tượng Hình ảnh của bạn, nhưng đối với bộ đệm pixel, bạn có thể sử dụng phân bổ tùy chỉnh được quản lý trong đối tượng Hình ảnh của bạn.Dưới đây là một phác thảo nhanh chóng và dơ bẩn:

• Sử dụng một mảng tĩnh của cấu trúc, mỗi struct có:
  • Một đoạn vững chắc của bộ nhớ có thể chứa hình ảnh N - các chunking sẽ giúp phân mảnh kiểm soát - thử một N ban đầu là 5 hoặc lâu hơn
  • một mảng song song của bools nêu rõ các hình ảnh tương ứng được sử dụng
• bố trí, tìm kiếm trên mảng cho một bộ đệm rỗng và thiết lập cờ của nó
  • Nếu không tìm thấy, thêm một cấu trúc mới đến hết mảng
• Để deallocate, tìm đệm tương ứng trong mảng (s) và rõ ràng cờ boolean

Đây là chỉ là một ý tưởng đơn giản với nhiều chỗ cho sự thay đổi. Bí quyết chính là tránh giải phóng và phân bổ lại bộ đệm pixel hình ảnh.

Answer 2

Nếu không có thêm thông tin về vấn đề (ví dụ ngôn ngữ), một điều bạn có thể làm là tránh phân bổ bằng cách sử dụng lại phân bổ và không phân bổ, vận hành và miễn phí. Allocator như dlmalloc xử lý phân mảnh tốt hơn so với Win32 heaps.

Answer 3

Đoán ở đây bạn có nghĩa là tránh phân mảnh và không tránh chống phân mảnh. Cũng đoán rằng bạn đang làm việc với một ngôn ngữ không được quản lý (c hoặc C++ có lẽ). Tôi sẽ đề nghị bạn phân bổ khối lượng lớn bộ nhớ và sau đó phân phát cấp phát heap từ các khối bộ nhớ được cấp phát. Nhóm bộ nhớ này vì chứa các khối bộ nhớ lớn ít bị phân mảnh hơn. Tóm lại, bạn nên thực hiện một bộ cấp phát bộ nhớ tùy chỉnh.

Xem một số ý tưởng chung về điều này here.

Answer 4

Tôi cho rằng bạn đang sử dụng thứ gì đó không được quản lý, bởi vì trong các nền tảng được quản lý, hệ thống (bộ thu gom rác) sẽ xử lý sự phân mảnh.

Đối với C/C++, bạn có thể sử dụng một số cấp phát khác, so với mặc định. (đã có một số chủ đề về phân bổ trên stackowerflow).

Ngoài ra, bạn có thể tạo bộ nhớ dữ liệu của riêng mình. Ví dụ, trong dự án tôi đang làm việc, chúng ta có một kho lưu trữ tùy chỉnh (pool) cho bitmap (chúng ta lưu trữ chúng trong một bộ nhớ lớn), bởi vì chúng ta có rất nhiều, và chúng ta theo dõi đống phân mảnh và chống phân mảnh khi phân mảnh lớn.

Answer 5

Bạn có thể cần triển khai quản lý bộ nhớ thủ công. Dữ liệu hình ảnh có tồn tại lâu không? Nếu không, sau đó bạn có thể sử dụng mẫu được sử dụng bởi máy chủ web apache: phân bổ số lượng lớn bộ nhớ và bọc chúng vào bộ nhớ. Vượt qua các hồ bơi đó làm đối số cuối cùng trong các hàm, để chúng có thể sử dụng nhóm để đáp ứng nhu cầu cấp phát bộ nhớ tạm thời. Khi chuỗi cuộc gọi kết thúc, tất cả bộ nhớ trong hồ bơi có thể không còn được sử dụng nữa, vì vậy bạn có thể chà khu vực bộ nhớ và sử dụng lại. Phân bổ nhanh, vì chúng chỉ có nghĩa là thêm một giá trị cho một con trỏ. Deallocation thực sự nhanh chóng, vì bạn sẽ giải phóng các khối bộ nhớ rất lớn cùng một lúc.

Nếu ứng dụng của bạn đa luồng, bạn có thể cần lưu trữ hồ bơi trong bộ nhớ cục bộ luồng, để tránh chi phí liên lạc qua luồng.

Answer 6

Có câu trả lời, nhưng thật khó để nói chung mà không biết chi tiết của sự cố.

Tôi giả sử Windows XP 32 bit.

Cố gắng tránh 100s MB bộ nhớ tiếp giáp, nếu bạn không may mắn, một vài dll ngẫu nhiên sẽ tự tải tại các điểm bất tiện thông qua không gian địa chỉ sẵn có của bạn nhanh chóng cắt giảm các vùng rất lớn của bộ nhớ liền kề. Tùy thuộc vào API bạn cần, điều này có thể khá khó ngăn chặn. Nó có thể khá ngạc nhiên như thế nào chỉ phân bổ một vài khối bộ nhớ 400MB ngoài việc sử dụng bộ nhớ 'bình thường' có thể khiến bạn không có nơi nào để phân bổ một khối 'nhỏ' 40MB cuối cùng.

Mặt khác, hãy preallocate khối kích thước hợp lý tại một thời điểm. Của thứ tự 10MB hoặc hơn là một khối thỏa hiệp tốt. Nếu bạn có thể quản lý để phân vùng dữ liệu của bạn thành loại khối kích thước này, bạn sẽ có thể lấp đầy không gian địa chỉ một cách hợp lý một cách hiệu quả.

Nếu bạn vẫn sắp hết dung lượng địa chỉ, bạn sẽ cần phải có khả năng chặn trang trong và ngoài dựa trên một số loại thuật toán lưu vào bộ nhớ cache. Việc chọn đúng khối để trang ra sẽ phụ thuộc rất nhiều vào algortihm xử lý của bạn và sẽ cần phân tích cẩn thận.

Chọn vị trí trang cần thực hiện là một quyết định khác. Bạn có thể quyết định chỉ viết chúng vào các tệp tạm thời. Bạn cũng có thể điều tra API Extenstions Address Windowing của Microsoft. Trong cả hai trường hợp, bạn cần phải cẩn thận trong thiết kế ứng dụng của bạn để làm sạch bất kỳ con trỏ nào trỏ đến thứ gì đó sắp được phân trang ra nếu không thì những điều thực sự xấu (tm) sẽ xảy ra.

Chúc may mắn!

Answer 7

Nếu bạn định thực hiện các thao tác trên ma trận hình ảnh lớn, bạn có thể muốn xem xét kỹ thuật được gọi là "ốp lát". Ý tưởng nói chung là tải hình ảnh trong bộ nhớ sao cho cùng một khối byte kề nhau sẽ không chứa các pixel trong một dòng, nhưng thay vì một hình vuông trong không gian 2D. Lý do đằng sau điều này là bạn sẽ thực hiện nhiều thao tác gần nhau hơn trong 2D thay vì trên một dòng quét.

Điều này sẽ không làm giảm việc sử dụng bộ nhớ của bạn, nhưng có thể có tác động lớn đến việc hoán đổi và hiệu suất trang.

Answer 8

Điều bạn sẽ nhấn ở đây là giới hạn phạm vi địa chỉ ảo, với 32b Windows cung cấp cho bạn tối đa 2 GB. Bạn cũng nên biết rằng việc sử dụng một API đồ họa như DirectX hoặc OpenGL sẽ sử dụng các phần mở rộng của 2 GB đó cho bộ đệm khung, họa tiết và dữ liệu tương tự.

1,5-2 GB cho ứng dụng 32b khá khó đạt được. Cách thanh lịch nhất để làm điều này là sử dụng hệ điều hành 64b và ứng dụng 64b. Ngay cả với hệ điều hành 64b và ứng dụng 32b, điều này có thể có phần khả thi, miễn là bạn sử dụng LARGE_ADDRESS_AWARE.

Tuy nhiên, khi bạn cần lưu trữ dữ liệu hình ảnh, bạn cũng có thể thực hiện việc này bằng cách sử dụng File Mapping as a memory store - điều này có thể được thực hiện theo cách bạn có bộ nhớ được truy cập, nhưng không sử dụng bất kỳ địa chỉ ảo nào ở tất cả.

Answer 9

Nếu bạn có thể tách biệt chính xác những nơi bạn có khả năng phân bổ khối lớn, bạn có thể (trên Windows) gọi trực tiếp VirtualAlloc thay vì đi qua trình quản lý bộ nhớ. Điều này sẽ tránh sự phân mảnh trong trình quản lý bộ nhớ thông thường.

Đây là giải pháp dễ dàng và không yêu cầu bạn sử dụng trình quản lý bộ nhớ tùy chỉnh.