3 ms·

Sutter's solution was to write more concurrent code, but that's not what helps in this case. Rather the CPU vendors have been throwing transistors at doing more

by mark-r 8y ago

Sutter's solution was to write more concurrent code, but that's not what helps in this case. Rather the CPU vendors have been throwing transistors at doing more math operations in parallel. All you need to do is make sure you're taking advantage of the vector instructions, whether that's done by the compiler or with intrinsic calls. Traditionally the fastest CRC code has used lookup tables, I wonder if that's creating cache pressure these days? Or maybe that approach was abandoned while I wasn't paying attention.

dragontamer 8y ago
> Rather the CPU vendors have been throwing transistors at doing more math operations in parallel. All you need to do is make sure you're taking advantage of the vector instructions, whether that's done by the compiler or with intrinsic calls. Instruction-level parallelism is incredibly important. I'd say that any optimizing programmer needs to fully understand ILP, and how it interacts with pipelines and dependency cutting (and register renaming). Modern CPUs are extremely well parallelized with ILP. Any good, modern hash function will take advantage of this feature of modern CPUs. Case in point, it seems like xxhash is SCALAR 32-bit / 64-bit code. No vectorization as far as I can tell, its purely using ILP to get its speed. Intel Assembly has a 64-bit multiplier (but vectorized only has 32-bit multipliers). I've theorized to myself that this 64-bit multiplier could lead to better mixing than the vectorized instructions, and it seems like xxhash goes for that. The 32-bit version of xxhash can likely be vectorized and optimized even further.
- corysama 8y ago
  https://moinakg.wordpress.com/2013/01/19/vectorizing-xxhash-for-fun-and-profit/ https://moinakg.wordpress.com/2013/01/19/vectorizing-xxhash-...
rurban 8y ago
Nope. The fastest crc code now uses the intrinsics and some parallel execution tricks, see crclib from Cloudflare.
- corysama 8y ago
  Where do I find this library? Googling “crclib from Cloudflare” without quotes returns your comment as the top hit :P
  - rurban 8y ago
    I have them here: https://github.com/cloudflare/zlib.git https://github.com/cloudflare/zlib.git https://github.com/rurban/crcutil.git https://github.com/rurban/crcutil.git

by mark-r 8y ago

dragontamer 8y ago

> Rather the CPU vendors have been throwing transistors at doing more math operations in parallel. All you need to do is make sure you're taking advantage of the vector instructions, whether that's done by the compiler or with intrinsic calls. Instruction-level parallelism is incredibly important. I'd say that any optimizing programmer needs to fully understand ILP, and how it interacts with pipelines and dependency cutting (and register renaming). Modern CPUs are extremely well parallelized with ILP. Any good, modern hash function will take advantage of this feature of modern CPUs. Case in point, it seems like xxhash is SCALAR 32-bit / 64-bit code. No vectorization as far as I can tell, its purely using ILP to get its speed. Intel Assembly has a 64-bit multiplier (but vectorized only has 32-bit multipliers). I've theorized to myself that this 64-bit multiplier could lead to better mixing than the vectorized instructions, and it seems like xxhash goes for that. The 32-bit version of xxhash can likely be vectorized and optimized even further.

corysama 8y ago
https://moinakg.wordpress.com/2013/01/19/vectorizing-xxhash-for-fun-and-profit/ https://moinakg.wordpress.com/2013/01/19/vectorizing-xxhash-...

rurban 8y ago

Nope. The fastest crc code now uses the intrinsics and some parallel execution tricks, see crclib from Cloudflare.

corysama 8y ago
Where do I find this library? Googling “crclib from Cloudflare” without quotes returns your comment as the top hit :P
- rurban 8y ago
  I have them here: https://github.com/cloudflare/zlib.git https://github.com/cloudflare/zlib.git https://github.com/rurban/crcutil.git https://github.com/rurban/crcutil.git