On Apr22, 2013, at 18:25 , Ants Aasma <a...@cybertec.at> wrote: > I was just now writing up a generic C based patch based on the > parallel FNV-1a + shift that we discussed with Florian with an added > round of mixing. Testing the performance in isolation indicates that: > 1) it is about an order of magnitude faster than the Sarwate CRC > method used in Postgresql. > 2) it is about 2x faster than fastest software based CRC method. > 3) by using -msse4.1 -funroll-loops -ftree-vectorize compilation > options the performance improves 5x. (within 20% of handcoded ASM) > > This leaves lingering doubts about the quality of the checksum. It's > hard if not impossible to prove absence of interesting patterns that > would trigger collisions. I do know the checksum quality is miles > ahead of the Fletcher sum originally proposed and during the last week > I haven't been able to think of a way to make the collision rate > significantly differ from CRC.
Note though that CRCs may very well have similar "interesting" corruption patterns which don't cause the checksum to change, though. The only guarantee they really give is that those patterns will involve more than N-1 flipped bits, where N is the hamming distance of the CRC. For 16-bit checksums, N can at most be 16 (since XOR-ing the data with a shifted version of the CRC polynomial will not cause the checksum to change). Thus, once more than two bytes on a page get corrupted, CRCs may not have any advantage over fnv1+shift or similar approaches. They may even work worse, since detecting some forms of corruption with 100% certainty means missing others with a probability of more than 2^-16. Some CRC polynomials for example detect all corruptions which affect an odd number of bits, but in turn have a probability of 2^-15 of missing ones which affect an even number of bits. Since we're mostly attempting to protect against disk, not memory corruption here, I'm not convinced at all that errors in only a few bits are all that common, and certainly not that they are more likely than other forms of corruption. I'd expect, for example, that blocks of 512 bytes (i.e. one sector) suddenly reading 0 is at least as likely as a single flipped bit. The one downside of the fnv1+shift approach is that it's built around the assumption that processing 64-bytes at once is the sweet spot. That might be true for x86 and x86_64 today, but it won't stay that way for long, and quite surely isn't true for other architectures. That doesn't necessarily rule it out, but it certainly weakens the argument that slipping it into 9.3 avoids having the change the algorithm later... best regards, Florian Pflug -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
