Tại sao một int trong OCaml chỉ 31 bit?

Question

Chưa thấy "tính năng" này ở bất kỳ nơi nào khác. Tôi biết rằng bit 32 được sử dụng để thu gom rác thải. Nhưng tại sao nó như vậy chỉ cho ints và không cho các loại cơ bản khác?

Answer 1

Đây được gọi là con trỏ được gắn nhãn và là một mẹo tối ưu hóa khá phổ biến được sử dụng trong nhiều trình thông dịch, máy ảo và hệ thống thời gian chạy khác nhau trong nhiều thập kỷ. Khá nhiều mọi triển khai Lisp đều sử dụng chúng, nhiều máy ảo Smalltalk, nhiều trình thông dịch Ruby, v.v.

Thông thường, trong các ngôn ngữ đó, bạn luôn chuyển các con trỏ đến các đối tượng. Một đối tượng bao gồm tiêu đề đối tượng, chứa siêu dữ liệu đối tượng (như kiểu đối tượng, lớp của nó, có thể truy cập các hạn chế kiểm soát hoặc chú thích bảo mật, vv) và sau đó là dữ liệu đối tượng thực. Vì vậy, một số nguyên đơn giản sẽ được biểu diễn như một con trỏ cộng với một đối tượng bao gồm siêu dữ liệu và số nguyên thực. Ngay cả với một đại diện rất nhỏ gọn, đó là một cái gì đó giống như 6 Byte cho một số nguyên đơn giản.

Ngoài ra, bạn không thể chuyển đối tượng số nguyên đó cho CPU để thực hiện số học số nguyên nhanh. Nếu bạn muốn thêm hai số nguyên, bạn thực sự chỉ có hai con trỏ, trỏ đến phần đầu của tiêu đề đối tượng của hai đối tượng số nguyên bạn muốn thêm. Vì vậy, trước tiên bạn cần phải thực hiện số học số nguyên trên con trỏ đầu tiên để thêm bù đắp vào đối tượng với nó nơi dữ liệu số nguyên được lưu trữ. Sau đó, bạn phải dereference địa chỉ đó. Làm tương tự với số nguyên thứ hai. Bây giờ bạn có hai số nguyên bạn thực sự có thể yêu cầu CPU thêm vào. Tất nhiên, bạn cần phải xây dựng một đối tượng số nguyên mới để giữ kết quả.

Vì vậy, để thực hiện một số nguyên Ngoài ra, bạn thực sự cần phải thực hiện ba bổ sung số nguyên cộng với hai dererefences con trỏ cộng với một xây dựng đối tượng. Và bạn chiếm gần 20 Byte.

Tuy nhiên, các trick là với cái gọi là kiểu giá trị bất biến như số nguyên, bạn thường làm không cần tất cả các siêu dữ liệu trong tiêu đề đối tượng: bạn chỉ có thể để lại tất cả những thứ ra ngoài, và chỉ đơn giản là tổng hợp nó (đó là VM-nerd-nói cho "giả mạo nó"), khi bất cứ ai quan tâm để xem xét. Số nguyên sẽ luôn là có lớp Integer, không cần phải lưu trữ riêng thông tin đó.Nếu ai đó sử dụng phản ánh để tìm ra lớp của số nguyên, bạn chỉ cần trả lời Integer và không ai biết rằng bạn đã không lưu trữ thông tin đó trong tiêu đề đối tượng và thực tế, có không phải là ngay cả tiêu đề đối tượng (hoặc một đối tượng).

Vì vậy, mẹo là lưu giá trị của đối tượng trong con trỏ đến đối tượng, có hiệu quả thu gọn hai thành một.

Có các CPU thực sự có không gian bổ sung trong một con trỏ (được gọi là bit thẻ) cho phép bạn lưu trữ thông tin bổ sung về con trỏ trong chính con trỏ. Thông tin bổ sung như "đây không thực sự là một con trỏ, đây là một số nguyên". Ví dụ bao gồm Burroughs B5000, các máy Lisp khác nhau hoặc AS/400. Thật không may, hầu hết các CPU chính thống hiện tại không có tính năng đó.

Tuy nhiên, có cách thoát ra: hầu hết các CPU chính thống hiện tại hoạt động chậm hơn đáng kể khi địa chỉ không được căn chỉnh trên các ranh giới từ. Một số thậm chí không hỗ trợ truy cập chưa được ký.

Điều này có nghĩa là trong thực tế, tất cả con trỏ sẽ chia hết cho 4, có nghĩa là họ sẽ luôn cuối với hai 0 bit. Điều này cho phép chúng tôi phân biệt giữa số thực con trỏ (kết thúc bằng số 00) và con trỏ thực sự là số nguyên trong ngụy trang (những kết thúc bằng 1). Và nó vẫn để lại cho chúng tôi tất cả các con trỏ kết thúc bằng số 10 miễn phí để thực hiện các công cụ khác. Ngoài ra, hầu hết các hệ điều hành hiện đại đều đặt trước các địa chỉ rất thấp, cho chúng ta một khu vực khác xung quanh (con trỏ bắt đầu bằng 24 0 s và kết thúc bằng 00).

Vì vậy, bạn có thể mã hóa số nguyên 31 bit thành con trỏ, chỉ cần dịch chuyển 1 bit sang bên trái và thêm 1 vào nó. Và bạn có thể thực hiện rất nhanh số học bằng số học, bằng cách đơn giản chuyển chúng một cách thích hợp (đôi khi thậm chí không cần thiết).

Chúng tôi làm gì với những không gian địa chỉ khác? Ví dụ điển hình bao gồm mã hóa float s trong không gian địa chỉ lớn khác và một số đối tượng đặc biệt như true, false, nil, 127 ký tự ASCII, một số chuỗi ngắn thường được sử dụng, danh sách trống, đối tượng trống, mảng trống và ở gần địa chỉ 0.

