Re: (MEMBER ...) with literal symbol(s)
Stavros Macrakis <[email protected]> Mon, 5 May 2025 14:44:14 -0400
| Newsgroups | gmane.comp.mathematics.maxima.general,gmane.lisp.gcl.devel |
|---|---|
| Message-ID | <CACLVabXxj7uJoChAjseDjyNDViNcW-t5=pCGWNS=BCdNUFn+EA@mail.gmail.com> |
--===============7519037502850526310== Content-Type: multipart/alternative; boundary="000000000000a3ed4b063467e37d" --000000000000a3ed4b063467e37d Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Mon, May 5, 2025 at 12:56=E2=80=AFPM Camm Maguire <[email protected]= g> wrote: > Greetings, and thanks for your feedback! > > Stavros Macrakis <[email protected]> writes: > > > Assuming that clause 2 applies to the loop in member > > > > 2) GCL will unroll loops over constant (and non-constant) lists up to > *src-loop-unroll-limit* (default 20) > > > > then this whole discussion is moot, since the vast majority (95%) of > constant lists of symbols are length 6 or less, and those are the > often-used cases. > > > > Unrolling the loop just allows the compiler to easily see the type of > each element one at a time. But as this is later than the decision to > compute the type integer on x, and as one does not know the unroll will > succeed until it does, it will not help in avoiding the former unless > there is an additional pass, or a backup/retry. Backup/retries can be > exponentially bad in compile time in egregious nested cases. > I don't know the internals of the GCL compiler, so I can't really say anything concrete. I would have thought that the compiler would start by determining the type of a function's arguments. In the case *(member x '(a b c))*, that's unknown and list-of-symbols (or maybe the compiler's type system can't represent list-of-X types?). Then it can dispatch to *member-eq*. > Re > > > > 5) GCL will not attempt to aggregate the types across all elements of = a > list, i.e. this whole list is of type symbol, so pull that out of the loo= p > as well. This > > seems ill-advised and unpractical to me at least at the moment. > > > > I'm surprised by this, and don't understand why it would be "ill-advise= d > and unpractical", but as I say it's moot if (2) is applied. > > The cleanest optimizations are lisp code inserts in the function source > which make sense in the generic case, and can be pruned by the compiler > in special cases. Hmm, I'm not sure how that applies to constant (quoted) arguments. Are you saying that *member* should be coded as (defun member (el lis) (cond ((or (symbolp el) (fixnump el)) (every #'(lambda (q) (or (symbolp q) (fixnump q)) lis) (member-eq el lis)) ...))) But that doesn't make sense in general, since as a function (not a macro), member doesn't know whether the arguments are quoted, which is the only case where the *every* clause makes sense. Setting separate compiler-macros, inline property > strings, or special compiler handler functions for a given function is > fragile and error prone. We've made a lot of progress cleaning up a lot > of the latter. > I don't know -- compiler macros seem like the natural solution. But I haven't worked on the innards of a Lisp compiler for decades, so I'm not sure I understand why they're a bad idea. -s (Trimming some of the context below.) It would be easy to add a check on the list alongside the check on x in > the source to prune this extra branch in the test, but at the cost of an > extra traversal of the list in the generic case, which seems like a > loser. > > > > > 3) GCL will pull the type-of on unknown x out of the loop and use it a= s > a key to a switch table inside the loop. > > > > Of course, this is unnecessary if arg 2 is a list of symbols, since eq > applies to all data types. In some styles of code, it might be faster to > test (and (symbolp x) (or > > (eq x 'c1) (eq x 'c2) ...)), but in the case of Maxima this will almost > always slow things down rather than speed them up. > > > > The expression (member x '(a b c...) :test #'eq) strikes me as verbose > and pedantic. Code should be easily readable by humans, and the extra > clause is clearly > > semantically unnecessary. memq is a bit better, but shouldn't be > necessary (there is nothing wrong with writing functions which encapsulat= e > some useful piece > > of Common Lisp functionality). If a particular compiler chooses not to > optimize that idiom, I'd say that's the compiler's problem. But according > to Camm's > > explanation, GCL does optimize it. So there's no issue. > > I agree in preferring the simple expression and relying on the compiler > to do the right thing. I cannot think at the moment of any instance in > GCL's own code which specifies :test #'eq. > > Take care, > > > > > -s > > > > On Sat, May 3, 2025 at 6:37=E2=80=AFAM Camm Maguire <camm@maguirefamily= .org> > wrote: > > > > Greetings! > > > > This is what is happening, with a twist. > > > > Since we don't know that *all* elements of the list will allow eql->eq > > ahead of time (optimization 5), one runtime check on x is done outside > > the loop to see if we can do eql->eq on that basis, e.g. an integer x0 > > is computed. The test then becomes (if x0 (eq a b) (eql a b)), and th= en > > eql goes to eq based on b anyway, so at the C level we have (if x0 (eq= a > > b) (eq a b)). All eql code in the example you cite has been eliminate= d. > > We have no optimization trying to recognize identical branches and > > eliminate the if. So instead of one machine instruction, you have two= , > > switch x0, (eq a b). > > > > Take care, > > > > David Scherfgen via Maxima-discuss > > <[email protected]> writes: > > > > > Thanks for the explanation, Camm. > > > > > > Optimizations 2) and 1) should suffice for this very common case in > Maxima's source to be optimized in GCL (just like SBCL does), optimizatio= n > 5) shouldn't > > be > > > necessary. > > > > > > Let's take the example (member x '(a b c)), i.e. unknown x and a lis= t > of literal symbols. > > > > > > Via 2), GCL should unroll that into (or (eql x 'a) (eql x 'b) (eql x > 'c)). > > > > > > Via 1), GCL should replace each of the (eql ...) with (eq ...), as > one of the arguments is a literal symbol. > > > > > > But that doesn't seem to be what's happening, right? > > > > > > Best regards > > > David Scherfgen > > >... > --000000000000a3ed4b063467e37d Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr"><div dir=3D"ltr"><div class=3D"gmail_default" style=3D"fon= t-family:georgia,serif;font-size:small;color:rgb(51,0,0)"><br></div></div><= br><div class=3D"gmail_quote gmail_quote_container"><div dir=3D"ltr" class= =3D"gmail_attr">On Mon, May 5, 2025 at 12:56=E2=80=AFPM Camm Maguire <<a= href=3D"mailto:[email protected]">[email protected]</a>> wrot= e:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0= .8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Greetings, an= d thanks for your feedback!<br> <br> Stavros Macrakis <<a href=3D"mailto:[email protected]" target=3D"_blank= ">[email protected]</a>> writes:<br> <br> > Assuming that clause 2 applies to the loop in member<br> ><br> >=C2=A0 2) GCL will unroll loops over constant (and non-constant) lists = up to *src-loop-unroll-limit* (default 20)<br> ><br> > then this whole discussion is moot, since the vast majority (95%) of c= onstant lists of symbols are length 6 or less, and those are the often-used= cases.<br> ><br> <br> Unrolling the loop just allows the compiler to easily see the type of<br> each element one at a time.=C2=A0 But as this is later than the decision to= <br> compute the type integer on x, and as one does not know the unroll will<br> succeed until it does, it will not help in avoiding the former unless<br> there is an additional pass, or a backup/retry.=C2=A0 Backup/retries can be= <br> exponentially bad in compile time in egregious nested cases.<br></blockquot= e><div><br></div><div><span class=3D"gmail_default" style=3D"font-family:ge= orgia,serif;font-size:small;color:rgb(51,0,0)"></span><span class=3D"gmail_= default" style=3D"font-family:georgia,serif;font-size:small;color:rgb(51,0,= 0)">I don't know the internals of the GCL compiler, so I can't real= ly say anything concrete.</span></div><div class=3D"gmail_default" style=3D= "font-family:georgia,serif;font-size:small;color:rgb(51,0,0)">I would have = thought that the compiler would start by determining the type of a function= 's arguments. In the case <b>(member x '(a b c))</b>, that's un= known and list-of-symbols (or maybe the compiler's type system can'= t represent list-of-X types?). Then it can dispatch to <b>member-eq</b>.=C2= =A0</div><div class=3D"gmail_default" style=3D"font-size:small"><br></div><= div class=3D"gmail_default" style=3D"font-size:small"><span style=3D"color:= rgb(34,34,34);font-family:Arial,Helvetica,sans-serif">> Re</span></div><= blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-l= eft:1px solid rgb(204,204,204);padding-left:1ex"> ><br> >=C2=A0 5) GCL will not attempt to aggregate the types across all elemen= ts of a list, i.e. this whole list is of type symbol, so pull that out of t= he loop as well.=C2=A0 This<br> >=C2=A0 seems ill-advised and unpractical to me at least at the moment.<= br> ><br> > I'm surprised by this, and don't understand why it would be &q= uot;ill-advised and unpractical", but as I say it's moot if (2) is= applied.<br> <br> The cleanest optimizations are lisp code inserts in the function source<br> which make sense in the generic case, and can be pruned by the compiler<br> in special cases.=C2=A0</blockquote><div><br></div><div><span class=3D"gmai= l_default" style=3D"font-family:georgia,serif;font-size:small;color:rgb(51,= 0,0)">Hmm, I'm not sure how that applies to constant (quoted) arguments= . Are you saying that <b>member</b>=C2=A0should be coded as</span></div><di= v><br></div></div><blockquote style=3D"margin:0 0 0 40px;border:none;paddin= g:0px"><div class=3D"gmail_quote gmail_quote_container"><div><span class=3D= "gmail_default" style=3D"font-size:small;color:rgb(51,0,0)"><font face=3D"m= onospace">(defun member (el lis)</font></span></div></div></blockquote><blo= ckquote style=3D"margin:0 0 0 40px;border:none;padding:0px"><div class=3D"g= mail_quote gmail_quote_container"><div><span class=3D"gmail_default" style= =3D"font-size:small;color:rgb(51,0,0)"><font face=3D"monospace">=C2=A0 =C2= =A0 =C2=A0 (cond ((or (symbolp el)</font></span></div><div><span class=3D"g= mail_default" style=3D"font-size:small;color:rgb(51,0,0)"><font face=3D"mon= ospace">=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(fixn= ump el))</font></span></div><div><span style=3D"font-family:monospace;color= :rgb(51,0,0)"><span class=3D"gmail_default" style=3D"font-family:georgia,se= rif;font-size:small;color:rgb(51,0,0)">=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0</span>(every #'(lambda (q) (or (symbolp= q) (fixnump q)) lis)</span></div><div><span class=3D"gmail_default" style= =3D"font-size:small;color:rgb(51,0,0)"><font face=3D"monospace">=C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(member-eq el lis))</font></span></di= v><div><span class=3D"gmail_default" style=3D"font-size:small;color:rgb(51,= 0,0)"><font face=3D"monospace">=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0...)))</font></span></div><div><span class=3D"gmail_default" style=3D= "font-size:small;color:rgb(51,0,0)"><font face=3D"monospace"><br></font></s= pan></div></div></blockquote><font color=3D"#330000" face=3D"monospace"><sp= an class=3D"gmail_default" style=3D"font-family:georgia,serif;font-size:sma= ll;color:rgb(51,0,0)">But that doesn't make sense in general, since as = a function (not a macro), member doesn't know whether the arguments are= quoted, which is the only case where the <b>every</b>=C2=A0clause makes se= nse.</span></font><div><font color=3D"#330000" face=3D"georgia, serif"><br>= </font><div class=3D"gmail_quote gmail_quote_container"><blockquote class= =3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rg= b(204,204,204);padding-left:1ex"> Setting separate compiler-macros, inline = property<br> strings, or special compiler handler functions for a given function is<br> fragile and error prone.=C2=A0 We've made a lot of progress cleaning up= a lot<br> of the latter.<br></blockquote><div><br></div><div><div class=3D"gmail_defa= ult" style=3D"font-family:georgia,serif;font-size:small;color:rgb(51,0,0)">= I don't know --=C2=A0 compiler macros seem like the natural solution. B= ut I haven't worked on the innards of a Lisp compiler for decades, so I= 'm not sure I understand why they're a bad idea.</div></div><div cl= ass=3D"gmail_default" style=3D"font-family:georgia,serif;font-size:small;co= lor:rgb(51,0,0)"><br></div><div class=3D"gmail_default" style=3D"font-famil= y:georgia,serif;font-size:small;color:rgb(51,0,0)">=C2=A0 =C2=A0 =C2=A0 =C2= =A0 -s</div><div class=3D"gmail_default" style=3D"font-family:georgia,serif= ;font-size:small;color:rgb(51,0,0)"><br></div><div class=3D"gmail_default" = style=3D"font-family:georgia,serif;font-size:small;color:rgb(51,0,0)">(Trim= ming some of the context below.)</div><div><br></div><blockquote class=3D"g= mail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204= ,204,204);padding-left:1ex"> It would be easy to add a check on the list alongside the check on x in<br> the source to prune this extra branch in the test, but at the cost of an<br= > extra traversal of the list in the generic case, which seems like a<br> loser.<br> <br> ><br> >=C2=A0 3) GCL will pull the type-of on unknown x out of the loop and us= e it as a key to a switch table inside the loop.<br> ><br> > Of course, this is unnecessary if arg 2 is a list of symbols, since eq= applies to all data types. In some styles of code, it might be faster to t= est (and (symbolp x) (or<br> > (eq x 'c1) (eq x 'c2) ...)), but in the case of Maxima this wi= ll almost always slow things down rather than speed them up.<br> ><br> > The expression (member x '(a b c...) :test #'eq) strikes me as= verbose and pedantic. Code should be easily readable by humans, and the ex= tra clause is clearly<br> > semantically unnecessary. memq is a bit better, but shouldn't be n= ecessary (there is nothing wrong with writing functions which encapsulate s= ome useful piece<br> > of Common Lisp functionality). If a particular compiler chooses not to= optimize that idiom, I'd say that's the compiler's problem. Bu= t according to Camm's<br> > explanation, GCL does optimize it. So there's no issue.<br> <br> I agree in preferring the simple expression and relying on the compiler<br> to do the right thing.=C2=A0 I cannot think at the moment of any instance i= n<br> GCL's own code which specifies :test #'eq.<br> <br> Take care,<br> <br> ><br> >=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 -s<br> ><br> > On Sat, May 3, 2025 at 6:37=E2=80=AFAM Camm Maguire <<a href=3D"mai= lto:[email protected]" target=3D"_blank">[email protected]</a>>= ; wrote:<br> ><br> >=C2=A0 Greetings!<br> ><br> >=C2=A0 This is what is happening, with a twist.<br> ><br> >=C2=A0 Since we don't know that *all* elements of the list will all= ow eql->eq<br> >=C2=A0 ahead of time (optimization 5), one runtime check on x is done o= utside<br> >=C2=A0 the loop to see if we can do eql->eq on that basis, e.g. an i= nteger x0<br> >=C2=A0 is computed.=C2=A0 The test then becomes (if x0 (eq a b) (eql a = b)), and then<br> >=C2=A0 eql goes to eq based on b anyway, so at the C level we have (if = x0 (eq a<br> >=C2=A0 b) (eq a b)).=C2=A0 All eql code in the example you cite has bee= n eliminated.<br> >=C2=A0 We have no optimization trying to recognize identical branches a= nd<br> >=C2=A0 eliminate the if.=C2=A0 So instead of one machine instruction, y= ou have two,<br> >=C2=A0 switch x0, (eq a b).<br> ><br> >=C2=A0 Take care,<br> ><br> >=C2=A0 David Scherfgen via Maxima-discuss<br> >=C2=A0 <<a href=3D"mailto:[email protected]" targ= et=3D"_blank">[email protected]</a>> writes:<br> ><br> >=C2=A0 > Thanks for the explanation, Camm.<br> >=C2=A0 ><br> >=C2=A0 > Optimizations 2) and 1) should suffice for this very common= case in Maxima's source to be optimized in GCL (just like SBCL does), = optimization 5) shouldn't<br> >=C2=A0 be<br> >=C2=A0 > necessary.<br> >=C2=A0 ><br> >=C2=A0 > Let's take the example (member x '(a b c)), i.e. un= known x and a list of literal symbols.<br> >=C2=A0 ><br> >=C2=A0 > Via 2), GCL should unroll that into (or (eql x 'a) (eql= x 'b) (eql x 'c)).<br> >=C2=A0 ><br> >=C2=A0 > Via 1), GCL should replace each of the (eql ...) with (eq .= ..), as one of the arguments is a literal symbol.<br> >=C2=A0 ><br> >=C2=A0 > But that doesn't seem to be what's happening, right= ?<br> >=C2=A0 ><br> >=C2=A0 > Best regards<br> >=C2=A0 > David Scherfgen<br> >=C2=A0 ><span class=3D"gmail_default" style=3D"font-family:georgia,s= erif;font-size:small;color:rgb(51,0,0)">...</span><br> </blockquote></div></div></div> --000000000000a3ed4b063467e37d-- --===============7519037502850526310== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline --===============7519037502850526310== Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Disposition: inline _______________________________________________ Maxima-discuss mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/maxima-discuss --===============7519037502850526310==--