<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body>
<div dir="ltr">A side question: Do lossy compressors have value for PETSc?<br clear="all">
<div>
<div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature">
<div dir="ltr"><br>
</div>
<div dir="ltr">--Junchao Zhang</div>
</div>
</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Thu, Jul 11, 2019 at 9:06 AM Jed Brown via petsc-dev <<a href="mailto:petsc-dev@mcs.anl.gov">petsc-dev@mcs.anl.gov</a>> wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
Zstd is a remarkably good compressor. I've experimented with it for<br>
compressing column indices for sparse matrices on structured grids and<br>
(after a simple transform: subtracting the row number) gotten<br>
decompression speed in the neighborhood of 10 GB/s (i.e., faster per<br>
core than DRAM). I've been meaning to follow up. The transformation<br>
described below (splitting the bytes) is yielding decompression speed<br>
around 1GB/s (in this link below), which isn't competitive for things<br>
like MatMult, but could be useful for things like trajectory<br>
checkpointing.<br>
<br>
<a href="https://drive.google.com/file/d/1wfLQyO2G5nofYFkS7pVbUW0-oJkQqBvv/view" rel="noreferrer" target="_blank">https://drive.google.com/file/d/1wfLQyO2G5nofYFkS7pVbUW0-oJkQqBvv/view</a><br>
<br>
<br>
<br>
<br>
---------- Forwarded message ----------<br>
From: "Radev, Martin" <<a href="mailto:martin.radev@tum.de" target="_blank">martin.radev@tum.de</a>><br>
To: "<a href="mailto:dev@arrow.apache.org" target="_blank">dev@arrow.apache.org</a>" <<a href="mailto:dev@arrow.apache.org" target="_blank">dev@arrow.apache.org</a>><br>
Cc: "Raoofy, Amir" <<a href="mailto:amir.raoofy@tum.de" target="_blank">amir.raoofy@tum.de</a>>, "Karlstetter, Roman" <<a href="mailto:roman.karlstetter@tum.de" target="_blank">roman.karlstetter@tum.de</a>><br>
Bcc: <br>
Date: Thu, 11 Jul 2019 09:55:03 +0000<br>
Subject: Re: Adding a new encoding for FP data<br>
Hello Liya Fan,<br>
<br>
<br>
this explains the technique but for a more complex case:<br>
<br>
<a href="https://fgiesen.wordpress.com/2011/01/24/x86-code-compression-in-kkrunchy/" rel="noreferrer" target="_blank">https://fgiesen.wordpress.com/2011/01/24/x86-code-compression-in-kkrunchy/</a><br>
<br>
For FP data, the approach which seemed to be the best is the following.<br>
<br>
Say we have a buffer of two 32-bit floating point values:<br>
<br>
buf = [af, bf]<br>
<br>
We interpret each FP value as a 32-bit uint and look at each individual byte. We have 8 bytes in total for this small input.<br>
<br>
buf = [af0, af1, af2, af3, bf0, bf1, bf2, bf3]<br>
<br>
Then we apply stream splitting and the new buffer becomes:<br>
<br>
newbuf = [af0, bf0, af1, bf1, af2, bf2, af3, bf3]<br>
<br>
We compress newbuf.<br>
<br>
Due to similarities the sign bits, mantissa bits and MSB exponent bits, we might have a lot more repetitions in data. For scientific data, the 2nd and 3rd byte for 32-bit data is probably largely noise. Thus in the original representation we would always have
a few bytes of data which could appear somewhere else in the buffer and then a couple bytes of possible noise. In the new representation we have a long stream of data which could compress well and then a sequence of noise towards the end.<br>
<br>
This transformation improved compression ratio as can be seen in the report.<br>
<br>
It also improved speed for ZSTD. This could be because ZSTD makes a decision of how to compress the data - RLE, new huffman tree, huffman tree of the previous frame, raw representation. Each can potentially achieve a different compression ratio and compression/decompression
speed. It turned out that when the transformation is applied, zstd would attempt to compress fewer frames and copy the other. This could lead to less attempts to build a huffman tree. It's hard to pin-point the exact reason.<br>
<br>
I did not try other lossless text compressors but I expect similar results.<br>
<br>
For code, I can polish my patches, create a Jira task and submit the patches for review.<br>
<br>
<br>
Regards,<br>
<br>
Martin<br>
<br>
<br>
________________________________<br>
From: Fan Liya <<a href="mailto:liya.fan03@gmail.com" target="_blank">liya.fan03@gmail.com</a>><br>
Sent: Thursday, July 11, 2019 11:32:53 AM<br>
To: <a href="mailto:dev@arrow.apache.org" target="_blank">dev@arrow.apache.org</a><br>
Cc: Raoofy, Amir; Karlstetter, Roman<br>
Subject: Re: Adding a new encoding for FP data<br>
<br>
Hi Radev,<br>
<br>
Thanks for the information. It seems interesting.<br>
IMO, Arrow has much to do for data compression. However, it seems there are<br>
some differences for memory data compression and external storage data<br>
compression.<br>
<br>
Could you please provide some reference for stream splitting?<br>
<br>
Best,<br>
Liya Fan<br>
<br>
On Thu, Jul 11, 2019 at 5:15 PM Radev, Martin <<a href="mailto:martin.radev@tum.de" target="_blank">martin.radev@tum.de</a>> wrote:<br>
<br>
> Hello people,<br>
><br>
><br>
> there has been discussion in the Apache Parquet mailing list on adding a<br>
> new encoder for FP data.<br>
> The reason for this is that the supported compressors by Apache Parquet<br>
> (zstd, gzip, etc) do not compress well raw FP data.<br>
><br>
><br>
> In my investigation it turns out that a very simple simple technique,<br>
> named stream splitting, can improve the compression ratio and even speed<br>
> for some of the compressors.<br>
><br>
> You can read about the results here:<br>
> <a href="https://drive.google.com/file/d/1wfLQyO2G5nofYFkS7pVbUW0-oJkQqBvv/view" rel="noreferrer" target="_blank">
https://drive.google.com/file/d/1wfLQyO2G5nofYFkS7pVbUW0-oJkQqBvv/view</a><br>
><br>
><br>
> I went through the developer guide for Apache Arrow and wrote a patch to<br>
> add the new encoding and test coverage for it.<br>
><br>
> I will polish my patch and work in parallel to extend the Apache Parquet<br>
> format for the new encoding.<br>
><br>
><br>
> If you have any concerns, please let me know.<br>
><br>
><br>
> Regards,<br>
><br>
> Martin<br>
><br>
><br>
</blockquote>
</div>
</body>
</html>