Principle:ClickHouse ClickHouse SIMD String Hashing
| Knowledge Sources | |
|---|---|
| Domains | Hashing, SIMD |
| Last Updated | 2026-02-08 00:00 GMT |
Overview
Leveraging CPU-specific hardware instructions to accelerate string hashing and comparison operations beyond what general-purpose algorithms can achieve.
Description
SIMD (Single Instruction Multiple Data) string hashing exploits modern CPU capabilities to process multiple bytes in parallel. For hashing, the key innovation is using hardware CRC32 instructions that were originally designed for checksums but provide excellent hash distribution at minimal computational cost. A single CRC32 instruction can process 8 bytes at once, making it much faster than byte-by-byte hashing. For string comparison, SIMD instructions can compare 16 bytes (128 bits) simultaneously using SSE2, or even more with AVX instructions.
The principle recognizes that theoretical hash quality matters less than practical performance in real workloads. While CRC32 is not cryptographically secure and has theoretical collision properties, it performs exceptionally well on real database data where strings tend to differ in predictable patterns. The hardware acceleration more than compensates for any theoretical disadvantages.
Usage
Use SIMD string hashing when building high-performance hash tables for database operations, caching systems, or any application that performs millions of hash table lookups per second. Choose CRC32-based hashing over cryptographic hashes when security is not a concern but performance is critical. Use SIMD string comparison when sorting, deduplicating, or comparing large volumes of string data.
Theoretical Basis
Hash Performance:
- CRC32 instruction: 1-3 CPU cycles per 8 bytes
- Traditional hash (like CityHash): 10-20 cycles per 8 bytes
- Speedup: 3-10x on typical string data
Comparison Performance:
- SIMD comparison: Compare 16 bytes in ~2-3 cycles
- Byte-by-byte comparison: 16 cycles minimum
- Speedup: 5-8x for string equality checks
Why CRC32 Works Well:
The CRC32 polynomial provides good avalanche properties - small changes in input cause large changes in output. The instruction operates on 64-bit chunks, naturally handling unaligned data. For hash tables, the distribution is "good enough" - collisions occur at similar rates to more expensive hash functions.
SIMD Comparison Strategy:
Load 16 bytes from each string into SIMD registers, perform parallel byte-wise comparison, produce a bit mask indicating equal bytes, and check if all bytes match. For longer strings, process in 16 or 64-byte chunks until a difference is found or the end is reached.
Practical Considerations:
The approach works best when:
- Strings are typically small to medium (8-256 bytes)
- Hardware support is available (x86 SSE4.2+, ARM CRC32, s390x)
- Hash table load factor is reasonable (avoiding excessive collisions)
The 64-bit hash output is adequate for applications with fewer than 2^32 unique strings (birthday paradox threshold).