3 ms·
Could you combine both techniques to run both the SIMD version on some chunks and the crc32 instruction on other chunks, in parallel? Of course this would only
by terrelln 4y ago
Could you combine both techniques to run both the SIMD version on some chunks and the crc32 instruction on other chunks, in parallel? Of course this would only work if they execute on different ports.
- dougall 4y agoHmm, yeah, this might work out... Two SIMD uops process 16 bytes, so each SIMD uop is doing eight bytes of work - the same as CRC32X, but with more frontend pressure (and preferable because they can run on any of the four SIMD ports, not just the one distinct CRC32X port). It gets a bit messy, and we can't expect a ton from this approach - the same loop with only the loads only runs at ~86GB/s, but it'd be worth a shot.
- AlotOfReading 4y agoYes, and ZLib provides an excellent example of how to do this (it's called braiding in the source code). There's an additional initialization and combination cost though. It doesn't really make sense for short messages.
- terrelln 4y agoThanks for the pointer, will have to take a look!
- sgtnoodle 4y agoIt seems like CRC inherently depends on results from earlier calculations, so it would be hard to parallelize like that. You could potentially do multiple independent CRC calculations in parallel, but then you're getting into more niche use cases.
- aaaaaaaaaaab 4y agoWrong. CRC is just polynomial division, which is simple to do in a divide and conquer fashion. It's pretty easy to derive CRC(A concat B) from CRC(A) and CRC(B). It needs a multiplication and a XOR.
- sgtnoodle 4y agoah, that's pretty cool! It looks like concatenation is a O(log(n)) operation involving appending a bunch of zeros rather than just a multiplication, though?
- aaaaaaaaaaab 4y agoIt depends. (A(x) mod Q(x)) * (B(x) mod Q(x)) = (A(x) * B(x)) mod Q(x) If the chunk size N is known beforehand you can pre-calculate x^N mod Q(x), so appending N zeros will be an O(1) multiplication. Only if the chunk size is not known, you have to calculate x^N mod Q(x) via modular exponentiation, which is O(log n). But you only need to do this once, and then you can reuse the value for all subsequent chunks.