... | @@ -121,10 +121,14 @@ evaluated: |
... | @@ -121,10 +121,14 @@ evaluated: |
|
|
|
|
|
## Tagging the LSB of an evaluated closure
|
|
## Tagging the LSB of an evaluated closure
|
|
|
|
|
|
|
|
|
|
|
|
>
|
|
>
|
|
>
|
|
> The idea is to encode the fact that a pointer points to an evaluated object by setting the LSB of the pointer. If the case expression detects that the closure is evaluated, it can avoid the jump and return, which are expensive on modern processors (indirect jumps).
|
|
> The idea is to encode the fact that a pointer points to an evaluated object by setting the LSB of the pointer. If the case expression detects that the closure is evaluated, it can avoid the jump and return, which are expensive on modern processors (indirect jumps).
|
|
|
|
>
|
|
|
|
>
|
|
|
|
|
|
<table><tr><th></th>
|
|
<table><tr><th> </th>
|
|
<th> bits 31..2 </th>
|
|
<th> bits 31..2 </th>
|
|
<th> bits 1 0
|
|
<th> bits 1 0
|
|
</th></tr>
|
|
</th></tr>
|
... | @@ -164,9 +168,11 @@ tagged: |
... | @@ -164,9 +168,11 @@ tagged: |
|
## Using more than one bit
|
|
## Using more than one bit
|
|
|
|
|
|
|
|
|
|
|
|
|
|
We can go a bit further than this, too. Since there are 2 spare bits (4 on a 64-bit machine), we can encode 4 (16) states. Taking 0 to mean "unevaluted", that leaves 3 (15) states to encode the values for the "tag" of the constructor. eg. an evaluated Bool would use 1 to indicate False and 2 to indicate True. An evaluated list cell would use 1 to indicate \[\] and 2 to indicate (:).
|
|
We can go a bit further than this, too. Since there are 2 spare bits (4 on a 64-bit machine), we can encode 4 (16) states. Taking 0 to mean "unevaluted", that leaves 3 (15) states to encode the values for the "tag" of the constructor. eg. an evaluated Bool would use 1 to indicate False and 2 to indicate True. An evaluated list cell would use 1 to indicate \[\] and 2 to indicate (:).
|
|
|
|
|
|
<table><tr><th></th>
|
|
|
|
|
|
<table><tr><th> </th>
|
|
<th> bits 31..2 </th>
|
|
<th> bits 31..2 </th>
|
|
<th> bits 1 0
|
|
<th> bits 1 0
|
|
</th></tr>
|
|
</th></tr>
|
... | @@ -198,9 +204,11 @@ This would require modifying all of the above plus modifying |
... | @@ -198,9 +204,11 @@ This would require modifying all of the above plus modifying |
|
## Using a tag directly in the pointer
|
|
## Using a tag directly in the pointer
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Constructors without children (such as `False` and `True`) only need their tag to be represented. Hence we can drop the pointer altogether as follows:
|
|
Constructors without children (such as `False` and `True`) only need their tag to be represented. Hence we can drop the pointer altogether as follows:
|
|
|
|
|
|
<table><tr><th></th>
|
|
|
|
|
|
<table><tr><th> </th>
|
|
<th> bits 31..2 </th>
|
|
<th> bits 31..2 </th>
|
|
<th> bits 1 0
|
|
<th> bits 1 0
|
|
</th></tr>
|
|
</th></tr>
|
... | @@ -222,56 +230,69 @@ Constructors without children (such as `False` and `True`) only need their tag t |
... | @@ -222,56 +230,69 @@ Constructors without children (such as `False` and `True`) only need their tag t |
|
</th></tr></table>
|
|
</th></tr></table>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
This still limits us to data types that have no more than two constructors with children. We can improve on this by noting that pointers will not point to low addresses. So we can make a simple test to distinguish between tags and pointers:
|
|
This still limits us to data types that have no more than two constructors with children. We can improve on this by noting that pointers will not point to low addresses. So we can make a simple test to distinguish between tags and pointers:
|
|
|
|
|
|
<table><tr><th></th>
|
|
|
|
|
|
<table><tr><th> </th>
|
|
<th> bits 31..2 </th>
|
|
<th> bits 31..2 </th>
|
|
<th> bits 1 0 </th>
|
|
<th> bits 1 0 </th>
|
|
<th></th></tr>
|
|
<th>
|
|
|
|
</th></tr>
|
|
<tr><th> unevaluated closure </th>
|
|
<tr><th> unevaluated closure </th>
|
|
<th> ptr </th>
|
|
<th> ptr </th>
|
|
<th> 00 </th>
|
|
<th> 00 </th>
|
|
<th></th></tr>
|
|
<th>
|
|
|
|
</th></tr>
|
|
<tr><th> cons. w/no children </th>
|
|
<tr><th> cons. w/no children </th>
|
|
<th> tag </th>
|
|
<th> tag </th>
|
|
<th> 01 </th>
|
|
<th> 01 </th>
|
|
<th> tag \< no. of constructors
|
|
<th> tag < no. of constructors
|
|
</th></tr>
|
|
</th></tr>
|
|
<tr><th> cons. w/ children </th>
|
|
<tr><th> cons. w/ children </th>
|
|
<th> ptr </th>
|
|
<th> ptr </th>
|
|
<th> 01 </th>
|
|
<th> 01 </th>
|
|
<th> ptr \>= no. of constructors
|
|
<th> ptr >= no. of constructors
|
|
</th></tr>
|
|
</th></tr>
|
|
<tr><th> cons. w/children no. 1 </th>
|
|
<tr><th> cons. w/children no. 1 </th>
|
|
<th> ptr </th>
|
|
<th> ptr </th>
|
|
<th> 10 </th>
|
|
<th> 10 </th>
|
|
<th></th></tr>
|
|
<th>
|
|
|
|
</th></tr>
|
|
<tr><th> cons. w/children no. 2 </th>
|
|
<tr><th> cons. w/children no. 2 </th>
|
|
<th> ptr </th>
|
|
<th> ptr </th>
|
|
<th> 11 </th>
|
|
<th> 11 </th>
|
|
<th></th></tr></table>
|
|
<th>
|
|
|
|
</th></tr></table>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Of course this assumes that we don't have data types with too many thousands of constructors.
|
|
Of course this assumes that we don't have data types with too many thousands of constructors.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
It might be possible that the case code for the alternatives above is becoming too complex. We might settle for the following "simple" option:
|
|
It might be possible that the case code for the alternatives above is becoming too complex. We might settle for the following "simple" option:
|
|
|
|
|
|
<table><tr><th></th>
|
|
|
|
|
|
<table><tr><th> </th>
|
|
<th> bits 31..2 </th>
|
|
<th> bits 31..2 </th>
|
|
<th> bits 1 0 </th>
|
|
<th> bits 1 0 </th>
|
|
<th></th></tr>
|
|
<th>
|
|
|
|
</th></tr>
|
|
<tr><th> unevaluated closure </th>
|
|
<tr><th> unevaluated closure </th>
|
|
<th> ptr </th>
|
|
<th> ptr </th>
|
|
<th> 00 </th>
|
|
<th> 00 </th>
|
|
<th></th></tr>
|
|
<th>
|
|
|
|
</th></tr>
|
|
<tr><th> cons. w/no children </th>
|
|
<tr><th> cons. w/no children </th>
|
|
<th> tag </th>
|
|
<th> tag </th>
|
|
<th> 01 </th>
|
|
<th> 01 </th>
|
|
<th> tag \< no. of constructors
|
|
<th> tag < no. of constructors
|
|
</th></tr>
|
|
</th></tr>
|
|
<tr><th> cons. w/ children </th>
|
|
<tr><th> cons. w/ children </th>
|
|
<th> ptr </th>
|
|
<th> ptr </th>
|
|
<th> 01 </th>
|
|
<th> 01 </th>
|
|
<th> ptr \>= no. of constructors
|
|
<th> ptr >= no. of constructors
|
|
</th></tr></table> |
|
</th></tr></table>
|
|
\ No newline at end of file |
|
|
|
|
|
|