#hashing #hash #murmur3 #murmur #hash-values

fastmurmur3

Fast non-cryptographic hash, with the benchmarks to prove it

2 unstable releases

0.2.0 Jun 19, 2023
0.1.2 Dec 14, 2021

#614 in Cryptography

Download history 36526/week @ 2024-08-22 39758/week @ 2024-08-29 35451/week @ 2024-09-05 24171/week @ 2024-09-12 18803/week @ 2024-09-19 22045/week @ 2024-09-26 20755/week @ 2024-10-03 15121/week @ 2024-10-10 19611/week @ 2024-10-17 26709/week @ 2024-10-24 16152/week @ 2024-10-31 11753/week @ 2024-11-07 21311/week @ 2024-11-14 12497/week @ 2024-11-21 6473/week @ 2024-11-28 5194/week @ 2024-12-05

46,002 downloads per month
Used in 24 crates (12 directly)

MIT license

18KB
342 lines

GitHub Contributors Stars Build Status Downloads Crates.io

Fastmurmur3

Murmur3 is a fast, non-cryptographic hash function. fastmurmur3 is, in my testing, the fastest implementation of Murmur3.

Usage

let bytes: &[u8] = b"hello world";
let x: u128 = fastmurmur3::hash(bytes);

Installation

cargo install fastmurmur3

Benchmarks

Summary

According to current benchmarks:

  • fastmurmur3 is the fastest.
  • xxh3_64 is 1.66x slower and only has a 64-bit value.
  • xxh3_128 is 2.50x slower.
  • fasthash contains the next fastest murmur3 implementation, but is still 4.47x slower than fastmurmur3.

Data

fastmurmur3             time:   [3.0878 ns 3.1215 ns 3.1619 ns]
xxhash_rust::xxh3_64    time:   [5.1473 ns 5.1872 ns 5.2456 ns]
xxhash_rust::xxh3_128   time:   [7.8066 ns 7.8271 ns 7.8499 ns]
fasthash                time:   [13.909 ns 13.960 ns 14.018 ns]
murmur3c                time:   [14.529 ns 14.604 ns 14.684 ns]
murmur3                 time:   [26.084 ns 26.163 ns 26.249 ns]
twox_hash::Xxh3Hash64   time:   [124.23 ns 126.46 ns 128.55 ns]
twox_hash::Xxh3Hash128  time:   [134.62 ns 136.75 ns 138.77 ns]
sha1                    time:   [209.55 ns 211.71 ns 214.88 ns]

Benchmark Future Work

  • These benchmarks are run on a limited input set and with a limited seed set. These more extensive benchmarks need to happen before definitively making the claim that fastmurmur3 is the fastest non-cryptographic hash function.

  • I'm not sure if these benchmarks are unfair to the reference C implementation because of linkage (i.e. rust function gets fully inlined, whereas C implementation stays as a separate fn call because of linking algorithm).

  • Besides speed, these benchmarks could also measure other hash properties like collision-resistance in comparison to other algorithms (xxhash, etc.).

  • It'd be nice to have pretty charts of the benchmarks.

  • I'd like to understand if there's steps I can take to make the benchmarks more reproducible (e.g. setting process priority, failing if it encounters memory contention, etc.)

  • I'd like to improve the benchmarking readout and abstract it into a better comparison tool. Right now, cargo bench and cargo criterion are built for tracking performance of the project over time. I'd like to have a better library for comparing performance within a benchmark group.

Correctness

The tests for fastmurmur3 perform fuzzing in comparison to the C implementation.

Contributing

Contributions are what make the open source community such an amazing place to learn, inspire, and create. Any contributions you make are greatly appreciated.

If you have a suggestion that would make this better, please fork the repo and create a pull request. You can also simply open an issue with the tag "enhancement". Don't forget to give the project a star! Thanks again!

  1. Fork the Project
  2. Create your Feature Branch (git checkout -b feature/AmazingFeature)
  3. Commit your Changes (git commit -m 'Add some AmazingFeature')
  4. Push to the Branch (git push origin feature/AmazingFeature)
  5. Open a Pull Request

No runtime deps