FLAC compression improvement patch

Topic: FLAC compression improvement patch (Read 45244 times) previous topic - next topic

0 Members and 1 Guest are viewing this topic.

FLAC compression improvement patch

2014-08-07 09:28:32

I was looking for a good way to use my summer break, so I looked into possible ways to improve the FLAC codec. In short: I found a way that improves compression of FLAC -8 by about 0.22 percentage point, which is 0.38%, at the cost of reducing the encoding speed to one third (so, if it was 60x, it'll now be 20x). I got these numbers from a nicely balanced pool of music of very different genres, see my lossless audio codec comparison for the list of CDs used.

The improvement for specific tracks may differ, but by the nature of this change, compression can only improve, i.e., there will be no tracks where compression ratio suffers from using this switch compared to not using it. Finally: decoding speed is not affected and there are no compatibility issues.

My question to you is: if I made a patch which adds an encoding switch (like WavPacks -x1), and it is accepted into the FLAC codebase for the next version, would you use it? After all, it's quite a large speed loss for a relatively small compression improvement.

FLAC compression improvement patch

Reply #1 – 2014-08-07 09:30:26

For those curious about what I did: I thought up a few new apodization functions/windows that are unlike any already in the codec. I thought, if using a variable blocksize algorithm is not a good idea (because of compatibility), why not try to steer the LPC algorithm into only looking at a specific part of the signal? Imagine that a block consists of 80% of signal that is similar, and 20% noise. The 20% noise is used in the LPC algorithm to generate a predictor and makes it worse at predicting the signal part.

So, I added two new apodization functions that only look at a part of the block to generate a predictor. -A partial_tukey(n) add n small apodization functions that all span a different part (1/n-th plus overlap) of the block. -A punchout_tukey(n) created n apodization functions that all span the whole signal except one part (1/n-th plus overlap in width). So partial_tukey(3) add three windows that all span one third of the block, punchout_tukey(3) add thee windows that all span two third of the block (there's a hole spanning one third of the block) By combining these functions with the default function, tukey(0.5), I ensure that compression can only improve. It outperforms the best combination of three existing apodization functions I've seen on my dataset by 0.07%.

Finally, I'm not a native speaker, so I'm still a little worried about the names. partial_tukey seems right, but for punchout_tukey, something different might be better. punched_tukey maybe? Maybe I should reverse the parts (tukey_partial and tukey_punched?)

FLAC compression improvement patch

Reply #2 – 2014-08-07 10:49:00

The next version of FLAC (currently in development) shows considerable speed increases over the current 1.3.0. It would be interesting to take lvqcl's code that includes the speed increases, patch it with your compression improvements, and then compare the speed to 1.3.0. Perhaps the speed penalty is not that big if it's compensated by the recent speed improvements.

To answer your question, I can't speak for anyone but myself but personally I've always found encoding speed of lesser importance as you only encode a file once.

Three questions:
1) does your patch have any implications for decoding speed of the resulting files?
2) do you think that once this patch is applied there might be room for improvement (either by you or by others) to make the code more efficient and regain some of the speed loss?
3) why not add it as a standard to -8? People that deliberately opt to use -8 instead of default -5 do so because they want optimum compression, not speed, so they likely will appreciate it.

FLAC compression improvement patch

Reply #3 – 2014-08-07 11:09:45

Quote from: ktf on 2014-08-07 09:28:32

My question to you is: if I made a patch which adds an encoding switch (like WavPacks -x1), and it is accepted into the FLAC codebase for the next version, would you use it? After all, it's quite a large speed loss for a relatively small compression improvement.

As Maurits, I'm not concerned about encoding speed so much. Any compression improvement is welcome, once the difference between TAK and FLAC at max settings isn't worth bearing TAK's unicode/platform incompatibility, I'm switching back. According to the wiki, the current difference is 1%. Reducing that to a 0.62% difference is quite interesting. I'm also interested in knowing if it can be improved even more. (edit: looking at my files, the figure of 1% seems to be outdated...)

Keep in mind that we also have flacCL, where the encoding impact would be a lot less.

Quote from: Maurits on 2014-08-07 10:49:00

1) does your patch have any implications for decoding speed of the resulting files?

Quote from: ktf on 2014-08-07 09:28:32

Finally: decoding speed is not affected and there are no compatibility issues.

Quote from: Maurits on 2014-08-07 10:49:00

3) why not add it as a standard to -8? People that deliberately opt to use -8 instead of default -5 do so because they want optimum compression, not speed, so they likely will appreciate it.

Why not call it -9 instead, to avoid confusion with "previous" -8 files?

