CRC calculation can be improved

[decipherer]

After making pull request #301 (Performance enhancement by skipping the (unnecessary) checks in ArraySegment) I started to wonder if it was possible to make the CRC calculation even faster. Since CRC calculation speed has a big influence on overall unzipping speed (and probably zipping too) this can potentially greatly improve the performance of SharpZipLib.

Sure enough, I found an algorithm that is significantly faster than the algorithm currently in use in SharpZipLib. Total unzipping time dropped by approx. 33% after I used this algorithm in SharpZipLib. The algorithm itself can be found here: https://github.com/force-net/Crc32.NET/blob/develop/Crc32.NET/SafeProxy.cs
Please note that the CRC lookup table is generated during the first call, so the first call is slightly slower (although I can hardly measure any difference on an 8k zipped file)

I would like to make a pull request to incorporate this faster algorithm in SharpZipLib. But I'm not sure how best to incorporate this since SharpZipLib at the moment does not have a lot of external dependencies. I can either

• Reference CRC32.net through nuget (no more maintenance of the CRC code within SharpZipLib, but an extra external dependency and less flexibility)
• Take only the code we need and incorporate that in SharpZipLib (Possible maintenance in the future, but it would add flexibility to i.e. pre-calculate the CRC lookup table and speed up the first call like it is done now in SharpZipLib)
• Internalize the dependency on CRC32.net. At the moment I'm not sure how to go about it though.
• ..? Maybe there's some other preferred way?

Can you please advise?

[Numpsy]

Sounds nice, and it does seem a shame to add an extra external dependency for what looks like a small amount of code.

Would it be possible and/or reasonable to 'internalize' it by adding it as a submodule and then including the source file for the internal class in the SZL project? maybe overkill compared ot just copying one or two files though.

[piksel]

We could use it as a paket dependency. One of the "core" directives I have for this repo is to not add any consumer dependencies.
Preferably we should do this without polluting the namespace (internal etc.)

[Numpsy]

On a related note, the Crc32.net issue @ force-net/Crc32.NET#10 refers to a CRC32 implementation using intrinsics for extra performance.
Sounce interesting, though the Spreads repo is MPL licenced so not as nice as the Crc32.NET licence.

[decipherer]

That intrinsics implementation looks to be very fast indeed! A pity that the license does not match.

I have not worked with paket before, but it seems it's possible to add a reference to a specific GitHub file,, so a reference to SafeProxy.cs could be added this way. Since this class is internal it would meet that requirement also.

It seems to be somewhat overkill to introduce paket for just referencing a single file though. Wouldn't it be easier to just copy the one file into SharpZipLib?

[Numpsy]

It seems to be somewhat overkill to introduce paket for just referencing a single file though. Wouldn't it be easier to just copy the one file into SharpZipLib?

Sounds the simplest idea if it is just one file - not something that would be complicated to update if a new version were picked up later.

[piksel]

Yes, perhaps it's a bit overkill. We could just add the source repo and commit hash to the header as a mean of upstream reference.

[decipherer]

Ok, I will create a pull request for further discussion based on copying the CRC32.net code whilst referencing the original code in the header.

Thanks for all the input thus far!

[decipherer]

I created a pull request for this: #318
It might be a bit different than expected, as upon implementation I found out that CRC32 is also used for Bzip2. This is a different form, so it was not supported by CRC32.NET directly. Therefore I made some changes to the code I pulled from that repository. The credits are still there though. Also credits go out to https://github.com/Michaelangel007/crc32 for accurately describing the different CRC32 forms.

Some remarks:

• I split up the unit testing for the checksums and added some more tests
• I really wanted to test the output from the internal static method in CRC32, as the implementation changed. Since I didn't want to make it public, I added an InternalsVisibleTo attribute to the main assembly.
• Repeating code in Crc32Proxy is avoided by using some Func's. I could have subclassed or write if/else statements, but I like it this way. I tested if there's any speed reduction by not repeating the code, but it is very minimal (< 5%) and only if you use a very small buffer.

Please let me know what you think.

[Numpsy]

I don't know much about the implementation details of the CRC bits, but fwiw, I tried testing the change against a simple unit test that I previously wrote to test creating a Zip64 file with several gigabytes of zeros, and:

Creating the file took 1 min 42 seconds using the master branch and 1 min 20 seconds with this change.
Opening the file and calling TestArchive on it takes 50 seconds with the master branch and 25 seconds with this change.

So, a pretty good speed up.

[decipherer]

Thanks for testing! I'm no CRC expert by any means either, but the writeup from Michealangel007 is pretty good, with some nice code examples.

