Context Navigation

Changes between Version 2 and Version 3 of WhyDoesNQPGenerateInefficientCode

Timestamp:: 11/25/09 23:55:39 (12 years ago)
Author:: samlh
Comment:: Reformat for easier reading

Legend:

: Unmodified
: Added
: Removed
: Modified

WhyDoesNQPGenerateInefficientCode

v2	v3
1	1	{{{
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>
	3	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.
	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>
	7	ok. How could Parrot enable smarter code generation?
	8
	9	<pmichaud>
	10	cotto_work: well, one of the big stumbling blocks at the moment is that lexicals can only be PMCs
	11	so anything that goes into a lexical ends up having to be boxed into a PMC
	12	an even bigger stumbling block is that Parrot doesn't have a good lvalue model or assignment semantics
	13	it tends to confuse "bind" with "assign"
	14	at least, it does that for most of the default PMC types
	15	there's also not a good reference model
	16	for keeping track of object references
	17	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
	18
	19	<cotto_work>
	20	That explains some of the generated code then.
	21
	22	<pmichaud>
	23	cotto_work: I do plan to have an option whereby code can say "assume this lexical/symbol isn't being rebound"
	24	but since parrot doesn't have a good assignment model, most folks end up doing rebinds
	25	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
	26
	27	<cotto_work>
	28	What's the difference between assignment and binding?
	29
	30	<pmichaud>
	31	assignment changes the value of an existing PMC
	32	binding causes a symbol table entry to point to a PMC
	33	so, for example
	34	$P0 = box 1
	35	$P1 = $P0
	36	these are examples of binding
	37	if after the above, I do: $P0 = box 3
	38	then $P1 ends up still being bound to the PMC containing 1
	39	and $P0 is bound to a new PMC containing 3
	40	okay so far?
	41
	42	<cotto_work>
	43	yes
	44
	45	<pmichaud>
	46	$P0 = box 1
	47	$P1 = $P0
	48	assign $P0, 3
	49	in this case, $P0 and $P1 still point to the same PMC, and the value of that PMC has changed to 3
	50	still okay?
	51
	52	<cotto_work>
	53	yes
	54
	55	<pmichaud>
	56	that's the difference
	57	now then, let's look at something like
	58	$P0 = new ['ResizablePMCArray']
	59	$P0[0] = 1
	60	$P1 = $P0[0]
	61	in this case, $P1 and $P0[0] are pointing to the same PMC (containing 1)
	62	but if we then do...
	63	$P0[0] = 3
	64	that's a binding, not an assignment
	65	such that $P1 refers to the old PMC (1), while $P0[0] refers to the new one (3)
	66	in other words, changing the value in the array has broken the bind
	67
	68	<moritz>
	69	pmichaud: this is becoming an FAQ... you should put that on a wiki page or so
	70
	71	<pmichaud>
	72	moritz: well, I have a few hours car ride today, perhaps I can type it up.
	73	but I also plan to do a NQP/compiler tutorial
	74
	75	<cotto_work>
	76	Thanks.
	77
	78	<pmichaud>
	79	where it gets really nasty is with
	80	$P0 = find_lex '$a'
	81	'foo'()
	82	if the "foo" subroutine does store_lex '$a', $P99 to put a new value in lexical $a
	83	then when we get back from 'foo', $P0 no longer points to the PMC associated with $a
	84	because store_lex does a bind
	85	and not an assign
	86
	87	<cotto_work>
	88	Then $P0 will have an out-of-date value
	89
	90	<pmichaud>
	91	exactly
	92	so, every time we need access to $a, we end up having to do a re-fetch
	93	because it's possible some other operation will have re-bound it to a different PMC
	94	ideally there would be an opcode that makes it easier to do assignment
	95	there is an opcode called 'assign', but it tends to do weird things with the built-in PMCs
	96	for example
	97	$P0 = new ['ResizablePMCArray']
	98	store_lex '$a', $P0
	99	which sets $a to be a RPA
	100	now 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>
	105	That changes the length to 3, doesn't it?
	106
	107	<pmichaud>
	108	what we want is $P1 to be an Integer 3
	109	right
	110	so the 'assign' opcode doesn't do what we want here
	111	late last year we added the 'copy' opcode to try to do this
	112	so we'd have
	113	$P1 = find_lex '$a'
	114	$P2 = box 3
	115	copy $P1, $P2 (replace $P1 with $P2)
	116	but it's horribly inefficient, because it involves making a clone of $P2 and then copying that structure into the PMC header for $P1
	117	but so far it's about the best we can do
	118	everything gets worse when we start talking about aggregate access
	119	because there's not a copy $P0[0], $P2 opcode yet
	120	and 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>
	124	There's a lot conspiring to prevent good code generation from nqp.
	125	Thanks you for that explanation.
	126
	127	<pmichaud>
	128	sure thing!
	129	ultimately it's that Parrot (vtable and core types) doesn't have a good container/value/lvalue model
	130	or, at least, one that doesn't map well to the HLL's we're targeting.
110	131	}}}