CRC32 performance

[Bryan Duxbury <br...@rapleaf.com>]

Hey all,

I've been profiling our map/reduce applications quite a bit over the  
last few weeks to try and get some performance improvements in our  
jobs. I noticed an interesting bottleneck in Hadoop itself I thought  
I should bring up.

FSDataOutputStream appears to create a CRC of the data being written  
via FSOutputSummer.write1. It uses the built-in Java CRC32  
implementation to do so. However, out of a 41-second reducer main  
thread, this CRC call is taking up around 13 seconds, or about 32%.  
This appears to dwarf the actual writing time  
(FSOutputSummer.flushBuffer) which only takes 1.9s (5%). This seems  
like an incredibly large amount of overhead to pay.

To my surprise, there's already a faster CRC implementation in the  
Java standard library called Adler32 which is described as "almost as  
reliable as a CRC-32 but can be computed much faster". This sounds  
very attractive, indeed. Some quick tests indicate that Adler32 is  
about 3x as fast.

Is there any reason why CRC32 was chosen, or why Adler32 wouldn't be  
an acceptable CRC? I understand that Adler32 is bad for small  
messages (small as in hundreds of bytes), but since this is behind a  
buffered writer, the messages should all be thousands of bytes to  
begin with. Worst case, I guess we could select the CRC algorithm  
based on the size of the message, using CRC32 for small messages and  
Adler32 for bigger ones.

-Bryan

Re: CRC32 performance

[Raghu Angadi <ra...@yahoo-inc.com>]

As we make more buffering improvements in Hadoop (HADOOP-3065, 
HADOOP-1702 etc), the relative cost of checksums keeps growing.

+1 for looking into better checksums.

Raghu.

Raghu Angadi wrote:
> 
> Datanodes and persistent storage can deal with different checksums. But 
> client does not support it yet (easier to fix since it is not tied to 
> persistent data).
> 
> Regd CPU comparisions, most reliable I found is to test with either by 
> maxing out CPU on a machine and comparing the time taken, or comparing 
> cpu reported in /proc/pid/stat. see 
> https://issues.apache.org/jira/browse/HADOOP-1702?focusedCommentId=12575553#action_12575553 
> ) for e.g.
> 
> Raghu.
> 
>

Re: CRC32 performance

[Raghu Angadi <ra...@yahoo-inc.com>]

Datanodes and persistent storage can deal with different checksums. But 
client does not support it yet (easier to fix since it is not tied to 
persistent data).

Regd CPU comparisions, most reliable I found is to test with either by 
maxing out CPU on a machine and comparing the time taken, or comparing 
cpu reported in /proc/pid/stat. see 
https://issues.apache.org/jira/browse/HADOOP-1702?focusedCommentId=12575553#action_12575553 
) for e.g.

Raghu.

Bryan Duxbury wrote:
> I put together a small benchmark app just for the two CRC algorithms 
> alone (code available on request). I run the same amount of data through 
> each one in exactly the same pattern. The results look like this:
> 
> Adler32: 1983 ms
> CRC32: 6514 ms
> Ratio: 0.30442125
> 
> The ratio holds for different lengths of tests, too. This would seem to 
> indicate that there's a fair bit of benefit to be extracted from 
> upgrading to Adler. From looking at the HDFS code, it even seems like 
> it's designed to work with different implementations of Checksum, so it 
> doesn't seem like it would be hard to use this instead.
> 
> I might still take the time to build an isolated benchmark that's 
> actually the hadoop code, but I thought I'd share these intermediate 
> results.
> 
> -Bryan
> 
> On Oct 7, 2008, at 10:31 AM, Doug Cutting wrote:
> 
>> Don't try this on anything but an experimental filesystem.  If you can 
>> simply find the places where HDFS calls the CRC algorithm and replace 
>> them with zeros, then you should be able to get a reasonable benchmark.
>>
>> Doug
>>
>> Bryan Duxbury wrote:
>>> I'm willing to give this a shot. Let me just be sure I understand 
>>> what I'd have to do: if I make it stop computing CRCs altogether, I 
>>> need to make changes in the datanode as well, right? To stop checking 
>>> validity of CRCs? Will this break anything interesting and unexpected?
>>> On Oct 6, 2008, at 4:58 PM, Doug Cutting wrote:
>>>> Bryan Duxbury wrote:
>>>>> I am profiling with YourKit on random reducers. I'm also running on 
>>>>> HDFS, so I don't know how one would go about disabling CRCs.
>>>>
>>>> Hack the CRC-computing code to fill things with zeros?
>>>>
>>>> Doug
> 

