On Wed, 18 May 2005 13:50:22 +0200, I wrote:
>The most important figure is, that at MaxSpeed (/O2) 2x32 is almost
>twice as fast as CRC32 while only being marginally slower than CRC32.
^^^^^
Silly typo! That should have been:
The most important figure is, that at MaxSpeed (/O2) 2x32 is almost
twice as fast as CRC64 while only being marginally slower than CRC32.

Servus
Manfred


---------------------------(end of broadcast)---------------------------
TIP 1: subscribe and unsubscribe commands go to majordomo@postgresql.org

> -----Original Message-----
> From: Manfred Koizar [mailto:mkoi-pg@aon.at]
> Sent: 25 May 2005 20:25
> To: Manfred Koizar
> Cc: Tom Lane; Greg Stark; Bruce Momjian; Mark Cave-Ayland
> (External); pgsql-hackers@postgresql.org
> Subject: Re: [HACKERS] Cost of XLogInsert CRC calculations

(cut)

> The most important figure is, that at MaxSpeed (/O2) 2x32 is
> almost twice as fast as CRC64 while only being marginally
> slower than CRC32.
>
> Servus
> Manfred





---------------------------(end of broadcast)---------------------------
TIP 1: subscribe and unsubscribe commands go to majordomo@postgresql.org

> -----Original Message-----
> From: Manfred Koizar [mailto:mkoi-pg@aon.at]
> Sent: 25 May 2005 20:25
> To: Manfred Koizar
> Cc: Tom Lane; Greg Stark; Bruce Momjian; Mark Cave-Ayland
> (External); pgsql-hackers@postgresql.org
> Subject: Re: [HACKERS] Cost of XLogInsert CRC calculations

(cut)

> The most important figure is, that at MaxSpeed (/O2) 2x32 is
> almost twice as fast as CRC64 while only being marginally
> slower than CRC32.
>
> Servus
> Manfred


Hi Manfred,

Sorry about taking a while to respond on this one - the hard drive on my
laptop crashed . I repeated your tests on my P4 laptop with gcc 3.2.3 and
reproduced the results below:


Opt 32 32a 32b 2x32 64 64a 64b
--------------------------------------------------------
O1 4.91 4.86 5.43 6.00 11.4 11.39 11.39
O2 4.96 4.94 4.69 5.18 15.86 18.75 24.73
O3 4.82 4.83 4.64 5.18 15.14 13.77 14.73

^^^^^^^^^^^^

So in summary I would say:

- Calculating a CRC64 using 2 x 32 int can be 3 times as fast as
using 1 x 64 int on
my 32-bit Intel laptop with gcc.

- The time difference between CRC32 and CRC64 is about 0.5s in the
worse case
shown during testing, so staying with CRC64 would not inflict too
great a penalty.


Kind regards,

Mark.

------------------------
WebBased Ltd
South West Technology Centre
Tamar Science Park
Plymouth
PL6 8BT

T: +44 (0)1752 797131
F: +44 (0)1752 791023
W: http://www.webbased.co.uk



---------------------------(end of broadcast)---------------------------
TIP 7: don't forget to increase your free space map settings

"Mark Cave-Ayland" <m.cave-ayland@webbased.co.uk> writes:
> Opt 32 32a 32b 2x32 64 64a 64b
> --------------------------------------------------------
> O1 4.91 4.86 5.43 6.00 11.4 11.39 11.39
> O2 4.96 4.94 4.69 5.18 15.86 18.75 24.73
> O3 4.82 4.83 4.64 5.18 15.14 13.77 14.73

Not sure I believe these numbers. Shouldn't 2x32 be about twice as slow
as just one 32-bit CRC?

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 5: Have you checked our extensive FAQ?

http://www.postgresql.org/docs/faq

> -----Original Message-----
> From: Tom Lane [mailto:tgl@sss.pgh.pa.us]
> Sent: 27 May 2005 15:00
> To: Mark Cave-Ayland (External)
> Cc: 'Manfred Koizar'; 'Greg Stark'; 'Bruce Momjian';
> pgsql-hackers@postgresql.org
> Subject: Re: [HACKERS] Cost of XLogInsert CRC calculations
>
>
> "Mark Cave-Ayland" <m.cave-ayland@webbased.co.uk> writes:
> > Opt 32 32a 32b 2x32 64 64a 64b
> > --------------------------------------------------------
> > O1 4.91 4.86 5.43 6.00 11.4 11.39 11.39
> > O2 4.96 4.94 4.69 5.18 15.86 18.75 24.73
> > O3 4.82 4.83 4.64 5.18 15.14 13.77 14.73
>
> Not sure I believe these numbers. Shouldn't 2x32 be about
> twice as slow as just one 32-bit CRC?

