Có vấn đề gì với các GC đánh dấu và quét?

Question

Tôi đang đọc Steve Yegge's "Dynamic Languages Strike Back" nói chuyện, và trong đó ông sắp xếp chỉ trích đánh dấu và quét GC (khoảng 5-10 phần trăm thông qua liên kết đó, "Lợn cố gắng để bay" trượt) Có gì sai với họ?

Answer 1

Dưới đây là bối cảnh của đoạn trích:

người thu gom rác về thế hệ là câu trả lời tốt nhất mà tôi đã có cho rằng, vì nó làm giảm tạm dừng, và thẳng thắn, những người thu gom rác cho tất cả các Các ngôn ngữ động [mới] hiện nay là crap. Chúng được đánh dấu và quét hoặc chúng được tính tham chiếu.

Từ báo giá, anh ấy dường như đang nói về các GC nguyên thủy thô sơ không phải là thế hệ. GC sinh lực vẫn có thể được đánh dấu và quét, nhưng họ có ít hơn rất nhiều để đánh dấu hầu hết thời gian, mà làm cho họ nhanh hơn rất nhiều so với "đánh dấu và quét thế giới mọi lúc".

Giả sử đó là ý của anh ấy, tôi đồng ý - nhưng anh ấy có thể nói rõ hơn. Ghi nhớ rằng đây là một cuộc nói chuyện chứ không phải là một luận án tiến sĩ mặc dù - đến với cách rõ ràng nhất có thể thể hiện mình "trên móng" là kinda khó khăn :)

Answer 2

Anh ấy tương phản nó để mark-compact:

người thu gom rác về thế hệ được câu trả lời tốt nhất mà tôi đã có cho rằng, bởi vì nó làm giảm tạm dừng, và thẳng thắn, những người thu gom rác cho tất cả các [mới] ngôn ngữ động hôm nay là crap. Chúng được đánh dấu và quét, hoặc chúng được tính tham chiếu.

Đánh dấu đồng bằng & quét GC không tốt vì chúng có vấn đề về phân mảnh đống. Với các cấp phân bổ cao phổ biến của các ngôn ngữ hỗ trợ GC, điều này thường trở thành vấn đề nhanh hơn so với các ngôn ngữ khác, ví dụ: C++, nơi có rất nhiều đối tượng chỉ xuất hiện trên stack.

Điều đó nói rằng, đánh dấu nhỏ gọn thực sự là đánh dấu & quét với nén được giải quyết trên đó, vì vậy thuật ngữ có thể tốt hơn. Người thu gom không nén thường được gọi là "bảo thủ" để phân biệt chúng.

Answer 3

Đây là một điểm cao cấp so sánh điểm khác nhau kỹ thuật được đề cập trong báo giá tham chiếu (. plus "mark-and-compact" ... mà là một biến thể của mark-và-sweep)

các đặc tính của bộ sưu tập tính tham khảo là:

• PRO - rác được thu hồi ngay lập tức (ngoài chu kỳ)
• PRO - thu gom rác thải tạm dừng nhỏ hơn và tối thiểu nếu bạn có thể hoãn cập nhật cấu trúc dữ liệu "không gian trống".
• CON - đếm tài liệu tham khảo cần phải được điều chỉnh trên hầu hết các con trỏ ghi hoạt động
• CON - miễn phí không gian không bao giờ là đầm
• CON - bởi vì không gian trống không đầm, một "không gian trống" cấu trúc dữ liệu phải được duy trì làm tăng chi phí phân bổ và phân bổ.
• Rác thải chu kỳ không được thu thập, trừ khi ứng dụng phá vỡ chu kỳ bằng tay.
• CON - cập nhật số lượng tham chiếu trong ứng dụng đa luồng là tốn kém hơn.

Đối với cổ điển mark-and-quét:

• PRO - không có con trỏ ghi overhead
• PRO - dữ liệu theo chu kỳ được thu thập
• PRO - lưu trữ tắc nghẽn quản lý đồng thời có thể tránh được (ngoài GC)
• Bộ sưu tập thu gom rác thải thế giới
• Không gian tự do chưa bao giờ được đầm chặt
• CON - vì không gian trống không được nén chặt, nên phải duy trì cấu trúc dữ liệu "không gian trống" để tăng chi phí phân bổ và phân bổ.

Đánh dấu và quét cổ điển đôi khi được sửa đổi để pha quét ảnh hưởng đến không gian trống bởi các đối tượng không phải là "trượt". Điều này được gọi là "mark-sweep-compact". Điều này là khá phức tạp nhưng:

• PRO - không có con trỏ ghi overhead
• PRO - dữ liệu theo chu kỳ được thu thập
• PRO - lưu trữ tắc nghẽn quản lý đồng thời có thể dễ dàng tránh được (ngoài GC)
• CON - bộ sưu tập rác thải thế giới
• PRO - không gian trống được đầm chặt, vì vậy phân bổ là giá rẻ
• CON - pha nhỏ gọn khá đắt tiền

Người thu gom hiện đại (bao gồm cả những người sưu tầm thế hệ điển hình) dựa trên đánh dấu và sao chép. Ý tưởng là các nhà sưu tập dấu vết các đối tượng trong một "từ không gian" sao chép chúng vào một "không gian". Khi nó được thực hiện, "để không gian" có một đoạn liền kề không gian trống ở cuối có thể được sử dụng để phân bổ các đối tượng mới. Từ "không gian" cũ được đặt ở một bên cho lần thu gom rác tiếp theo chạy. Điều tốt đẹp về việc sao chép bộ sưu tập là chi phí thu gom rác liên kết với một đối tượng rác gần bằng không.

• CON - con trỏ ghi trên không (để ghi lại khi một "thế hệ mới" con trỏ được viết thành một đối tượng "thế hệ cũ")
• PRO - dữ liệu theo chu kỳ được thu thập
• PRO - lưu trữ tắc nghẽn quản lý đồng thời có thể có thể dễ dàng tránh được (ngoài GC)
• Thu gom rác tạm ngừng, mặc dù điều này có thể được giảm thiểu với chi phí của một số chi phí thời gian chạy theo số
• PRO - với bộ sưu tập thế hệ, bạn thường GC chỉ là một phần của đống với rất nhiều rác, và do đó chi phí đầu vào GC ít hơn trên avera ge
• PRO - tạm dừng GC nhỏ hơn (phần lớn thời gian)
• PRO - không gian trống là đầm, vì vậy phân bổ là rẻ
• PRO - nén chặt đến với giá rẻ hơn so với một compacter trượt
• CON - bạn cần để dự trữ thêm một không gian đối tượng cho người thu thập.

Một bộ sưu tập thế hệ là nơi có nhiều không gian (thế hệ), được thu thập ở các mức giá khác nhau. Điều này được dựa trên giả thuyết rằng hầu hết các đối tượng được tạo ra và sau đó trở thành không thể truy cập trong một khoảng thời gian ngắn. Vì vậy, bởi rác thu thập không gian chứa các đối tượng trẻ, bạn đòi lại một lượng không gian tương đối lớn với chi phí tương đối thấp. Bạn vẫn cần phải thu thập các thế hệ cũ, nhưng điều này có thể xảy ra ít thường xuyên hơn.

(Bộ sưu tập đánh dấu và quét có thể là thế hệ, nhưng việc trả tiền không lớn như đối với người thu thập bản sao.)