Changes between Version 4 and Version 5 of SemiTagging


Ignore:
Timestamp:
Oct 11, 2006 1:04:06 PM (8 years ago)
Author:
alexey
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • SemiTagging

    v4 v5  
    1313GHC jumps to the code for the x closure, which returns when x is evaluated. Commonly, x is already evaluated, and the code for an evaluated constructor just (vector) returns immediately. 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). 
    1414 
     15||  || bits 31..2 || bits 1 0 || 
     16|| unevaluated closure || ptr || 00 || 
     17|| evaluated constructor closure || ptr || 01 || 
     18 
    1519This would require modifying 
    1620 * the GC to set the LSB bit of constructor closure pointers, 
     
    2125 
    2226We 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 (:). 
     27 
     28||  || bits 31..2 || bits 1 0 || 
     29|| unevaluated closure || ptr || 00 || 
     30|| cons. no. 1    || ptr || 01 || 
     31|| cons. no. 2    || ptr || 10 || 
     32|| cons. no. 3    || ptr || 11 || 
    2333 
    2434The nice thing about the current approach is that code size is small; implementing the test and jump will certainly add extra code to compiled case expressions. But the gains might be worth it. Complexity-wise this means masking out these bits when following any pointer to a heap object, which means carefully checking most of the runtime.