Zstandard

[Cyan]

I want to have zstd in such a way that it takes input from an array instead of file or stdin. (...). c-store gives columns to compression algorithm in form of char*.(...). So, please release a version of zstd with input being taken from char* type and output being stored in another char* variable.

Hi Mitra,
not sure if I fully understand your question,
it looks to me that current zstd API is able to provide what you are looking for.

Here it is extracted :

size_t ZSTD_compress(void* dst, size_t maxDstSize, const void* src, size_t srcSize);
size_t ZSTD_decompress(void* dst, size_t maxOriginalSize, const void* src, size_t compressedSize);

In this context, void* acts like a type wildcard. You can provide char* instead if you wish.
This will work, the same way as memcpy(void* dst, const void* src, size_t size) does.

[Cyan]

*** stack smashing detected ***: zstd terminated

Linux binary. X86.
Reading from stdin. Writing to disk.

Latest update should hopefully fix this issue.

[Cyan]

i may look into porting OP backend so that you can see the compression limits of the format

tornado greedy/lazy compressor also has only passive repdist recognition, tornado OP as well as both lzma modes has active repdist recognition

@Bulat : if you still are interested in porting these OP functions,
the internal working of Zstd has been adapted to more easily implement multiple parsing strategies.

The new internal API works around seqStore_t object.

1) When a "sequence" is finally decided,
a sequence starting with literals and their Length, an offset code, and a matchLength,
it can be stored into seqStore using :

static void ZSTD_storeSeq(seqStore_t* seqStorePtr, size_t litLength, const BYTE* literals, size_t offset, size_t matchLength)

2) When an entire memory block is completely transformed into multiple sequences,
start the compression by using :

static size_t ZSTD_compressSequences(BYTE* dst, size_t maxDstSize, const seqStore_t* seqStorePtr, size_t lastLLSize, size_t srcSize)

[Bulat Ziganshin]

ZSTD bindings for Node.js

[mitra]

Hi Cyan,
From my c-store database, I have called ZSTD_compress and ZSTD_decompress and I have included "zstd-master/lib/zstd.h" in my header files. Now problem is, should I plug just the lib part of zstd-master and make use of makefile in lib to create zstd binaries or should I include whole zstd-master into my database folder? Please suggest me how to proceed in running the thing.

[Cyan]

This really depends on the way you build your application.
Let's say the main idea is to include all files in "lib" directory.
You will likely need only a portion of them, typically :
zstd.h
zstd.c
fse.h
fse.c
fse-static.h

[Alvaro]

Hi Cyan,
I know you have a lot to do, but I wonder if you can include in the API a feature that would allow to generate the frequency table from multiple source files, so that I can use it later for compressing them into one single database, and being able to access it in real time in small blocks. This way I could acess a huge compressed database very fast.
thx,
Alvaro

[Cyan]

Hi Alvaro


There are potentially several questions embedded into your requirement.


If what you wish is "just the frequency table" as stated, then it's possible to do it now.
This part is handled by the FSE advanced API.
Look into :

size_t FSE_count(unsigned* count, const unsigned char* src, size_t srcSize, unsigned* maxSymbolValuePtr);

size_t FSE_normalizeCount(short* normalizedCounter, unsigned tableLog, const unsigned* count, size_t total, unsigned maxSymbolValue);

size_t FSE_buildCTable(void* CTable, const short* normalizedCounter, unsigned maxSymbolValue, unsigned tableLog);

If what you wish is to get some "precalculated entropy tables" applicable for all symbol types generated by Zstd,
then this is more complex.
I planned to implement this feature, since it's important for compressing small packets, but it's not going to happen soon.
There are a few caveats to solve first.
If programming remain a side activity, 2016 looks a probable timeline.


If what you wish is a kind of optimal "precomputed dictionary" selected to improve compression of some files or DB rows divided into small blocks,
then it's necessary to develop a "dictionary builder", which is in essence a complete project on its own.
I currently do not plan to develop such a tool.
Well, of course, should my employer require me to work on it, this statement will change.

[mitra]

Hi Cyan,

A. What is the significance of magic number(0xFD2FB51C) in zstd code? Is that a random constant or purposefully given value?

B. Why did you add 12 to srcsize to get maxdstsize while we add only 7(header(4)+end(3)) to srcsize even in worst case. Is it not enough to add 7 to srcsize in zstd_compressBound function?

