SharpZipLib icon indicating copy to clipboard operation
SharpZipLib copied to clipboard

Optimize InflaterHuffmanTree

Open lahma opened this issue 2 years ago • 0 comments

This PR improves InflaterHuffmanTree.BuildTree in the following ways:

  • Take in ReadOnlySpan<byte> instead of IList<byte>, IList causes interface dispatch and could change in size in theory which makes it hard to optimize for runtime, ROS ensures fast iteration and fixed size
    • made this new constructor internal so old there shouldn't be a breaking change for library consumers, in the future the span based version would be better in public API
  • Move tree byte building from static constructor to ROS<byte> => new [] { b1, b2 } which ensures data is loaded from assembly static data section without the need of allocations, created test case to generate the data using same logic that was in the static constructor

Results


BenchmarkDotNet v0.13.7, Windows 11 (10.0.23521.1000)
AMD Ryzen 9 5950X, 1 CPU, 32 logical and 16 physical cores
.NET SDK 7.0.400
  [Host]     : .NET 6.0.21 (6.0.2123.36311), X64 RyuJIT AVX2
  Job-JCGLDA : .NET 6.0.21 (6.0.2123.36311), X64 RyuJIT AVX2
  Job-RETHYE : .NET Framework 4.8.1 (4.8.9181.0), X64 RyuJIT VectorSize=256


ICSharpCode.SharpZipLib.Benchmark.Zip.ZipFile

Diff Method Toolchain Mean Error Allocated
Old ReadLargeZipFile .NET 6.0 1.308 s 0.0080 s 535.66 MB
New .NET 6.0 871.0 ms (-35%) 3.79 ms 502.96 MB (-6%)
Old ReadLargeZipFile .NET Framework 4.6.2 1.431 s 0.0072 s 543.65 MB
New .NET Framework 4.6.2 1,072.6 ms (-27%) 4.94 ms 510.85 MB (-6%)

ICSharpCode.SharpZipLib.Benchmark.Zip.ZipInputStream

Diff Method Toolchain Mean Error Allocated
Old ReadZipInputStream .NET 6.0 151.3 ms 0.55 ms 104.54 KB
New .NET 6.0 150.9 ms (0%) 0.11 ms 95.27 KB (-9%)
Old ReadZipInputStream .NET Framework 4.6.2 150.6 ms 0.53 ms 106.05 KB
New .NET Framework 4.6.2 151.2 ms (0%) 0.82 ms 96.05 KB (-9%)

I certify that I own, and have sufficient rights to contribute, all source code and related material intended to be compiled or integrated with the source code for the SharpZipLib open source product (the "Contribution"). My Contribution is licensed under the MIT License.

lahma avatar Aug 12 '23 19:08 lahma