Problems with the density_context by multiple uses

[191919]

I ran a profiling test which showed that calloc is the top CPU consumer. I saw in density_allocate_context, there is a line:

memset(context->dictionary, 0, context->dictionary_size);

(It turned out that gcc optimized the combination of x=malloc(y) and memset(x,0,y) into single calloc(x) call.)

So the problem was that every time I use the compress or decompress routine, density must clear (1<<16)*(2+1)*4 = 786432 bytes. That is quite a burden for all machines.

I see there is a density_compress_with_context function which seems to allow a pre-allocated context to be used by multiple times, but since the dictionary inside the context has been changed, the output (compressed buffer) cannot be decompressed correctly.

[g1mv]

Hello ! For compression and decompression to work properly the dictionary used must be in the same state when starting a compress/decompress session.
On some platforms, if you do not zero the memory it can contain random data after a malloc and this leads to the problem described above i.e. dictionary states not being identical before compress and decompress.
In the previous versions of density I had a preset zero dictionary set up once and for all in the stack and I copied its content every time the dict was initialized, but I seriously doubt this can be faster than an optimized memset function.
As you point out rightly though, you can use your own custom context, so if you want to compress a lot of small datasets (lots of potential dictionary zeroing which cause slowdowns), what you could do is concatenate every 1000 datasets into one for example, and then compress the resulting concatenated dataset (hence only one dictionary init for every 1000 datasets so 1000 times less zeroing, as you would use the same context over and over).
One of the advantages of this method, apart from speed, is that when the datasets are very similar in nature, the context dictionary is already matching the data and compression ratio improves as the algorithms' "learning curve" reduces.
The drawbacks of this method is that you can't decompress a single dataset, you have to decompress a block of 1000 to access a single one, but with an intelligent cache system you can also greatly improve performance here.

[191919]

I am trying to add density to InnoDB page compression algorithm list. Concatenation of data blocks is impossible. In fact, a lot of scenarios don't allow data concatenation, e.g., real time data or per-file transfer.

Would you please check the possibility of reducing the dictionary size?

[g1mv]

The main problem with a small dictionary size is that machine learning of dataset structures (unless they are very simple) will be less efficient, resulting in a decreased compression ratio.
But I completely understand the problem you're facing, I'll have a look into it. Maybe there is a way to do memory zeroing much faster than memset or calloc which I'm unaware of ?
Another option would be to calloc a lot of memory at once say 128MB for example (one big calloc should be faster than numerous small ones), and then use it fragment after fragment. Depending on the algorithm you're choosing it would easily make up for hundreds of uses.
Or in the case of a multithreaded environment, you could have an idle thread preparing some memory for future use as dictionaries (zeroization in the background) ?

[tarsa]

Hi Guillaume,
I think I have another solution :) Instead of shrinking dictionary size you can use flags to denote which dictionary entries are valid and which are possibly dirty. A bit flag consume 32x less than 32-bit value, thus you would need to only clear 24 KiB of flags at the beginning. The drawback is of course overhead of flags management. But there's also a solution - make the dirty (i.e. flag based) mode adaptive and after processing e.g. 20 KB of data zero all unused dictionary entries and switch to original mode that doesn't use flags.

[g1mv]

Hey Piotr ^^ Thanks, yes this is looking like a promising idea at first impression. I'll have to investigate and benchmark it but it would clearly greatly reduce the amount of mem zeroing on algo initialization.
If one wants to compress/decompress a huge number of very small datasets though, this method will for sure improve the mem init speed but bitflag dictionary processing will always be active and alter algorithms speed, so in all cases there will be a performance hit for processing small datasets, which is not something desirable really.
So maybe another idea would be to have a variable size dictionary, starting at a small size and then increasing in size as we reach a certain threshold of processed data. That way the initial dictionary size could be allocated and zeroed very quickly while still ensuring reasonable compression ratios for smallish datasets, and be augmented later on to its final size as the processed data quantity grows.
The switch to the final, bigger dictionary could take place after a certain data amount is processed (for example after having processed 32kB), or after noticing the start of a degradation in compression ratio (would be very useful for low entropy datasets as the bigger dictionary would never be necessary, but in all other cases it incurs a temporary reduction in compression ratio before the new dictionary is setup).

[191919]

I tried the approach of allocating a huge size of memory, using it as an array of memory block with size of each one is 768KB, managing it with a bitmap and clearing the dirty ones with another thread.

In the case of InnoDB page compression under a heavily loaded server, I have to allocate over 4GB memory to catch up the pace of memory demand, with the zeroing thread eating up 30% time of a core.

Perhaps the reduction of dictionary size is the final solution.

[g1mv]

@191919 , out of testing purposes, would you have a histogram or something equivalent of the data quantity against size you're using for testing ? ie for example 123 datasets < 1kB, 345 datasets >= 1kB and < 2kB, 234 datasets >= 2kB and < 3kB, etc. ? Thanks. That would help testing Piotr @tarsa 's idea and the variable dictionary size one.

