chu kỳ CPU malloc

Question

Chi phí của malloc(), xét về chu kỳ CPU? (Vista/OS, phiên bản mới nhất của gcc, mức tối ưu hóa cao nhất, ...)

Về cơ bản, tôi đang triển khai cấu trúc DAG phức tạp (tương tự như danh sách được liên kết) bao gồm một số 16B (ít phổ biến hơn) 20B nút (phổ biến hơn).

Thỉnh thoảng, tôi sẽ phải xóa một số nút và sau đó thêm một số nút. Nhưng, thay vì luôn sử dụng malloc() và free(), tôi có thể chỉ cần di chuyển các nút không cần thiết đến cuối cấu trúc dữ liệu của mình, sau đó cập nhật các trường khi thuật toán của tôi tiếp tục. Nếu một nút miễn phí có sẵn, tôi sẽ cập nhật các trường; nếu không, tôi sẽ phải phân bổ một cái mới.

Vấn đề là, tôi có thể chỉ có một nút miễn phí có sẵn trong khi có để nhập, ví dụ, 20 nút giá trị của dữ liệu. Điều này có nghĩa:

• tôi sẽ kiểm tra đối với một nút miễn phí có sẵn
• Vui lòng cung sẽ thành công, và rằng nút miễn phí sẽ được cập nhật
• tôi sẽ kiểm tra đối với một nút có sẵn 19 lần trở lên
• Tất cả các kiểm tra sẽ không thành công và malloc() sẽ được gọi mỗi lần

Câu hỏi: Có thực sự đáng giá không? Tôi có nên chỉ malloc() và miễn phí() như bình thường, hoặc là nó có giá trị nó để giữ một số nút miễn phí có sẵn ở cuối danh sách, và tiếp tục kiểm tra ngay cả khi nó thường sẽ thất bại và dẫn đến malloc() anyway?

Cụ thể hơn,

chi phí CPU của malloc là gì() ??

Answer 1

Điều đó có quan trọng không? Có thật không?

Câu trả lời đúng là "nó phụ thuộc".

Nó phụ thuộc vào vô số điều

• gì khác hệ điều hành đang làm lúc
• Làm thế nào phân mảnh bộ nhớ đã trở thành
• tốc độ của bộ nhớ và bộ xử lý trên máy tính client
• vv

Nếu mã này có hiệu suất ồ ạt quan trọng, chúng thời gian mọi thứ bạn có thể và làm việc ra các mô hình tốt nhất cho trường hợp sử dụng của bạn.

Nếu nó không phải là bit quan trọng nhất về hiệu suất, chỉ cần làm bất cứ điều gì là rõ ràng và đơn giản nhất để triển khai và duy trì.

"Chúng ta nên quên đi hiệu quả nhỏ, nói rằng khoảng 97% thời gian: sớm tối ưu hóa là gốc rễ của mọi tội lỗi", Donald Knuth

Answer 2

Là nó thực sự giá trị nó?

Bạn sẽ phải đo lường để biết, thời gian.

Answer 3

Ngoài những gì @rikh được đánh dấu, nếu bạn muốn cấp phát bộ nhớ cực nhanh, một kỹ thuật là phân bổ trước các khối có kích thước bạn cần (nhiều trong số chúng).

Tôi đã viết các trình quản lý bộ nhớ tùy chỉnh có danh sách các khối có kích thước khác nhau được phân bổ trước.

Ngoài ra, bạn cũng có thể kết hợp lược đồ kiểm tra giới hạn bộ nhớ vào các khối bạn đang quản lý.

Answer 4

malloc() không có chi phí cố định về độ trễ vì nhiều trạng thái có thể mà trình quản lý bộ nhớ phải xử lý để đáp ứng yêu cầu của bạn.

