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

[Ronald S. Bultje]

Hi,

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(-)


lgtm.

Ronald