[art] Re: Gdeflate as RFC

[Vikram Kushwaha <[e-mail]>]

Hi John,

We are not suggesting this as a replacement for Deflate or for use in standard systems. Instead, we aim to propose it as an RFC, allowing implementers with parallelism-friendly hardware to reference and adopt it in their systems if they choose.

~Vikram

-----Original Message-----
From: John R Levine <[e-mail]>
Sent: Tuesday, September 17, 2024 2:03 PM
To: Vikram Kushwaha <[e-mail]>; Akshay Subramaniam <[e-mail]>; Martin Thomson <[e-mail]>; [e-mail]
Subject: RE: [art] Re: Gdeflate as RFC

Thanks for your note.  This is all informative but it still doesn't give me an understanding of why we would want to add this algorithm as an additional one for HTTP.

It's certainly faster in some circumstances but I'm not seeing how it'd offer an interesting difference on normal systems like PCs or phones that have a few CPU cores and a few GPU cores.

R's,
John

On Tue, 17 Sep 2024, Vikram Kushwaha wrote:

> Hi Martin/John,
> Please let us know if you have any more questions on GDeflate performance.
>
> Thanks!
>
> ~Vikram
>
> From: Akshay Subramaniam <[e-mail]>
> Sent: Thursday, August 29, 2024 6:58 PM
> To: Vikram Kushwaha <[e-mail]>; Martin Thomson
> <[e-mail]>; John R Levine <[e-mail]>; [e-mail]
> Subject: Re: [art] Re: Gdeflate as RFC
>
> Hi all,
>
> I can't read the full history of this email thread, especially plots or other attachments that were shared but let me add some thoughts on GDeflate vs ZSTD.
>
> I'm assuming the plots that you saw were some fairly coarse grained average compression ratio and throughput plots. Some clarifications on that:
>
>  1.  Both GDeflate and ZSTD in those plots are implemented on the GPU. Specifically, the ZSTD implementation used there is a custom CUDA based GPU implementation in the nvCOMP library, not the public CPU ZSTD library.
>
>  1.  The compression ratios for GDeflate are higher than ZSTD mainly because the compression techniques are different. Since GDeflate was designed for fast decompression, we implemented a high compression version of the compressor (similar to libdeflate level 12). Our GPU implementation of ZSTD was developed mainly for database applications where both compression and decompression throughput matter and so we tradeoff some compression ratio for throughput. The difference in compression ratio is only a result of the compressor implementations, not of the stream formats themselves.
>
>  1.  The speed difference between GDeflate and ZSTD depends a lot on the dataset. The main innovation in GDeflate is to make the entropy decoding much faster with the swizzling technique. But if the decompression performance is bottlenecked by LZ decompression, then the gap between GDeflate and ZSTD would be smaller.
>
>     *   Here's an example just for the Silesia corpus, GDeflate decompression throughput is 53 GB/s while ZSTD (on GPU) is 39 GB/s. So GDeflate is ~36% faster in this case. If we take a dataset that is much more entropy decode bound, the difference might be expected to grow.
> I want to reiterate that the ZSTD numbers are from a highly optimized GPU implementation in nvCOMP. If you look at the performance of the regular ZSTD libary on lzbench<https://github.com/inikep/lzbench>, it tops out at 1.2GB/s.
>
> There is one other use case for GDeflate that might be interesting. Since the main innovation in GDeflate is from faster entropy coding, we can use a very fast throughput compression algorithm by only entropy coding data without the LZ phase. This allows for symmetric compression and decompression throughputs of 150-200 GB/s and allows for compression to be used in communication bound applications where communication is done over relatively high performance networks.
>
> Thanks,
> Akshay
> ________________________________
> From: Vikram Kushwaha
> <[e-mail]<mailto:[e-mail]>>
> Sent: Thursday, August 29, 2024 10:36 AM
> To: Martin Thomson <[e-mail]<mailto:[e-mail]>>; John
> R Levine <[e-mail]<mailto:[e-mail]>>;
> [e-mail]<mailto:[e-mail]> <[e-mail]<mailto:[e-mail]>>;
> Akshay Subramaniam
> <[e-mail]<mailto:[e-mail]>>
> Subject: RE: [art] Re: Gdeflate as RFC
>
> I am not familiar with ZSTD, but adding @Akshay Subramaniam who will be able to better answer questions on the ZSTD vs Deflate performance.
>
>
> ~Vikram
>
> -----Original Message-----
> From: Martin Thomson <[e-mail]<mailto:[e-mail]>>
> Sent: Wednesday, August 28, 2024 8:52 PM
> To: Vikram Kushwaha
> <[e-mail]<mailto:[e-mail]>>; John R Levine
> <[e-mail]<mailto:[e-mail]>>;
> [e-mail]<mailto:[e-mail]>
> Subject: Re: [art] Re: Gdeflate as RFC
>
> Thanks for sharing that Vikram, it's helpful.
>
> I'm curious as to what zstd folks think about these results.  Is it the case that the tuning of zstd was to ensure that the throughput would be comparable to gdeflate?  From my understanding, zstd is capable of far better compression ratios than deflate and that your work was primarily focused on throughput, such that gdeflate would necessarily outperform zstd on that axis as much as it seems to have done in this scenario.
>
> I'm not sufficiently expert here, so I'll defer to others.  However, those numbers aren't necessarily convincing (though the OOMs on zstd might be if it were explained).  zstd seems to have slightly less throughput and compression both, but it's not so clearly a win as I'd have expected.  LZ4 is clearly unsuitable, but that's expected.
>
> On Thu, Aug 29, 2024, at 06:29, Vikram Kushwaha wrote:
>> Hi John/Martin,
>>
>> As I continue to work on the IPR disclosures, as requested, attaching
>> comparisons of GDeflate performance with other compression algorithms.
>> The summary is that GDeflate has a high throughput while maintaining
>> a high compression ratio.
>>
>> Thanks,
>> ~Vikram
>>
>> -----Original Message-----
>> From: Vikram Kushwaha
>> <[e-mail]<mailto:[e-mail]>>
>> Sent: Monday, August 5, 2024 9:51 PM
>> To: John R Levine <[e-mail]<mailto:[e-mail]>>; Martin
>> Thomson <[e-mail]<mailto:[e-mail]>>;
>> [e-mail]<mailto:[e-mail]>
>> Subject: RE: [art] Re: Gdeflate as RFC
>>
>> Thanks all for your feedback.
>>
>> I am still reading up on the IP disclosures, I will follow up on that
>> in an another email.
>>
>>> What sort of applications do you have in mind here?
>> This will be useful in applications where GPU decompression can be
>> done on the fly, offloading the work from CPU. One use case is gaming
>> where frames are streamed and data asset decompressions are handled
>> by some of the GPU cores.
>>
>>
>>> If it's supposed to be generally useful it'd also be helpful to have some idea how it works on normal CPUs.
>> That would depend on how the decompressor is written. If a CPU based
>> decompressor can make use of the parallel nature of the decompression
>> with gdeflate(it should be with thread programming) it will be
>> faster, though we haven't written one and so do not have numbers for
>> comparison as CPU cores vary a lot.
>>
>> I am going to send out an email comparing gdeflate with zstd and other formats.
>>
>> Of course, lower end GPUs will show a smaller gain but it will still
>> be faster than CPU decompression. The advantage we are going for is
>> by offloading decompression to GPU, CPU can be used for other tasks.
>> This is quite useful in gaming/visualization apps where CPU to GPU
>> communication is a bottleneck.
>>
>> One more thing I would like to add is that Microsoft has already
>> adopted GDeflate as their default GPU decompression method, so by
>> promoting this as a RFC we were hoping to standardize it more globally.
>>
>> ~Vikram
>>
>> -----Original Message-----
>> From: John R Levine <[e-mail]<mailto:[e-mail]>>
>> Sent: Thursday, August 1, 2024 8:29 PM
>> To: Martin Thomson <[e-mail]<mailto:[e-mail]>>;
>> [e-mail]<mailto:[e-mail]>
>> Cc: Vikram Kushwaha
>> <[e-mail]<mailto:[e-mail]>>
>> Subject: Re: [art] Re: Gdeflate as RFC
>>
>> On Fri, 2 Aug 2024, Martin Thomson wrote:
>>> On Fri, Aug 2, 2024, at 06:38, John Levine wrote:
>>>> What sort of applications do you have in mind here? The main place
>>>> DEFLAATE is used in IETF protocols is in compressed HTTP streams
>>>> which doesn't strike me as the kind of thing one would often do on a GPU.
>>>
>>> I don't see why not, if the GPU is that much faster.
>>
>> That benchmark is on an RTX3090 which has 10,000 cores.  I'm typing
>> this on an M2 Pro laptop whose GPU has 19 cores.  I believe their
>> benchmark but I also don't see how it's relevant to anything but high
>> end dedicated GPUs.
>>
>>> I'm more concerned about the comparison to more modern stuff, like
>>> brotli or zstd.  Those tend to offer far better compression
>>> performance than deflate. ...
>>
>> That is an excellent point if we're going to change the comprsssion scheme.
>>
>> R's,
>> John
>>
>>
>> Attachments:
>> * GDeflateComparison.pdf
>

Regards,
John Levine, [e-mail], Taughannock Networks, Trumansburg NY Please consider the environment before reading this e-mail. https://jl.ly/