Hi, On Fri, Sep 25, 2015 at 3:28 PM, Henrik Gramner <hen...@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 _______________________________________________ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
