On 2013-03-06 13:34:21 +0200, Heikki Linnakangas wrote: > On 06.03.2013 10:41, Simon Riggs wrote: > >On 5 March 2013 18:02, Jeff Davis<pg...@j-davis.com> wrote: > > > >>Fletcher is probably significantly faster than CRC-16, because I'm just > >>doing int32 addition in a tight loop. > >> > >>Simon originally chose Fletcher, so perhaps he has more to say. > > > >IIRC the research showed Fletcher was significantly faster for only a > >small loss in error detection rate. > > > >It was sufficient to make our error detection> 1 million times > >better, possibly more. That seems sufficient to enable early detection > >of problems, since if we missed the first error, a second is very > >likely to be caught (etc). So I am assuming that we're trying to catch > >a pattern of errors early, rather than guarantee we can catch the very > >first error. > > Fletcher's checksum is good in general, I was mainly worried about > truncating the Fletcher-64 into two 8-bit values. I can't spot any obvious > weakness in it, but if it's indeed faster and as good as a straightforward > Fletcher-16, I wonder why that method is not more widely used.
I personally am not that convinced that fletcher is a such good choice given that it afaik doesn't distinguish between all-zero and all-one runs that are long enough. > Another thought is that perhaps something like CRC32C would be faster to > calculate on modern hardware, and could be safely truncated to 16-bits using > the same technique you're using to truncate the Fletcher's Checksum. Greg's > tests showed that the overhead of CRC calculation is significant in some > workloads, so it would be good to spend some time to optimize that. It'd be > difficult to change the algorithm in a future release without breaking > on-disk compatibility, so let's make sure we pick the best one. I had implemented a noticeably faster CRC32 implementation somewhere around 201005202227.49990.and...@anarazel.de . I have since repeatedly seen pg's CRC32 implementation being a major limitation, so I think brushing up that patch would be a good idea. We might think about switching the polynom for WAL at the same time, given, as you say, CRC32c is available in hardware. The bigger problem is probably stuff like the control file et al. Greetings, Andres Freund -- Andres Freund http://www.2ndQuadrant.com/ PostgreSQL Development, 24x7 Support, Training & Services -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
