pipeline: optimize _compare_differences functions

This optimizes the layer and pipeline _compare_differences functions so
neither of them use the GArray api since building up the list of
ancestors by appending to a shared GArray was showing quite high on
profiles due to how frequently pipeline comparisons are made. Instead
we now build up a transient, singly linked list by allocating GList
nodes via alloca to build up the parallel lists of ancestors.

This tweaked approach actually ends up being a bit more concise than
before, we avoid the overhead of the GArray api and now avoid making any
function calls while comparing (assuming the _get_parent() calls always
inline), we avoiding needing to get the default cogl context.

Reviewed-by: Neil Roberts <neil@linux.intel.com>

1 files changed, 44 insertions, 54 deletions

diff --git a/cogl/cogl-pipeline-layer.c b/cogl/cogl-pipeline-layer.c
index 963412aa..8c8d066c 100644
--- a/cogl/cogl-pipeline-layer.c
+++ b/cogl/cogl-pipeline-layer.c
@@ -376,82 +376,72 @@ unsigned long
 _cogl_pipeline_layer_compare_differences (CoglPipelineLayer *layer0,
                                           CoglPipelineLayer *layer1)
 {
+  GSList *head0 = NULL;
+  GSList *head1 = NULL;
   CoglPipelineLayer *node0;
   CoglPipelineLayer *node1;
-  int len0;
-  int len1;
-  int len0_index;
-  int len1_index;
+  int len0 = 0;
+  int len1 = 0;
   int count;
-  int i;
-  CoglPipelineLayer *common_ancestor = NULL;
+  GSList *common_ancestor0;
+  GSList *common_ancestor1;
   unsigned long layers_difference = 0;
 
-  _COGL_GET_CONTEXT (ctx, 0);
-
   /* Algorithm:
    *
    * 1) Walk the ancestors of each layer to the root node, adding a
-   *    pointer to each ancester node to two GArrays:
-   *    ctx->pipeline0_nodes, and ctx->pipeline1_nodes.
+   *    pointer to each ancester node to two linked lists
    *
-   * 2) Compare the arrays to find the nodes where they stop to
-   *    differ.
+   * 2) Compare the lists to find the nodes where they start to
+   *    differ marking the common_ancestor node for each list.
    *
-   * 3) For each array now iterate from index 0 to the first node of
-   *    difference ORing that nodes ->difference mask into the final
-   *    pipeline_differences mask.
+   * 3) For each list now iterate starting after the common_ancestor
+   *    nodes ORing each nodes ->difference mask into the final
+   *    differences mask.
    */
 
-  g_array_set_size (ctx->pipeline0_nodes, 0);
-  g_array_set_size (ctx->pipeline1_nodes, 0);
   for (node0 = layer0; node0; node0 = _cogl_pipeline_layer_get_parent (node0))
-    g_array_append_vals (ctx->pipeline0_nodes, &node0, 1);
+    {
+      GSList *link = alloca (sizeof (GSList));
+      link->next = head0;
+      link->data = node0;
+      head0 = link;
+      len0++;
+    }
   for (node1 = layer1; node1; node1 = _cogl_pipeline_layer_get_parent (node1))
-    g_array_append_vals (ctx->pipeline1_nodes, &node1, 1);
-
-  len0 = ctx->pipeline0_nodes->len;
-  len1 = ctx->pipeline1_nodes->len;
-  /* There's no point looking at the last entries since we know both
-   * layers must have the same default layer as their root node. */
-  len0_index = len0 - 2;
-  len1_index = len1 - 2;
-  count = MIN (len0, len1) - 1;
-  for (i = 0; i < count; i++)
     {
-      node0 = g_array_index (ctx->pipeline0_nodes,
-                             CoglPipelineLayer *, len0_index--);
-      node1 = g_array_index (ctx->pipeline1_nodes,
-                             CoglPipelineLayer *, len1_index--);
-      if (node0 != node1)
-        {
-          common_ancestor = _cogl_pipeline_layer_get_parent (node0);
-          break;
-        }
+      GSList *link = alloca (sizeof (GSList));
+      link->next = head1;
+      link->data = node1;
+      head1 = link;
+      len1++;
     }
 
-  /* If we didn't already find the first the common_ancestor ancestor
-   * that's because one pipeline is a direct descendant of the other
-   * and in this case the first common ancestor is the last node we
-   * looked at. */
-  if (!common_ancestor)
-    common_ancestor = node0;
-
-  count = len0 - 1;
-  for (i = 0; i < count; i++)
+  /* NB: There's no point looking at the head entries since we know both layers
+   * must have the same default layer as their root node. */
+  common_ancestor0 = head0;
+  common_ancestor1 = head1;
+  head0 = head0->next;
+  head1 = head1->next;
+  count = MIN (len0, len1) - 1;
+  while (count--)
     {
-      node0 = g_array_index (ctx->pipeline0_nodes, CoglPipelineLayer *, i);
-      if (node0 == common_ancestor)
+      if (head0->data != head1->data)
         break;
-      layers_difference |= node0->differences;
+      common_ancestor0 = head0;
+      common_ancestor1 = head1;
+      head0 = head0->next;
+      head1 = head1->next;
     }
 
-  count = len1 - 1;
-  for (i = 0; i < count; i++)
+  for (head0 = common_ancestor0->next; head0; head0 = head0->next)
     {
-      node1 = g_array_index (ctx->pipeline1_nodes, CoglPipelineLayer *, i);
-      if (node1 == common_ancestor)
-        break;
+      node0 = head0->data;
+      layers_difference |= node0->differences;
+    }
+  for (head1 = common_ancestor1->next; head1; head1 = head1->next)
+    {
+      node1 = head1->data;
       layers_difference |= node1->differences;
     }