FLAC compression improvement patch

Reply #4 – 2014-08-07 11:32:51

Quote from: ChronoSphere on 2014-08-07 11:09:45

Quote from: Maurits on 2014-08-07 10:49:00
1) does your patch have any implications for decoding speed of the resulting files?

Quote from: ktf on 2014-08-07 09:28:32
Finally: decoding speed is not affected and there are no compatibility issues.

Ah, don't know how I missed that!

FLAC compression improvement patch

Reply #5 – 2014-08-07 11:40:33

Quote from: Maurits on 2014-08-07 10:49:00

It would be interesting to take lvqcl's code that includes the speed increases, patch it with your compression improvements, and then compare the speed to 1.3.0.

I did, the tests I've been running have taken a week now, and further tuning will take two more weeks of 24/7 testing. It would be very stupid indeed, to not work from the latest git but from the 1.3.0 code. As most people reported between 60% and 100% increase in speed, that would add up to the speed a little less than halving.

Quote

1) does your patch have any implications for decoding speed of the resulting files?
2) do you think that once this patch is applied there might be room for improvement (either by you or by others) to make the code more efficient and regain some of the speed loss?
3) why not add it as a standard to -8? People that deliberately opt to use -8 instead of default -5 do so because they want optimum compression, not speed, so they likely will appreciate it.

1) No, it should not, because it only adds extra 'tries' to model the signal with a predictor.
2) Any speed improvement that affects this speed loss will affect the encoding speed in general, because the stage that generates and evaluates the predictor (the most processing power consuming stage of the encoding process) is repeated for different windows. As I see no possibility for correlation between the repetitions, any improvement should come from the code that I did not touch
3) Might be an option, but I feel like I'm 'undoing' much of the progress lvqcl made. He did a hell of a job improving the SSE code, but if this improvement is added as standard to -8, that won't be visible.

Quote from: ChronoSphere on 2014-08-07 11:09:45

According to the wiki, the current difference is 1%. Reducing that to a 0.62% difference is quite interesting. I'm also interested in knowing if it can be improved even more.

The data in the wiki is for default encoding modes (otherwise, comparing is very hard), and is taken from my lossless audio codec comparison. If one uses TAK for the compression improvement, using the default is not a good choice. The difference between TAK and FLAC for the same encoding speed is more like 2.5 percentage point, which is 4%.

Quote from: ChronoSphere on 2014-08-07 11:09:45

Why not call it -9 instead, to avoid confusion with "previous" -8 files?

Well, the improvement of 0.22 percentage point for 1/3th of the speed is only one of the options. I'm experimenting with combinations of window functions that gain 0.3 percenage point for 1/6th of the speed. You see, there will probably be two to three settings for this, and furthermore, they can be used with setting -5 as well, for slightly faster decoding. Furthermore, settings higer than -8 has been a --lax (non-subset) setting in early versions of FLAC, in FLACCL (IIRC), Flake and FFMPEG, this might confuse people.

So, I'm not sure how to incorporate this. Just add the apodization functions so advanced users can manually add them to the command line, make it a little easier and add it to a bunch of switches (which is more accessible) or add it by default to a (new) compression level...?

FLAC compression improvement patch

Reply #6 – 2014-08-07 11:50:18

Ask on the flac-dev list. -8 compression has a very specific definition and I'm not clear whether your new function fits within that. In any case, it isn't my decision Like many people said, trading off encoding speed for a tiny bit more compression will be useful in a lot of cases.

FLAC compression improvement patch

Reply #7 – 2014-08-07 11:54:31

Just adding new switches is fine too. Being able to do -8 -x1 or similar is just as fine.

As for confusion, I see where you're coming from, but considering flacCL's presets have different tuning parameters for same number presets, they can't be compared to libflac directly anyway. Wasn't the reason the 9+ presets were named --lax (non subset) because they fell out of specs decoding-wise, making it hard for hardware players to decode them?

Also yes, the difference between TAK p4m and FLAC -8 for my library is 4,7%

FLAC compression improvement patch

Reply #8 – 2014-08-07 12:11:15

Quote from: lithopsian on 2014-08-07 11:50:18

Ask on the flac-dev list.

This. This is a clever idea. Ask what the current maintainers think is the best solution, that'll give you the best chances of getting accepted upstream.

FLAC compression improvement patch

Reply #9 – 2014-08-07 12:27:12

Sure, I will, as soon as I'm done with the rigorous testing and tuning and updating the documentation. I'm not yet sure how many switches can be (sanely) added and how much they improve, and I don't want to send in anything that isn't finished yet. In the mean time, I just wanted to know what people here think

