OCaml의 int가 왜 31 비트입니까?

OCaml의 int가 왜 31 비트입니까?

---

이 "기능"을 다른 곳에서는 보지 못했습니다. 32 비트가 가비지 수집에 사용된다는 것을 알고 있습니다. 그러나 왜 다른 기본 유형이 아닌 int 전용입니까?

---

이것을 태그 포인터 표시 라고하며 수십 년 동안 많은 다른 통역사, VM 및 런타임 시스템에서 사용되는 매우 일반적인 최적화 트릭입니다. 거의 모든 Lisp 구현에서 다수의 Smalltalk VM, 많은 Ruby 인터프리터 등을 사용합니다.

일반적으로 이러한 언어에서는 항상 객체에 대한 포인터를 전달합니다. 객체 자체는 객체 메타 데이터 (예 : 객체 유형, 클래스, 액세스 제어 제한 또는 보안 주석 등)와 실제 객체 데이터 자체를 포함하는 객체 헤더로 구성됩니다. 따라서 간단한 정수는 포인터와 메타 데이터 및 실제 정수로 구성된 객체로 표시됩니다. 매우 컴팩트 한 표현이라도 간단한 정수의 경우 6 바이트와 같습니다.

또한 이러한 정수 객체를 CPU로 전달하여 빠른 정수 산술을 수행 할 수 없습니다. 두 개의 정수를 추가하려면 실제로 두 개의 포인터 만 있으며, 추가하려는 두 개의 정수 객체의 객체 헤더 시작 부분을 가리 킵니다. 따라서 첫 번째 포인터에서 정수 산술을 수행하여 정수 데이터가 저장된 객체에 오프셋을 추가해야합니다. 그런 다음 해당 주소를 역 참조해야합니다. 두 번째 정수로 똑같이 다시하십시오. 이제 CPU에 실제로 추가하도록 요청할 수있는 두 개의 정수가 있습니다. 물론 이제 결과를 보유 할 새로운 정수 객체를 생성해야합니다.

따라서 하나의 정수 덧셈 을 수행 하려면 실제로 세 개의 정수 덧셈과 두 개의 포인터 역 참조 및 하나의 객체 구성 을 수행해야합니다 . 그리고 거의 20 바이트를 차지합니다.

