Re: PICs [was v8 first impressions]
"David Griswold" <[email protected]> Fri, 12 Sep 2008 15:23:04 -0700
| Newsgroups | gmane.comp.lang.smalltalk.strongtalk |
|---|---|
| Message-ID | <[email protected]> |
------=_Part_133575_18333526.1221258184772 Content-Type: text/plain; charset=ISO-8859-1 Hi Eliot, On Fri, Sep 12, 2008 at 10:24 AM, Eliot Miranda <[email protected]>wrote: > [...] > > > Um, variable arity doesn't imply variable size. In the VisualWorks VM I > use PICs and megamorphic PICs. I call the former "closed PICs" because they > have a maximum arity and hence apply to a closed set. I call the latter > "open PICs" because they apply to an open set of classes. When a send site > becomes polymorphic I allocate a PIC that has room for 8 entries and fill in > only two. The last instruction of the PIC is a jump to a routine that > extends the PIC. When the third class is encountered the jump to the extend > routine is overwritten by the dispatch for the third class and a new jump to > the extend routine is written. When the routine is reached from a PIC with > all 8 entries filled it finds or allocates an open PIC and binds the send > site to the open PIC. > > So no fragmentation and plenty of type information. For VisualWorks I > would see the following typical distributions > unlinked send 33% of all sites > monomorphic send 60% > polymorphic send 6% (2 to 8 cases) > megamorphic send 0.6% > > i.e. the ratios of monomorphic to polymorphic to megamorphic sends are very > close to 100 to 10 to 1. > There is still fragmentation in your scheme, it is simply hidden in the unused space at the end of unfilled PICs. However, at least it doesn't accumulate arbitrarily and doesn't require compaction. On the other hand it is unreclaimable. It is basically the kind of fragmentation one gets from lost space at the end of fixed size disk blocks. I'm willing to bet that on average your PICs are not more than half full, although the total space lost I'm sure is small. But it is an nice easy way to reduce PIC space management complexity. Your statistics are static measurements; the dynamic measurements are the relevant ones. As a demonstration that there can be big differences, 33% unlinked sites statically = 0% unlinked sites dynamically. Although there should still be some decent correlation between static and dynamic stats, other things being equal. At any rate, VisualWorks statistics are almost irrelevant anyway because these numbers are affected radically by inlining and customization. The percentage of monomorphic sites increases significantly, almost completely at the expense of (non-mega) polymorphic sites. Most of the small polymorphic sites in the code I am familiar with come from self sends in superclasses dispatching to methods implemented or overridden in subclasses; these always become monomorphic after customization. So wouldn't argue that for a non-inlining VM PICs might be very useful. But Strongtalk is a very different beast. -Dave --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Strongtalk-general" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/strongtalk-general?hl=en -~----------~----~----~----~------~----~------~--~--- ------=_Part_133575_18333526.1221258184772 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr">Hi Eliot,<br><br><div class=3D"gmail_quote">On Fri, Sep 12= , 2008 at 10:24 AM, Eliot Miranda <span dir=3D"ltr"><<a href=3D"mailto:e= [email protected]">[email protected]</a>></span> wrote:<br><b= lockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px = #ccc solid;padding-left:1ex;"> <div dir=3D"ltr"><div class=3D"gmail_quote"><blockquote class=3D"gmail_quot= e" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">= [...]</blockquote><div><br></div><div>Um, variable arity doesn't imply = variable size. In the VisualWorks VM I use PICs and megamorphic PICs.= I call the former "closed PICs" because they have a maximu= m arity and hence apply to a closed set. I call the latter "open= PICs" because they apply to an open set of classes. When a send= site becomes polymorphic I allocate a PIC that has room for 8 entries and = fill in only two. The last instruction of the PIC is a jump to a rout= ine that extends the PIC. When the third class is encountered the jum= p to the extend routine is overwritten by the dispatch for the third class = and a new jump to the extend routine is written. When the routine is = reached from a PIC with all 8 entries filled it finds or allocates an open = PIC and binds the send site to the open PIC. </div> <div><br></div><div>So no fragmentation and plenty of type information. &nb= sp;For VisualWorks I would see the following typical distributions</div><di= v> unlinked send 33% of all si= tes</div><div> monomorphic send 60%</div> <div> polymorphic send 6% (2 to 8= cases)</div><div> megamorphic send 0.6%</div><div>= <br></div><div>i.e. the ratios of monomorphic to polymorphic to megamorphic= sends are very close to 100 to 10 to 1.</div><div> </div></div></div></blockquote><div><br></div><div>There is still fragmenta= tion in your scheme, it is simply hidden in the unused space at the end of = unfilled PICs. However, at least it doesn't accumulate arbitraril= y and doesn't require compaction. On the other hand it is unrecla= imable. It is basically the kind of fragmentation one gets from lost = space at the end of fixed size disk blocks. I'm willing to bet th= at on average your PICs are not more than half full, although the total spa= ce lost I'm sure is small. But it is an nice easy way to reduce P= IC space management complexity.</div> <div><br></div><div>Your statistics are static measurements; the dynamic me= asurements are the relevant ones. As a demonstration that there can b= e big differences, 33% unlinked sites statically =3D 0% unlinked sites dyna= mically. Although there should still be some decent correlation betwe= en static and dynamic stats, other things being equal.</div> <div><br></div><div>At any rate, VisualWorks statistics are almost irreleva= nt anyway because these numbers are affected radically by inlining and cust= omization. The percentage of monomorphic sites increases significantl= y, almost completely at the expense of (non-mega) polymorphic sites. = Most of the small polymorphic sites in the code I am familiar with come fro= m self sends in superclasses dispatching to methods implemented or overridd= en in subclasses; these <span class=3D"Apple-style-span" style=3D"font-styl= e: italic;"><span class=3D"Apple-style-span" style=3D"font-weight: bold;">a= lways </span></span>become monomorphic after customization.</div> <div><br></div><div>So wouldn't argue that for a non-inlining VM PICs m= ight be very useful. But Strongtalk is a very different beast.</div><= div><br></div><div>-Dave</div></div></div><br> --~--~---------~--~----~------------~-------~--~----~<br> You received this message because you are subscribed to the Google Groups &= quot;Strongtalk-general" group. <br> To post to this group, send email= to [email protected] <br> To unsubscribe from this group= , send email to [email protected] <br> For mo= re options, visit this group at http://groups.google.com/group/strongtalk-g= eneral?hl=3Den <br> -~----------~----~----~----~------~----~------~--~---<b= r> <br> ------=_Part_133575_18333526.1221258184772--