Thanks in advance!

[Cyan]

A. What is the significance of magic number(0xFD2FB51C) in zstd code? Is that a random constant or purposefully given value?

It's an identifier, which simply identify the current version of the frame format.
Since the current frame format is temporary and very simple (no parameter), this will change at a later time.
The change will be identified by a new magic number.

B. Why did you add 12 to srcsize to get maxdstsize while we add only 7(header(4)+end(3)) to srcsize even in worst case. Is it not enough to add 7 to srcsize in zstd_compressBound function?

In fact, the correct value should be 10.
frame header (4) + block header (3) + frame end (3)

It used to be 12 when I wrote this line of code, because back then, we had :
frame header (4) + block header (4) + frame end (4)
I simply forgot to update zstd_compressBound when reducing block headers from 4 to 3 bytes.

In the end, this has little importance : the current formula still requires many more bytes than target,
because it still relies on FSE_compressBound, which is sized to avoid any buffer overflow risk.
Overtime, this limitation will be overcome, reducing the result of zstd_compressBound.
But that will require a bit more development time...

[mitra]

Hi Cyan,
What is the difference between LZW and ZSTD and LZ4 compression techniques..?? All of them have dictionaries and use the same to compress or decompress. Is there any programming improvements among them or Is there any algorithmic difference which makes it faster?

[Cyan]

> What is the difference between LZW and ZSTD and LZ4 compression techniques..??

Well, they are not that equivalent.
Google is a good friend for this question.

LZW really has this notion of "dictionary" built in, with a requirement to mimic dictionary evolution in both encoder & decoder.
It outputs an "entry ID into the dictionary".
http://en.wikipedia.org/wiki/Lempel%...%E2%80%93Welch

LZ4 & ZSTD are more "LZ77". Which means they use the input buffer as a kind of "dictionary".
They output a "distance", in order to look back data into buffer.
http://en.wikipedia.org/wiki/LZ77_and_LZ78

The key point is on the decoding side :
LZ78/LZW requires to maintain the "dictionary" during decompression, so it's an extra load, both for CPU and memory.

In contrast, LZ77 just outputs distances. So there is no need for "dictionary" during decompression.
That's why LZ4 uses almost no memory during decompression (only the input/output buffers).


What separates ZSTD from LZ4 is that LZ4 is byte-aligned, static modeled, LZ77,
with a fixed window size (64KB)

In contrast, ZSTD is an Order-0 modeled LZ77, using FSE.
It also includes a rep-mode, for aligned structures.
Which is just a different way to represent "distances".
ZSTD can also afford variable window size, up to great distances.

Therefore, LZ4 is simpler and faster,
while ZSTD is more powerful but more complex.

[cbloom]

I finally did a little test of ZStd.

The encode speed is quite incredible!

[mitra]

Zstd is encoding with more than 10x speed when compared to lzw when checked with stand alone codes. When I integrate Zstd into C-Store(column oriented dbms which compresses data before storing into db) instead of lzw, It is showing only 2x performance gain in speed. Why is this happening? Is it because of C-Store's complexity or will there be any problem in Zstd when we integrtae that to some other code?

[Cyan]

That could be because of memory cost.
I don't know exactly about lzw memory cost, so I suspect it is in the 32KB + Buffer range.
Zstd is more on the 128 KB + Buffer range.
So, depending on what other tasks you have to do at the same time, it is possible this has an effect (thinks about cache flush/eviction).

It's possible to change that, by modifying tuning constants at the beginning of zstd.c.

The plan is to make such value fully and clearly configurable in the future.
We just are not there yet...

[dbbd]

I'm trying to convert code using zlib to zstd. This is all in-memory compression/decompression.
My input and output are iovecs. With zlib, when I compress, the compression stops when there is no more output space, and then I allocate a new block and continue the compression. (I assign the new buffer to next_out, and update avail_out in the stream descriptor)

I don't see how I can do this with zstd.

