Re: Finding the applicable methods...
"David McClain (as dbm at refined-audiometrics dot com)" <[email protected]> Wed, 15 Jul 2026 03:25:08 -0700
| Newsgroups | gmane.lisp.lispworks.general |
|---|---|
| Message-ID | <[email protected]> |
--Apple-Mail=_94B117C3-62D6-40EF-8241-506BD758A253 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=utf-8 Actually=E2=80=A6 I misspoke.=20 I just invented a purely functional hash table, using the RB-Trees as = the container.=20 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: >=20 > Well, thanks for that info. Looks like I missed all the documentation = in the Hyperspec about CLOS. I=E2=80=99ll go find it. >=20 > 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 >=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 >=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, >=20 > =46rom this: >=20 > (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)) >=20 >=20 > To this: >=20 > (defstruct (node (:type vector) > (:constructor singleton-node (k v)) > (:constructor %create (l k v r h))) > l k v r (h 1)) >=20 >=20 > 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 >=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. >=20 > Just sayin=E2=80=A6=20 >=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 >=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 >=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. >=20 >=20 >=20 >> On Jul 14, 2026, at 10:16, Martin Simmons <[email protected]> = wrote: >>=20 >> CLOS:GENERIC-FUNCTION-METHOD-COMBINATION >=20 --Apple-Mail=_94B117C3-62D6-40EF-8241-506BD758A253 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;">Actually=E2=80=A6 I = misspoke. <div><br></div><div>I just invented a purely functional = hash table, using the RB-Trees as the = container. </div><div><br></div><div>I had stated that there were = no such thing. It was quite trivial to implement.<div><br = id=3D"lineBreakAtBeginningOfMessage"><div><br><blockquote = type=3D"cite"><div>On Jul 14, 2026, at 12:11, David McClain (as dbm at = refined-audiometrics dot com) <[email protected]> = wrote:</div><br class=3D"Apple-interchange-newline"><div><meta = http-equiv=3D"content-type" content=3D"text/html; charset=3Dutf-8"><div = 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></div></div></blockquote></div><br></div></div></body= ></html>= --Apple-Mail=_94B117C3-62D6-40EF-8241-506BD758A253-- _______________________________________________ Lisp Hug - the mailing list for LispWorks users [email protected] http://www.lispworks.com/support/lisp-hug.html