[cogl] cogl-pipeline: Store the uniform overrides in an array instead of list

[Neil Roberts <nroberts src gnome org>]

commit 4a7cd0d2ac0b2e794d11b55dec43f3a688fff63c
Author: Neil Roberts <neil linux intel com>
Date:   Fri Nov 4 17:56:44 2011 +0000

    cogl-pipeline: Store the uniform overrides in an array instead of list
    
    Previously the uniform overrides were stored in a linked list. Now
    they are stored in a g_malloc'd array. The values are still tightly
    packed so that there is only a value for each uniform that has a
    corresponding bit in override_mask. The allocated size of the array
    always exactly corresponds to the number of bits set in the
    override_mask. This means that when a new uniform value is set on a
    pipeline it will have to grow the array and copy the old values
    in. The assumption is that setting a value for a new uniform is much
    less frequent then setting a value for an existing uniform so it makes
    more sense to optimise the latter.
    
    The advantage of using an array is that we can quickly jump to right
    boxed value given a uniform location by doing a population count in
    the bitmask for the number of bits less than the given uniform
    location. This can be done in O(1) time whereas the old approach using
    a list would scale by the number of bits set.
    
    Reviewed-by: Robert Bragg <robert linux intel com>

 cogl/cogl-pipeline-private.h      |   26 ++-------
 cogl/cogl-pipeline-progend-glsl.c |   11 ++--
 cogl/cogl-pipeline-state.c        |  104 ++++++++++++++++--------------------
 cogl/cogl-pipeline.c              |   48 +++++++----------
 4 files changed, 77 insertions(+), 112 deletions(-)
---
diff --git a/cogl/cogl-pipeline-private.h b/cogl/cogl-pipeline-private.h
index 4c2dd2b..a6100a8 100644
--- a/cogl/cogl-pipeline-private.h
+++ b/cogl/cogl-pipeline-private.h
@@ -339,32 +339,18 @@ typedef struct
   CoglWinding front_winding;
 } CoglPipelineCullFaceState;
 
-typedef struct _CoglPipelineUniformOverride CoglPipelineUniformOverride;
-
-COGL_SLIST_HEAD (CoglPipelineUniformOverrideList,
-                 CoglPipelineUniformOverride);
-
-struct _CoglPipelineUniformOverride
-{
-  COGL_SLIST_ENTRY (CoglPipelineUniformOverride) list_node;
-
-  /* We don't need to store the location of the uniform here because
-     it is implicit from the order in the list */
-
-  /* One of these overrides can effectively remove a uniform by
-     setting the boxed value type to none. In that case no attempt
-     will be made to upload the value */
-
-  CoglBoxedValue value;
-};
-
 typedef struct
 {
   CoglBitmask override_mask;
+
+  /* This is an array of values. Only the uniforms that have a bit set
+     in override_mask have a corresponding value here. The uniform's
+     location is implicit from the order in this array */
+  CoglBoxedValue *override_values;
+
   /* Uniforms that have been modified since this pipeline was last
      flushed */
   CoglBitmask changed_mask;
-  CoglPipelineUniformOverrideList override_list;
 } CoglPipelineUniformsState;
 
 typedef struct
diff --git a/cogl/cogl-pipeline-progend-glsl.c b/cogl/cogl-pipeline-progend-glsl.c
index 891be79..2c7f857 100644
--- a/cogl/cogl-pipeline-progend-glsl.c
+++ b/cogl/cogl-pipeline-progend-glsl.c
@@ -559,7 +559,8 @@ typedef struct
   unsigned long *uniform_differences;
   int n_differences;
   CoglContext *ctx;
-  CoglPipelineUniformOverride *override;
+  const CoglBoxedValue *values;
+  int value_index;
 } FlushUniformsClosure;
 
 static gboolean
@@ -609,13 +610,13 @@ flush_uniform_cb (int uniform_num, void *user_data)
       if (uniform_location != -1)
         _cogl_boxed_value_set_uniform (data->ctx,
                                        uniform_location,
-                                       &data->override->value);
+                                       data->values + data->value_index);
 
       data->n_differences--;
       COGL_FLAGS_SET (data->uniform_differences, uniform_num, FALSE);
     }
 
-  data->override = COGL_SLIST_NEXT (data->override, list_node);
+  data->value_index++;
 
   return data->n_differences > 0;
 }
