Re: Finding the applicable methods...
"David McClain (as dbm at refined-audiometrics dot com)" <[email protected]> Tue, 14 Jul 2026 12:11:14 -0700
| Newsgroups | gmane.lisp.lispworks.general |
|---|---|
| Message-ID | <[email protected]> |
--Apple-Mail=_51E81477-48EF-4C71-947B-90DB2BDEF517
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
charset=utf-8
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).=20
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.=20
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,
=46rom 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.=20
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=E2=80=A6=20
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.=20
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. =20
And, on the other hand, I don=E2=80=99t 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:
>=20
> CLOS:GENERIC-FUNCTION-METHOD-COMBINATION
--Apple-Mail=_51E81477-48EF-4C71-947B-90DB2BDEF517
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html;
charset=utf-8
<html aria-label=3D"message body"><head><meta http-equiv=3D"content-type" =
content=3D"text/html; charset=3Dutf-8"></head><body =
style=3D"overflow-wrap: break-word; -webkit-nbsp-mode: space; =
line-break: after-white-space;">Well, thanks for that info. Looks 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 back of =
my throat regarding the use of CLOS and =E2=80=9Cstrongly typed=E2=80=9D =
code (as strong as Lisp allows). </div><div><br></div><div>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. </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 and NIL for empty =
nodes,</div><div><br></div><div>=46rom =
this:</div><div><br></div><div><div><font face=3D"Monaco">(defclass node =
(tree)</font></div><div><font face=3D"Monaco"> ((l :reader =
node-l</font></div><div><font face=3D"Monaco"> =
:initarg :l</font></div><div><font face=3D"Monaco"> =
:type tree)</font></div><div><font =
face=3D"Monaco"> (k :reader =
node-k</font></div><div><font face=3D"Monaco"> =
:reader node-key</font></div><div><font face=3D"Monaco"> =
:initarg :k</font></div><div><font =
face=3D"Monaco"> :initarg =
:key)</font></div><div><font face=3D"Monaco"> (v =
:reader node-v</font></div><div><font face=3D"Monaco"> =
:reader node-val</font></div><div><font =
face=3D"Monaco"> :initarg =
:v</font></div><div><font face=3D"Monaco"> =
:initarg :val)</font></div><div><font face=3D"Monaco"> =
(r :reader node-r</font></div><div><font =
face=3D"Monaco"> :initarg =
:r</font></div><div><font face=3D"Monaco"> =
:type tree)</font></div><div><font =
face=3D"Monaco"> (h :reader =
node-h</font></div><div><font face=3D"Monaco"> =
:reader height</font></div><div><font face=3D"Monaco"> =
:initarg :h</font></div><div><font =
face=3D"Monaco"> :type =
fixnum))</font></div><div><font face=3D"Monaco"> =
(:default-initargs</font></div><div><font face=3D"Monaco"> =
:l +empty+</font></div><div><font face=3D"Monaco"> :r =
+empty+</font></div><div><font face=3D"Monaco"> :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"> =
(:constructor =
singleton-node (k v))</font></div><div><font face=3D"Monaco"> =
(:constructor =
%create (l k v r h)))</font></div><div><font face=3D"Monaco"> l k =
v r (h 1))</font></div><div><br></div><div><br></div></div><div><div>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. </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 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.</div><div><br></div><div>Just =
sayin=E2=80=A6 </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 than a decade. Their =
advantage is them being purely functional and =
immutable. </div><div><br></div><div>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. =
</div><div><br></div><div>And, on the other hand, I don=E2=80=99t =
need keys that have an ordering relation. All they need is some notion =
of equality.</div><div><br></div><div><br></div><div><br><blockquote =
type=3D"cite"><div>On Jul 14, 2026, at 10:16, Martin Simmons =
<[email protected]> wrote:</div><br =
class=3D"Apple-interchange-newline"><div><span style=3D"caret-color: =
rgb(0, 0, 0); font-family: LucidaGrande; font-size: 14px; font-style: =
normal; font-variant-caps: normal; font-weight: 400; letter-spacing: =
normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: =
none; white-space: normal; widows: 2; word-spacing: 0px; =
-webkit-text-stroke-width: 0px; text-decoration: none; float: none; =
display: inline =
!important;">CLOS:GENERIC-FUNCTION-METHOD-COMBINATION</span></div></blockq=
uote></div><br></div></body></html>=
--Apple-Mail=_51E81477-48EF-4C71-947B-90DB2BDEF517--
_______________________________________________
Lisp Hug - the mailing list for LispWorks users
[email protected]
http://www.lispworks.com/support/lisp-hug.html