• John Koleszar's avatar
    Optimize vp9_tree_probs_from_distribution · bd84685f
    John Koleszar authored
    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