Re: Finding the applicable methods...
"Robert Goldman (as rpgoldman at sift dot net)" <[email protected]> Tue, 14 Jul 2026 15:09:45 -0500
| Newsgroups | gmane.lisp.lispworks.general |
|---|---|
| Message-ID | <[email protected]> |
--=_MailMate_CFFBB2D9-C431-40A3-ACAB-8D2985E24091_= Content-Type: text/plain; charset=UTF-8; format=flowed; markup=markdown Content-Transfer-Encoding: 8bit Just curious -- does the `(:type vector)` in the `defstruct` speed things up? What's the factor of speedup over using `defstruct` without that? Thanks! On 14 Jul 2026, at 14:11, David McClain (as dbm at refined-audiometrics dot com) wrote: > Well, thanks for that info. Looks like I missed all the documentation > in the Hyperspec about CLOS. I’ll go find it. > > But something was sticking in the back of my throat regarding the use > of CLOS and “strongly typed” 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 > Instance 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…) 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 2x 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. 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. > > Just sayin… > > 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 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’t need keys that have an ordering > relation. 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 Robert P. Goldman Research Fellow Smart Information Flow Technologies (d/b/a SIFT, LLC) 319 N. First Ave., Suite 400 Minneapolis, MN 55401 Google Voice: (612) 326-3934 Cell: (612) 384-3454 Email: [email protected] --=_MailMate_CFFBB2D9-C431-40A3-ACAB-8D2985E24091_= Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable <!DOCTYPE html> <html> <head> <meta http-equiv=3D"Content-Type" content=3D"text/xhtml; charset=3Dutf-8"= > </head> <body><div style=3D"font-family: sans-serif;"><div class=3D"markdown" sty= le=3D"white-space: normal;"> <p dir=3D"auto">Just curious -- does the <code style=3D"margin: 0 0; padd= ing: 0 0.25em; border-radius: 3px; background-color: #F7F7F7;">(:type vec= tor)</code> in the <code style=3D"margin: 0 0; padding: 0 0.25em; border-= radius: 3px; background-color: #F7F7F7;">defstruct</code> speed things up= ? What's the factor of speedup over using <code style=3D"margin: 0 0; pa= dding: 0 0.25em; border-radius: 3px; background-color: #F7F7F7;">defstruc= t</code> without that?</p> <p dir=3D"auto">Thanks!</p> <p dir=3D"auto">On 14 Jul 2026, at 14:11, David McClain (as dbm at refine= d-audiometrics dot com) wrote:</p> <blockquote style=3D"margin: 0 0 5px; padding-left: 5px; border-left: 2px= solid #777777; color: #777777;"> <p dir=3D"auto">Well, thanks for that info. Looks like I missed all the d= ocumentation in the Hyperspec about CLOS. I=E2=80=99ll go find it.</p> <p dir=3D"auto">But something was sticking in the back of my throat regar= ding the use of CLOS and =E2=80=9Cstrongly typed=E2=80=9D code (as strong= as Lisp allows).</p> <p dir=3D"auto">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 S= ingleton Instance class, as per the example offered by Didier Verna.</p> <p dir=3D"auto">But the use of CLOS produces code that runs about 50x slo= wer 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 struc= ts for extant nodes and NIL for empty nodes,</p> <p dir=3D"auto">From this:</p> <p dir=3D"auto">(defclass node (tree)<br> ((l :reader node-l<br> :initarg :l<br> :type tree)<br> (k :reader node-k<br> :reader node-key<br> :initarg :k<br> :initarg :key)<br> (v :reader node-v<br> :reader node-val<br> :initarg :v<br> :initarg :val)<br> (r :reader node-r<br> :initarg :r<br> :type tree)<br> (h :reader node-h<br> :reader height<br> :initarg :h<br> :type fixnum))<br> (:default-initargs<br> :l +empty+<br> :r +empty+<br> :h 1))</p> <p dir=3D"auto">To this:</p> <p dir=3D"auto">(defstruct (node (:type vector)<br> (:constructor singleton-node (k v))<br> (:constructor %create (l k v r h)))<br> l k v r (h 1))</p> <p dir=3D"auto">The RB-Trees code now runs only 20x slower than Hash-tabl= es. There is a 2x cost to using CLOS over bare untyped simple-vectors.</p= > <p dir=3D"auto">One might argue that more fully typed is preferable? But = speed is also seductive. And why not? When we make Trees out of Lisp LIST= s, there is no strong typing for them, and yet we happily run with CONS T= rees anyway. That is the most natural thing to do in Lisp. By going furth= er to fixed-size simple vectors, I save space by eliding the List spine, = and also gain speed in direct random access to node elements.</p> <p dir=3D"auto">Just sayin=E2=80=A6</p> <p dir=3D"auto">This all dates from years ago when I lifted the RB-Tree i= mplementation from the OCaml Standard Library. I have been using RB-Trees= on/off for more than a decade. Their advantage is them being purely func= tional and immutable.</p> <p dir=3D"auto">There is no purely functional hash-table design, but I fa= ke it with a sometimes mutable hash-table married to a A-list of addition= s, removals, and updates. Every so often, I smash the A-list back and reb= uild the hash-table.</p> <p dir=3D"auto">And, on the other hand, I don=E2=80=99t need keys that ha= ve an ordering relation. All they need is some notion of equality.</p> <blockquote style=3D"margin: 0 0 5px; padding-left: 5px; border-left: 2px= solid #777777; border-left-color: #999999; color: #999999;"> <p dir=3D"auto">On Jul 14, 2026, at 10:16, Martin Simmons <a href=3D"mail= to:[email protected]" style=3D"color: #999999;">[email protected]</= a> wrote:</p> <p dir=3D"auto">CLOS:GENERIC-FUNCTION-METHOD-COMBINATION</p> </blockquote> </blockquote> <p dir=3D"auto">Robert P. Goldman<br> Research Fellow<br> Smart Information Flow Technologies (d/b/a SIFT, LLC)</p> <p dir=3D"auto">319 N. First Ave., Suite 400<br> Minneapolis, MN 55401</p> <p dir=3D"auto">Google Voice: (612) 326-3934<br> Cell: (612) 384-3454<br> Email: <a href=3D"mailto:[email protected]" style=3D"color: #3983C4;"= >[email protected]</a></p> </div> </div> </body> </html> --=_MailMate_CFFBB2D9-C431-40A3-ACAB-8D2985E24091_=-- _______________________________________________ Lisp Hug - the mailing list for LispWorks users [email protected] http://www.lispworks.com/support/lisp-hug.html