• L1_530092
  • 181.9KB
  • zip
  • 0
  • VIP专享
  • 0
  • 2022-05-21 07:13
xxHash-极快的哈希算法 xxHash是一种极快的哈希算法,以RAM速度限制运行。 它成功完成了测试套件,该套件可评估哈希函数的冲突,分散和随机性。 代码具有高度的可移植性,并且散列在所有平台上都是相同的(小/大字节序)。 分支 地位 掌握 开发者 基准测试 该基准测试使用SMHasher速度测试,该测试是在Windows 7 32位盒上使用Visual 2010编译的。 参考系统使用Core 2 Duo @ 3GHz 名称 速度 质量 作者 5.4 GB /秒 10 YC 杂项哈希3a 2.7 GB /秒 10 奥斯汀·阿普比(Austin Appleby) 盒子 1.4 GB /秒 9 布雷特·马尔维(Bret Mulvey) 查找3 1.2 GB /秒 9 鲍勃·詹金斯(Bob Jenkins) 城市哈希64 1.05 GB /秒 10 派克(Pik
xxHash - Extremely fast hash algorithm ====================================== <!-- TODO: Update. --> xxHash is an Extremely fast Hash algorithm, running at RAM speed limits. It successfully completes the [SMHasher](https://code.google.com/p/smhasher/wiki/SMHasher) test suite which evaluates collision, dispersion and randomness qualities of hash functions. Code is highly portable, and hashes are identical on all platforms (little / big endian). |Branch |Status | |------------|---------| |master | [![Build Status](https://travis-ci.org/Cyan4973/xxHash.svg?branch=master)](https://travis-ci.org/Cyan4973/xxHash?branch=master) | |dev | [![Build Status](https://travis-ci.org/Cyan4973/xxHash.svg?branch=dev)](https://travis-ci.org/Cyan4973/xxHash?branch=dev) | Benchmarks ------------------------- The benchmark uses SMHasher speed test, compiled with Visual 2010 on a Windows Seven 32-bit box. The reference system uses a Core 2 Duo @3GHz | Name | Speed | Quality | Author | |---------------|--------------------|:-------:|-------------------| | [xxHash] | 5.4 GB/s | 10 | Y.C. | | MurmurHash 3a | 2.7 GB/s | 10 | Austin Appleby | | SBox | 1.4 GB/s | 9 | Bret Mulvey | | Lookup3 | 1.2 GB/s | 9 | Bob Jenkins | | CityHash64 | 1.05 GB/s | 10 | Pike & Alakuijala | | FNV | 0.55 GB/s | 5 | Fowler, Noll, Vo | | CRC32 | 0.43 GB/s &dagger; | 9 | | | MD5-32 | 0.33 GB/s | 10 | Ronald L.Rivest | | SHA1-32 | 0.28 GB/s | 10 | | [xxHash]: https://www.xxhash.com Note &dagger;: SMHasher's CRC32 implementation is known to be slow. Faster implementations exist. Q.Score is a measure of quality of the hash function. It depends on successfully passing SMHasher test set. 10 is a perfect score. Algorithms with a score < 5 are not listed on this table. A more recent version, XXH64, has been created thanks to [Mathias Westerdahl](https://github.com/JCash), which offers superior speed and dispersion for 64-bit systems. Note however that 32-bit applications will still run faster using the 32-bit version. SMHasher speed test, compiled using GCC 4.8.2, on Linux Mint 64-bit. The reference system uses a Core i5-3340M @2.7GHz | Version | Speed on 64-bit | Speed on 32-bit | |------------|------------------|------------------| | XXH64 | 13.8 GB/s | 1.9 GB/s | | XXH32 | 6.8 GB/s | 6.0 GB/s | This project also includes a command line utility, named `xxhsum`, offering similar features to `md5sum`, thanks to [Takayuki Matsuoka](https://github.com/t-mat)'s contributions. ### License The library files `xxhash.c` and `xxhash.h` are BSD licensed. The utility `xxhsum` is GPL licensed. ### New hash algorithms Starting with `v0.7.0`, the library includes a new algorithm named `XXH3`, which is able to generate 64 and 128-bit hashes. The new algorithm is much faster than its predecessors for both long and small inputs, which can be observed in the following graphs: ![XXH3, bargraph](https://user-images.githubusercontent.com/750081/61976096-b3a35f00-af9f-11e9-8229-e0afc506c6ec.png) ![XXH3, latency, random size](https://user-images.githubusercontent.com/750081/61976089-aedeab00-af9f-11e9-9239-e5375d6c080f.png) To access these new prototypes, one needs to unlock their declaration, using the build macro `XXH_STATIC_LINKING_ONLY`. The algorithm is currently in development, meaning its return values might still change in future versions. However, the API is stable, and can be used in production, typically for generation of ephemeral hashes (produced and consumed in same session). `XXH3` has now reached "release candidate" status. If everything remains fine, its format will be "frozen" and become final. After which, return values of `XXH3` and `XXH128` will no longer change in future versions. `XXH3`'s return values will be officially finalized upon reaching `v0.8.0`. ### Build modifiers The following macros can be set at compilation time to modify libxxhash's behavior. They are generally disabled by default. - `XXH_INLINE_ALL`: Make all functions `inline`, with implementations being directly included within `xxhash.h`. Inlining functions is beneficial for speed on small keys. It's _extremely effective_ when key length is expressed as _a compile time constant_, with performance improvements observed in the +200% range . See [this article](https://fastcompression.blogspot.com/2018/03/xxhash-for-small-keys-impressive-power.html) for details. - `XXH_PRIVATE_API`: same outcome as `XXH_INLINE_ALL`. Still available for legacy support. The name underlines that `XXH_*` symbols will not be exported. - `XXH_NAMESPACE`: Prefixes all symbols with the value of `XXH_NAMESPACE`. This macro can only use compilable character set. Useful to evade symbol naming collisions, in case of multiple inclusions of xxHash's source code. Client applications still use the regular function names, as symbols are automatically translated through `xxhash.h`. - `XXH_FORCE_MEMORY_ACCESS`: The default method `0` uses a portable `memcpy()` notation. Method `1` uses a gcc-specific `packed` attribute, which can provide better performance for some targets. Method `2` forces unaligned reads, which is not standards compliant, but might sometimes be the only way to extract better read performance. Method `3` uses a byteshift operation, which is best for old compilers which don't inline `memcpy()` or big-endian systems without a byteswap instruction - `XXH_FORCE_ALIGN_CHECK`: Use a faster direct read path when input is aligned. This option can result in dramatic performance improvement when input to hash is aligned on 32 or 64-bit boundaries, when running on architectures unable to load memory from unaligned addresses, or suffering a performance penalty from it. It is (slightly) detrimental on platform with good unaligned memory access performance (same instruction for both aligned and unaligned accesses). This option is automatically disabled on `x86`, `x64` and `aarch64`, and enabled on all other platforms. - `XXH_VECTOR` : manually select a vector instruction set (default: auto-selected at compilation time). Available instruction sets are `XXH_SCALAR`, `XXH_SSE2`, `XXH_AVX2`, `XXH_AVX512`, `XXH_NEON` and `XXH_VSX`. Compiler may require additional flags to ensure proper support (for example, `gcc` on linux will require `-mavx2` for AVX2, and `-mavx512f` for AVX512). - `XXH_NO_PREFETCH` : disable prefetching. XXH3 only. - `XXH_PREFETCH_DIST` : select prefecting distance. XXH3 only. - `XXH_NO_INLINE_HINTS`: By default, xxHash uses `__attribute__((always_inline))` and `__forceinline` to improve performance at the cost of code size. Defining this macro to 1 will mark all internal functions as `static`, allowing the compiler to decide whether to inline a function or not. This is very useful when optimizing for smallest binary size, and is automatically defined when compiling with `-O0`, `-Os`, `-Oz`, or `-fno-inline` on GCC and Clang. This may also increase performance depending on compiler and architecture. - `XXH_REROLL`: Reduces the size of the generated code by not unrolling some loops. Impact on performance may vary, depending on platform and algorithm. - `XXH_ACCEPT_NULL_INPUT_POINTER`: if set t