Ví dụ, trong những nhà chú giải MRI, YARV và Rubinius Ruby, số nguyên được mã hóa theo cách tôi mô tả ở trên, false được mã hóa dưới dạng địa chỉ 0 (mà chỉ như vậy xảy cũng là đại diện của false trong C), true làm địa chỉ 2 (chỉ xảy ra là đại diện C của true được dịch chuyển một chút) và nil là 4.

Answer 2

Nó không chính xác "được sử dụng để thu gom rác thải". Nó được sử dụng để phân biệt nội bộ giữa một con trỏ và một số nguyên không có hộp.

Answer 3

Xem phần "trình bày các số nguyên, bit thẻ, giá trị phân bổ đống" của https://ocaml.org/learn/tutorials/performance_and_profiling.html để có mô tả đúng.

Câu trả lời ngắn gọn là nó dành cho hiệu suất. Khi truyền một đối số cho một hàm, nó được truyền như một số nguyên hoặc một con trỏ. Ở cấp độ ngôn ngữ cấp máy không có cách nào để biết nếu một thanh ghi có chứa một số nguyên hay một con trỏ, nó chỉ là một giá trị 32 hoặc 64 bit. Vì vậy, thời gian chạy OCaml kiểm tra bit thẻ để xác định xem những gì nó nhận được là một số nguyên hoặc một con trỏ. Nếu bit thẻ được đặt, thì giá trị là một số nguyên và nó được chuyển đến quá tải chính xác. Nếu không, nó là một con trỏ và kiểu được tra cứu.

Tại sao chỉ các số nguyên có thẻ này? Bởi vì mọi thứ khác được chuyển thành con trỏ. Những gì được thông qua là một số nguyên hoặc một con trỏ đến một số kiểu dữ liệu khác. Chỉ với một bit thẻ, chỉ có thể có hai trường hợp.

Answer 4

tôi có thêm liên kết này để giúp các OP để hiểu thêm A 63-bit floating-point type for 64-bit OCaml

Mặc dù tiêu đề của bài viết dường như khoảng float, nó thực sự nói về extra 1 bit

Thời gian chạy OCaml cho phép đa hình thông qua thống nhất các loại . Mỗi giá trị OCaml được biểu diễn dưới dạng một từ đơn, để có thể thực hiện một đơn, ví dụ: "danh sách các thứ", với các chức năng truy cập (ví dụ: List.length) và xây dựng (ví dụ: List.map) các danh sách này hoạt động giống nhau cho dù chúng là danh sách các int, của phao hoặc danh sách các tập hợp các số nguyên.

Bất kỳ nội dung nào không vừa với từ được phân bổ trong một khối trong vùng . Từ đại diện cho dữ liệu này sau đó là một con trỏ tới khối. Vì heap chỉ chứa các khối từ, tất cả các con trỏ này là căn chỉnh: các bit quan trọng nhất của chúng ít bit luôn không được đặt.

Nhà thầu không có tranh cãi (như thế này: nhập trái cây = Apple | Cam | Chuối) và số nguyên không đại diện cho quá nhiều thông tin mà chúng cần phân bổ trong vùng heap. Đại diện của họ là unboxed. Dữ liệu nằm ngay bên trong từ mà nếu không sẽ là con trỏ . Vì vậy, trong khi một danh sách các danh sách thực sự là một danh sách các con trỏ, thì một danh sách các số int có chứa ints với một số ít gián tiếp hơn. Các chức năng truy cập và xây dựng các chức năng không nhận thấy vì ints và con trỏ có cùng kích thước.

Tuy nhiên, Trình thu gom rác cần phải là có thể nhận ra con trỏ từ số nguyên. Một con trỏ trỏ tới một khối được hình thành tốt trong heap theo định nghĩa còn sống (vì nó là đang được GC truy cập) và phải được đánh dấu như vậy. Một số nguyên có thể có bất kỳ giá trị nào và nếu có thể, nếu không đề phòng, hãy vô tình xem như một con trỏ. Điều này có thể làm cho các khối chết trông sống động, nhưng nhiều hơn tệ hơn, nó cũng sẽ làm cho GC thay đổi bit theo thứ mà nó nghĩ là tiêu đề của khối trực tiếp, khi nó thực sự theo sau một số nguyên trông giống như một con trỏ làm rối tung dữ liệu người dùng.

Đây là lý do tại sao các số nguyên không được cung cấp cung cấp 31 bit (cho bit OCAMl 32 bit) hoặc 63 bit (cho 64-bit OCaml) cho trình lập trình OCaml. Trong biểu diễn, đằng sau các cảnh , bit ít quan trọng nhất của một từ chứa số nguyên luôn được đặt để phân biệt nó với một con trỏ. 31- hoặc 63-bit số nguyên là khá bất thường, vì vậy bất kỳ ai sử dụng OCaml đều biết điều này. Những gì người dùng của OCaml thường không biết là lý do tại sao không có loại phao không có hộp mở rộng 63-bit63 bit cho OCAMl 64 bit.

Answer 5

Tại sao int trong OCaml chỉ 31 bit?

Về cơ bản, để có được hiệu suất tốt nhất có thể trên định lý lý thuyết Coq trong đó hoạt động thống trị là khớp mẫu và loại dữ liệu chi phối là các loại biến thể.Biểu diễn dữ liệu tốt nhất được tìm thấy là biểu diễn thống nhất sử dụng thẻ để phân biệt con trỏ với dữ liệu không được hộp.

Nhưng tại sao cách này chỉ dành cho int và không dành cho các loại cơ bản khác?

Không chỉ int. Các loại khác như char và enums sử dụng cùng một biểu tượng được gắn thẻ.