Lz4: [Question] Compression/Decompression using totally fixed dictionary state.

[FrankStain]

Hi again.

So, previously i had learned the closed topics, but found nothing answering my question.

I think about can i use lz4 compression/decompression streams like an processor with fixed state, which just translates the income stream into outcome one.
I have a lot of small (<100B) data blocks, which are intensively used in data stream like an instructions. I know the order and content of my stream, so i can just construct the dictionary once and use it over all stream saving the good-enough quality.
I had test one, it works as i intend.

But what disturbs me now is the need to use LZ4_loadDict and LZ4_setStreamDecode on every compression/decompression. I just don't want to spend the time on it. There are a lot of other things needs more time around.
The state of single shader unit, for example, becomes locked while processing the vertex stream of single drawcall and vertices are processed very quickly.

Can i fix the code of lz4 somehow to turn the adaptivity off and get rid of that functions?
Or mby is there some workaround to reach the behavior i need?

[Cyan4973]

Not sure if I understood correctly, here are ideas that come to mind :

• LZ4_setStreamDecode() is extremely light. You should not be concerned by its CPU cost.
• LZ4_loadDict() is expensive. You should not need to use it between each block.

2 solutions I can think of :

• use LZ4_compressContinue(), do not use LZ4_loadDict() between blocks. This will work as long as previous data blocks remain accessible and unmodified. Check the resulting compression ratio. It will suffer if data blocks are "scattered" in memory. Best cases is when all blocks follow each other in memory. Only use LZ4_loadDict() when you _have to_ move your data away from their previous position in memory, preferably rarely or never.
• do not use streaming. Just use LZ4_compress_fast(). Each block will be independent. Compression ratio will suffer.

[FrankStain]

@Cyan4973 , the major thing i wish to reach is the locking the state of (de)compressor. Making it constant and irrelevant to all current restrictions.

https://github.com/lz4/lz4/blob/dev/lib/lz4.h#L262

Up to 64KB of previously compressed data is assumed to remain present and unmodified in memory !

So i have to keep some kind of ring buffer and use memcpy before compressing (from source memory into ring buffer). But actually i don't need it since my dictionary may be effectively precalculated.

https://github.com/lz4/lz4/blob/dev/lib/lz4.h#L305

Previously decoded blocks must remain available at the memory position where they were decoded (up to 64 KB).

It means i have to use ring buffer not only for compression, but for decompression as well. That is the second memcpy (from the ring buffer into destination memory) which i actually don't need.

More than. Each instruction have to be compressed individually and may be discarded just before decompression. In case of adaptive compression it means the break of decompression.
Also the compression stream really may be of kind "single head - lot of tails", which means i actually don't need to have lot of compression streams. I need only one compression stream with fixed dictionary and fixed state for all consumers.

Previously i had tested LZ4_compress_fast_continue and LZ4_decompress_safe_continue using ring buffers, the decompression fails immediately just after first discard of instruction. Decompression also fails after the second "tail" appears for compression stream. That is regular and well behavior, but it's not suitable for my purposes.
So, next step is the using of fixed dictionary. It works well, discarded instructions not affect the decompression. Also i can use any number of "tails" for compression stream.
The ring buffers has some security issues and additional costs, so it would be good to get rid of it.

And all that leads me to necessary of calling LZ4_loadDict() before each compression and LZ4_setStreamDecode before each decompression.
(Just like here: https://github.com/lz4/lz4/blob/dev/examples/dictionaryRandomAccess.c )
And i'm asking about the possibility of getting rid of that two functions on every (de)compression. Does it possible to fix the code to be able turning the adaptivity on and off?

maybe I'm mistaken some way or don't understand. Feel free to correct my supposes. :)

• do not use streaming. Just use LZ4_compress_fast(). Each block will be independent. Compression ratio will suffer.

Sadly, it's ineffective, since the raw size of instruction is less than after compression.

[FrankStain]

My current W.I.P. description.

I had found the way to reach good enough compression using the static dictionary. Sadly, currently it means i still need to use memcpy before compression and after decompression, combining it with LZ4_loadDict() and LZ4_setStreamDecode functions.
I just found the way to permanently enable the prefix mode. To reach it, i use 128KB buffer, where the first half stores the dictionary and the second one used as (de)compression buffer.
The space saving ratio i can reach now is 30-70% , this is much more than i supposed.

Further reading of code reveals for me only four places where the hashTable is modified in LZ4_compress_generic:

1. https://github.com/lz4/lz4/blob/dev/lib/lz4.c#L528
2. https://github.com/lz4/lz4/blob/dev/lib/lz4.c#L559
3. https://github.com/lz4/lz4/blob/dev/lib/lz4.c#L636
4. https://github.com/lz4/lz4/blob/dev/lib/lz4.c#L648

Am i on right direction?
Currently i plan to edit the code for turning the adaptivity on and off.

@Cyan4973 , what do you think about PR with my changes? Could it be useful for others in general?

[Cyan4973]

Hi @FrankStain

Apparently, you're moving into "dictionary compression" territory.
That sounds totally nice.

The decoder should not be a concern. Just give it the position of the dictionary with LZ4_setStreamDecode () before starting decoding a new block. Or use the combined version LZ4_decompress_safe_usingDict(), which is probably the simplest one.
You don't even have to copy the dictionary, it can remain in place.

The compression side is a bit more involving, but still solvable.

• create a "reference context" LZ4_stream_t refCtx;.
• load the dictionary _once_ into the reference context : LZ4_loadDict(&refCtx, dict, dictSize);
• From now on, do no longer modify the reference context
• For future compression, create one (or several) active contexts : LZ4_stream_t CCtx;
• Before each compression, copy the reference context into the active one : memcpy(&CCtx, &refCtx, sizeof(refCtx));
• Compress your block

It's not necessary to copy the dictionary itself, it can remain in place.
Copying a context is still a memcpy() operation, so it's not free, but it's _a lot_ cheaper than loading a dictionary, so you should experience a great speed boost.