[as an example for what I want to do, I'd like to modify FIO_compressFilename to compress into a memory buffer that is allocated block by block, instead of writing each compressed block to the output file]

[Cyan]

This is indeed not a supported scenario for the time being.

The final zstd API is likely to be inspired by current LZ4 streaming API, which is able to support this scenario.
But that's not available today.


The second suggestion, to modify FIO_compressFilename to compress into a memory buffer allocated block by block,
is relatively easy to support.
It's planned to be provided by a "buffered zstd" library, which will be part of the package.
However, I have no specific date of release to share right now.

In case of urgent need, I can only invite you to modify FIO_compressFilename the way you propose.

[mitra]

Hi Cyan,
I find there is a slight difference between APIs when data is provided through a file and when it is given as arrays from a test program.
I witnessed a strange problem, that is, when I provide the data from a file to zstd, it is compressing and decompressing it faster than when I provide the 'same' data in the form of an array from a test program. I actually thought reading and writing into file takes time so the first way should take more time than second. But the case reversed. Why is this happening?
I use zstd to compress and decompress data by providing it with char arrays. By stand alone performance(where data is given through files), I was happy and excited that there is faster decompression rate and this could improve my overall read speed. But I could not get that performance when I integrated and send the data through char arrays. Is there any difference which significantly decreases the speed between those two ways..??

This reply is very important to me, thanks in advance.

[avitar]

Would you please tell me where latest win32 and win64 .exe versions of zstd are and add a link that points to them?

Latest 64 bit I have is 25/1/2015, no 32 bit version.

TIA john

[Cyan]

Hi @mitra


Indeed, it's not a normal outcome.
Compressing a memory segment using zstd should always be faster than sending it as a file to an external zstd process.

The only situation which I can imagine to produce such a result
is a noticeable difference in compilation settings.
Maybe one process is 32-bits and the other 64-bits,
maybe be one is -O2 and the other is -O3,
etc.

But at the end of the day, compressing/decompressing a memory segment should always end up being (significantly) faster.

[Cyan]

Would you please tell me where latest win32 and win64 .exe versions of zstd are and add a link that points to them?

Latest 64 bit I have is 25/1/2015, no 32 bit version.

TIA john

I typically do not provide pre-compiled binaries, only source code.
But if that is a need, I could review that policy.

[avitar]

Yes please & keep them up to date when new versions are available. j

[mitra]

Can ZSTD be called a dictionary based compression technique? If yes, is the dictionary created during compression process readable?

What is the significance of '128 kb' as blocksize? Can I increase or decrease it so that the process of compression/decompression becomes faster?

[Cyan]

> Can ZSTD be called a dictionary based compression technique? If yes, is the dictionary created during compression process readable?

Yes. The dictionary consists of the last compressed data so far, up to maxWindowSize (512 KB by default)

> What is the significance of '128 kb' as blocksize? Can I increase or decrease it so that the process of compression/decompression becomes faster?

Yes, but don't expect large differences.
This is a classical "speed vs ratio" situation.
The larger the block size, the less update is necessary, and the less dynamically adapted the entropy.
You may try different values.
I already received a few reports of such attempts. Conclusion is, it does not change the result significantly.

[mitra]

I have a file of 1MB. Instead of reading it 128kb at a time and processing, I read all data at once and compressed and decompressed using ZSTD_compress() and ZSTD_decompress() functions respectively. The assumption was, reading whole data and processing should save time as we dont need to read multiplt times. But, to my surprise, reading in chunks and processing is taking less time than reading whole file and processing.

How can I explain this result? Could you share what you think is the reason for this?

[Bulat Ziganshin]

it's definitely not zstd-specific, so you can ask on SO or so. the incremental approach give OS the chances to overlap computations and I/O rather than to perform them sequentially

[mitra]

Hello Cyan,

Good day.

We have a situation where data is getting padded with junk values and given to zstd. On that padded data, zstd is not giving the same performance as it gives when normal data is sent. Can you suggest anything to deal with this? Is there a way to improve performance, interms of speed when junk values are given?

Thanks in advance.

[Bulat Ziganshin]

I have a file of 1MB. Instead of reading it 128kb at a time and processing, I read all data at once and compressed and decompressed using ZSTD_compress() and ZSTD_decompress() functions respectively

i overlooked much more straightforward explanation - the cpu L2 cache is 256 KB and compression in 128 KB chunks may be faster exactly because all your matches are fit into L2$

[krithika]

hi cyan,
im trying to implement zstd using simd technique. when i see the possibility of this, i doubt if it could be done,coz im not quite sure abt the ctable. what do u think abt this implementation.
Thanks in advance.

[Cyan]

It's an interesting attempt.
I don't know the result of it. You are likely to find some improvements in some limited parts of the code, which is still a good thing.