Re: CRC32 performance

[Bryan Duxbury <br...@rapleaf.com>]

I put together a small benchmark app just for the two CRC algorithms  
alone (code available on request). I run the same amount of data  
through each one in exactly the same pattern. The results look like  
this:

Adler32: 1983 ms
CRC32: 6514 ms
Ratio: 0.30442125

The ratio holds for different lengths of tests, too. This would seem  
to indicate that there's a fair bit of benefit to be extracted from  
upgrading to Adler. From looking at the HDFS code, it even seems like  
it's designed to work with different implementations of Checksum, so  
it doesn't seem like it would be hard to use this instead.

I might still take the time to build an isolated benchmark that's  
actually the hadoop code, but I thought I'd share these intermediate  
results.

-Bryan

On Oct 7, 2008, at 10:31 AM, Doug Cutting wrote:

> Don't try this on anything but an experimental filesystem.  If you  
> can simply find the places where HDFS calls the CRC algorithm and  
> replace them with zeros, then you should be able to get a  
> reasonable benchmark.
>
> Doug
>
> Bryan Duxbury wrote:
>> I'm willing to give this a shot. Let me just be sure I understand  
>> what I'd have to do: if I make it stop computing CRCs altogether,  
>> I need to make changes in the datanode as well, right? To stop  
>> checking validity of CRCs? Will this break anything interesting  
>> and unexpected?
>> On Oct 6, 2008, at 4:58 PM, Doug Cutting wrote:
>>> Bryan Duxbury wrote:
>>>> I am profiling with YourKit on random reducers. I'm also running  
>>>> on HDFS, so I don't know how one would go about disabling CRCs.
>>>
>>> Hack the CRC-computing code to fill things with zeros?
>>>
>>> Doug

Re: CRC32 performance

[Doug Cutting <cu...@apache.org>]

Don't try this on anything but an experimental filesystem.  If you can 
simply find the places where HDFS calls the CRC algorithm and replace 
them with zeros, then you should be able to get a reasonable benchmark.

Doug

Bryan Duxbury wrote:
> I'm willing to give this a shot. Let me just be sure I understand what 
> I'd have to do: if I make it stop computing CRCs altogether, I need to 
> make changes in the datanode as well, right? To stop checking validity 
> of CRCs? Will this break anything interesting and unexpected?
> 
> On Oct 6, 2008, at 4:58 PM, Doug Cutting wrote:
> 
>> Bryan Duxbury wrote:
>>> I am profiling with YourKit on random reducers. I'm also running on 
>>> HDFS, so I don't know how one would go about disabling CRCs.
>>
>> Hack the CRC-computing code to fill things with zeros?
>>
>> Doug
> 

Re: CRC32 performance

[Bryan Duxbury <br...@rapleaf.com>]

I'm willing to give this a shot. Let me just be sure I understand  
what I'd have to do: if I make it stop computing CRCs altogether, I  
need to make changes in the datanode as well, right? To stop checking  
validity of CRCs? Will this break anything interesting and unexpected?

On Oct 6, 2008, at 4:58 PM, Doug Cutting wrote:

> Bryan Duxbury wrote:
>> I am profiling with YourKit on random reducers. I'm also running  
>> on HDFS, so I don't know how one would go about disabling CRCs.
>
> Hack the CRC-computing code to fill things with zeros?
>
> Doug

Re: CRC32 performance

[Doug Cutting <cu...@apache.org>]