Well it surprised me, although Manfred's results with VC6 on /MaxSpeed show
a similar margin. The real killer has to be that I wrote a CRC32 routine in
x86 inline assembler (which in comparison to the gcc-produced version stores
the CRC for each iteration in registers instead of in memory as part of the
current frame) which comes in at 6.5s....


Kind regards,

Mark.

------------------------
WebBased Ltd
South West Technology Centre
Tamar Science Park
Plymouth
PL6 8BT

T: +44 (0)1752 797131
F: +44 (0)1752 791023
W: http://www.webbased.co.uk



---------------------------(end of broadcast)---------------------------
TIP 4: Don't 'kill -9' the postmaster

> -----Original Message-----
> From: Tom Lane [mailto:tgl@sss.pgh.pa.us]
> Sent: 27 May 2005 15:00
> To: Mark Cave-Ayland (External)
> Cc: 'Manfred Koizar'; 'Greg Stark'; 'Bruce Momjian';
> pgsql-hackers@postgresql.org
> Subject: Re: [HACKERS] Cost of XLogInsert CRC calculations

(cut)

> Not sure I believe these numbers. Shouldn't 2x32 be about twice as
> slow as just one 32-bit CRC?

Also I've just quickly tested on the Xeon Linux FC1 box I used with my
original program using Manfred's program and the margin is even closer:

Opt 32 32a 32b 2x32 64 64a 64b
------------------------------------------------------
O1 2.75 2.81 2.71 3.16 3.53 3.64 7.25
O2 2.75 2.78 2.87 2.94 7.63 10.61 11.93
O3 2.84 2.85 3.03 2.99 7.63 7.64 7.71

I don't know whether gcc is just producing an inefficient CRC32 compared to
2x32 but the results seem very odd.... There must be something else we are
missing?


Kind regards,

Mark.

------------------------
WebBased Ltd
South West Technology Centre
Tamar Science Park
Plymouth
PL6 8BT

T: +44 (0)1752 797131
F: +44 (0)1752 791023
W: http://www.webbased.co.uk



---------------------------(end of broadcast)---------------------------
TIP 1: subscribe and unsubscribe commands go to majordomo@postgresql.org

"Mark Cave-Ayland" <m.cave-ayland@webbased.co.uk> writes:
> I don't know whether gcc is just producing an inefficient CRC32 compared to
> 2x32 but the results seem very odd.... There must be something else we are
> missing?

I went back and looked at the code, and see that I was misled by
terminology: what we've been calling "2x32" in this thread is not two
independent CRC32 calculations, it is use of 32-bit arithmetic to execute
one CRC64 calculation. The inner loop looks like

while (__len-- > 0)
{
int __tab_index = ((int) (__crc1 >> 24) ^ *__data++) & 0xFF;

__crc1 = crc_table1[__tab_index] ^ ((__crc1 << 8) | (__crc0 >> 24));
__crc0 = crc_table0[__tab_index] ^ (__crc0 << 8);
}

whereas a plain CRC32 looks like

while (__len-- > 0)
{
int __tab_index = ((int) (crc >> 24) ^ *__data++) & 0xFF;

crc = crc_table[__tab_index] ^ (crc << 8);
}

where the crc variables are uint32 in both cases. (The true 64-bit
calculation looks like the latter, except that the crc variable is
uint64, as is the crc_table, and the >> 24 becomes >> 56. The "2x32"
code is an exact emulation of the true 64-bit code, with __crc1 and
__crc0 holding the high and low halves of the 64-bit crc.)

In my tests the second loop is about 10% faster than the first on an
Intel machine, and maybe 20% faster on HPPA. So evidently the bulk of
the cost is in the __tab_index calculation, and not so much in the table
fetches. This is still a bit surprising, but it's not totally silly.

Based on the numbers we've seen so far, one could argue for staying
with the 64-bit CRC, but changing the rule we use for selecting which
implementation code to use: use the true 64-bit code only when
sizeof(unsigned long) == 64, and otherwise use the 2x32 code, even if
there is a 64-bit unsigned long long type available. This essentially
assumes that the unsigned long long type isn't very efficient, which
isn't too unreasonable. This would buy most of the speedup without
giving up anything at all in the error-detection department.

Alternatively, we might say that 64-bit CRC was overkill from day one,
and we'd rather get the additional 10% or 20% or so speedup. I'm kinda
leaning in that direction, but only weakly.

Comments?

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 7: don't forget to increase your free space map settings

Tom Lane wrote:
> Alternatively, we might say that 64-bit CRC was overkill from day one,
> and we'd rather get the additional 10% or 20% or so speedup. I'm kinda
> leaning in that direction, but only weakly.

Yes, I lean in that direction too since the CRC calculation is showing
up in our profiling.

