[FFmpeg-devel] [PATCH 1/2] libavcodec/zmbvenc: block scoring improvements/bug fixes

[Michael Niedermayer]

On Thu, Feb 21, 2019 at 09:26:44PM +0000, Matthew Fearnley wrote:
> On Thu, 21 Feb 2019 at 19:28, Michael Niedermayer <michael at niedermayer.cc>
> wrote:
> 
> > On Thu, Feb 21, 2019 at 11:19:08AM +0100, Tomas Härdin wrote:
> > > ons 2019-02-20 klockan 22:12 +0100 skrev Michael Niedermayer:
> > > > On Sat, Feb 09, 2019 at 01:10:20PM +0000, Matthew Fearnley wrote:
> > > > > - Improve block choices by counting 0-bytes in the entropy score
> > > > > - Make histogram use uint16_t type, to allow byte counts from 16*16
> > > > > (current block size) up to 255*255 (maximum allowed 8bpp block size)
> > > > > - Make sure score table is big enough for a full block's worth of
> > bytes
> > > > > - Calculate *xored without using code in inner loop
> > > >
> > > > This should have been split into multiple changes
> > >
> > > Alas
> > >
> >
> > > > compression seems to become slightly worse from this change
> > > >
> > > > ./ffmpeg -i matrixbench_mpeg2.mpg -vframes 30 -vcodec zmbv -an -y
> > test-old.avi
> > > > ./ffmpeg -i matrixbench_mpeg2.mpg -vframes 30 -vcodec zmbv -an -y
> > test-new.avi
> > > >
> > > > -rw-r----- 1 michael michael 1175466 Feb 20 22:06 test-new.avi
> > > > -rw-r----- 1 michael michael 1174832 Feb 20 22:07 test-old.avi
> > >
> > > A whopping 0.05% change,
> >
> > no its just a tiny difference but i think it still would make sense to
> > understand it.
> > Generally a patch doing 4 improvments would be expected to improve things.
> > This was not a hand picked case. I mean its not as if I saw 10 cases
> > improving things and i picked the 11th. i looked at one case and that was
> > worse
> >
> > Also either way the patch should have been split, dont you agree ?
> > it also would make it much easier to within seconds identify which
> > change actually caused the 0.05% difference. (maybe avoiding this
> > discussion as it maybe would be obvious from that if this is a
> > ommision in the commit message a bug a rare outlier ...)
> >
> > Hi Michael.  First, let me say thanks for your feedback on this patch.
> Let me address some of this..
> 

> - Yes: in retrospect, I think I should have split the patch.
> I struggled here to work out how to split up my changes, and spent too long
> staring too closely at the code to see this.
> I still perhaps have some way to go before I would be able to get a proper
> feel for the general FFmpeg development ecosystem.

if something is unclear, ask, yes i know this is often not so simple but
especially in case of for example spliting patches, if you dont know how
its easy to ask 


> 
> - To clear up the effects: the change from 'i=1' to 'i=0' was the only
> change that should make any difference in the output.
> The rest of the changes were to improve the speed of an inner loop, and to
> fix two bugs that happily cancelled each other out, but would have broken
> if the code were changed to emit larger blocks.  These should not lead to
> changes in the blocks chosen or the final compression size.
> 

> - Regarding the worse compression: let me start by stating that scoring on
> byte frequency alone will not always predict well how Deflate will work,
> since Deflate also uses pattern matching as well.
> Frequency-based block scoring will only ever be a heuristic.  There may be
> scope for improving the scoring, but it would add a lot of complexity, and
> I think it would be easy to make things worse rather than better.  (I found
> this in my brief experiments with including the frequencies from the
> previous block.)

implementing the exact scoring by using Deflate itself would allow us to
understand how much there is between the heuristic and what is achievable.
If there is a gap that is significant then it may be interresting to
look at improving the heuristic if the gap is small than the whole
heuristic improvment path can be discarded.
The obvious improvment for the heuristic would be to move to higher
order entropy estimation. ATM IIUC this uses a 0th order. 1st order could
be tried or any fast compression algorithm could also be used to estimate
entropy.
It also would be interresting to see how a higher order heuristic or
some simple fast LZ like compressor would perform with the previous block.
That is if the issue you saw with the previous block inclusion was because
of the very simplistic entropy estimation.


> 
> I think the main thing that persuaded me to make this particular change
> from 1 to 0 was that it gave a pure entropy-based score, and allowed me,
> mathematically, to use the same scoring table on both full and partial
> blocks, without having to worry about the effects of omitting the 0-bytes
> in the score in each case.
> 
> I focused my testing on the available ZMBV samples, which were likely all
> generated by DOSBox, and my findings were that while not all movies were
> smaller, overall the gains outweighed the losses.
> I'm slightly sad to hear it didn't improve this real-world movie sample.
> But I think this level in this case is acceptable, and not outside the
> expected range of size difference that I've seen.  And the improvements to
> the motion estimation range (from the other patch) should tend to lead to a
> compression improvement overall.
> 

> Maybe I should have been clearer though, that the scoring changes won't
> bring universal improvements.  And if someone looks into this and finds on
> average results are worsened by the change, I won't complain if it gets
> reverted.

please be more verbose in future commit messages. I mean for example this mail
contains alot of valuable information which would be interresting to
someone looking at the commit.

Also more verbose commit messages can help reviewers review changes.

Thanks

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

The greatest way to live with honor in this world is to be what we pretend
to be. -- Socrates
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 181 bytes
Desc: not available
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20190222/299553ad/attachment.sig>