I made another pull request (#319) for this, which is basically the same change, but using subclassing instead of Func<>'s. I feel that some people probably might like this better.

[Numpsy]

fwiw, added a couple of BenchmarkDotNet benchmarks comparing this PR to the current code @ #328

[piksel]

I am currently running benchmarks on #319 and #516 using

dotnet run -c Release -f netcoreapp2.1 -- -f '*' --join

[piksel]

Current implementation (master)

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19041.508 (2004/?/20H1)
AMD Ryzen 7 3800X, 1 CPU, 16 logical and 8 physical cores
.NET Core SDK=5.0.100-preview.8.20417.9
  [Host]     : .NET Core 2.1.21 (CoreCLR 4.6.29130.01, CoreFX 4.6.29130.02), X64 RyuJIT
  Job-AVMSLM : .NET Core 2.1.21 (CoreCLR 4.6.29130.01, CoreFX 4.6.29130.02), X64 RyuJIT
  Job-HCWAMU : .NET Framework 4.8 (4.8.4220.0), X64 RyuJIT

Method	Toolchain	Mean	Error	StdDev	Ratio	RatioSD	Allocated
Adler32LargeUpdate	.NET Core 2.1	198.6 ms	2.95 ms	2.61 ms	1.02	0.02	-
Adler32LargeUpdate	net461	195.4 ms	3.35 ms	2.97 ms	1.00	0.00	-
BZip2CrcLargeUpdate	.NET Core 2.1	1,164.6 ms	6.16 ms	5.76 ms	1.02	0.01	-
BZip2CrcLargeUpdate	net461	1,137.3 ms	9.38 ms	8.78 ms	1.00	0.00	-
Crc32LargeUpdate	.NET Core 2.1	945.4 ms	5.24 ms	4.90 ms	1.00	0.01	-
Crc32LargeUpdate	net461	947.4 ms	3.10 ms	2.74 ms	1.00	0.00	-
ReadZipInputStream	.NET Core 2.1	356.8 ms	5.05 ms	4.48 ms	1.00	0.02	106616 B
ReadZipInputStream	net461	358.1 ms	4.25 ms	3.97 ms	1.00	0.00	114736 B
WriteZipOutputStream	.NET Core 2.1	612.9 ms	11.63 ms	10.87 ms	0.96	0.02	362648 B
WriteZipOutputStream	net461	635.3 ms	11.78 ms	11.57 ms	1.00	0.00	368928 B

[piksel]

PR #319

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19041.508 (2004/?/20H1)
AMD Ryzen 7 3800X, 1 CPU, 16 logical and 8 physical cores
.NET Core SDK=5.0.100-preview.8.20417.9
  [Host]     : .NET Core 2.1.21 (CoreCLR 4.6.29130.01, CoreFX 4.6.29130.02), X64 RyuJIT
  Job-RQIUQR : .NET Core 2.1.21 (CoreCLR 4.6.29130.01, CoreFX 4.6.29130.02), X64 RyuJIT
  Job-QIKFQA : .NET Framework 4.8 (4.8.4220.0), X64 RyuJIT

Method	Toolchain	Mean	Error	StdDev	Ratio	RatioSD	Allocated
Adler32LargeUpdate	.NET Core 2.1	200.9 ms	3.81 ms	3.56 ms	1.02	0.02	-
Adler32LargeUpdate	net461	196.6 ms	2.10 ms	1.86 ms	1.00	0.00	-
BZip2CrcLargeUpdate	.NET Core 2.1	152.3 ms	3.01 ms	3.47 ms	1.01	0.03	-
BZip2CrcLargeUpdate	net461	151.0 ms	3.00 ms	3.20 ms	1.00	0.00	-
Crc32LargeUpdate	.NET Core 2.1	153.9 ms	3.07 ms	4.21 ms	1.02	0.03	-
Crc32LargeUpdate	net461	150.9 ms	2.26 ms	2.01 ms	1.00	0.00	-
ReadZipInputStream	.NET Core 2.1	157.7 ms	2.32 ms	2.17 ms	1.00	0.02	106616 B
ReadZipInputStream	net461	157.1 ms	2.70 ms	3.00 ms	1.00	0.00	109275 B
WriteZipOutputStream	.NET Core 2.1	437.5 ms	8.71 ms	14.55 ms	1.00	0.06	362648 B
WriteZipOutputStream	net461	440.7 ms	8.72 ms	21.71 ms	1.00	0.00	368928 B

[piksel]

PR #516

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.19041.508 (2004/?/20H1)
AMD Ryzen 7 3800X, 1 CPU, 16 logical and 8 physical cores
.NET Core SDK=5.0.100-preview.8.20417.9
  [Host]     : .NET Core 2.1.21 (CoreCLR 4.6.29130.01, CoreFX 4.6.29130.02), X64 RyuJIT
  Job-DYBSVV : .NET Core 2.1.21 (CoreCLR 4.6.29130.01, CoreFX 4.6.29130.02), X64 RyuJIT
  Job-SNAPLI : .NET Framework 4.8 (4.8.4220.0), X64 RyuJIT

Method	Toolchain	Mean	Error	StdDev	Ratio	RatioSD	Allocated
Adler32LargeUpdate	.NET Core 2.1	198.7 ms	2.20 ms	2.05 ms	1.00	0.02	-
Adler32LargeUpdate	net461	199.6 ms	3.72 ms	3.48 ms	1.00	0.00	-
BZip2CrcLargeUpdate	.NET Core 2.1	167.9 ms	2.83 ms	3.58 ms	1.01	0.03	-
BZip2CrcLargeUpdate	net461	167.1 ms	3.23 ms	3.32 ms	1.00	0.00	-
Crc32LargeUpdate	.NET Core 2.1	171.3 ms	1.73 ms	1.62 ms	1.00	0.01	-
Crc32LargeUpdate	net461	171.3 ms	2.18 ms	2.04 ms	1.00	0.00	-
ReadZipInputStream	.NET Core 2.1	160.4 ms	1.71 ms	1.52 ms	1.00	0.02	106616 B
ReadZipInputStream	net461	160.6 ms	2.46 ms	2.18 ms	1.00	0.00	108592 B
WriteZipOutputStream	.NET Core 2.1	432.5 ms	8.64 ms	13.95 ms	0.98	0.06	362648 B
WriteZipOutputStream	net461	450.4 ms	8.92 ms	22.88 ms	1.00	0.00	368928 B

[decipherer]

Look good, both pull requests have a significant performance enhancement 👍

[piksel]

@decipherer Yeah, the difference between them is not really significant. Either would be a great improvement in performance.

[piksel]

The CRC32 saga has been concluded as of v1.3.1 which included #516.
It was chosen because I could actually be confident in the changes it made.

Sorry for taking this long and not using your PRs @decipherer and @dpethes. I got a little bit burned by #202 and shied away from CRC changes after that.

Thanks for your contributions!