Re: Finding the applicable methods...
"Marco Antoniotti (as marco dot antoniotti at unimib dot it)" <[email protected]> Wed, 15 Jul 2026 12:35:04 +0200
| Newsgroups | gmane.lisp.lispworks.general |
|---|---|
| Message-ID | <CAG0Nw2npkLfWEFvr6g_E7kNF+gDMzDbcjZcatjmjNDBB-a-U7A@mail.gmail.com> |
--0000000000007a1ddc0656a3e197 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Careful: if you use RB-trees you are getting logarithmic operations. Not expected constant. On Wed, Jul 15, 2026 at 12:27=E2=80=AFPM David McClain (as dbm at refined-audiometrics dot com) <[email protected]> wrote: > Actually=E2=80=A6 I misspoke. > > I just invented a purely functional hash table, using the RB-Trees as the > container. > > I had stated that there were no such thing. It was quite trivial to > implement. > > > On Jul 14, 2026, at 12:11, David McClain (as dbm at refined-audiometrics > dot com) <[email protected]> wrote: > > Well, thanks for that info. Looks like I missed all the documentation in > the Hyperspec about CLOS. I=E2=80=99ll go find it. > > But something was sticking in the back of my throat regarding the use of > CLOS and =E2=80=9Cstrongly typed=E2=80=9D code (as strong as Lisp allows)= . > > I had been using a class hierarchy to represent Red-Black Tree Nodes (an > extant NODE) and an EMPTY node. EMPTY was turned into a Singleton Instanc= e > class, as per the example offered by Didier Verna. > > But the use of CLOS produces code that runs about 50x slower than using a > Hash-table. (I know, RB-Trees use ordered keys and hash-tables do not=E2= =80=A6) And > so, after recasting my code into vector structs for extant nodes and NIL > for empty nodes, > > From this: > > (defclass node (tree) > ((l :reader node-l > :initarg :l > :type tree) > (k :reader node-k > :reader node-key > :initarg :k > :initarg :key) > (v :reader node-v > :reader node-val > :initarg :v > :initarg :val) > (r :reader node-r > :initarg :r > :type tree) > (h :reader node-h > :reader height > :initarg :h > :type fixnum)) > (:default-initargs > :l +empty+ > :r +empty+ > :h 1)) > > > To this: > > (defstruct (node (:type vector) > (:constructor singleton-node (k v)) > (:constructor %create (l k v r h))) > l k v r (h 1)) > > > The RB-Trees code now runs only 20x slower than Hash-tables. There is a 2= x > cost to using CLOS over bare untyped simple-vectors. > > One might argue that more fully typed is preferable? But speed is also > seductive. And why not? When we make Trees out of Lisp LISTs, there is no > strong typing for them, and yet we happily run with CONS Trees anyway. Th= at > is the most natural thing to do in Lisp. By going further to fixed-size > simple vectors, I save space by eliding the List spine, and also gain spe= ed > in direct random access to node elements. > > Just sayin=E2=80=A6 > > This all dates from years ago when I lifted the RB-Tree implementation > from the OCaml Standard Library. I have been using RB-Trees on/off for mo= re > than a decade. Their advantage is them being purely functional and > immutable. > > There is no purely functional hash-table design, but I fake it with a > sometimes mutable hash-table married to a A-list of additions, removals, > and updates. Every so often, I smash the A-list back and rebuild the > hash-table. > > And, on the other hand, I don=E2=80=99t need keys that have an ordering r= elation. > All they need is some notion of equality. > > > > On Jul 14, 2026, at 10:16, Martin Simmons <[email protected]> wrote: > > CLOS:GENERIC-FUNCTION-METHOD-COMBINATION > > > > --=20 Marco Antoniotti, Professor, Director tel. +39 - 02 64 48 79 01 DISCo, University of Milan-Bicocca U14 2043 http://dcb.disco.unimib.it Viale Sarca 336 I-20126 Milan (MI) ITALY REGAINS: https://regains.disco.unimib.it/ --0000000000007a1ddc0656a3e197 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <div dir=3D"ltr">Careful: if you use RB-trees you are getting=C2=A0logarith= mic operations.=C2=A0 Not expected constant.</div><br><div class=3D"gmail_q= uote gmail_quote_container"><div dir=3D"ltr" class=3D"gmail_attr">On Wed, J= ul 15, 2026 at 12:27=E2=80=AFPM David McClain (as dbm at refined-audiometri= cs dot com) <<a href=3D"mailto:[email protected]">lisp-hug@lispwork= s.com</a>> wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"ma= rgin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:= 1ex"><div>Actually=E2=80=A6 I misspoke.=C2=A0<div><br></div><div>I just inv= ented a purely functional hash table, using the RB-Trees as the container.= =C2=A0</div><div><br></div><div>I had stated that there were no such thing.= It was quite trivial to implement.<div><br id=3D"m_-7382914619168786246lin= eBreakAtBeginningOfMessage"><div><br><blockquote type=3D"cite"><div>On Jul = 14, 2026, at 12:11, David McClain (as dbm at refined-audiometrics dot com) = <<a href=3D"mailto:[email protected]" target=3D"_blank">lisp-hug@li= spworks.com</a>> wrote:</div><br><div><div>Well, thanks for that info. L= ooks like I missed all the documentation in the Hyperspec about CLOS. I=E2= =80=99ll go find it.<div><br></div><div>But something was sticking in the b= ack of my throat regarding the use of CLOS and =E2=80=9Cstrongly typed=E2= =80=9D code (as strong as Lisp allows).=C2=A0</div><div><br></div><div>I ha= d been using a class hierarchy to represent Red-Black Tree Nodes (an extant= NODE) and an EMPTY node. EMPTY was turned into a Singleton Instance class,= as per the example offered by Didier Verna.=C2=A0</div><div><br></div><div= >But the use of CLOS produces code that runs about 50x slower than using a = Hash-table. (I know, RB-Trees use ordered keys and hash-tables do not=E2=80= =A6) And so, after recasting my code into vector structs for extant nodes a= nd NIL for empty nodes,</div><div><br></div><div>From this:</div><div><br><= /div><div><div><font face=3D"Monaco">(defclass node (tree)</font></div><div= ><font face=3D"Monaco">=C2=A0 ((l =C2=A0:reader =C2=A0node-l</font></div><d= iv><font face=3D"Monaco">=C2=A0 =C2=A0 =C2=A0 =C2=A0:initarg :l</font></div= ><div><font face=3D"Monaco">=C2=A0 =C2=A0 =C2=A0 =C2=A0:type =C2=A0 =C2=A0t= ree)</font></div><div><font face=3D"Monaco">=C2=A0 =C2=A0(k =C2=A0:reader = =C2=A0node-k</font></div><div><font face=3D"Monaco">=C2=A0 =C2=A0 =C2=A0 = =C2=A0:reader =C2=A0node-key</font></div><div><font face=3D"Monaco">=C2=A0 = =C2=A0 =C2=A0 =C2=A0:initarg :k</font></div><div><font face=3D"Monaco">=C2= =A0 =C2=A0 =C2=A0 =C2=A0:initarg :key)</font></div><div><font face=3D"Monac= o">=C2=A0 =C2=A0(v =C2=A0:reader =C2=A0node-v</font></div><div><font face= =3D"Monaco">=C2=A0 =C2=A0 =C2=A0 =C2=A0:reader =C2=A0node-val</font></div><= div><font face=3D"Monaco">=C2=A0 =C2=A0 =C2=A0 =C2=A0:initarg :v</font></di= v><div><font face=3D"Monaco">=C2=A0 =C2=A0 =C2=A0 =C2=A0:initarg :val)</fon= t></div><div><font face=3D"Monaco">=C2=A0 =C2=A0(r =C2=A0:reader =C2=A0node= -r</font></div><div><font face=3D"Monaco">=C2=A0 =C2=A0 =C2=A0 =C2=A0:inita= rg :r</font></div><div><font face=3D"Monaco">=C2=A0 =C2=A0 =C2=A0 =C2=A0:ty= pe =C2=A0 =C2=A0tree)</font></div><div><font face=3D"Monaco">=C2=A0 =C2=A0(= h =C2=A0:reader =C2=A0node-h</font></div><div><font face=3D"Monaco">=C2=A0 = =C2=A0 =C2=A0 =C2=A0:reader =C2=A0height</font></div><div><font face=3D"Mon= aco">=C2=A0 =C2=A0 =C2=A0 =C2=A0:initarg :h</font></div><div><font face=3D"= Monaco">=C2=A0 =C2=A0 =C2=A0 =C2=A0:type =C2=A0 =C2=A0fixnum))</font></div>= <div><font face=3D"Monaco">=C2=A0 (:default-initargs</font></div><div><font= face=3D"Monaco">=C2=A0 =C2=A0:l +empty+</font></div><div><font face=3D"Mon= aco">=C2=A0 =C2=A0:r +empty+</font></div><div><font face=3D"Monaco">=C2=A0 = =C2=A0:h 1))</font></div></div><div><br></div><div><br></div><div>To this:<= /div><div><br></div><div><div><font face=3D"Monaco">(defstruct (node (:type= vector)</font></div><div><font face=3D"Monaco">=C2=A0 =C2=A0 =C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0(:constructor singleton-node (k v))</fon= t></div><div><font face=3D"Monaco">=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0(:constructor %create (l k v r h)))</font></div><di= v><font face=3D"Monaco">=C2=A0 l k v r (h 1))</font></div><div><br></div><d= iv><br></div></div><div><div>The RB-Trees code now runs only 20x slower tha= n Hash-tables. There is a 2x cost to using CLOS over bare untyped simple-ve= ctors.=C2=A0</div><div><br></div><div>One might argue that more fully typed= is preferable? But speed is also seductive. And why not? When we make Tree= s out of Lisp LISTs, there is no strong typing for them, and yet we happily= run with CONS Trees anyway. That is the most natural thing to do in Lisp. = By going further to fixed-size simple vectors, I save space by eliding the = List spine, and also gain speed in direct random access to node elements.</= div><div><br></div><div>Just sayin=E2=80=A6=C2=A0</div><div><br></div><div>= This all dates from years ago when I lifted the RB-Tree implementation from= the OCaml Standard Library. I have been using RB-Trees on/off for more tha= n a decade. Their advantage is them being purely functional and immutable.= =C2=A0</div><div><br></div><div>There is no purely functional hash-table de= sign, but I fake it with a sometimes mutable hash-table married to a A-list= of additions, removals, and updates. Every so often, I smash the A-list ba= ck and rebuild the hash-table. =C2=A0</div><div><br></div><div>And, on the = other hand, I don=E2=80=99t need keys that have an ordering relation. All t= hey need is some notion of equality.</div><div><br></div><div><br></div><di= v><br><blockquote type=3D"cite"><div>On Jul 14, 2026, at 10:16, Martin Simm= ons <<a href=3D"mailto:[email protected]" target=3D"_blank">martin@li= spworks.com</a>> wrote:</div><br><div><span style=3D"font-family:LucidaG= rande;font-size:14px;font-style:normal;font-variant-caps:normal;font-weight= :400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:= none;white-space:normal;word-spacing:0px;text-decoration:none;float:none;di= splay:inline">CLOS:GENERIC-FUNCTION-METHOD-COMBINATION</span></div></blockq= uote></div><br></div></div></div></blockquote></div><br></div></div></div><= /blockquote></div><div><br clear=3D"all"></div><br><span class=3D"gmail_sig= nature_prefix">-- </span><br><div dir=3D"ltr" class=3D"gmail_signature"><di= v dir=3D"ltr"><div><span style=3D"font-family:monospace">Marco Antoniotti, = Professor, Director =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 tel. +39 - 0= 2 64 48 79 01<br>DISCo, University of Milan-Bicocca U14 2043=C2=A0=C2=A0 <a= href=3D"http://dcb.disco.unimib.it" target=3D"_blank">http://dcb.disco.uni= mib.it</a><br>Viale Sarca 336<br>I-20126 Milan (MI) ITALY<br><br></span></d= iv><span style=3D"font-family:monospace">REGAINS: <a href=3D"https://regain= s.disco.unimib.it/" target=3D"_blank">https://regains.disco.unimib.it/</a><= br></span></div></div> --0000000000007a1ddc0656a3e197-- _______________________________________________ Lisp Hug - the mailing list for LispWorks users [email protected] http://www.lispworks.com/support/lisp-hug.html