quadtree: Optimize recalculate_parent_area_stats()

There is no need to go through the entire tree in case one leaf node
has a minimal change in it. As long as we have gone high enough in the
tree that there is no more any changes to the corner vectors, we can
stop walking the tree up. According to perf measurements, this
optimization reduces the tree area recalculation overhead about 50%.

Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>

diff --git a/quadtree.c b/quadtree.c
index 72973c8bba7ae35049f087057790db577719edb6..cb4add658e44ed0d25a6968bf6a495c7595ec041 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -213,10 +213,21 @@ static void _recalculate_node_area_stats(struct quadtree *node)
 
 static void recalculate_parent_area_stats(struct quadtree *node)
 {
+       struct vector old_corner[2];
+
        while (node) {
+               memcpy(&old_corner, &node->corner, sizeof(old_corner));
+
                _recalculate_node_area_stats(node);
 
-               node = node->parent;
+               /*
+                * Stop propagating the changes up in the tree if
+                * nothing has changed
+                */
+               if (memcmp(&old_corner, &node->corner, sizeof(old_corner)))
+                       node = node->parent;
+               else
+                       node = NULL;
        }
 }