Re: Finding the applicable methods...
"David McClain (as dbm at refined-audiometrics dot com)" <[email protected]> Tue, 14 Jul 2026 14:19:39 -0700
| Newsgroups | gmane.lisp.lispworks.general |
|---|---|
| Message-ID | <[email protected]> |
--Apple-Mail=_1B0595E0-4E92-4D4D-8E68-29B05F3A6CE0
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
charset=utf-8
Answer: Roughly the same speedup, or just a hair faster, depending on =
how much variance you believe is real in a consumer machine.
Timings are on a ca. 2024 M4 iMac with 32 GB RAM.
I ran each of these tests 3 times and took the median reported values. =
No changes to the Hash-table code, and it runs 43% faster on this new =
Lisp session. So a fair amount of the timing variation must be due to =
other external factors.=20
Hence with the comparison between the two types of DEFSTRUCT, it is =
unclear whether or not the WITHOUT (:TYPE VECTOR) is really any faster =
than WITH. Here it shows a 27% speedup.,
The test is to take an empty table, and add 1,000,000 precomputed random =
single-float values as the key and the corresponding map value. So the =
only data generation comes from (AREF *PRECOMPUTED-RANDOM* IX).
I am tempted to conclude that there is no difference in speed, and a =
small=E2=80=99ish cost in memory using the DEFSTRUCT without the (:TYPE =
VECTOR).
;; Timing with (:TYPE VECTOR) NODE Struct:
;; =CE=BCs/add Alloc bytes Page Faults
;; ------ ----------- -----------
;; RB-Trees: 2.8 920 0.048
;; Hash-tables: 0.19 52 0.005
;;
;; Take away the (:TYPE VECTOR) in the NODE Struct:
;; RB-Trees: 2.2 1075 0.031
;; Hash-tables: 0.13 53 0.004
(defparameter *tst-coll*
(let ((arr (make-array 1_000_000
:element-type 'single-float)))
(dotimes (ix (length arr))
(setf (aref arr ix) (random 1f0)))
arr))
(defun tst ()
(let ((x (empty)))
(dotimes (ix (length *tst-coll*))
(addf x (aref *tst-coll* ix)))
(cardinal x)))
(time (tst))
(defun tsth ()
(let ((tbl (make-hash-table)))
(dotimes (ix (length *tst-coll*))
(setf (gethash (aref *tst-coll* ix) tbl) t))
tbl))
(time (tsth))
> On Jul 14, 2026, at 13:09, Robert Goldman (as rpgoldman at sift dot =
net) <[email protected]> wrote:
>=20
> Just curious -- does the (:type vector) in the defstruct speed things =
up? What's the factor of speedup over using defstruct without that?
>=20
> Thanks!
>=20
> On 14 Jul 2026, at 14:11, David McClain (as dbm at =
refined-audiometrics dot com) 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
> 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,
>=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
> 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
> 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.
>=20
> 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.
>=20
> On Jul 14, 2026, at 10:16, Martin Simmons [email protected] =
<mailto:[email protected]> wrote:
>=20
> CLOS:GENERIC-FUNCTION-METHOD-COMBINATION
>=20
> Robert P. Goldman
> Research Fellow
> Smart Information Flow Technologies (d/b/a SIFT, LLC)
>=20
> 319 N. First Ave., Suite 400
> Minneapolis, MN 55401
>=20
> Google Voice: (612) 326-3934
> Cell: (612) 384-3454
> Email: [email protected] <mailto:[email protected]>
--Apple-Mail=_1B0595E0-4E92-4D4D-8E68-29B05F3A6CE0
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;">Answer: Roughly the same speedup, or =
just a hair faster, depending on how much variance you believe is real =
in a consumer machine.<div><br></div><div>Timings are on a ca. 2024 M4 =
iMac with 32 GB RAM.</div><div><br></div><div>I ran each of these tests =
3 times and took the median reported values. No changes to the =
Hash-table code, and it runs 43% faster on this new Lisp session. So a =
fair amount of the timing variation must be due to other external =
factors. </div><div><br></div><div>Hence with the comparison =
between the two types of DEFSTRUCT, it is unclear whether or not the =
WITHOUT (:TYPE VECTOR) is really any faster than WITH. Here it shows a =
27% speedup.,</div><div><br></div><div>The test is to take an empty =
table, and add 1,000,000 precomputed random single-float values as the =
key and the corresponding map value. So the only data generation comes =
from (AREF *PRECOMPUTED-RANDOM* IX).</div><div><br></div><div>I am =
tempted to conclude that there is no difference in speed, and a =
small=E2=80=99ish cost in memory using the DEFSTRUCT without the (:TYPE =
VECTOR).</div><div><br></div><div><br></div><div><div><div><font =
face=3D"Monaco">;; Timing with (:TYPE VECTOR) NODE =
Struct:</font></div><div><font face=3D"Monaco">;; =
=CE=BCs/add Alloc bytes =
Page Faults</font></div><div><font face=3D"Monaco">;; =
------ =
----------- -----------</font></div><div><font =
face=3D"Monaco">;; RB-Trees: 2.8 =
920 =
0.048</font></div><div><font face=3D"Monaco">;; Hash-tables: 0.19 =
52 =
0.005</font></div><div><font =
face=3D"Monaco">;;</font></div><div><font face=3D"Monaco">;; Take away =
the (:TYPE VECTOR) in the NODE Struct:</font></div><div><font =
face=3D"Monaco">;; RB-Trees: 2.2 =
1075 =
0.031</font></div><div><font face=3D"Monaco">;; Hash-tables: 0.13 =
53 =
0.004</font></div><div><font =
face=3D"Monaco"><br></font></div><div><font =
face=3D"Monaco"><br></font></div><div><div><font =
face=3D"Monaco">(defparameter *tst-coll*</font></div><div><font =
face=3D"Monaco"> (let ((arr (make-array =
1_000_000</font></div><div><font face=3D"Monaco"> =
=
:element-type 'single-float)))</font></div><div><font =
face=3D"Monaco"> (dotimes (ix (length =
arr))</font></div><div><font face=3D"Monaco"> (setf =
(aref arr ix) (random 1f0)))</font></div><div><font face=3D"Monaco"> =
arr))</font></div><div><font =
face=3D"Monaco"><br></font></div><div><font face=3D"Monaco">(defun tst =
()</font></div><div><font face=3D"Monaco"> (let ((x =
(empty)))</font></div><div><font face=3D"Monaco"> (dotimes =
(ix (length *tst-coll*))</font></div><div><font face=3D"Monaco"> =
(addf x (aref *tst-coll* ix)))</font></div><div><font =
face=3D"Monaco"> (cardinal x)))</font></div><div><font =
face=3D"Monaco"><br></font></div><div><font face=3D"Monaco">(time =
(tst))</font></div><div><font face=3D"Monaco"><br></font></div><div><font =
face=3D"Monaco">(defun tsth ()</font></div><div><font =
face=3D"Monaco"> (let ((tbl =
(make-hash-table)))</font></div><div><font face=3D"Monaco"> =
(dotimes (ix (length *tst-coll*))</font></div><div><font =
face=3D"Monaco"> (setf (gethash (aref *tst-coll* ix) =
tbl) t))</font></div><div><font face=3D"Monaco"> =
tbl))</font></div><div><font face=3D"Monaco"><br></font></div><div><font =
face=3D"Monaco">(time =
(tsth))</font></div></div><div><br></div><div><br></div><blockquote =
type=3D"cite"><div>On Jul 14, 2026, at 13:09, Robert Goldman (as =
rpgoldman at sift dot net) <[email protected]> =
wrote:</div><br class=3D"Apple-interchange-newline"><div>
<meta http-equiv=3D"Content-Type" content=3D"text/xhtml; charset=3Dutf-8">=
<div><div style=3D"font-family: sans-serif;"><div class=3D"markdown" =
style=3D"white-space: normal;"><p dir=3D"auto">Just curious -- does the =
<code style=3D"margin: 0 0; padding: 0 0.25em; border-radius: 3px; =
background-color: #F7F7F7;">(:type vector)</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; padding: 0 =
0.25em; border-radius: 3px; background-color: #F7F7F7;">defstruct</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 refined-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 documentation 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 regarding 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 =
Singleton 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 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,</p><p =
dir=3D"auto">=46rom 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-tables. 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 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.</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 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.</p><p dir=3D"auto">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.</p><p dir=3D"auto">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.</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"mailto:[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>
</div>
</div></blockquote></div><br></div></body></html>=
--Apple-Mail=_1B0595E0-4E92-4D4D-8E68-29B05F3A6CE0--
_______________________________________________
Lisp Hug - the mailing list for LispWorks users
[email protected]
http://www.lispworks.com/support/lisp-hug.html