FLAC compression improvement patch

Reply #10 – 2014-08-07 13:05:28

0.38% improvement doesn't sound like a lot but I might be crazy enough to use it. Current FLAC uses --best as a synonym for -8 but I don't think it would be a horrible idea to repurpose --best to give highest compression possible. But that purpose would mean its functionality should change with --lax.

FLAC compression improvement patch

Reply #11 – 2014-08-07 13:08:08

Would be interesting to see how this works in FLACCL. So you add 3*partial_tukey(3) + 3*punchout_tukey(3)+tukey(0.5) to a total of 7 windows?

FLAC compression improvement patch

Reply #12 – 2014-08-07 14:00:11

Quote from: ktf on 2014-08-07 09:30:26

For those curious about what I did: I thought up a few new apodization functions/windows that are unlike any already in the codec. I thought, if using a variable blocksize algorithm is not a good idea (because of compatibility), why not try to steer the LPC algorithm into only looking at a specific part of the signal? Imagine that a block consists of 80% of signal that is similar, and 20% noise. The 20% noise is used in the LPC algorithm to generate a predictor and makes it worse at predicting the signal part.

Funny: That's quite similar to a proposal i made in 2006: Improved FLAC encoder, need help retuning presets.

But it was only a hypothesis. Great you came up with a similar idea and also tried it!

FLAC compression improvement patch

Reply #13 – 2014-08-07 14:34:16

Quote from: Case on 2014-08-07 13:05:28

Current FLAC uses --best as a synonym for -8 but I don't think it would be a horrible idea to repurpose --best to give highest compression possible. But that purpose would mean its functionality should change with --lax.

I'm not sure what you mean by that. --best can be repurposed as -8 + some apodizations functions if that is what you mean, but that is still within the subset. I don't think the reference encoder should 'encourage' generating non-subset streams in any way.

Quote from: Gregory S. Chudov on 2014-08-07 13:08:08

Would be interesting to see how this works in FLACCL. So you add 3*partial_tukey(3) + 3*punchout_tukey(3)+tukey(0.5) to a total of 7 windows?

Yes, I think improvements would be similar. Seeing that the stage apodizations are used is floating point math heavy, it might even work better/faster with FLACCL than the reference encoder, right? And yes, that's a total of 7 windows. From the first results, it looks like -A tukey(0.5) as default (-x0) is a good starting point, -x1 would be -A tukey(0.5) -A partial_tukey(2) and -x2 could be -A tukey(0.5) -A partial_tukey(2) -A punchout_tukey(3) In that case, -x0 would be 1 window, -x1 would be 3 windows and -x2 would be 6 windows. I'm still running checks, tests and comparisons for many settings on a lot of material to make sure this works for all kinds of music.

Quote from: TBeck on 2014-08-07 14:00:11

Funny: That's quite similar to a proposal i made in 2006: Improved FLAC encoder, need help retuning presets.

Indeed, it's even the same line of thinking. I have been thinking of ways to implement variable blocksizes in FLAC for some time now, but as this might break some decoders (even though it is subset-compatible), this looked like a good workaround. I've tried some modifications and ideas in the past, but this is the first one that actually seems to work.

FLAC compression improvement patch

Reply #14 – 2014-08-07 14:52:45

Quote from: ktf on 2014-08-07 14:34:16

I've tried some modifications and ideas in the past, but this is the first one that actually seems to work.

And "0.22 percentage" isn't bad. If i remember right, the average effect of TAK's variable blocksize mechanism was not bigger than 0.45 percent, at least not for low predictor counts (<= 12). Ok, since FLAC and TAK differ in many aspects, the maximum possible effect for FLAC might be different.

FLAC compression improvement patch

Reply #15 – 2014-08-07 14:55:28

I am no expert but this way of heavy processing really may shine on flacCL using the GPU!

FLAC compression improvement patch

Reply #16 – 2014-08-07 16:25:23

Quote from: ktf on 2014-08-07 14:34:16

Quote from: Case on 2014-08-07 13:05:28
Current FLAC uses --best as a synonym for -8 but I don't think it would be a horrible idea to repurpose --best to give highest compression possible. But that purpose would mean its functionality should change with --lax.

I'm not sure what you mean by that. --best can be repurposed as -8 + some apodizations functions if that is what you mean, but that is still within the subset. I don't think the reference encoder should 'encourage' generating non-subset streams in any way.

I meant that if --best is repurposed to mean best compression possible, it's not enough that it uses your new code behind the back in subset compatible mode. If user wants to create non-subset files with best compression it should tweak all the other options with new limits since it's no longer bound by subset limits.

