Hash tables multiple keys per value...?
in [Lisp]
|
From: Madhu on 18 Jan 2010 10:25 * Robert Uhl <m3iqaz8n3l.fsf(a)latakia.octopodial-chrome.com> : Wrote on Mon, 18 Jan 2010 08:11:10 -0700: | "Frode V. Fjeld" <frode(a)netfonds.no> writes: |> |> I.e. to hash over some combination of each key's sxhash (taking care |> not to combine them so as to generate a bignum). | | Note that SXHASH doesn't care about anything more than the top level | of a list: | | cl-user> (sxhash '(1 2 3 (4))) | 224526978 | cl-user> (sxhash '(1 2 3 (4 5))) | 224526978 I believe Frodef was suggesting you should do something like: * (reduce 'logior '(1 2 3 (4)) :key #'sxhash) 1031 * (reduce 'logior '(1 2 3 (4 5)) :key #'sxhash) 526343 -- Madhu
From: Pillsy on 18 Jan 2010 11:46 On Jan 18, 3:14 am, Tamas K Papp <tkp...(a)gmail.com> wrote: > On Sun, 17 Jan 2010 23:37:26 +0200, Captain Obvious wrote: [...] > > Now my version is faster by whopping 7%! > Nope. If you do a shitload of lookups, you just inline the bloody > thing. This is good advice, but if inlining isn't an option for some reason, you have another route which also involves just a single declaration and eliminates consing: the DYNAMIC-EXTENT declaration. I tried three versions of the hash lookup, without inlining, on SBCL 1.0.21 (gee, maybe it's time to upgrade?) ;;; lookup-test.lisp (declaim (optimize speed)) (defun simple-lookup (ht k1 k2) (gethash (cons k1 k2) ht)) (progn (let ((the-cons (cons nil nil))) (defun ugly-lookup (ht k1 k2) (setf (car the-cons) k1 (cdr the-cons) k2) (gethash the-cons ht)))) (defun dx-lookup (ht k1 k2) (let ((the-cons (cons k1 k2))) (declare (dynamic-extent the-cons)) (gethash the-cons ht))) (progn (defparameter *ht* (make-hash-table :test #'equal)) (setf (gethash (cons 5 10) *ht*) 10)) (defmacro deftest (name fn) `(defun ,name () (time (dotimes (i 10000000) (,fn *ht* 5 10))))) (deftest test-simple-lookup simple-lookup) (deftest test-ugly-lookup ugly-lookup) (deftest test-dx-lookup dx-lookup) ; compiling file "/Users/mtp/lisp/lookup-test.lisp" (written 18 JAN 2010 11:40:01 AM): ; /Users/mtp/lisp/lookup-test.fasl written ; compilation finished in 0:00:00 NIL CL-USER> (test-simple-lookup) Evaluation took: 1.813 seconds of real time 1.799895 seconds of total run time (1.784424 user, 0.015471 system) [ Run times consist of 0.031 seconds GC time, and 1.769 seconds non- GC time. ] 99.28% CPU 3,917,843,462 processor cycles 79,998,984 bytes consed NIL CL-USER> (test-ugly-lookup) Evaluation took: 3.432 seconds of real time 3.407829 seconds of total run time (3.396038 user, 0.011791 system) 99.30% CPU 7,418,751,288 processor cycles 5,008 bytes consed NIL CL-USER> (test-dx-lookup) Evaluation took: 1.755 seconds of real time 1.745271 seconds of total run time (1.736452 user, 0.008819 system) 99.43% CPU 3,794,412,856 processor cycles 0 bytes consed DX-LOOKUP is a tiny bit faster than SIMPLE-LOOKUP, and does no consing, just like UGLY-LOOKUP, all by adding a single declaration that expresses its intent very clearly. Cheers, Pillsy
From: Frode V. Fjeld on 18 Jan 2010 12:04 Madhu <enometh(a)meer.net> writes: > I believe Frodef was suggesting you should do something like: > > * (reduce 'logior '(1 2 3 (4)) :key #'sxhash) > 1031 Actually this is precisely what I wrote originally before I substituted (sxhash keys). But like I said there are several considerations to make here, most of which are dependant on the application's requirements and the (performance) characteristics of the lisp implementation. -- Frode V. Fjeld
From: Tamas K Papp on 18 Jan 2010 12:12 On Mon, 18 Jan 2010 08:46:57 -0800, Pillsy wrote: > On Jan 18, 3:14 am, Tamas K Papp <tkp...(a)gmail.com> wrote: >> On Sun, 17 Jan 2010 23:37:26 +0200, Captain Obvious wrote: > [...] >> > Now my version is faster by whopping 7%! > >> Nope. If you do a shitload of lookups, you just inline the bloody >> thing. > > This is good advice, but if inlining isn't an option for some reason, > you have another route which also involves just a single declaration and > eliminates consing: the DYNAMIC-EXTENT declaration. > > I tried three versions of the hash lookup, without inlining, on SBCL > 1.0.21 (gee, maybe it's time to upgrade?) Probably :-) > DX-LOOKUP is a tiny bit faster than SIMPLE-LOOKUP, and does no consing, > just like UGLY-LOOKUP, all by adding a single declaration that expresses > its intent very clearly. I rarely (if ever) use dynamic extend declarations in SBCL, it is usually pretty good at figuring out stuff. Well, maybe not always, but generally it is not worth even thinking about these things. Anyhow, I think that we have pretty much beaten this example to death. Also, AFAIK in SBCL gethash caches the last key, so we are testing the cost of an equality comparison. In real life the cost of finding a different key each time in the table would most likely dominate. Tamas
From: Robert Uhl on 18 Jan 2010 13:04
Madhu <enometh(a)meer.net> writes: > | > | Note that SXHASH doesn't care about anything more than the top level > | of a list: > | > | cl-user> (sxhash '(1 2 3 (4))) > | 224526978 > | cl-user> (sxhash '(1 2 3 (4 5))) > | 224526978 > > I believe Frodef was suggesting you should do something like: > > * (reduce 'logior '(1 2 3 (4)) :key #'sxhash) > 1031 > > * (reduce 'logior '(1 2 3 (4 5)) :key #'sxhash) > 526343 And yet: cl-user> (reduce 'logior '(1 2 3 (4 5 6 (6 7))) :key #'sxhash) 501984895 cl-user> (reduce 'logior '(1 2 3 (4 5 6 (6 7 8))) :key #'sxhash) 501984895 The basic issue is that SXHASH really isn't the right tool for the job--the guarantees that the standard gives aren't good enough for generating a unique key, which is what's needed to key a hashtable. That makes sense, since SXHASH is meant to _hash_ a unique key, and collisions are expected. -- Robert A. Uhl Wilner's Observation: All conversations with a potato should be conducted in private. |