Tại sao gói này thực thi gói AVL thành con trỏ trong triển khai 64 bit nhưng không phải 32 bit?

Question

Trong this AVL tree implementation from Solaris, struct avl_node được định nghĩa theo cách rõ ràng nếu biên dịch cho thư viện 32 bit.

Nhưng đối với thư viện 64 con trỏ đến nút của cha mẹ được đóng gói thành "avl_pcb". Và có vẻ như chỉ có 61 bit của một nhà thơ được lưu trữ.

1. Tại sao tính năng này hoạt động?
2. Tại sao không thực hiện điều tương tự cho 32-bit?

Answer 1

Trên máy 64 bit, con trỏ thường được căn chỉnh ở các ranh giới từ, ở bội số của tám byte. Kết quả là, ba bit thấp nhất của một con trỏ sẽ bằng không. Do đó, nếu một cấu trúc dữ liệu cần ba bit thông tin, nó có thể đóng gói chúng vào ba bit thấp nhất của một con trỏ. Bằng cách đó:

• Để theo dõi con trỏ, hãy xóa ba bit thấp nhất của giá trị con trỏ, sau đó bỏ qua nó.
• Để đọc một trong ba bit, hãy che dấu phần còn lại của các bit trong con trỏ và đọc chúng trực tiếp.

Cách tiếp cận này khá chuẩn và không mất bất kỳ khả năng trỏ đến địa chỉ nào, vì thường vì lý do hiệu suất hoặc phần cứng bạn sẽ không muốn có con trỏ không được căn chỉnh. Tôi không chắc chắn về lý do tại sao họ không làm điều này trong trường hợp 32-bit, vì với ba con trỏ họ có thể dễ dàng ẩn các bit cần thiết bằng cách sử dụng cùng một thủ thuật nhưng với hai bit cho mỗi con trỏ. Tôi đoán rằng đó là một điều thực hiện: nếu bạn làm bit gói vào dưới cùng của con trỏ, bạn tăng chi phí sau con trỏ vì tính toán cần thiết để xóa các bit. Lưu ý, ví dụ, trong trường hợp 64-bit, các bit được đóng gói vào con trỏ cha, chỉ được sử dụng cho các hoạt động không phổ biến như tính toán những người kế thừa sắp xếp hoặc thực hiện phép quay trên chèn hoặc xóa. Điều này giúp tra cứu nhanh chóng. Trong trường hợp 32 bit, để ẩn 3 bit, việc thực hiện sẽ cần phải sử dụng các bit thấp hơn của hai con trỏ, một trong số đó sẽ phải là con trỏ trái hoặc phải. Tôi đoán là hiệu suất của việc tìm kiếm cây chậm lại không đáng để tiết kiệm không gian, vì vậy họ quyết định chỉ lấy bộ nhớ và lưu trữ chúng một cách riêng biệt. Đây chỉ là suy đoán, mặc dù, vì họ hoàn toàn có thể đã lưu trữ các bit trong đáy của con trỏ của họ nếu họ muốn.

Lưu ý: nếu triển khai sử dụng cây đỏ/đen thay vì cây AVL, thì chỉ cần hai bit thông tin: một chút để biết nút đó có màu đỏ hay đen và một chút để biết liệu nút có phải là con trái hoặc phải không. Trong trường hợp đó, hai bit cần thiết luôn có thể được đóng gói vào một con trỏ 32 bit. Đây là một trong những lý do tại sao cây đỏ đen là phổ biến.

Hy vọng điều này sẽ hữu ích!