[191919]

@gpnuma As mentioned in my previous post, I am adding density as a candidate algorithm of InnoDB page compression, the page size can be specified when you create the table.

[g1mv]

Ok thanks I see !

[tarsa]

Hey Piotr ^^ Thanks, yes this is looking like a promising idea at first impression. I'll have to investigate and benchmark it but it would clearly greatly reduce the amount of mem zeroing on algo initialization.
If one wants to compress/decompress a huge number of very small datasets though, this method will for sure improve the mem init speed but bitflag dictionary processing will always be active and alter algorithms speed, so in all cases there will be a performance hit for processing small datasets, which is not something desirable really.

If all data streams are below threshold then indeed density would always run with active bitflags management.

Dynamic buffer size sounds OK and should be faster than bitflag management before hitting threshold, but it has disadvantages:

• decreased compression ratio due to smaller dictionary size at the beginning (but probably it won't be a big decrease if threshold is carefully chosen),
• possibly big lag when transferring data from small dictionary to big dictionary assuming you would be doing that - otherwise further compression ratio decrease would happen
• using prebuilt dictionaries would be not feasible or be less efficient

The idea with dictionaries and bitflag management is that you can copy entries from a pre-built dictionary on first use instead of zeroing them. Pre-built dictionaries are most effective on small independent data blocks that share a lot of entries in dictionaries. Investigation is needed to assess whether pre-built dictionaries can greatly help improving compression ratio in InnoDB case.

I'm not sure what would be the overhead of bitflag management, though. If it's very high then it wouldn't be an interesting alternative. But given the possible advantages it's worth checking.

What do you think?

[g1mv]

Yes I'm definitely going to check it, the only drawback I can see is that some algorithms like chameleon are so fast that even a bit masking and test might hit performance in a non negligible way, but I'll let benchmarking be the judge.

decreased compression ratio due to smaller dictionary size at the beginning (but probably it won't be a big decrease if threshold is carefully chosen)

That's absolutely right, there will be more collisions after hashing. My idea is to initially consider groups of 2 bytes instead of 4 so dictionary entries are already twice as small, and use a dictionary with a lot less entries which could additionally make it fit in higher Lx caches to compensate the loss of speed incurred by doubling hashing ops. 2 byte entries gives a max of 65536 possibilities, I need to benchmark what's feasible but I'm pretty sure a 1024 or 2048 entry dictionary would give a reasonable compression ratio... to be tested. That would be 64 or 32 times entries less than the current dictionary for chameleon as an example, and would require 2x1024=2kB or 2x2048=4kB mem to be zeroed against the current 4x65536 = 256kB for chameleon. So 128 or 64 times faster.

possibly big lag when transferring data from small dictionary to big dictionary assuming you would be doing that - otherwise further compression ratio decrease would happen

That's definitely a problem. One solution I see for this is - if not using a prebuilt dictionary - performing an ascendant 256-byte zeroing and a big dictionary insert (if the hashed value is below the zeroing counter obviously) every let's say 256 bytes read during the initial "small dictionary phase", so in the beginning the big dictionary would get populated progressively without any impact on speed. By choosing carefully the frequency of big dictionary inserts, when we switch to the "big dictionary phase" it is already pre-populated with coherent data.

using prebuilt dictionaries would be not feasible or be less efficient

I don't really think unless I missed your point that this would be an issue. Instead of pre-building one big dictionary you could just as well pre-build a small and a big one.

I'd be glad to know your opinion on this, before I give all of the ideas a trial run, it's very possible I could have overlooked something ^^

[tarsa]

I don't really think unless I missed your point that this would be an issue. Instead of pre-building one big dictionary you could just as well pre-build a small and a big one.

But how to transfer modifications (done while compressing data before exceeding threshold) from small dictionary to big dictionary? Perhaps for chameleon it would be quick, but for mandala and lion you would need to reconcile queues of chunks in dictionary entries. That would probably be slower than redoing compression from scratch using big dictionary.

One solution I see for this is - if not using a prebuilt dictionary - performing an ascendant 256-byte zeroing and a big dictionary insert (if the hashed value is below the zeroing counter obviously) every let's say 256 bytes read during the initial "small dictionary phase", so in the beginning the big dictionary would get populated progressively without any impact on speed.

Neat solution. Could be the winner although you will have an extra branch here so benchmarks will tell the truth.

Lots of experimentation ahead :) On my side, I'm busy with a Rust rewrite (and improvement) of demixer ( https://encode.ru/threads/1671-Demixer-new-tree-based-bitwise-CM-codec-is-in-development ). Currently I'm working on tree handling and it's very tricky. Nobody said developing compression algorithms would be easy, though.