Anyone have (or know of) an efficient way of getting a sha1 digest of some data in gambit?
All I could find was http://www-pu.informatik.uni-tuebingen.de/users/knauel/sw/myscsh/sha1.scm
which (after minor hacking) can do:
(time (sha1-hash-byte-vector (make-u8vector 1000000))) 301187 ms real time 135097 ms cpu time (130412 user, 4685 system) 25815 collections accounting for 108377 ms real time (46618 user, 1795 system) 3598449540 bytes allocated no minor faults no major faults 1090135108572819471271096978636225236080936489142
Way too slow for even moderately large data. Can anyone help?
Afficher les réponses par date
On Dec 5, 2006, at 12:16 AM, |/|/ Bendick wrote:
Anyone have (or know of) an efficient way of getting a sha1 digest of some data in gambit?
All I could find was http://www-pu.informatik.uni-tuebingen.de/users/knauel/sw/myscsh/ sha1.scm
which (after minor hacking) can do:
(time (sha1-hash-byte-vector (make-u8vector 1000000))) 301187 ms real time 135097 ms cpu time (130412 user, 4685 system) 25815 collections accounting for 108377 ms real time (46618 user, 1795 system) 3598449540 bytes allocated no minor faults no major faults 1090135108572819471271096978636225236080936489142
It would have been helpful to see your hacking.
I used yome's statprof.scm to see where the hotspots were. I presume you used the util.scm from the same source distribution; that sucks pretty bad, as well as some of the low-level stuff in sha1.scm. Anyway, I've included my files below; with these I get
[brad:~/Desktop] lucier% gsc all [brad:~/Desktop] lucier% gsi -:m100000 Gambit Version 4.0 beta 20
(load "all")
*** WARNING -- Variable "format" used in module "all.o3" is undefined "/Users/lucier/Desktop/all.o3"
(time (sha1-hash-byte-vector (make-u8vector 100000)))
(time (sha1-hash-byte-vector (make-u8vector 100000))) 1649 ms real time 970 ms cpu time (810 user, 160 system) 1 collection accounting for 2 ms real time (1 user, 0 system) 113510176 bytes allocated no minor faults no major faults 1059294638103097938543302566657632700864129177053
(time (sha1-hash-byte-vector (make-u8vector 1000000)))
(time (sha1-hash-byte-vector (make-u8vector 1000000))) 18210 ms real time 8846 ms cpu time (8537 user, 309 system) 11 collections accounting for 20 ms real time (16 user, 2 system) 1134964564 bytes allocated no minor faults no major faults 1090135108572819471271096978636225236080936489142
which is not fast, but perhaps you can make more of it. Note that I set up a 100MB heap to start to avoid a lot of garbage collections (but we do allocate over 1GB of memory during the computation; your code allocated over 3.5GB).
That was on my 1.67GHz PowerPC laptop. On a 64-bit machine (like my 2GHz G5), it's more interesting:
[descartes:~/Desktop/sha1] lucier% gsc -:m100000 Gambit Version 4.0 beta 20
(load "all")
*** WARNING -- Variable "format" used in module "all.o1" is undefined "/Users/lucier/Desktop/sha1/all.o1"
(time (sha1-hash-byte-vector (make-u8vector 100000)))
(time (sha1-hash-byte-vector (make-u8vector 100000))) 410 ms real time 403 ms cpu time (376 user, 27 system) no collections 32515888 bytes allocated no minor faults no major faults 1059294638103097938543302566657632700864129177053
(time (sha1-hash-byte-vector (make-u8vector 1000000)))
(time (sha1-hash-byte-vector (make-u8vector 1000000))) 4567 ms real time 3877 ms cpu time (3726 user, 151 system) 3 collections accounting for 13 ms real time (11 user, 3 system) 324987176 bytes allocated no minor faults no major faults 1090135108572819471271096978636225236080936489142
Still note great, but here we allocate only 1/3 as much memory, and most of that could be eliminated with a more careful circular shift (masking *before* shifting instead of after) and fixnum declarations. Left as an exercise for the reader ;-).
Brad
On 12/4/06, Bradley Lucier lucier@math.purdue.edu wrote:
Still note great, but here we allocate only 1/3 as much memory, and most of that could be eliminated with a more careful circular shift (masking *before* shifting instead of after) and fixnum declarations. Left as an exercise for the reader ;-).
Brad
Or you could use Guillaume's Gambit interface to OpenSSL's sha1 routines:
http://66.102.7.104/search?q=cache:WUj3-7OmyWwJ:paste.lisp.org/display/9642
But maybe that's cheating... :)
(Google cache because paste.lisp.org appears to be b0rked.)
--Jeff
On Tue 05 Dec 2006 06:16, "|/|/ Bendick" wbendick@gmail.com writes:
Anyone have (or know of) an efficient way of getting a sha1 digest of some data in gambit?
All I could find was http://www-pu.informatik.uni-tuebingen.de/users/knauel/sw/myscsh/sha1.scm which (after minor hacking) can do:
(time (sha1-hash-byte-vector (make-u8vector 1000000))) 301187 ms real time 135097 ms cpu time (130412 user, 4685 system) 25815 collections accounting for 108377 ms real time (46618 user, 1795 system) 3598449540 bytes allocated no minor faults no major faults 1090135108572819471271096978636225236080936489142
Way too slow for even moderately large data. Can anyone help?
Note that the SHA1 implementation you are referring to is intended for computing the digest of very small messages, i.e. MySQL password data (about 20 bytes), and not as a general purpose implementation of SHA1. There are lots of possibilites to improve the speed of this code (especially, when running it on Gambit). But I don't care; it just doesn't make a difference for the intended purpose (which is: access MySQL databases without having to link scsh against libmysqlclient).
However, if you are interested in a fast version of the SHA1 code I would recommend to change the code to use Gambit's homogeneous vectors (u32-vectors) and fixnums. This change would be very cheap and I would expect it to increase the speed considerably.
-Eric
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On 5-Dec-06, at 12:16 AM, |/|/ Bendick wrote:
Anyone have (or know of) an efficient way of getting a sha1 digest of some data in gambit?
All I could find was http://www-pu.informatik.uni-tuebingen.de/users/knauel/sw/myscsh/ sha1.scm
which (after minor hacking) can do:
(time (sha1-hash-byte-vector (make-u8vector 1000000))) 301187 ms real time 135097 ms cpu time (130412 user, 4685 system) 25815 collections accounting for 108377 ms real time (46618 user, 1795 system) 3598449540 bytes allocated no minor faults no major faults 1090135108572819471271096978636225236080936489142
Way too slow for even moderately large data. Can anyone help?
The Gambit distribution contains optimized implementations of MD5, SHA-1, SHA-224, and SHA-256 in the file lib/digest.scm . They could be optimized further (especially for SHA-224 and SHA-256) but MD5 and SHA-1 run much faster than the other Scheme versions I have encountered and they allocate very little.
Marc
Hmm, is there any documentation anywhere on how namespace works?
On 12/5/06, Marc Feeley feeley@iro.umontreal.ca wrote:
The Gambit distribution contains optimized implementations of MD5, SHA-1, SHA-224, and SHA-256 in the file lib/digest.scm . They could be optimized further (especially for SHA-224 and SHA-256) but MD5 and SHA-1 run much faster than the other Scheme versions I have encountered and they allocate very little.
Marc