Heap được tối ưu hóa cho (nhưng không giới hạn) sử dụng đơn luồng

Question

Tôi sử dụng triển khai heap tùy chỉnh trong một trong các dự án của tôi. Nó bao gồm hai phần chính:

1. Cố định khối khối kích thước. I E. một đống phân bổ các khối của một kích thước cụ thể mà thôi. Nó phân bổ các khối bộ nhớ lớn hơn (các trang bộ nhớ ảo hoặc từ một vùng nhớ khác), và sau đó chia chúng thành các đơn vị phân bổ nguyên tử.

   Nó thực hiện phân bổ/giải phóng nhanh (trong O (1)) và không có phí sử dụng bộ nhớ, không tính đến những điều được áp đặt bởi vùng bên ngoài.

2. Heap mục đích chung toàn cầu. Nó bao gồm các thùng của đống (kích thước cố định) ở trên. WRT kích thước phân bổ được yêu cầu, nó chọn nhóm thích hợp và thực hiện phân bổ thông qua nó.

   Vì toàn bộ ứng dụng là (nhiều) đa luồng - heap toàn cầu khóa xô thích hợp trong khi hoạt động.

   Lưu ý: trái ngược với heaps truyền thống, vùng này yêu cầu kích thước phân bổ không chỉ cho phân bổ mà còn cho giải phóng. Điều này cho phép xác định nhóm thích hợp mà không cần tìm kiếm hoặc chi phí bộ nhớ thừa (chẳng hạn như lưu kích thước khối trước khối được phân bổ). Mặc dù hơi kém thuận tiện, điều này là ok trong trường hợp của tôi. Hơn nữa, vì "cấu hình thùng" được biết tại thời gian biên dịch (được thực hiện thông qua mẫu voodoo C++) - nhóm thích hợp được xác định tại thời gian biên dịch.

Cho đến nay mọi thứ đều trông (và hoạt động) tốt.

Gần đây tôi đã làm việc trên một thuật toán thực hiện các hoạt động heap rất nhiều, và tự nhiên bị ảnh hưởng đáng kể bởi hiệu suất heap. Profiling tiết lộ rằng hiệu suất của nó bị ảnh hưởng đáng kể bởi khóa. Nghĩa là, vùng heap hoạt động rất nhanh (phân bổ điển hình chỉ bao gồm một vài hướng dẫn dereferencing), nhưng vì toàn bộ ứng dụng là đa luồng - nhóm thích hợp được bảo vệ bởi phần quan trọng, dựa trên các hướng dẫn liên khóa nặng hơn nhiều.

Tôi đã sửa lỗi này bằng cách đưa thuật toán này vào vùng chuyên dụng của riêng nó, không được bảo vệ bởi một phần quan trọng. Nhưng điều này áp đặt một số vấn đề/hạn chế ở cấp mã. Chẳng hạn như nhu cầu truyền thông tin ngữ cảnh sâu trong ngăn xếp bất cứ nơi nào có thể cần đến heap. Người ta cũng có thể sử dụng TLS để tránh điều này, nhưng điều này có thể gây ra một số vấn đề với việc tái nhập cảnh trong trường hợp cụ thể của tôi.

Điều này làm tôi băn khoăn: Có kỹ thuật nào được biết để tối ưu hóa heap cho (nhưng không giới hạn) sử dụng một luồng không?

EDIT:

Đặc biệt cảm ơn @Voo cho thấy kiểm tra ra tcmalloc của google.

Dường như nó hoạt động tương tự như những gì tôi đã làm nhiều hơn hoặc ít hơn (ít nhất là đối với các đối tượng nhỏ). Nhưng ngoài ra họ giải quyết vấn đề chính xác tôi có, bằng cách duy trì mỗi thread bộ nhớ đệm.

Tôi cũng nghĩ theo hướng này, nhưng tôi đã nghĩ đến việc duy trì mỗi thread heaps. Sau đó giải phóng một khối bộ nhớ được cấp phát từ heap thuộc một thread khác có phần phức tạp: người ta nên chèn nó vào một hàng đợi bị khóa, và thread khác cần được thông báo, và giải phóng phân bổ đang chờ một cách không đồng bộ. Khẳng định không đồng bộ có thể gây ra vấn đề: nếu luồng đó bận vì lý do nào đó (ví dụ thực hiện một phép tính tích cực) - không có sự sắp xếp bộ nhớ thực sự xảy ra. Cộng với kịch bản đa luồng, chi phí của deallocation cao hơn đáng kể.

