On 25/09/15 21:35, Henrik Gramner 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(-) >
Possibly Ok. lu _______________________________________________ libav-devel mailing list [email protected] https://lists.libav.org/mailman/listinfo/libav-devel