Vì kích thước nút của bạn tương đối nhỏ, bạn nên xem xét việc phân bổ một số kích thước lớn hơn, có thể từ 10 kích thước nút trở lên cho mỗi phân bổ và thêm các nút bổ sung vào hồ bơi không sử dụng của bạn. Bằng cách đó bạn sẽ phải phân bổ không chắc chắn ít thường xuyên hơn. Nhưng quan trọng hơn, bạn sẽ giảm số lượng phân mảnh bộ nhớ gây ra bởi quá nhiều phân bổ nhỏ.

Ngẫu nhiên, tôi không xem xét loại thiết kế này là "Tối ưu hóa sớm" vì bạn không tìm kiếm lý do để tiêm các đặc điểm thiết kế không thích hợp mà không có lý do chính đáng. Các cấu trúc dữ liệu có thể phát triển đến kích thước tùy ý và tồn tại trong khoảng thời gian tùy ý cần một chút suy đoán trước.

Đặc biệt vì cấu trúc dữ liệu có xu hướng tìm cách sử dụng tập quán ngoài kế hoạch và thường bởi các nhà phát triển khác, điều quan trọng là phải cân bằng hợp lý về mặt rõ ràng và hành vi dự đoán.

Viết cấu trúc của bạn phù hợp với các chức năng phân bổ và deallocation của riêng bạn. Thực hiện riêng những điều đó. Ban đầu, họ chỉ cần malloc và miễn phí một nút duy nhất để thực hiện gỡ lỗi dễ dàng hơn. Sau đó bạn có thể thiết kế lại chúng với các thuật toán fancier như nhu cầu của bạn ra lệnh.

Answer 5

Cần tìm hiểu xem khối phân bổ tối thiểu nào có trong hệ điều hành đích của bạn. Bạn có thể tốt hơn off malloc() ing trong 4K khối và sử dụng đó như hồ bơi không sử dụng của bạn.

Answer 6

Bạn có thể muốn xem xét các trình phân bổ gộp; AT & T's vmalloc gói cung cấp phân bổ gộp cho ví dụ.

Answer 7

Bất kỳ lời khuyên nào ở trên khuyến khích bạn thử một số kỹ thuật cụ thể là sai. Lời khuyên trên cho bạn biết để tránh tối ưu hóa sớm (một nguyên tắc rất quan trọng thực sự), là đúng.

Bạn đã cho chúng tôi một câu hỏi vô nghĩa. CPU gì? Nhanh quá? Kiến trúc gì? Malloc là hàm C. Những gì thực hiện các thói quen heap tiêu chuẩn là bạn nói về? Một trong Microsoft Visual C/C++? Một trong đó đi kèm với thư viện chuẩn GNU (stdlibc) trên Linux/Unix/Posix?

Bạn chưa đo hiệu suất của mình và sau đó cho chúng tôi biết hiệu suất đang tải là gì, bạn không cho chúng tôi biết bạn đã viết các bài kiểm tra đơn vị để kiểm tra tải.Bạn đang làm thiết kế ban đầu của bạn và "suy nghĩ của bạn về bao nhiêu chu kỳ" cùng một lúc? Bởi vì đó chỉ là ngớ ngẩn.

Answer 8

Heaps, đặc biệt đối với phân bổ bộ nhớ nhỏ, thường được cấu trúc dưới dạng danh sách được liên kết, trong đó mỗi ô heap trỏ tới bước tiếp theo. Khi phân bổ bộ nhớ, người cấp phát sẽ đi bộ đống cho đến khi nó tìm thấy một ô đủ lớn cho phân bổ được yêu cầu. Khi bộ nhớ của bạn trở nên bị phân mảnh hơn, bạn sẽ phải đi bộ một số lượng lớn hơn và lớn hơn của các tế bào. Mặc dù một lượng lớn công việc đã được thực hiện để giảm thiểu thời gian phân bổ, tốt nhất là tránh mọi vấn đề cùng nhau.

Cũng có thể là một ý tưởng tốt để phân bổ một khối lớn và phân chia số này giữa một số mục danh sách. điều này có thể có nghĩa là bạn có ít bộ đệm ẩn hơn khi đi bộ danh sách được liên kết của bạn.

