From: JTK <je...@gm...> - 2015-06-26 00:04:19
|
Apologies if this is an inane question, but is the following intended? cl-user> (lisp-implementation-version) "1.2.11" cl-user> (sxhash #(2)) 1193941381096739655 cl-user> (sxhash #(1 2)) 1193941381096739655 cl-user> (sxhash #(3 1 2)) 1193941381096739655 cl-user> (sxhash #()) 1193941381096739655 cl-user> (sxhash (vector "bunny")) 1193941381096739655 Admittedly, it conforms with CLHS http://www.lispworks.com/documentation/lw61/CLHS/Body/f_sxhash.htm <http://www.lispworks.com/documentation/lw61/CLHS/Body/f_sxhash.htm> It comes from target-sxhash.lisp where (array ;; case of array (typecase x (simple-string (sxhash x)) ; through DEFTRANSFORM ;;; falls through to here (t (logxor 191020317 (sxhash (array-rank x)))))) So every 1d array has the same sxhash. Is there a reason the first few elements aren’t used, like for a list? |
From: James Y K. <fo...@fu...> - 2015-06-26 01:36:57
|
Yes, this is basically a stupidity in the CL spec. sxhash can only use parts of the object which are immutable, if equal does an identity (eq) comparison for that type. "The hash-code for an object is always the same within a single session provided that the object is not visibly modified with regard to the equivalence test equal." And since arrays are for some illogical reason not compared by content with equal (while lists are) neither may sxhash use the content of an array. The behavior of equal truly makes no sense, but there you are... The address of the object could be returned by sxhash, except that sbcl has a moving GC, so the address doesn't stay constant. So that's out. So really the only alternative would be for sbcl to allocate an extra word of memory to store an sxhash value for objects that are compared by identity with equal. But that would be kinda a waste of memory. So it doesn't. On June 25, 2015 8:04:12 PM EDT, JTK <je...@gm...> wrote: > > >Apologies if this is an inane question, but is the following intended? > >cl-user> (lisp-implementation-version) >"1.2.11" >cl-user> (sxhash #(2)) >1193941381096739655 >cl-user> (sxhash #(1 2)) >1193941381096739655 >cl-user> (sxhash #(3 1 2)) >1193941381096739655 >cl-user> (sxhash #()) >1193941381096739655 >cl-user> (sxhash (vector "bunny")) >1193941381096739655 > >Admittedly, it conforms with CLHS >http://www.lispworks.com/documentation/lw61/CLHS/Body/f_sxhash.htm ><http://www.lispworks.com/documentation/lw61/CLHS/Body/f_sxhash.htm> > >It comes from target-sxhash.lisp where > > >(array ;; case of array > (typecase x > (simple-string (sxhash x)) ; through DEFTRANSFORM > ;;; falls through to here > (t (logxor 191020317 (sxhash (array-rank x)))))) > > >So every 1d array has the same sxhash. Is there a reason the first few >elements aren’t used, >like for a list? > >------------------------------------------------------------------------ > >------------------------------------------------------------------------------ >Monitor 25 network devices or servers for free with OpManager! >OpManager is web-based network management software that monitors >network devices and physical & virtual servers, alerts via email & sms >for fault. Monitor 25 devices for free with no restriction. Download >now >http://ad.doubleclick.net/ddm/clk/292181274;119417398;o > >------------------------------------------------------------------------ > >_______________________________________________ >Sbcl-devel mailing list >Sbc...@li... >https://lists.sourceforge.net/lists/listinfo/sbcl-devel |
From: Jean-Philippe P. <hex...@gm...> - 2015-06-26 04:37:46
|
"And since arrays are for some illogical reason not compared by content with equal (while lists are) neither may sxhash use the content of an array. The behavior of equal truly makes no sense, but there you are..." I think it's slightly inaccurate and/or misleading to say that EQUAL "compares lists by content". EQUAL recursively compares the CARs and CDRs of conses, which just happens to be a fairly similar behavior to "comparing lists by content". I think treating lists and vectors/arrays differently makes a bit more sense in that context. Perhaps. (And I'm sure there are other good arguments in favor of what the CLHS prescribes.) (CLHS EQUAL, for reference: http://www.lispworks.com/documentation/HyperSpec/Body/f_equal.htm) On Thu, Jun 25, 2015 at 9:07 PM, James Y Knight <fo...@fu...> wrote: > Yes, this is basically a stupidity in the CL spec. > > sxhash can only use parts of the object which are immutable, if equal does > an identity (eq) comparison for that type. > > "The hash-code for an object is always the same within a single session > provided that the object is not visibly modified with regard to the > equivalence test equal." > > And since arrays are for some illogical reason not compared by content > with equal (while lists are) neither may sxhash use the content of an > array. The behavior of equal truly makes no sense, but there you are... > > The address of the object could be returned by sxhash, except that sbcl > has a moving GC, so the address doesn't stay constant. So that's out. > > So really the only alternative would be for sbcl to allocate an extra word > of memory to store an sxhash value for objects that are compared by > identity with equal. But that would be kinda a waste of memory. So it > doesn't. > > On June 25, 2015 8:04:12 PM EDT, JTK <je...@gm...> wrote: > >> >> >> Apologies if this is an inane question, but is the following intended? >> >> cl-user> (lisp-implementation-version) >> "1.2.11" >> cl-user> (sxhash #(2)) >> 1193941381096739655 >> cl-user> (sxhash #(1 2)) >> 1193941381096739655 >> cl-user> (sxhash #(3 1 2)) >> 1193941381096739655 >> cl-user> (sxhash #()) >> 1193941381096739655 >> cl-user> (sxhash (vector "bunny")) >> 1193941381096739655 >> >> Admittedly, it conforms with CLHS >> http://www.lispworks.com/documentation/lw61/CLHS/Body/f_sxhash.htm >> >> It comes from target-sxhash.lisp where >> >> >> (array ;; case of array >> (typecase x >> (simple-string (sxhash x)) ; through DEFTRANSFORM >> ;;; falls through to here >> (t (logxor 191020317 (sxhash (array-rank x)))))) >> >> >> So every 1d array has the same sxhash. Is there a reason the first few >> elements aren’t used, >> like for a list? >> >> ------------------------------ >> >> Monitor 25 network devices or servers for free with OpManager! >> OpManager is web-based network management software that >> monitors >> network devices and physical & virtual servers, alerts via email & sms >> for fault. Monitor 25 devices for free with no restriction. Download now >> http://ad.doubleclick.net/ddm/clk/292181274;119417398;o >> >> ------------------------------ >> >> Sbcl-devel mailing list >> Sbc...@li... >> https://lists.sourceforge.net/lists/listinfo/sbcl-devel >> >> > > ------------------------------------------------------------------------------ > Monitor 25 network devices or servers for free with OpManager! > OpManager is web-based network management software that monitors > network devices and physical & virtual servers, alerts via email & sms > for fault. Monitor 25 devices for free with no restriction. Download now > http://ad.doubleclick.net/ddm/clk/292181274;119417398;o > _______________________________________________ > Sbcl-devel mailing list > Sbc...@li... > https://lists.sourceforge.net/lists/listinfo/sbcl-devel > > |
From: JTK <je...@gm...> - 2015-06-26 06:15:45
|
James (and Jean-Philippe) Thanks for the explanation about equal and arrays. Would something like the following be a bit better than using array rank? It doesn’t use the array contents either, but should discriminate among arrays by size and shape and element type. Or am I missing some subtle point. (defun new-sxhash (x) (cond ((and (arrayp x) (not (stringp x)) (not (bit-vector-p x))) (logxor (sxhash (array-dimensions x)) (sxhash (array-element-type x)))) ;; (t ;; all other things (sxhash x)))) > On Jun 25, 2015, at 3:07 PM, James Y Knight <fo...@fu...> wrote: > > Yes, this is basically a stupidity in the CL spec. > > sxhash can only use parts of the object which are immutable, if equal does an identity (eq) comparison for that type. > > "The hash-code for an object is always the same within a single session provided that the object is not visibly modified with regard to the equivalence test equal." > > And since arrays are for some illogical reason not compared by content with equal (while lists are) neither may sxhash use the content of an array. The behavior of equal truly makes no sense, but there you are... > > The address of the object could be returned by sxhash, except that sbcl has a moving GC, so the address doesn't stay constant. So that's out. > > So really the only alternative would be for sbcl to allocate an extra word of memory to store an sxhash value for objects that are compared by identity with equal. But that would be kinda a waste of memory. So it doesn't. > > On June 25, 2015 8:04:12 PM EDT, JTK <je...@gm...> wrote: > > > Apologies if this is an inane question, but is the following intended? > > cl-user> (lisp-implementation-version) > "1.2.11" > cl-user> (sxhash #(2)) > 1193941381096739655 > cl-user> (sxhash #(1 2)) > 1193941381096739655 > cl-user> (sxhash #(3 1 2)) > 1193941381096739655 > cl-user> (sxhash #()) > 1193941381096739655 > cl-user> (sxhash (vector "bunny")) > 1193941381096739655 > > Admittedly, it conforms with CLHS http://www.lispworks.com/documentation/lw61/CLHS/Body/f_sxhash.htm <http://www.lispworks.com/documentation/lw61/CLHS/Body/f_sxhash.htm> > > It comes from target-sxhash.lisp where > > > (array ;; case of array > (typecase x > (simple-string (sxhash x)) ; through DEFTRANSFORM > ;;; falls through to here > (t (logxor 191020317 (sxhash (array-rank x)))))) > > > So every 1d array has the same sxhash. Is there a reason the first few elements aren’t used, > like for a list? > > > Monitor 25 network devices or servers for free with OpManager! > OpManager is web-based network management software that > monitors > network devices and physical & virtual servers, alerts via email & sms > for fault. Monitor 25 devices for free with no restriction. Download now > http://ad.doubleclick.net/ddm/clk/292181274;119417398;o <http://ad.doubleclick.net/ddm/clk/292181274;119417398;o> > > > Sbcl-devel mailing list > Sbc...@li... > https://lists.sourceforge.net/lists/listinfo/sbcl-devel <https://lists.sourceforge.net/lists/listinfo/sbcl-devel> |
From: Douglas K. <do...@go...> - 2015-06-26 07:43:48
|
For non-simple arrays, it would not be valid to include the dimensions because they can change; and possibly not valid to include the element-type. It's probably not supposed to work to displace an array to a differently typed array, but it does work, and there's an open bug questioning that. For simple-arrays, the code isn't wrong, but it conses at least one list, possibly two. It would be preferable to iterate over the dimensions and mix each into the hash one at a time; and probably just use %other-pointer-widetag to get an opaque number to mix in for the element type. |