... | ... | @@ -121,10 +121,14 @@ evaluated: |
|
|
|
|
|
## 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).
|
|
|
>
|
|
|
>
|
|
|
|
|
|
<table><tr><th></th>
|
|
|
<table><tr><th> </th>
|
|
|
<th> bits 31..2 </th>
|
|
|
<th> bits 1 0
|
|
|
</th></tr>
|
... | ... | @@ -164,9 +168,11 @@ tagged: |
|
|
## 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 (:).
|
|
|
|
|
|
<table><tr><th></th>
|
|
|
|
|
|
<table><tr><th> </th>
|
|
|
<th> bits 31..2 </th>
|
|
|
<th> bits 1 0
|
|
|
</th></tr>
|
... | ... | @@ -198,9 +204,11 @@ This would require modifying all of the above plus modifying |
|
|
## 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:
|
|
|
|
|
|
<table><tr><th></th>
|
|
|
|
|
|
<table><tr><th> </th>
|
|
|
<th> bits 31..2 </th>
|
|
|
<th> bits 1 0
|
|
|
</th></tr>
|
... | ... | @@ -222,56 +230,69 @@ Constructors without children (such as `False` and `True`) only need their tag t |
|
|
</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:
|
|
|
|
|
|
<table><tr><th></th>
|
|
|
|
|
|
<table><tr><th> </th>
|
|
|
<th> bits 31..2 </th>
|
|
|
<th> bits 1 0 </th>
|
|
|
<th></th></tr>
|
|
|
<th>
|
|
|
</th></tr>
|
|
|
<tr><th> unevaluated closure </th>
|
|
|
<th> ptr </th>
|
|
|
<th> 00 </th>
|
|
|
<th></th></tr>
|
|
|
<th>
|
|
|
</th></tr>
|
|
|
<tr><th> cons. w/no children </th>
|
|
|
<th> tag </th>
|
|
|
<th> 01 </th>
|
|
|
<th> tag \< no. of constructors
|
|
|
<th> tag < no. of constructors
|
|
|
</th></tr>
|
|
|
<tr><th> cons. w/ children </th>
|
|
|
<th> ptr </th>
|
|
|
<th> 01 </th>
|
|
|
<th> ptr \>= no. of constructors
|
|
|
<th> ptr >= no. of constructors
|
|
|
</th></tr>
|
|
|
<tr><th> cons. w/children no. 1 </th>
|
|
|
<th> ptr </th>
|
|
|
<th> 10 </th>
|
|
|
<th></th></tr>
|
|
|
<th>
|
|
|
</th></tr>
|
|
|
<tr><th> cons. w/children no. 2 </th>
|
|
|
<th> ptr </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.
|
|
|
|
|
|
|
|
|
|
|
|
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 1 0 </th>
|
|
|
<th></th></tr>
|
|
|
<th>
|
|
|
</th></tr>
|
|
|
<tr><th> unevaluated closure </th>
|
|
|
<th> ptr </th>
|
|
|
<th> 00 </th>
|
|
|
<th></th></tr>
|
|
|
<th>
|
|
|
</th></tr>
|
|
|
<tr><th> cons. w/no children </th>
|
|
|
<th> tag </th>
|
|
|
<th> 01 </th>
|
|
|
<th> tag \< no. of constructors
|
|
|
<th> tag < no. of constructors
|
|
|
</th></tr>
|
|
|
<tr><th> cons. w/ children </th>
|
|
|
<th> ptr </th>
|
|
|
<th> 01 </th>
|
|
|
<th> ptr \>= no. of constructors
|
|
|
</th></tr></table> |
|
|
\ No newline at end of file |
|
|
<th> ptr >= no. of constructors
|
|
|
</th></tr></table>
|
|
|
|
|
|
|