[FFmpeg-devel] [PATCH] checkasm: Use a self-balancing tree

Ronald S. Bultje rsbultje at gmail.com
Sat Sep 26 12:53:08 CEST 2015


On Fri, Sep 25, 2015 at 3:28 PM, Henrik Gramner <henrik at gramner.com> wrote:

> Tested functions are internally kept in a binary search tree for efficient
> lookups. The downside of the current implementation is that the tree
> quickly
> becomes unbalanced which causes an unneccessary amount of comparisons
> between
> nodes. Improve this by changing the tree into a self-balancing left-leaning
> red-black tree with a worst case lookup/insertion time complexity of O(log
> n).
> Significantly reduces the recursion depth and makes the tests run around
> 10%
> faster overall. The relative performance improvement compared to the
> existing
> non-balanced tree will also most likely increase as more tests are added.
> ---
>  tests/checkasm/checkasm.c | 59
> +++++++++++++++++++++++++++++++++++++----------
>  1 file changed, 47 insertions(+), 12 deletions(-)



More information about the ffmpeg-devel mailing list