From: Juho S. <js...@ik...> - 2004-05-11 11:50:23
Attachments:
sbcl-symbol-hash.patch
|
The attached patch changes the initialization of symbol-hash-slot to be based on the symbol's name instead of being generated randomly. This allows SBCL to use SYMBOL-HASH for implementing SXHASH for symbols (ANSI requires that the SXHASHes of similar symbols should be consistent between different Lisp images of the same implementation). This gives some reasonable performance improvements in the compiler: Benchmark Reference 0.8.10.17 0.8.10.17-js1 ------------------------------------------------------------------------ COMPILER [ 38.90|0.13] 1.00|0.0034 0.94|0.0046 Note that the patched version also had some changes to CLRHASH that I'm going to post soon, which account for about a fourth of the improvement (at least that's what the effect was on an earlier version; I didn't test the changes separately on 0.8.10.17). Problems: - x86 only, since other architectures don't support SYMBOL-HASH. I've seen some vague references in source code comments, mailing list archives and blogs about SYMBOL-HASH being only meant for GEN(C)GC, but everyone seems to have forgotten the details. - Somewhat kludgy. - Makes MAKE-SYMBOL slower by 50%-100%. Some of the lost performance might regained by inlining or other optimizations, but since MAKE-SYMBOL seems like a rather unlikely bottleneck I didn't look into it. -- Juho Snellman |
From: Christophe R. <cs...@ca...> - 2004-05-12 11:57:00
|
Juho Snellman <js...@ik...> writes: > - x86 only, since other architectures don't support SYMBOL-HASH. > I've seen some vague references in source code comments, mailing > list archives and blogs about SYMBOL-HASH being only meant for > GEN(C)GC, but everyone seems to have forgotten the details. Given that the non-x86 name for that slot is "unused", it ought to be possible to make it contain the hash value... > - Makes MAKE-SYMBOL slower by 50%-100%. Some of the lost performance > might regained by inlining or other optimizations, but since > MAKE-SYMBOL seems like a rather unlikely bottleneck I didn't > look into it. What would the effect be of altering sxhash on symbols to (let ((result (symbol-hash symbol))) (if (minusp result) (setf (symbol-hash symbol) (%sxhash-simple-substring ...)) result)) ? In other words, to cache the hash value at the first call to sxhash, so that throwaway symbols don't incur the penalty? > --- src/code/sxhash.lisp 15 Sep 2003 09:21:38 -0000 1.5 > +++ src/code/sxhash.lisp 10 May 2004 21:31:21 -0000 > @@ -104,6 +104,5 @@ > (deftransform sxhash ((x) (symbol)) > (if #+sb-xc-host nil #-sb-xc-host (constant-lvar-p x) > (sxhash (lvar-value x)) While we're at it, are there any calls to sxhash on constant symbols within the system? If there are, then this could be replaced by (if (constant-lvar-p x) #+sb-xc-host '(load-time-value (sxhash (lvar-value x))) #-sb-xc-host (sxhash (lvar-value x)) <non-constant case>) > - '(%sxhash-simple-string (symbol-name x)))) > - > + '(symbol-hash x))) Cheers, Christophe -- http://www-jcsu.jesus.cam.ac.uk/~csr21/ +44 1223 510 299/+44 7729 383 757 (set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b))) (defvar b "~&Just another Lisp hacker~%") (pprint #36rJesusCollegeCambridge) |
From: Juho S. <js...@ik...> - 2004-05-13 16:55:23
Attachments:
sbcl-symbol-hash.patch
|
On Wed, May 12, 2004 at 12:54:37PM +0100, Christophe Rhodes wrote: > What would the effect be of altering sxhash on symbols to > (let ((result (symbol-hash symbol))) > (if (minusp result) > (setf (symbol-hash symbol) (%sxhash-simple-substring ...)) > result)) > ? In other words, to cache the hash value at the first call to > sxhash, so that throwaway symbols don't incur the penalty? Good idea, I tried something along those lines (main difference being the use of 0 instead of a negative value for the uninitialized values). The difference in compiler performance is small enough to qualify as noise, and as expected it removes the problems with MAKE-SYMBOL. More importantly the rest of the code is cleaner this way. Updated patch attached. > While we're at it, are there any calls to sxhash on constant symbols > within the system? If there are, then this could be replaced by > (if (constant-lvar-p x) > #+sb-xc-host '(load-time-value (sxhash (lvar-value x))) > #-sb-xc-host (sxhash (lvar-value x)) > <non-constant case>) > > - '(%sxhash-simple-string (symbol-name x)))) > > - > > + '(symbol-hash x))) I don't think there are any calls to SXHASH on constant anything in the system. -- Juho Snellman |
From: Christophe R. <cs...@ca...> - 2004-05-20 11:18:58
|
Juho Snellman <js...@ik...> writes: > On Wed, May 12, 2004 at 12:54:37PM +0100, Christophe Rhodes wrote: >> What would the effect be of altering sxhash on symbols to >> (let ((result (symbol-hash symbol))) >> (if (minusp result) >> (setf (symbol-hash symbol) (%sxhash-simple-substring ...)) >> result)) >> ? In other words, to cache the hash value at the first call to >> sxhash, so that throwaway symbols don't incur the penalty? > > Good idea, I tried something along those lines (main difference being > the use of 0 instead of a negative value for the uninitialized > values). The difference in compiler performance is small enough to > qualify as noise, and as expected it removes the problems with > MAKE-SYMBOL. More importantly the rest of the code is cleaner this > way. > > Updated patch attached. It looks mostly good. Does it work on NIL? (I confess I can't see how it does). NIL's symbol-hash slot doesn't contain a fixnum, so it would seem to me that if it works on NIL, it only works by accident -- but maybe I'm missing something. Cheers, Christophe -- http://www-jcsu.jesus.cam.ac.uk/~csr21/ +44 1223 510 299/+44 7729 383 757 (set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b))) (defvar b "~&Just another Lisp hacker~%") (pprint #36rJesusCollegeCambridge) |
From: Juho S. <js...@ik...> - 2004-05-20 19:10:28
|
On Thu, May 20, 2004 at 06:20:43PM +0100, Christophe Rhodes wrote: > The attached works on alpha. Before I go ahead and generalise to > sparc, could you check that it still works on x86? I've deleted a > bunch of stuff from the backend that I think isn't necessary, but it > would be nice to have that confirmed... Works for me. > +;;; FIXME: is this necessary? > +(defknown %set-symbol-hash (symbol (integer 0 #.sb!xc:most-positive-fixnum)) > + t (unsafe)) At least making it known in some way is neccessary. But perhaps it's better to use :set-known on the slot definition since you replaced the VOP with a setter? -- Juho Snellman |
From: Christophe R. <cs...@ca...> - 2004-05-21 12:31:27
|
Juho Snellman <js...@ik...> writes: > On Thu, May 20, 2004 at 06:20:43PM +0100, Christophe Rhodes wrote: >> The attached works on alpha. Before I go ahead and generalise to >> sparc, could you check that it still works on x86? I've deleted a >> bunch of stuff from the backend that I think isn't necessary, but it >> would be nice to have that confirmed... > > Works for me. OK. I have committed this in sbcl-0.8.10.43, noting in passing that it's much nicer on non-x86 machines than it is on x86s. For those of you who think differently, you may wish to note that this version will not build on PowerPC; an implementation of the SYMBOL-HASH VOP (in src/compiler/*/cell.lisp) is required for this backend. Tested patches welcome. Cheers, Christophe -- http://www-jcsu.jesus.cam.ac.uk/~csr21/ +44 1223 510 299/+44 7729 383 757 (set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b))) (defvar b "~&Just another Lisp hacker~%") (pprint #36rJesusCollegeCambridge) |
From: David S. <da...@da...> - 2004-05-22 18:23:37
|
Christophe Rhodes <cs...@ca...> writes: > For those of you who think differently, you may wish to note that this > version will not build on PowerPC; an implementation of the > SYMBOL-HASH VOP (in src/compiler/*/cell.lisp) is required for this > backend. Tested patches welcome. $ sbcl This is SBCL 0.8.10.44, an implementation of ANSI Common Lisp. More information about SBCL is available at <http://www.sbcl.org/>. SBCL is free software, provided as is, with absolutely no warranty. It is mostly in the public domain; some portions are provided under BSD-style licenses. See the CREDITS and COPYING files in the distribution for more information. ; loading system definition from ; #P"/Users/david/usr/lib/sbcl/systems/sb-bsd-sockets.asd" into ; #<PACKAGE "ASDF2745"> ; registering #<SYSTEM SB-BSD-SOCKETS {489D77A9}> as SB-BSD-SOCKETS ; registering #<SYSTEM SB-BSD-SOCKETS-TESTS {40116461}> as SB-BSD-SOCKETS-TESTS ; loading system definition from ; #P"/Users/david/usr/lib/sbcl/systems/sb-posix.asd" into #<PACKAGE "ASDF2845"> ; registering #<SYSTEM SB-POSIX {40A5AC59}> as SB-POSIX ; registering #<SYSTEM SB-POSIX-TESTS {40B8FB99}> as SB-POSIX-TESTS * (sxhash 'foo) 361886622 * (sb-kernel::symbol-hash 'foo) 361886622 * (sb-kernel::symbol-hash 'nil) 33554434 * (quit) david@interloper:~/usr/src/sbcl $ cvs diff -u src/compiler/ppc/cell.lisp Index: src/compiler/ppc/cell.lisp =================================================================== RCS file: /cvsroot/sbcl/sbcl/src/compiler/ppc/cell.lisp,v retrieving revision 1.3 diff -u -r1.3 cell.lisp --- src/compiler/ppc/cell.lisp 10 Nov 2003 23:26:38 -0000 1.3 +++ src/compiler/ppc/cell.lisp 22 May 2004 17:41:54 -0000 @@ -83,6 +83,19 @@ (:policy :fast) (:translate symbol-value)) +(define-vop (symbol-hash) + (:policy :fast-safe) + (:translate symbol-hash) + (:args (symbol :scs (descriptor-reg))) + (:results (res :scs (any-reg))) + (:result-types positive-fixnum) + (:generator 2 + ;; The symbol-hash slot of NIL holds NIL because it is also the + ;; cdr slot, so we have to strip off the two low bits to make sure + ;; it is a fixnum. The lowtag selection magic that is required to + ;; ensure this is explained in the comment in objdef.lisp + (loadw res symbol symbol-hash-slot other-pointer-lowtag) + (inst clrrwi res res (1- n-lowtag-bits)))) ;;;; Fdefinition (fdefn) objects. -- I wouldn't mind the rat race so much if it wasn't for all the damn cats. |
From: Christophe R. <cs...@ca...> - 2004-05-22 22:38:07
|
David Steuber <da...@da...> writes: > * (sxhash 'foo) > 361886622 > * (sb-kernel::symbol-hash 'foo) > 361886622 > * (sb-kernel::symbol-hash 'nil) > 33554434 Thank you. I've merged this into sbcl-0.8.10.48. Cheers, Christophe -- http://www-jcsu.jesus.cam.ac.uk/~csr21/ +44 1223 510 299/+44 7729 383 757 (set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b))) (defvar b "~&Just another Lisp hacker~%") (pprint #36rJesusCollegeCambridge) |