FLAC compression improvement patch

Reply #17 – 2014-08-07 17:08:39

Thumb up!
In my opinion it should be
-8 (as FLAC 1.3.0 because lvqcl's speed improvements are really nice)
-8 --extreme (for this new patch/configuration)

FLAC compression improvement patch

Reply #18 – 2014-08-07 17:12:42

Quote from: TBeck on 2014-08-07 14:52:45

Ok, since FLAC and TAK differ in many aspects, the maximum possible effect for FLAC might be different.

Sure, as TAK compresses much better, improving on it is much harder too. I think comparing FLAC and TAK in this way does no justice to the work you've done on TAK, really.

Quote from: Case on 2014-08-07 16:25:23

I meant that if --best is repurposed to mean best compression possible, it's not enough that it uses your new code behind the back in subset compatible mode. If user wants to create non-subset files with best compression it should tweak all the other options with new limits since it's no longer bound by subset limits.

Alright, now I understand what you mean. Yes, you are probably right: If I introduce new options, the best options should change too to reflect this, and as it is no longer coupled to -8 it might change for using --lax as well. I'm in doubt about >48kHz material, FLAC's subset has no restriction on blocksize for samplerates higher than 48kHz, but for compatibility it is probably not a good idea to increase blocksize, right?

FLAC compression improvement patch

Reply #19 – 2014-08-07 17:45:19

Quote from: ktf on 2014-08-07 17:12:42

I'm in doubt about >48kHz material, FLAC's subset has no restriction on blocksize for samplerates higher than 48kHz, but for compatibility it is probably not a good idea to increase blocksize, right?

I can only talk for my older Slimdevice. Using a blocksize greater 4608 for 24/88.2+96 results in silence.
I noticed that because flacCL defaults to 8192 for these resolutions while regular flac uses 4096.

FLAC compression improvement patch

Reply #20 – 2014-08-07 17:49:01

Right, in that case, enabling higher blocksizes for high samplerates is probably not a good idea. Thanks for sharing this information.

FLAC compression improvement patch

Reply #21 – 2014-08-07 19:09:58

Quote from: ktf on 2014-08-07 17:12:42

Quote from: TBeck on 2014-08-07 14:52:45
Ok, since FLAC and TAK differ in many aspects, the maximum possible effect for FLAC might be different.

Sure, as TAK compresses much better, improving on it is much harder too. I think comparing FLAC and TAK in this way does no justice to the work you've done on TAK, really.

What i really tried to say was, that the gain of your method is quite significant if you compare it to TAK's sub framing, which possibly is close to the optimum, which can be achieved with variable size sub frames embedded in a fixed size frame.

Sorry, my english degenerates fast if i don't post at hydrogen...

FLAC compression improvement patch

Reply #22 – 2014-08-10 19:35:30

I was busy finishing the testing I was doing when I stumbled across something rather interesting...

When using so many apodizations, it seems the -e switch (exhaustive modelling) becomes less usefull. See this data

Code: [Select]

      ---- Compression setting ----                                                   , Compr., Encsp, Decsp
-8 -A tukey(0.5) -A partial_tukey(2) -A punchout_tukey(3)                             , 56.450, 13.9 , 376.7
-8 -A tukey(0.5) -A partial_tukey(2) -A punchout_tukey(3) --no-exhaustive-model-search, 56.511, 64.0 , 379.9
-8                                                                                    , 56.690, 60.1 , 379.0
-8 --no-exhaustive-model-search                                                       , 56.850, 169.5, 377.5

As you can see, with only the default apodization, the compression gain for using -e is 0.3% at the cost of reducing the encoding speed to 1/3th. However, when using six apodization functions, the gain is only 0.1% at the cost of reducing the encoding speed to 1/5th. So gain decreases while effort increases.

So, I've just sent a mail to the flac-dev list proposing to drop the use of the -e options for compression level -7 and -8 and instead using more apodization functions. You can see the difference here: http://www.audiograaf.nl/misc_stuff/settin...sualisation.pdf If this change is accepted, FLAC will be both faster and better compressing...

FLAC compression improvement patch

Reply #23 – 2014-08-10 19:49:43

I'd use it.

FLAC compression improvement patch

Reply #24 – 2014-08-10 22:03:04

I am not sure I completely understand. I tried encoding a file with these parameters and for me the "-8 -A tukey(0.5) -A partial_tukey(2) -A punchout_tukey(3)" gave a worse compression rate than simply using -8... Or are those benchmarks with your custom code applied?

edit: I'd still want an option to allow me to do an exhaustive search, even if the gains are minimal.

Notice