]> granicus.if.org Git - libvpx/commit
Optimize vp9_tree_probs_from_distribution
authorJohn Koleszar <jkoleszar@google.com>
Sun, 10 Mar 2013 20:39:30 +0000 (13:39 -0700)
committerJohn Koleszar <jkoleszar@google.com>
Sun, 10 Mar 2013 20:39:30 +0000 (13:39 -0700)
commitbd84685f7841f4f571f063a18b96d53e0fdef8cc
treed807ec221401c29f8e4a20dba720c8cef338b3b5
parent4209bba4627bb148fce5b8b6caa4de5ac526fa92
Optimize vp9_tree_probs_from_distribution

The previous implementation visited each node in the tree multiple times
because it used each symbol's encoding to revisit the branches taken and
increment its count. Instead, we can traverse the tree depth first and
calculate the probabilities and branch counts as we walk back up. The
complexity goes from somewhere between O(nlogn) and O(n^2) (depending on
how balanced the tree is) to O(n).

Only tested one clip (256kbps, CIF), saw 13% decoding perf improvement.

Note that this optimization should port trivially to VP8 as well. In VP8,
the decoder doesn't use this function, but it does routinely show up
on the profile for realtime encoding.

Change-Id: I4f2848e4f41dc9a7694f73f3e75034bce08d1b12
vp9/common/vp9_entropy.c
vp9/common/vp9_entropymode.c
vp9/common/vp9_entropymv.c
vp9/common/vp9_treecoder.c
vp9/common/vp9_treecoder.h
vp9/encoder/vp9_bitstream.c