Fast Hamming distance calculation for hexadecimal strings
Project description
Why yet another Hamming distance library?
There are a lot of fantastic (python) libraries that offer methods to calculate various edit distances, including Hamming distances: Distance, textdistance, scipy, jellyfish, etc.
In this case, I needed a hamming distance library that worked on hexadecimal strings (i.e., a Python str) and performed blazingly fast. Furthermore, I often did not care about hex strings greater than 256 bits. That length constraint is different vs all the other libraries and enabled me to explore vectorization techniques via numba, numpy, and even SSE/AVX.
Lastly, I wanted to minimize dependencies, meaning you do not need to install numpy, gmpy, cython, pypy, pythran, etc.
Eventually, after playing around with gmpy.popcount, numba.jit, pythran.run, numpy, and AVX2, I decided to write what I wanted in a raw C++ header. Note: the only C++-feature I’m exploiting is C++ exceptions; without that, this could easily be C. At this point, I’m using raw char* and int*, so exploring re-writing this in Fortran makes little sense. Vectorization techniques also ended up adding more overhead from data transfer between vector registers and normal registers; also, converting the hex strings to vector-register-ingestible floats from char* proved to have a non-trivial overhead.
Installation
To install, ensure you have Python 2.7 or 3.4+. Run:
pip install hexhamming
or to install from source:
git clone https://github.com/mrecachinas/hexhamming cd hexhamming python setup.py install # or pip install .
If you want to contribute to hexhamming, you should install the dev dependencies:
pip install -r requirements-dev.txt
and make sure the tests pass with:
pytest # or tox -e py27,...
Example
To use the base C++ extension, you can simply run:
>>> from hexhamming import hamming_distance >>> hamming_distance('deadbeef', '00000000') 24
To use the lookup-based C++ extension, replace the above hamming_distance with hamming_distance_lookup.
If your machine supports the Intel SSE4/AVX2 instruction set, replace the above hamming_distance with fast_hamming_distance. Note: to use fast_hamming_distance, your hex string must be 64 characters or less (i.e., 256 bits or less).
Benchmark
Below is a benchmark using pytest-benchmark on my early 2016 1.2 GHz Intel m5 8 GB 1867 MHz LPDDR3 macOS Mojave (10.14.3) with Python 2.7.15 and clang-1000.11.45.5.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for hexhamming-1.0-cp36-cp36m-macosx_10_13_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f5a2901a96cbf94e42ae3b4131a8956bda9a424f0c071914aa467a18c06cd169 |
|
MD5 | 161ac27d7baa0e81698749c295d70998 |
|
BLAKE2b-256 | 5651219ecbce734dd51f887a64662f32d12e00e245ad78d48bfce29ea548b126 |
Hashes for hexhamming-1.0-cp27-cp27m-macosx_10_13_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e68803278f70b27793868a6fd682229b47711c729bee09032ce277ee551d50ee |
|
MD5 | f67d7c14a65a4c94a76941bf02f48908 |
|
BLAKE2b-256 | d7b657f9b5a076cefbf2c93e64e4de949f78e3e305acfde636ef743eef75eb71 |