Điều gì làm cho một lược đồ dựa trên heap chậm hơn một lược đồ dựa trên stack?

Question

Tôi đang phát triển một trình biên dịch cho một ngôn ngữ tương tự như Đề án, và đang đọc qua luận án của Dybvig. Trong đó, ông nói rằng đạt được hầu hết hiệu suất của mình đạt được bằng cách phân bổ các khung gọi trên stack thay vì trên đống. Có một số thủ thuật cần phải được thực hiện để thực sự làm cho công việc này trong sự hiện diện của đóng cửa và tiếp tục.

Câu hỏi của tôi là hiệu suất này đến từ đâu? Nó hoàn toàn là vì chúng tôi đặt ít căng thẳng vào bộ thu gom rác?

Đặt một cách khác: Giả sử chúng tôi có số lượng bộ nhớ vô hạn, các khung cuộc gọi được phân bổ sẽ vẫn nhanh hơn khung cuộc gọi được phân bổ heap?

Answer 1

Tôi nghĩ Eli đã trả lời câu hỏi của bạn, vì vậy tôi sẽ dán nhận xét của anh ấy ở đây và nhận tín dụng cho nó :).

Eli Barzilay viết:

(a) đối phó với đống mất nhiều thời gian hơn vì nó đòi hỏi phải quét nó (nó không tuyến tính như stack); (b) thực tế tất cả các kiến ​​trúc cpu đặt trọng tâm hơn vào việc truy cập stack càng nhanh càng tốt, và không phải như vậy với heap.

Để làm điều này, tôi sẽ thêm chung vẫy tay về vị trí bộ nhớ cache. Đó là, một ngăn xếp giữ tất cả các hành động trong một phần rất nhỏ của bộ nhớ, mà hầu như chắc chắn sẽ ở lại trong bộ nhớ cache.

Answer 2

Appel đã viết số paper tuyên bố rằng phân bổ đống có thể nhanh hơn phân bổ ngăn xếp. Về mặt toán học, nó là chính xác, nhưng anh ta bỏ qua cách các bộ vi xử lý hiện đại được điều chỉnh để chạy mã có sử dụng ngăn xếp (vùng nhớ đệm, hướng dẫn ngăn xếp hiệu quả, v.v.) và truy cập heap có nhiều indirections (xấu trong CPU hiện đại).