HTTPS SSH
                             MURMURHASH3
                             ===========

                           By Robert Smith

INTRODUCTION & USAGE
--------------------

MURMURHASH3 is a relatively efficient implementation of the 32-bit
MurmurHash3 algorithms written in Common Lisp without FFI.

Specifically, the 32-bit algorithm to produce a 32-bit hash is
supported for octet vectors or files with the polymorphic function
MURMURHASH3:MURMURHASH32. This returns two values: the 32-bit hash,
and the number of bytes hashed.

The 32-bit algorithm to produce a 128-bit hash is also supported for
octet vectors or files with the polymorphic function
MURMURHASH3:MURMURHASH128. This returns five values: the first four
are the 32-bit hash values, the fifth is the number of bytes hashed.

Currently, the 64-bit variant of the 128-bit hash is not supported.

The seed defaults to 42, which can be specified by the second argument
of each of the above functions.

The API is subject to change.


ALGORITHM
---------

The algorithm is roughly described in the following places:

    * https://code.google.com/p/smhasher/wiki/MurmurHash3
    * http://en.wikipedia.org/wiki/MurmurHash

The reference implementation is written in C++ and can be found here:

    * https://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp

The code was tested using Peter Scott's C port, called "murmur3", of
the reference implementation. It can be found here:

    https://github.com/PeterScott/murmur3


PERFORMANCE
-----------

Performance is relatively good for certain platforms, but about 2x to
3x slower than the advertised claim of at least 2 GB/s. There are a
variety of possible reasons for this, including safety overhead
incured by Lisp.

For platforms with worse performance (5-20x slower), it is likely they
can improve with extensive type declarations for both variables and
return types.


SBCL:

On 2.6 GHz Intel Core i7 with 16 GB of RAM using SBCL
"1.2.7.56-ff0b9bb", I sustain between 800 MB/s and 1 GB/s for hashing
arrays around 256 MB in size. Here are the results for the 32-bit hash
function for arrays:

    > (murmurhash3-tests:test-performance-32)
    1.00 KB in 0.0 s @ inf MB/s
    2.00 KB in 0.0 s @ inf MB/s
    4.00 KB in 0.0 s @ inf MB/s
    8.00 KB in 0.0 s @ inf MB/s
    16.00 KB in 0.0 s @ inf MB/s
    32.00 KB in 0.0 s @ inf MB/s
    64.00 KB in 0.0 s @ inf MB/s
    128.00 KB in 0.0 s @ inf MB/s
    256.00 KB in 0.001 s @ 250.00 MB/s
    512.00 KB in 0.001 s @ 500.00 MB/s
    1.00 MB in 0.001 s @ 0.98 GB/s
    2.00 MB in 0.005 s @ 400.00 MB/s
    4.00 MB in 0.005 s @ 800.00 MB/s
    8.00 MB in 0.01 s @ 800.00 MB/s
    16.00 MB in 0.018 s @ 888.89 MB/s
    32.00 MB in 0.041 s @ 780.49 MB/s
    64.00 MB in 0.078 s @ 820.51 MB/s
    128.00 MB in 0.15 s @ 853.33 MB/s
    256.00 MB in 0.302 s @ 847.68 MB/s

And for 128-bit hashes, we sustain nearly 1 GB/s:

    > (murmurhash3-tests:test-performance-128)
    1.00 KB in 0.0 s @ inf MB/s
    2.00 KB in 0.0 s @ inf MB/s
    4.00 KB in 0.0 s @ inf MB/s
    8.00 KB in 0.0 s @ inf MB/s
    16.00 KB in 0.0 s @ inf MB/s
    32.00 KB in 0.0 s @ inf MB/s
    64.00 KB in 0.0 s @ inf MB/s
    128.00 KB in 0.0 s @ inf MB/s
    256.00 KB in 0.001 s @ 250.00 MB/s
    512.00 KB in 0.001 s @ 500.00 MB/s
    1.00 MB in 0.002 s @ 500.00 MB/s
    2.00 MB in 0.004 s @ 500.00 MB/s
    4.00 MB in 0.006 s @ 666.67 MB/s
    8.00 MB in 0.011 s @ 727.27 MB/s
    16.00 MB in 0.02 s @ 800.00 MB/s
    32.00 MB in 0.035 s @ 914.29 MB/s
    64.00 MB in 0.063 s @ 0.99 GB/s
    128.00 MB in 0.13 s @ 0.96 GB/s
    256.00 MB in 0.259 s @ 0.97 GB/s

For files, I sustain about 500 MB/s for a 2 GB file when the disk is
an SSD.


Clozure CL:

The performance situation is a bit more dire. I sustain about
10-12 MB/s for both file and array tests.


LispWorks:

I sustain about 45 MB/s for both file and array tests.



TESTING
-------

The system has been tested with:

    * SBCL 1.2.7 (.56-ff0b9bb)
    * CCL 1.10 (r16089)
    * LispWorks 6.1.1

Make sure MURMURHASH3-TESTS is visible to ASDF, possibly by loading
"murmurhash3-tests.asd". Then run

    (asdf:test-system :murmurhash3)

Currently, only the array functions are tested.


ACKNOWLEDGEMENTS
----------------

This code has its roots from hacking sessions with Mark H. David
<mhd@yv.org>. He actually wrote the first Lisp version. He claimed it
is probably best to just use FFI, which aggravated me and caused me to
improve his version, which I then rewrote from scratch over a weekend.