Bryan Duxbury wrote:
> I am profiling with YourKit on random reducers. I'm also running on 
> HDFS, so I don't know how one would go about disabling CRCs.

Hack the CRC-computing code to fill things with zeros?

Doug

Re: CRC32 performance

[Bryan Duxbury <br...@rapleaf.com>]

I am profiling with YourKit on random reducers. I'm also running on  
HDFS, so I don't know how one would go about disabling CRCs.

-Bryan

On Oct 6, 2008, at 4:35 PM, Doug Cutting wrote:

> How are you profiling?  I don't trust most profilers.
>
> Have you tried, e.g., disabling checksums and seeing how much  
> performance is actually gained?  For the local filesystem, you can  
> easily disable checksums by binding file: URI's to  
> RawLocalFileSystem in your configuration.
>
> Doug
>
> Bryan Duxbury wrote:
>> Hey all,
>> I've been profiling our map/reduce applications quite a bit over  
>> the last few weeks to try and get some performance improvements in  
>> our jobs. I noticed an interesting bottleneck in Hadoop itself I  
>> thought I should bring up.
>> FSDataOutputStream appears to create a CRC of the data being  
>> written via FSOutputSummer.write1. It uses the built-in Java CRC32  
>> implementation to do so. However, out of a 41-second reducer main  
>> thread, this CRC call is taking up around 13 seconds, or about  
>> 32%. This appears to dwarf the actual writing time  
>> (FSOutputSummer.flushBuffer) which only takes 1.9s (5%). This  
>> seems like an incredibly large amount of overhead to pay.
>> To my surprise, there's already a faster CRC implementation in the  
>> Java standard library called Adler32 which is described as "almost  
>> as reliable as a CRC-32 but can be computed much faster". This  
>> sounds very attractive, indeed. Some quick tests indicate that  
>> Adler32 is about 3x as fast.
>> Is there any reason why CRC32 was chosen, or why Adler32 wouldn't  
>> be an acceptable CRC? I understand that Adler32 is bad for small  
>> messages (small as in hundreds of bytes), but since this is behind  
>> a buffered writer, the messages should all be thousands of bytes  
>> to begin with. Worst case, I guess we could select the CRC  
>> algorithm based on the size of the message, using CRC32 for small  
>> messages and Adler32 for bigger ones.
>> -Bryan

Re: CRC32 performance

[Doug Cutting <cu...@apache.org>]

How are you profiling?  I don't trust most profilers.

Have you tried, e.g., disabling checksums and seeing how much 
performance is actually gained?  For the local filesystem, you can 
easily disable checksums by binding file: URI's to RawLocalFileSystem in 
your configuration.

Doug

Bryan Duxbury wrote:
> Hey all,
> 
> I've been profiling our map/reduce applications quite a bit over the 
> last few weeks to try and get some performance improvements in our jobs. 
> I noticed an interesting bottleneck in Hadoop itself I thought I should 
> bring up.
> 
> FSDataOutputStream appears to create a CRC of the data being written via 
> FSOutputSummer.write1. It uses the built-in Java CRC32 implementation to 
> do so. However, out of a 41-second reducer main thread, this CRC call is 
> taking up around 13 seconds, or about 32%. This appears to dwarf the 
> actual writing time (FSOutputSummer.flushBuffer) which only takes 1.9s 
> (5%). This seems like an incredibly large amount of overhead to pay.
> 
> To my surprise, there's already a faster CRC implementation in the Java 
> standard library called Adler32 which is described as "almost as 
> reliable as a CRC-32 but can be computed much faster". This sounds very 
> attractive, indeed. Some quick tests indicate that Adler32 is about 3x 
> as fast.
> 
> Is there any reason why CRC32 was chosen, or why Adler32 wouldn't be an 
> acceptable CRC? I understand that Adler32 is bad for small messages 
> (small as in hundreds of bytes), but since this is behind a buffered 
> writer, the messages should all be thousands of bytes to begin with. 
> Worst case, I guess we could select the CRC algorithm based on the size 
> of the message, using CRC32 for small messages and Adler32 for bigger ones.
> 
> -Bryan