Vì lý do này, tôi sẽ tránh việc sử dụng tần số cao của malloc và miễn phí và thêm sự phức tạp thêm của một người tự do.

Answer 9

Nếu bộ nhớ không bao giờ được giải phóng, malloc() sẽ có xu hướng chạy khá nhanh. Nếu nhiều khối bộ nhớ được sử dụng và giải phóng, malloc() có thể trở nên khá chậm. Các thông tin cụ thể về tốc độ hoặc tốc độ chậm sẽ được áp dụng cho bất kỳ hình thức sử dụng cụ thể nào phụ thuộc mạnh mẽ vào việc triển khai và đôi khi chỉ hơi kém mạnh mẽ hơn trong giai đoạn của mặt trăng.

Trong một số trường hợp, đặc biệt là với các hệ thống nhúng, việc sử dụng bộ nhớ sẽ tuân thủ nghiêm ngặt mẫu LIFO. Trong trường hợp đó, có thể hữu ích khi chỉ cần lấy tất cả bộ nhớ có thể muốn sử dụng (trên các hệ thống nhúng này thường có thể được thực hiện tại thời gian liên kết) và giữ một con trỏ đến đầu khu vực đó và phần cuối của không gian được phân bổ (mà ban đầu là sự bắt đầu của khu vực). Để cấp phát các byte 'n', chỉ cần sao chép con trỏ không gian cuối được phân bổ, thêm 'n' vào bản gốc và trả về giá trị đã sao chép. Để giải phóng một đoạn và tất cả mọi thứ được phân bổ sau nó, sao chép địa chỉ của đoạn này vào con trỏ không gian được cấp phát cuối cùng.

Lưu ý rằng phương pháp này có tổng chi phí trên không cho mỗi khối và cả phân bổ và deallocation đều rất rẻ. Giới hạn LIFO có thể là một vấn đề, nhưng nếu hầu hết việc sử dụng là LIFO và một cách rõ ràng biết mọi thứ cần phải tồn tại sau khi "quét", người ta có thể di chuyển mọi thứ cần được giữ sau khi "quét" bắt đầu không gian được phân bổ và đặt con trỏ sau các công cụ được di chuyển.

Answer 10

Yêu cầu chi phí cho một đơn malloc là câu hỏi sai.

yếu tố suy giảm hiệu suất thông thường là:

• Kích thước làm việc thiết lập (bao nhiêu byte bạn đang "cảm động" trong ví dụ một giây)
• phân mảnh bộ nhớ (bao lâu malloc để tìm một phù hợp và khối lượng này sẽ làm tăng kích thước thiết lập làm việc này bao nhiêu)

Từ kinh nghiệm của tôi, khi bạn phải mong đợi nhiều nút có kích thước đó (> ~ 100K ... Hàng triệu), những điều này không quan trọng.

Tùy chỉnh Allocator
Tất nhiên, nếu bạn có thể điều chỉnh thuật toán để sử dụng ít bộ nhớ hơn hoặc ít nút hơn thì hãy làm như vậy. Tuy nhiên, thay vì để cho mối quan tâm chi phí phân bổ bị rò rỉ vào giải pháp của bạn, cô lập nó trong một phân bổ tùy chỉnh.

Lựa chọn đơn giản nhất là quá tải mới cho lớp học của bạn, điều này có nghĩa là mã giải pháp của bạn không bị ảnh hưởng.

Trình phân bổ phụ thuộc một chút vào nhu cầu của thuật toán.Để thường xuyên phân bổ và giải phóng các khối có kích thước giống nhau, một fixed-size pool là sự lựa chọn kinh điển.

An arena allocator có thể hoạt động tốt hơn nếu bạn có nhiều phân bổ và rất ít lần xóa (tức là bạn không đủ khả năng không phát hành bộ nhớ đã giải phóng).

Tuy nhiên, yếu tố quyết định giữa hai thường là địa phương tham chiếu. Nếu có bất cứ điều gì bạn có thể làm để thúc đẩy điều đó, bạn có thể giành được nhiều thời gian.