그러나 비결은 정수와 같은 소위 불변 값 유형을 사용 하면 일반적으로 객체 헤더에 모든 메타 데이터 가 필요 하지 않다는 것입니다. 모든 내용을 그대로두고 합성 할 수 있습니다 (VM-nerd- 누군가가보고 싶어 할 때 "가짜"라고 말하십시오. 정수에는 항상 class Integer가 있으며 해당 정보를 별도로 저장할 필요가 없습니다. 누군가가 정수의 클래스 알아낼 반사를 사용하는 경우, 당신은 단순히 응답 Integer하고 아무도 당신이 실제로 객체 헤더에 정보를 저장하지 않았 음을 알 수 없으며 그 사실이 없는 경우에도 객체 헤더 (또는 목적).

그래서, 트릭의 값은 저장하는 것입니다 의 포인터 내에서 객체를 에 효과적으로 하나에 두 개의 붕괴, 객체.

실제로 포인터 자체 내에 포인터에 대한 추가 정보를 저장할 수 있는 포인터 (소위 태그 비트 ) 내에 추가 공간이있는 CPU가 있습니다. "이것은 실제로 포인터가 아니며 정수입니다"와 같은 추가 정보. 예로는 버로우즈 B5000, 다양한 리스프 머신 또는 AS / 400이 있습니다. 불행히도, 현재 주류 CPU의 대부분에는 해당 기능이 없습니다.

그러나 해결 방법이 있습니다. 주소가 워드 경계에 정렬되지 않으면 대부분의 최신 주류 CPU가 상당히 느리게 작동합니다. 일부는 정렬되지 않은 액세스를 전혀 지원하지 않습니다.

이것이 의미하는 것은 실제로 모든 포인터를 4로 나눌 수 있다는 것입니다. 즉, 항상 두 0비트로 끝납니다 . 이를 통해 실제 포인터 (로 끝나는 00포인터)와 실제로 변장 된 정수 (로 끝나는 포인터) 를 구별 할 수 있습니다 1. 그리고 그것은 여전히 10다른 일을 할 수 있는 모든 포인터로 우리를 떠납니다 . 또한 대부분의 최신 운영 체제는 매우 낮은 주소를 보유하므로 다른 영역 (예 : 24 0초로 끝나고 포인터로 끝나는 포인터 00)을 제공합니다.

따라서 31 비트 정수를 포인터를 1 비트 왼쪽으로 이동하고 추가 1하여 포인터로 인코딩 할 수 있습니다 . 그리고 그것들을 적절하게 이동시킴으로써 (때로는 필요하지 않은 경우에도) 매우 빠른 정수 연산을 수행 할 수 있습니다 .

다른 주소 공간으로 무엇을해야합니까? 음, 전형적인 예는 인코딩 등이 float다른 큰 주소 공간과 같은 특수 목적의 숫자에들 true, false, nil, 가까운 127 개 ASCII 문자, 일반적으로 사용되는 짧은 문자열, 빈리스트, 빈 오브젝트, 빈 배열 등 0주소.

예를 들어, MRI, YARV 및 Rubinius 루비 인터프리터에, 정수, I는 전술 한 방법을 인코딩 false주소로 인코딩된다 0(너무 발생 도 의 표현으로 false, C)에 true어드레스로서 2너무 우연히 ( C의 표현은 true하나의 비트 시프트)와 nil같은 4.

---

자세한 설명 은 https://ocaml.org/learn/tutorials/performance_and_profiling.html의 "정수, 태그 비트, 힙 할당 값 표시"섹션을 참조하십시오 .

짧은 대답은 성능을위한 것입니다. 함수에 인수를 전달하면 정수 또는 포인터로 전달됩니다. 머신 레벨 언어 레벨에서는 레지스터에 정수 또는 포인터가 포함되어 있는지 여부를 알 수있는 방법이 없으며 32 또는 64 비트 값입니다. 따라서 OCaml 런타임은 태그 비트를 확인하여 수신 한 것이 정수인지 포인터인지 확인합니다. 태그 비트가 설정되면 값은 정수이며 올바른 과부하로 전달됩니다. 그렇지 않으면 포인터이며 유형이 조회됩니다.

왜 정수에만이 태그가 있습니까? 다른 모든 것은 포인터로 전달되기 때문입니다. 전달되는 것은 정수 또는 다른 데이터 유형에 대한 포인터입니다. 태그 비트가 하나만 있으면 두 가지 경우 만있을 수 있습니다.

---

"가비지 수집에 사용되지"않습니다. 포인터와 unboxed 정수를 내부적으로 구별하는 데 사용됩니다.

---

OP가 64 비트 OCaml의 63 비트 부동 소수점 유형을 더 잘 이해할 수 있도록이 링크를 추가해야합니다.

이 기사의 제목은에 대해 보이지만 float실제로는extra 1 bit

OCaml 런타임은 유형의 균일 한 표현을 통해 다형성을 허용합니다. 모든 OCaml 값은 단일 단어로 표시되므로 이러한 목록에 액세스 (예 : List.length) 및 빌드 (예 : List.map)하는 기능을 사용하여 "사물 목록"에 대한 단일 구현을 가질 수 있습니다. 정수, 부동 소수점 또는 정수 세트 목록과 동일하게 작동합니다.

Anything that does not fit in in a word is allocated in a block in the heap. The word representing this data is then a pointer to the block. Since the heap contains only blocks of words, all these pointers are aligned: their few least significants bits are always unset.

Argumentless constructors (like this: type fruit = Apple | Orange | Banana) and integers do not represent so much information that they need to be allocated in the heap. Their representation is unboxed. The data is directly inside the word that would otherwise have been a pointer. So while a list of lists is actually a list of pointers, a list of ints contains the ints with one less indirection. The functions accessing and building lists do not notice because ints and pointers have the same size.

Still, the Garbage Collector needs to be able to recognize pointers from integers. A pointer points to a well-formed block in the heap that is by definition alive (since it is being visited by the GC) and should be marked so. An integer can have any value and could, if precautions were not taken, accidentally look like a pointer. This could cause dead blocks to look alive, but much worse, it would also cause the GC to change bits in what it thinks is the header of a live block, when it is actually following an integer that looks like a pointer and messing up user data.

This is why unboxed integers provide 31 bits (for 32-bit OCaml) or 63 bits (for 64-bit OCaml) to the OCaml programmer. In the representation, behind the scenes, the least significant bit of a word containing an integer is always set, to distinguish it from a pointer. 31- or 63-bit integers are rather unusual, so anyone who uses OCaml at all knows this. What users of OCaml do not usually know is why there isn't a 63-bit unboxed float type for 64-bit OCaml.

---

Why is an int in OCaml only 31 bits?

Basically, to get the best possible performance on the Coq theorem prover where the dominant operation is pattern matching and the dominant data types are variant types. The best data representation was found to be a uniform representation using tags to distinguish pointers from unboxed data.

But why is it that way only for ints and not for the other basic types?

Not only int. Other types such as char and enums use the same tagged representation.

참고URL : https://stackoverflow.com/questions/3773985/why-is-an-int-in-ocaml-only-31-bits