Changes between Version 2 and Version 3 of WhyDoesNQPGenerateInefficientCode

Show
Ignore:
Timestamp:
11/25/09 23:55:39 (5 years ago)
Author:
samlh
Comment:

Reformat for easier reading

Legend:

Unmodified
Added
Removed
Modified
  • WhyDoesNQPGenerateInefficientCode

    v2 v3  
    11{{{ 
    2 <pmichaud> cotto_work: I do expect to try to generate smarter pir, yes.  However, the structure of Parrot doesn't allow for a lot smarter PIR. 
    3 <pmichaud> (I'm hoping parrot will change that... but I don't expect it to happen anytime in the near future.) 
    4 <cotto_work> ok.  How could Parrot enable smarter code generation? 
    5 <Tene> The fix isn't too bad, but I haven't done it yet. 
    6 <cotto_work> It sounds like that might fit in with Lorito. 
    7 <pmichaud> cotto_work: well, one of the big stumbling blocks at the moment is that lexicals can only be PMCs 
    8 <pmichaud> so anything that goes into a lexical ends up having to be boxed into a PMC 
    9 <pmichaud> an even bigger stumbling block is that Parrot doesn't have a good lvalue model or assignment semantics 
    10 <pmichaud> it tends to confuse "bind" with "assign" 
    11 <pmichaud> at least, it does that for most of the default PMC types 
    12 <pmichaud> there's also not a good reference model 
    13 <pmichaud> for keeping track of object references 
    14 <pmichaud> as a result, the code that nqp generates tends to have to be somewhat pessimistic, such as continually refetching lexical and global symbol tables because of the possibility of a symbol being rebound 
    15 <Coke> pmichaud,tene: > puts [list [catch barf var] $var] 
    16 <Coke> 1 {Could not find non-existent sub barf} 
    17 <Coke> whee. 
    18 <cotto_work> That explains some of the generated code then. 
    19 * cconstantine has quit (Quit: cconstantine) 
    20 <Coke> pmichaud: any issue with switching partcl-nqp to build with "nqp" instead of "parrot-nqp" for now? 
    21 <Coke> (then I don't have to ping you to cut a new 'release' =-) 
    22 <pmichaud> cotto_work: I do plan to have an option whereby code can say "assume this lexical/symbol isn't being rebound" 
    23 <pmichaud> but since parrot doesn't have a good assignment model, most folks end up doing rebinds 
    24 <pmichaud> partcl-nqp just went through this yesterday (until I fixed it this morning) whereby symbols were being re-bound to new PMCs instead of changing the value of an existing multiply-bound PMC 
    25 <cotto_work> What's the difference between assignment and binding? 
    26 <pmichaud> assignment changes the value of an existing PMC 
    27 <pmichaud> binding causes a symbol table entry to point to a PMC 
    28 <pmichaud> so, for example 
    29 <pmichaud> $P0 = box 1 
    30 <pmichaud> $P1 = $P0 
    31 <pmichaud> these are examples of binding 
    32 <pmichaud> if after the above, I do:    $P0 = box 3 
    33 <pmichaud> then $P1 ends up still being bound to the PMC containing 1 
    34 <pmichaud> and $P0 is bound to a new PMC containing 3 
    35 <pmichaud> okay so far? 
    36 <cotto_work> yes 
    37 <pmichaud> $P0 = box 1 
    38 <pmichaud> $P1 = $P0 
    39 <pmichaud> assign $P0, 3 
    40 <pmichaud> in this case,  $P0 and $P1 still point to the same PMC, and the value of that PMC has changed to 3 
    41 <pmichaud> still okay? 
    42 <cotto_work> yes 
    43 <pmichaud> that's the difference 
    44 <pmichaud> now then, let's look at something like 
    45 <pmichaud> $P0 = new ['ResizablePMCArray'] 
    46 <pmichaud> $P0[0] = 1 
    47 <pmichaud> $P1 = $P0[0] 
    48 <pmichaud> in this case, $P1 and $P0[0] are pointing to the same PMC  (containing 1) 
    49 <pmichaud> but if we then do... 
    50 <pmichaud> $P0[0] = 3 
    51 <pmichaud> that's a binding, not an assignment 
    52 <pmichaud> such that $P1 refers to the old PMC (1), while $P0[0] refers to the new one (3) 
    53 <pmichaud> in other words, changing the value in the array has broken the bind 
    54 <moritz> pmichaud: this is becoming an FAQ... you should put that on a wiki page or so 
    55 <pmichaud> moritz: well, I have a few hours car ride today, perhaps I can type it up. 
    56 <pmichaud> but I also plan to do a NQP/compiler tutorial 
    57 <Coke> pmichaud: is t/sanity.t working for you? 
    58 <pmichaud> Coke: it was as of my last push 
    59 <cotto_work> Thanks. 
    60 <pmichaud> where it gets *really* nasty is with 
    61 <pmichaud>    $P0 = find_lex '$a' 
    62 <pmichaud>     'foo'() 
    63 <pmichaud> if the "foo" subroutine does   store_lex  '$a', $P99    to put a new value in lexical $a 
    64 <pmichaud> then when we get back from 'foo', $P0 no longer points to the PMC associated with $a 
    65 <dalek> nqp-rx: ae0666c | tene++ | t/nqp/44-try-catch.t: 
    66 <dalek> nqp-rx: Update test plan 
    67 <dalek> nqp-rx: review: http://github.com/perl6/nqp-rx/commit/ae0666cf489a209c1aa2bffb1a829ce689a3b146 
    68 <pmichaud> because store_lex does a bind 
    69 <pmichaud> and not an assign 
    70 <cotto_work> Then $P0 will have an out-of-date value 
    71 <pmichaud> exactly 
    72 <pmichaud> so, every time we need access to $a, we end up having to do a re-fetch 
    73 <pmichaud> because it's possible some other operation will have re-bound it to a different PMC 
    74 <dalek> rakudo: 2eb38b5 | moritz++ | perl6.pir: 
    75 <dalek> rakudo: alias Object and Mu, as suggested by jnthn++; wins us back quite a few tests 
    76 <dalek> rakudo: review: http://github.com/rakudo/rakudo/commit/2eb38b5bf07f1c4392a9d1d75f3fd1cf7d877105 
    77 <pmichaud> ideally there would be an opcode that makes it easier to do assignment 
    78 <pmichaud> there is an opcode called 'assign', but it tends to do weird things with the built-in PMCs 
    79 <pmichaud> for example 
    80 <pmichaud> $P0 = new ['ResizablePMCArray'] 
    81 <pmichaud> store_lex '$a', $P0 
    82 <pmichaud> which sets $a to be a RPA 
    83 <pmichaud> now we want to do the equivalent of  $a = 3   -- i.e., change it to an Integer 3 
    84 <pmichaud> $P1 = find_lex '$a' 
    85 <pmichaud> assign $P1, 3      #   oooops! 
    86 <cotto_work> That changes the length to 3, doesn't it? 
    87 <pmichaud> what we want is $P1 to be an Integer 3 
    88 <pmichaud> right 
    89 <pmichaud> so the 'assign' opcode doesn't do what we want here 
    90 <pmichaud> late last year we added the 'copy' opcode to try to do this 
    91 <pmichaud> so we'd have 
    92 <pmichaud> $P1 = find_lex '$a' 
    93 <pmichaud> $P2 = box 3 
    94 <pmichaud> copy $P1, $P2    (replace $P1 with $P2) 
    95 * pjcj (~pjcj@80-218-204-119.dclient.hispeed.ch) has joined #parrot 
    96 * slavorg gives channel operator status to pjcj 
    97 <pmichaud> but it's horribly inefficient, because it involves making a clone of $P2 and then copying that structure into the PMC header for $P1 
    98 <pmichaud> but so far it's about the best we can do 
    99 <pmichaud> everything gets worse when we start talking about aggregate access 
    100 <pmichaud> because there's not a    copy $P0[0], $P2    opcode yet 
    101 <pmichaud> and this leads to allison's comment that it really should be the PMCs/vtables that determine behavior instead of opcodes 
    102 <pmichaud> (which is where the model completely breaks down) 
    103 <cotto_work> There's a lot conspiring to prevent good code generation from nqp. 
    104 <cotto_work> Thanks you for that explanation. 
    105 <pmichaud> sure thing! 
    106 <dukeleto> 'ello 
    107 <pmichaud> ultimately it's that Parrot (vtable and core types) doesn't have a good container/value/lvalue model 
    108 <pmichaud> or, at least, one that doesn't map well to the HLL's we're targing. 
    109 <pmichaud> *targeting 
     2<pmichaud>  
     3cotto_work: I do expect to try to generate smarter pir, yes.  However, the structure of Parrot doesn't allow for a lot smarter PIR. 
     4(I'm hoping parrot will change that... but I don't expect it to happen anytime in the near future.) 
     5 
     6<cotto_work> 
     7ok.  How could Parrot enable smarter code generation? 
     8 
     9<pmichaud> 
     10cotto_work: well, one of the big stumbling blocks at the moment is that lexicals can only be PMCs 
     11so anything that goes into a lexical ends up having to be boxed into a PMC 
     12an even bigger stumbling block is that Parrot doesn't have a good lvalue model or assignment semantics 
     13it tends to confuse "bind" with "assign" 
     14at least, it does that for most of the default PMC types 
     15there's also not a good reference model 
     16for keeping track of object references 
     17as a result, the code that nqp generates tends to have to be somewhat pessimistic, such as continually refetching lexical and global symbol tables because of the possibility of a symbol being rebound 
     18 
     19<cotto_work>  
     20That explains some of the generated code then. 
     21 
     22<pmichaud> 
     23cotto_work: I do plan to have an option whereby code can say "assume this lexical/symbol isn't being rebound" 
     24but since parrot doesn't have a good assignment model, most folks end up doing rebinds 
     25partcl-nqp just went through this yesterday (until I fixed it this morning) whereby symbols were being re-bound to new PMCs instead of changing the value of an existing multiply-bound PMC 
     26 
     27<cotto_work>  
     28What's the difference between assignment and binding? 
     29 
     30<pmichaud> 
     31assignment changes the value of an existing PMC 
     32binding causes a symbol table entry to point to a PMC 
     33so, for example 
     34 $P0 = box 1 
     35 $P1 = $P0 
     36these are examples of binding 
     37if after the above, I do:    $P0 = box 3 
     38then $P1 ends up still being bound to the PMC containing 1 
     39and $P0 is bound to a new PMC containing 3 
     40okay so far? 
     41 
     42<cotto_work>  
     43yes 
     44 
     45<pmichaud>  
     46 $P0 = box 1 
     47 $P1 = $P0 
     48 assign $P0, 3 
     49in this case,  $P0 and $P1 still point to the same PMC, and the value of that PMC has changed to 3 
     50still okay? 
     51 
     52<cotto_work>  
     53yes 
     54 
     55<pmichaud>  
     56that's the difference 
     57now then, let's look at something like 
     58 $P0 = new ['ResizablePMCArray'] 
     59 $P0[0] = 1 
     60 $P1 = $P0[0] 
     61in this case, $P1 and $P0[0] are pointing to the same PMC  (containing 1) 
     62but if we then do... 
     63 $P0[0] = 3 
     64that's a binding, not an assignment 
     65such that $P1 refers to the old PMC (1), while $P0[0] refers to the new one (3) 
     66in other words, changing the value in the array has broken the bind 
     67 
     68<moritz>  
     69pmichaud: this is becoming an FAQ... you should put that on a wiki page or so 
     70 
     71<pmichaud>  
     72moritz: well, I have a few hours car ride today, perhaps I can type it up. 
     73but I also plan to do a NQP/compiler tutorial 
     74 
     75<cotto_work>  
     76Thanks. 
     77 
     78<pmichaud>  
     79where it gets *really* nasty is with 
     80   $P0 = find_lex '$a' 
     81   'foo'() 
     82if the "foo" subroutine does   store_lex  '$a', $P99    to put a new value in lexical $a 
     83then when we get back from 'foo', $P0 no longer points to the PMC associated with $a 
     84because store_lex does a bind 
     85and not an assign 
     86 
     87<cotto_work>  
     88Then $P0 will have an out-of-date value 
     89 
     90<pmichaud>  
     91exactly 
     92so, every time we need access to $a, we end up having to do a re-fetch 
     93because it's possible some other operation will have re-bound it to a different PMC 
     94ideally there would be an opcode that makes it easier to do assignment 
     95there is an opcode called 'assign', but it tends to do weird things with the built-in PMCs 
     96for example 
     97 $P0 = new ['ResizablePMCArray'] 
     98 store_lex '$a', $P0 
     99which sets $a to be a RPA 
     100now we want to do the equivalent of  $a = 3   -- i.e., change it to an Integer 3 
     101 $P1 = find_lex '$a' 
     102 assign $P1, 3      #   oooops! 
     103 
     104<cotto_work>  
     105That changes the length to 3, doesn't it? 
     106 
     107<pmichaud>  
     108what we want is $P1 to be an Integer 3 
     109right 
     110so the 'assign' opcode doesn't do what we want here 
     111late last year we added the 'copy' opcode to try to do this 
     112so we'd have 
     113 $P1 = find_lex '$a' 
     114 $P2 = box 3 
     115 copy $P1, $P2    (replace $P1 with $P2) 
     116but it's horribly inefficient, because it involves making a clone of $P2 and then copying that structure into the PMC header for $P1 
     117but so far it's about the best we can do 
     118everything gets worse when we start talking about aggregate access 
     119because there's not a    copy $P0[0], $P2    opcode yet 
     120and this leads to allison's comment that it really should be the PMCs/vtables that determine behavior instead of opcodes 
     121(which is where the model completely breaks down) 
     122 
     123<cotto_work>  
     124There's a lot conspiring to prevent good code generation from nqp. 
     125Thanks you for that explanation. 
     126 
     127<pmichaud>  
     128sure thing! 
     129ultimately it's that Parrot (vtable and core types) doesn't have a good container/value/lvalue model 
     130or, at least, one that doesn't map well to the HLL's we're targeting. 
    110131}}}