@@ -698,8 +699,8 @@ _cogl_pipeline_progend_glsl_flush_uniforms (CoglPipeline *pipeline,
           const CoglPipelineUniformsState *parent_uniforms_state =
             &pipeline->big_state->uniforms_state;
 
-          data.override =
-            COGL_SLIST_FIRST (&parent_uniforms_state->override_list);
+          data.values = parent_uniforms_state->override_values;
+          data.value_index = 0;
 
           _cogl_bitmask_foreach (&parent_uniforms_state->override_mask,
                                  flush_uniform_cb,
diff --git a/cogl/cogl-pipeline-state.c b/cogl/cogl-pipeline-state.c
index e9cf5c7..8f7eefa 100644
--- a/cogl/cogl-pipeline-state.c
+++ b/cogl/cogl-pipeline-state.c
@@ -240,8 +240,9 @@ _cogl_pipeline_user_shader_equal (CoglPipeline *authority0,
 
 typedef struct
 {
-  const CoglBoxedValue **values;
-  const CoglPipelineUniformOverride *override_values;
+  const CoglBoxedValue **dst_values;
+  const CoglBoxedValue *src_values;
+  int override_count;
 } GetUniformsClosure;
 
 static gboolean
@@ -249,10 +250,10 @@ get_uniforms_cb (int uniform_num, void *user_data)
 {
   GetUniformsClosure *data = user_data;
 
-  if (data->values[uniform_num] == NULL)
-    data->values[uniform_num] = &data->override_values->value;
+  if (data->dst_values[uniform_num] == NULL)
+    data->dst_values[uniform_num] = data->src_values + data->override_count;
 
-  data->override_values = COGL_SLIST_NEXT (data->override_values, list_node);
+  data->override_count++;
 
   return TRUE;
 }
@@ -268,14 +269,15 @@ _cogl_pipeline_get_all_uniform_values (CoglPipeline *pipeline,
   memset (values, 0,
           sizeof (const CoglBoxedValue *) * ctx->n_uniform_names);
 
-  data.values = values;
+  data.dst_values = values;
 
   do
     {
       const CoglPipelineUniformsState *uniforms_state =
         &pipeline->big_state->uniforms_state;
 
-      data.override_values = COGL_SLIST_FIRST (&uniforms_state->override_list);
+      data.override_count = 0;
+      data.src_values = uniforms_state->override_values;
 
       if ((pipeline->differences & COGL_PIPELINE_STATE_UNIFORMS))
         _cogl_bitmask_foreach (&uniforms_state->override_mask,
@@ -1398,44 +1400,13 @@ cogl_pipeline_set_point_size (CoglPipeline *pipeline,
                                    _cogl_pipeline_point_size_equal);
 }
 
-typedef struct
-{
-  int location;
-  CoglPipelineUniformOverride *previous_override;
-  CoglPipelineUniformOverride *found_override;
-  CoglPipelineUniformOverride *it;
-} FindUniformOverrideClosure;
-
-static gboolean
-find_uniform_override_cb (int it_location,
-                          void *user_data)
-{
-  FindUniformOverrideClosure *data = user_data;
-
-  if (it_location < data->location)
-    {
-      data->previous_override = data->it;
-      data->it = COGL_SLIST_NEXT (data->it, list_node);
-
-      return TRUE;
-    }
-  else
-    {
-      if (it_location == data->location)
-        data->found_override = data->it;
-
-      return FALSE;
-    }
-}
-
 static CoglBoxedValue *
 _cogl_pipeline_override_uniform (CoglPipeline *pipeline,
                                  int location)
 {
   CoglPipelineState state = COGL_PIPELINE_STATE_UNIFORMS;
   CoglPipelineUniformsState *uniforms_state;
-  FindUniformOverrideClosure find_data;
-  CoglPipelineUniformOverride *override;
+  int override_index;
 
   _COGL_GET_CONTEXT (ctx, NULL);
 
@@ -1452,36 +1423,53 @@ _cogl_pipeline_override_uniform (CoglPipeline *pipeline,
 
   uniforms_state = &pipeline->big_state->uniforms_state;
 
-  find_data.previous_override = NULL;
-  find_data.found_override = NULL;
-  find_data.it = COGL_SLIST_FIRST (&uniforms_state->override_list);
-  find_data.location = location;
-
-  _cogl_bitmask_foreach (&uniforms_state->override_mask,
-                         find_uniform_override_cb,
-                         &find_data);
+  /* Count the number of bits that are set below this location. That
+     should give us the position where our new value should lie */
+  override_index = _cogl_bitmask_popcount_upto (&uniforms_state->override_mask,
+                                                location);
 
   _cogl_bitmask_set (&uniforms_state->changed_mask, location, TRUE);
 
   /* If this pipeline already has an override for this value then we
      can just use it directly */
-  if (find_data.found_override)
-    return &find_data.found_override->value;
+  if (_cogl_bitmask_get (&uniforms_state->override_mask, location))
+    return uniforms_state->override_values + override_index;
 
-  /* We need to add a new override */
-  override = g_slice_new (CoglPipelineUniformOverride);
-  _cogl_boxed_value_init (&override->value);
+  /* We need to create a new override value in the right position
+     within the array. This is pretty inefficient but the hope is that
+     it will be much more common to modify an existing uniform rather
+     than modify a new one so it is more important to optimise the
+     former case. */
 
-  if (find_data.previous_override)
-    COGL_SLIST_INSERT_AFTER (find_data.previous_override, override, list_node);
+  if (uniforms_state->override_values == NULL)
+    {
+      g_assert (override_index == 0);
+      uniforms_state->override_values = g_new (CoglBoxedValue, 1);
+    }
   else
-    COGL_SLIST_INSERT_HEAD (&uniforms_state->override_list,
-                            override,
-                            list_node);
+    {
+      /* We need to grow the array and copy in the old values */
+      CoglBoxedValue *old_values = uniforms_state->override_values;
+      int old_size = _cogl_bitmask_popcount (&uniforms_state->override_mask);
+
+      uniforms_state->override_values = g_new (CoglBoxedValue, old_size + 1);
+
+      /* Copy in the old values leaving a gap for the new value */
+      memcpy (uniforms_state->override_values,
+              old_values,
+              sizeof (CoglBoxedValue) * override_index);
+      memcpy (uniforms_state->override_values,
+              old_values + override_index + 1,
+              sizeof (CoglBoxedValue) * (old_size - override_index));
+
+      g_free (old_values);
+    }
+
+  _cogl_boxed_value_init (uniforms_state->override_values + override_index);
 
   _cogl_bitmask_set (&uniforms_state->override_mask, location, TRUE);
 
-  return &override->value;
+  return uniforms_state->override_values + override_index;
 }
 
 void
diff --git a/cogl/cogl-pipeline.c b/cogl/cogl-pipeline.c
index a2af621..1cd9317 100644
--- a/cogl/cogl-pipeline.c
+++ b/cogl/cogl-pipeline.c
@@ -224,7 +224,7 @@ _cogl_pipeline_init_default_pipeline (void)
 
   _cogl_bitmask_init (&uniforms_state->override_mask);
   _cogl_bitmask_init (&uniforms_state->changed_mask);
-  COGL_SLIST_INIT (&uniforms_state->override_list);
+  uniforms_state->override_values = NULL;
 
   ctx->default_pipeline = _cogl_pipeline_object_new (pipeline);
 }
@@ -467,16 +467,12 @@ _cogl_pipeline_free (CoglPipeline *pipeline)
     {
       CoglPipelineUniformsState *uniforms_state
         = &pipeline->big_state->uniforms_state;
-      CoglPipelineUniformOverride *override, *tmp;
+      int n_overrides = _cogl_bitmask_popcount (&uniforms_state->override_mask);
+      int i;
 
-      COGL_SLIST_FOREACH_SAFE (override,
-                               &uniforms_state->override_list,
-                               list_node,
-                               tmp)
-        {
-          _cogl_boxed_value_destroy (&override->value);
-          g_slice_free (CoglPipelineUniformOverride, override);
-        }
+      for (i = 0; i < n_overrides; i++)
+        _cogl_boxed_value_destroy (uniforms_state->override_values + i);
+      g_free (uniforms_state->override_values);
 
       _cogl_bitmask_destroy (&uniforms_state->override_mask);
       _cogl_bitmask_destroy (&uniforms_state->changed_mask);
@@ -953,27 +949,21 @@ _cogl_pipeline_copy_differences (CoglPipeline *dest,
 
   if (differences & COGL_PIPELINE_STATE_UNIFORMS)
     {
-      CoglPipelineUniformOverride *prev = NULL;
-      CoglPipelineUniformOverride *override;
+      int n_overrides =
+        _cogl_bitmask_popcount (&src->big_state->uniforms_state.override_mask);
+      int i;
 
-      COGL_SLIST_INIT (&big_state->uniforms_state.override_list);
+      big_state->uniforms_state.override_values =
+        g_malloc (n_overrides * sizeof (CoglBoxedValue));
 
-      COGL_SLIST_FOREACH (override,
-                          &src->big_state->uniforms_state.override_list,
-                          list_node)
+      for (i = 0; i < n_overrides; i++)
         {
-          CoglPipelineUniformOverride *new_override =
-            g_slice_new (CoglPipelineUniformOverride);
-          _cogl_boxed_value_copy (&new_override->value,
-                                  &override->value);
-          if (prev)
-            COGL_SLIST_INSERT_AFTER (prev, new_override, list_node);
-          else
-            COGL_SLIST_INSERT_HEAD (&big_state->uniforms_state.override_list,
-                                    new_override,
-                                    list_node);
-
-          prev = new_override;
+          CoglBoxedValue *dst_bv =
+            big_state->uniforms_state.override_values + i;
+          const CoglBoxedValue *src_bv =
+            src->big_state->uniforms_state.override_values + i;
+
+          _cogl_boxed_value_copy (dst_bv, src_bv);
         }
 
       _cogl_bitmask_init (&big_state->uniforms_state.override_mask);
@@ -1073,7 +1063,7 @@ _cogl_pipeline_init_multi_property_sparse_state (CoglPipeline *pipeline,
           &pipeline->big_state->uniforms_state;
         _cogl_bitmask_init (&uniforms_state->override_mask);
         _cogl_bitmask_init (&uniforms_state->changed_mask);
-        COGL_SLIST_INIT (&uniforms_state->override_list);
+        uniforms_state->override_values = NULL;
       }
     }
 }