[FFmpeg-devel] [PATCH] checkasm: Use a self-balancing tree
michaelni at gmx.at
Fri Sep 25 21:57:07 CEST 2015
On Fri, Sep 25, 2015 at 09:28:26PM +0200, 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(-)
is there any reason why this doesnt use
Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
The educated differ from the uneducated as much as the living from the
dead. -- Aristotle
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 181 bytes
Desc: Digital signature
More information about the ffmpeg-devel