--
Bruce Momjian | http://candle.pha.pa.us
pgman@candle.pha.pa.us | (610) 359-1001
+ If your life is a hard drive, | 13 Roberts Road
+ Christ can be your backup. | Newtown Square, Pennsylvania 19073

---------------------------(end of broadcast)---------------------------
TIP 2: you can get off all lists at once with the unregister command
(send "unregister YourEmailAddressHere" to majordomo@postgresql.org)

> -----Original Message-----
> From: Tom Lane [mailto:tgl@sss.pgh.pa.us]
> Sent: 27 May 2005 17:49
> To: Mark Cave-Ayland (External)
> Cc: 'Manfred Koizar'; 'Greg Stark'; 'Bruce Momjian';
> pgsql-hackers@postgresql.org
> Subject: Re: [HACKERS] Cost of XLogInsert CRC calculations

(cut)

> I went back and looked at the code, and see that I was misled by
> terminology: what we've been calling "2x32" in this thread is
> not two independent CRC32 calculations, it is use of 32-bit
> arithmetic to execute one CRC64 calculation.

Yeah, I did find the terminology a little confusing until I looked at the
source itself. It doesn't make much sense publishing numbers if you don't
know their meaning

> Based on the numbers we've seen so far, one could argue for
> staying with the 64-bit CRC, but changing the rule we use for
> selecting which implementation code to use: use the true
> 64-bit code only when sizeof(unsigned long) == 64, and
> otherwise use the 2x32 code, even if there is a 64-bit
> unsigned long long type available. This essentially assumes
> that the unsigned long long type isn't very efficient, which
> isn't too unreasonable. This would buy most of the speedup
> without giving up anything at all in the error-detection department.

All our servers are x86 based Linux with gcc, so if a factor of 2 speedup
for CPU calculations is the minimum improvement that we get as a result of
this thread then I would be very happy.

> Alternatively, we might say that 64-bit CRC was overkill from
> day one, and we'd rather get the additional 10% or 20% or so
> speedup. I'm kinda leaning in that direction, but only weakly.

What would you need to persuade you either way? I believe that disk drives
use CRCs internally to verify that the data has been read correctly from
each sector. If the majority of the errors would be from a disk failure,
then a corrupt sector would have to pass the drive CRC *and* the PostgreSQL
CRC in order for an XLog entry to be considered valid. I would have thought
the chances of this being able to happen would be reasonably small and so
even with CRC32 this can be detected fairly accurately.

In the case of an OS crash then we could argue that there may be a partially
written sector to the disk, in which case again either one or both of the
drive CRC and the PostgreSQL CRC would be incorrect and so this condition
could also be reasonably detected using CRC32.

As far as I can tell, the main impact of this would be that we would reduce
the ability to accurately detect multiple random bit errors, which is more
the type of error I would expect to occur in RAM (alpha particles etc.). How
often would this be likely to occur? I believe that different generator
polynomials have different characteristics that can make them more sensitive
to a particular type of error. Perhaps Manfred can tell us the generator
polynomial that was used to create the lookup tables?


Kind regards,

Mark.

------------------------
WebBased Ltd
South West Technology Centre
Tamar Science Park
Plymouth
PL6 8BT

T: +44 (0)1752 797131
F: +44 (0)1752 791023
W: http://www.webbased.co.uk



---------------------------(end of broadcast)---------------------------
TIP 6: Have you searched our list archives?

http://archives.postgresql.org

"Mark Cave-Ayland" <m.cave-ayland@webbased.co.uk> writes:
>> Alternatively, we might say that 64-bit CRC was overkill from
>> day one, and we'd rather get the additional 10% or 20% or so
>> speedup. I'm kinda leaning in that direction, but only weakly.

> What would you need to persuade you either way? I believe that disk drives
> use CRCs internally to verify that the data has been read correctly from
> each sector. If the majority of the errors would be from a disk failure,
> then a corrupt sector would have to pass the drive CRC *and* the PostgreSQL
> CRC in order for an XLog entry to be considered valid. I would have thought
> the chances of this being able to happen would be reasonably small and so
> even with CRC32 this can be detected fairly accurately.

It's not really a matter of backstopping the hardware's error detection;
if we were trying to do that, we'd keep a CRC for every data page, which
we don't. The real reason for the WAL CRCs is as a reliable method of
identifying the end of WAL: when the "next record" doesn't checksum you
know it's bogus. This is a nontrivial point because of the way that we
re-use WAL files --- the pages beyond the last successfully written page
aren't going to be zeroes, they'll be filled with random WAL data.

Personally I think CRC32 is plenty for this job, but there were those
arguing loudly for CRC64 back when we made the decision originally ...

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 4: Don't 'kill -9' the postmaster