OTOH ý tưởng với bộ nhớ đệm có vẻ đơn giản hơn nhiều và hiệu quả hơn. Tôi sẽ cố gắng giải quyết nó.

Cảm ơn rất nhiều.

P.S .:

Thật vậy tcmalloc google là tuyệt vời. Tôi tin rằng nó được thực hiện khá giống với những gì tôi đã làm (ít nhất là kích thước cố định một phần).

Tuy nhiên, để trở thành thực tế, có một vấn đề mà vùng heap của tôi vượt trội. Theo tài liệu, tcmalloc áp đặt một chi phí khoảng 1% (tiệm cận), trong khi chi phí của tôi là 0,0061%. Đó là 4/64K chính xác.

:)

Answer 1

Một ý nghĩ là duy trì cấp phát bộ nhớ cho mỗi luồng. Đặt trước các khối bộ nhớ khá chunky cho mỗi bộ cấp phát từ một bộ nhớ toàn cục. Thiết kế thuật toán của bạn để gán các khối chunky từ các địa chỉ bộ nhớ liền kề (nhiều hơn về sau).

Khi trình cấp phát cho một chuỗi đã cho ở mức thấp trên bộ nhớ, nó yêu cầu nhiều bộ nhớ hơn từ nhóm bộ nhớ chung. Hoạt động này yêu cầu khóa, nhưng sẽ xảy ra ít thường xuyên hơn trong trường hợp hiện tại của bạn. Khi bộ cấp phát cho một luồng đã cho giải phóng nó là byte cuối cùng, trả về tất cả bộ nhớ cho bộ cấp phát đó cho nhóm bộ nhớ toàn cục (giả sử luồng được kết thúc).

Cách tiếp cận này sẽ có xu hướng thoát bộ nhớ sớm hơn cách tiếp cận hiện tại của bạn (bộ nhớ có thể được dành riêng cho một chuỗi không bao giờ cần đến). Mức độ mà đó là một vấn đề phụ thuộc vào hồ sơ tạo/đời/hủy hồ sơ của ứng dụng của bạn (s). Bạn có thể giảm thiểu điều đó với chi phí phức tạp hơn, ví dụ: bằng cách giới thiệu một tín hiệu cho thấy một bộ cấp phát bộ nhớ cho luồng đã cho hết bộ nhớ, và toàn bộ pool được loại bỏ, các bộ cấp phát bộ nhớ khác có thể trả lời bằng cách giải phóng bộ nhớ.

Lợi thế của lược đồ này là nó sẽ có xu hướng loại bỏ false sharing, vì bộ nhớ cho một chuỗi nhất định sẽ có xu hướng được phân bổ trong không gian địa chỉ liền kề.

Lưu ý phụ, nếu bạn chưa đọc, tôi đề xuất IBM's Inside Memory Management bài viết cho bất kỳ ai đang triển khai quản lý bộ nhớ của riêng họ.

CẬP NHẬT

Nếu mục tiêu là phải có phân bổ bộ nhớ rất nhanh tối ưu hóa cho môi trường đa luồng (như trái ngược với việc học làm thế nào để làm điều đó cho mình), có một cái nhìn tại allocators bộ nhớ thay thế. Nếu mục tiêu là học tập, có lẽ hãy kiểm tra mã nguồn của họ.

• Hoarde
• tcmalloc (nhờ Voo)

Answer 2

Nó có thể là một ý tưởng tốt để đọc Jeff Bonwicks giấy tờ kinh điển trên bộ cấp phát tấm và vmem. Bản phân phối bản gốc ban đầu âm thanh phần nào những gì bạn đang làm. Mặc dù không phải là rất đa luồng thân thiện nó có thể cung cấp cho bạn một số ý tưởng.

The Slab Allocator: An Object-Caching Kernel Memory Allocator

Sau đó, ông đã mở rộng khái niệm với VMEM, mà chắc chắn sẽ cung cấp cho bạn một số ý tưởng vì nó có hành vi rất đẹp trong một môi trường đa cpu.

Magazines and Vmem: Extending the Slab Allocator to Many CPUs and Arbitrary Resources