[gambit-list] SHA1 in Gambit

Bradley Lucier lucier at math.purdue.edu
Tue Dec 5 02:12:28 EST 2006


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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: sha1.scm
Type: application/octet-stream
Size: 7846 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20061205/d7322744/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: util.scm
Type: application/octet-stream
Size: 578 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20061205/d7322744/attachment-0001.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: all.scm
Type: application/octet-stream
Size: 159 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20061205/d7322744/attachment-0002.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: byte-vectors.scm
Type: application/octet-stream
Size: 162 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20061205/d7322744/attachment-0003.obj>


More information about the Gambit-list mailing list