Fix T78296: Performance - Use Binary Search for MDeformWeight

Use binary search for querying deform weights.

Spring 02_020_A.anim.blend on Ryzen 1700X goes from 12.4 to 12.7fps.

During profiling it was detected that adding new items to the head was faster than adding to the tail.

Reviewed By: Campbell Barton

Differential Revision: https://developer.blender.org/D8127

9 files changed, 134 insertions, 17 deletions

diff --git a/source/blender/blenkernel/BKE_blender_version.h b/source/blender/blenkernel/BKE_blender_version.h
index 57f22a8d709..556c1c961dc 100644
--- a/source/blender/blenkernel/BKE_blender_version.h
+++ b/source/blender/blenkernel/BKE_blender_version.h
@@ -40,7 +40,7 @@ extern "C" {
 
 /* Blender file format version. */
 #define BLENDER_FILE_VERSION BLENDER_VERSION
-#define BLENDER_FILE_SUBVERSION 6
+#define BLENDER_FILE_SUBVERSION 7
 
 /* Minimum Blender version that supports reading file written with the current
  * version. Older Blender versions will test this and show a warning if the file
diff --git a/source/blender/blenkernel/BKE_deform.h b/source/blender/blenkernel/BKE_deform.h
index 04b85aebb39..b5a7df9ff57 100644
--- a/source/blender/blenkernel/BKE_deform.h
+++ b/source/blender/blenkernel/BKE_deform.h
@@ -54,6 +54,7 @@ void BKE_object_defgroup_unique_name(struct bDeformGroup *dg, struct Object *ob)
 
 struct MDeformWeight *BKE_defvert_find_index(const struct MDeformVert *dv, const int defgroup);
 struct MDeformWeight *BKE_defvert_ensure_index(struct MDeformVert *dv, const int defgroup);
+void BKE_defvert_array_sort_weights(struct MDeformVert *dv, const int num_verts);
 void BKE_defvert_add_index_notest(struct MDeformVert *dv, int defgroup, const float weight);
 void BKE_defvert_remove_group(struct MDeformVert *dvert, struct MDeformWeight *dw);
 void BKE_defvert_clear(struct MDeformVert *dvert);
@@ -163,6 +164,16 @@ void BKE_defvert_extract_vgroup_to_polyweights(struct MDeformVert *dvert,
 
 void BKE_defvert_weight_to_rgb(float r_rgb[3], const float weight);
 
+#ifndef NDEBUG
+bool BKE_defvert_is_sorted_for_assert(const struct MDeformVert *dv);
+#  define BKE_DEFVERT_IS_SORTED_ASSERT(dv) BLI_assert(BKE_defvert_is_sorted_for_assert(dv))
+#else
+#  define BKE_DEFVERT_IS_SORTED_ASSERT(dv) \
+    if (false) { \
+      (void)(dv); \
+    }
+#endif
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/source/blender/blenkernel/intern/customdata.c b/source/blender/blenkernel/intern/customdata.c
index c11fa69db76..6843c4c58fa 100644
--- a/source/blender/blenkernel/intern/customdata.c
+++ b/source/blender/blenkernel/intern/customdata.c
@@ -47,6 +47,7 @@
 
 #include "BKE_customdata.h"
 #include "BKE_customdata_file.h"
+#include "BKE_deform.h"
 #include "BKE_main.h"
 #include "BKE_mesh_mapping.h"
 #include "BKE_mesh_remap.h"
@@ -320,6 +321,7 @@ static void layerInterp_mdeformvert(const void **sources,
       }
       dvert->dw[i] = node->dw;
     }
+    BKE_defvert_array_sort_weights(dvert, count);
   }
   else {
     memset(dvert, 0, sizeof(*dvert));
diff --git a/source/blender/blenkernel/intern/deform.c b/source/blender/blenkernel/intern/deform.c
index b97935d57f2..7e924db5ae4 100644
--- a/source/blender/blenkernel/intern/deform.c
+++ b/source/blender/blenkernel/intern/deform.c
@@ -216,6 +216,47 @@ void BKE_defvert_sync(MDeformVert *dvert_dst, const MDeformVert *dvert_src, cons
   }
 }
 
+/* -------------------------------------------------------------------- */
+/** \name Deform Weights - Sorting
+ *
+ * \{ */
+
+/* Reorder the weights so they are sorted. It is required that all `MDeformVert` weights are sorted
+ * so we can use binary search.
+ */
+static int defweight_cmp(const void *a, const void *b)
+{
+  const MDeformWeight *dw1 = a;
+  const MDeformWeight *dw2 = b;
+  if (dw1->def_nr < dw2->def_nr) {
+    return -1;
+  }
+  else if (dw1->def_nr > dw2->def_nr) {
+    return 1;
+  }
+  else {
+    return 0;
+  }
+}
+
+static void defvert_sort_weights(struct MDeformVert *dvert)
+{
+  if (dvert->dw) {
+    qsort(dvert->dw, dvert->totweight, sizeof(MDeformWeight), defweight_cmp);
+  }
+}
+
+void BKE_defvert_array_sort_weights(struct MDeformVert *dvert, const int num_verts)
+{
+  if (!dvert) {
+    return;
+  }
+  for (int i = 0; i < num_verts; i++) {
+    defvert_sort_weights(&dvert[i]);
+  }
+}
+/* \} */
+
 /**
  * be sure all flip_map values are valid
  */
@@ -260,6 +301,7 @@ void BKE_defvert_remap(MDeformVert *dvert, int *map, const int map_len)
       dw->def_nr = map[dw->def_nr];
     }
   }
+  defvert_sort_weights(dvert);
 }
 
 /**
@@ -459,6 +501,7 @@ void BKE_defvert_flip(MDeformVert *dvert, const int *flip_map, const int flip_ma
       }
     }
   }
+  defvert_sort_weights(dvert);
 }
 
 void BKE_defvert_flip_merged(MDeformVert *dvert, const int *flip_map, const int flip_map_len)
@@ -665,23 +708,40 @@ float BKE_defvert_array_find_weight_safe(const struct MDeformVert *dvert,
   return BKE_defvert_find_weight(dvert + index, defgroup);
 }
 
+static int defvert_index_get(const MDeformVert *dvert, const int defgroup)
+{
+  int low = 0;
+  int high = dvert->totweight - 1;
+  int mid;
+  while (low < high) {
+    mid = (low + high) / 2;
+    MDeformWeight *dweight = &dvert->dw[mid];
+    const unsigned int dweight_def_nr = dweight->def_nr;
+    if (dweight_def_nr == defgroup) {
+      return mid;
+    }
+    if (dweight_def_nr < defgroup) {
+      low = mid + 1;
+    }
+    else {
+      high = mid - 1;
+    }
+  }
+  return -1;
+}
+
 MDeformWeight *BKE_defvert_find_index(const MDeformVert *dvert, const int defgroup)
 {
-  if (dvert && defgroup >= 0) {
-    MDeformWeight *dw = dvert->dw;
-    unsigned int i;
+  BLI_assert(dvert);
+  BLI_assert(defgroup >= 0);
 
-    for (i = dvert->totweight; i != 0; i--, dw++) {
-      if (dw->def_nr == defgroup) {
-        return dw;
-      }
-    }
+  int index = defvert_index_get(dvert, defgroup);
+  if (index == -1) {
+    return NULL;
   }
   else {
-    BLI_assert(0);
+    return &dvert->dw[index];
   }
-
-  return NULL;
 }
 
 /**
@@ -706,17 +766,18 @@ MDeformWeight *BKE_defvert_ensure_index(MDeformVert *dvert, const int defgroup)
 
   dw_new = MEM_mallocN(sizeof(MDeformWeight) * (dvert->totweight + 1), "deformWeight");
   if (dvert->dw) {
-    memcpy(dw_new, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
+    memcpy(dw_new + 1, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
     MEM_freeN(dvert->dw);
   }
   dvert->dw = dw_new;
-  dw_new += dvert->totweight;
   dw_new->weight = 0.0f;
   dw_new->def_nr = defgroup;
   /* Group index */
 
   dvert->totweight++;
 
+  defvert_sort_weights(dvert);
+
   return dw_new;
 }
 
@@ -740,14 +801,15 @@ void BKE_defvert_add_index_notest(MDeformVert *dvert, int defgroup, const float
   dw_new = MEM_callocN(sizeof(MDeformWeight) * (dvert->totweight + 1),
                        "defvert_add_to group, new deformWeight");
   if (dvert->dw) {
-    memcpy(dw_new, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
+    memcpy(dw_new + 1, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
     MEM_freeN(dvert->dw);
   }
   dvert->dw = dw_new;
-  dw_new += dvert->totweight;
   dw_new->weight = weight;
   dw_new->def_nr = defgroup;
   dvert->totweight++;
+
+  defvert_sort_weights(dvert);
 }
 
 /**
@@ -773,7 +835,7 @@ void BKE_defvert_remove_group(MDeformVert *dvert, MDeformWeight *dw)
       BLI_assert(dvert->dw != NULL);
 
       if (i != dvert->totweight) {
-        dvert->dw[i] = dvert->dw[dvert->totweight];
+        memmove(&dvert->dw[i], &dvert->dw[i + 1], sizeof(MDeformWeight) * dvert->totweight - i);
       }
 
       dvert->dw = MEM_reallocN(dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
@@ -1525,4 +1587,17 @@ void BKE_defvert_weight_to_rgb(float r_rgb[3], const float weight)
   }
 }
 
+#ifndef NDEBUG
+bool BKE_defvert_is_sorted_for_assert(const MDeformVert *dv)
+{
+  const MDeformWeight *dw = dv->dw;
+  for (int i = 1; i < dv->totweight; i++) {
+    if (dw[i - 1].def_nr > dw[i].def_nr) {
+      return false;
+    }
+  }
+  return true;
+}
+#endif
+
 /** \} */
diff --git a/source/blender/blenkernel/intern/object_deform.c b/source/blender/blenkernel/intern/object_deform.c
index 6ca1442497a..f7d22f300ef 100644
--- a/source/blender/blenkernel/intern/object_deform.c
+++ b/source/blender/blenkernel/intern/object_deform.c
@@ -534,6 +534,7 @@ void BKE_object_defgroup_index_map_apply(MDeformVert *dvert,
       dv->totweight = totweight;
     }
   }
+  BKE_defvert_array_sort_weights(dv, dvert_len);
 }
 
 /**
diff --git a/source/blender/blenloader/intern/versioning_290.c b/source/blender/blenloader/intern/versioning_290.c
index 0d16b58d28f..a99da5eb333 100644
--- a/source/blender/blenloader/intern/versioning_290.c
+++ b/source/blender/blenloader/intern/versioning_290.c
@@ -27,6 +27,9 @@
 #include "DNA_constraint_types.h"
 #include "DNA_genfile.h"
 #include "DNA_gpencil_modifier_types.h"
+#include "DNA_gpencil_types.h"
+#include "DNA_lattice_types.h"
+#include "DNA_mesh_types.h"
 #include "DNA_modifier_types.h"
 #include "DNA_object_types.h"
 #include "DNA_screen_types.h"
@@ -34,6 +37,7 @@
 
 #include "BKE_collection.h"
 #include "BKE_colortools.h"
+#include "BKE_deform.h"
 #include "BKE_lib_id.h"
 #include "BKE_main.h"
 
@@ -354,6 +358,26 @@ void blo_do_versions_290(FileData *fd, Library *UNUSED(lib), Main *bmain)
     }
   }
 
+  /* Make sure that all weights of MDeformVert are sorted. */
+  if (!MAIN_VERSION_ATLEAST(bmain, 290, 7)) {
+    for (Mesh *mesh = bmain->meshes.first; mesh != NULL; mesh = mesh->id.next) {
+      BKE_defvert_array_sort_weights(mesh->dvert, mesh->totvert);
+    }
+    for (Lattice *lt = bmain->lattices.first; lt != NULL; lt = lt->id.next) {
+      const int totvert = lt->pntsu * lt->pntsv * lt->pntsw;
+      BKE_defvert_array_sort_weights(lt->dvert, totvert);
+    }
+    for (bGPdata *gp = bmain->gpencils.first; gp != NULL; gp = gp->id.next) {
+      LISTBASE_FOREACH (bGPDlayer *, layer, &gp->layers) {
+        LISTBASE_FOREACH (bGPDframe *, frame, &layer->frames) {
+          LISTBASE_FOREACH (bGPDstroke *, stroke, &frame->strokes) {
+            BKE_defvert_array_sort_weights(stroke->dvert, stroke->totpoints);
+          }
+        }
+      }
+    }
+  }
+
   /**
    * Versioning code until next subversion bump goes here.
    *
diff --git a/source/blender/blenloader/intern/writefile.c b/source/blender/blenloader/intern/writefile.c
index 4e2b4fef9a0..29461298cea 100644
--- a/source/blender/blenloader/intern/writefile.c
+++ b/source/blender/blenloader/intern/writefile.c
@@ -159,6 +159,7 @@
 #include "BKE_constraint.h"
 #include "BKE_curve.h"
 #include "BKE_curveprofile.h"
+#include "BKE_deform.h"
 #include "BKE_fcurve.h"
 #include "BKE_fcurve_driver.h"
 #include "BKE_global.h"  // for G
@@ -2044,6 +2045,7 @@ static void write_dverts(BlendWriter *writer, int count, MDeformVert *dvlist)
     /* Write deformation data for each dvert */
     for (int i = 0; i < count; i++) {
       if (dvlist[i].dw) {
+        BKE_DEFVERT_IS_SORTED_ASSERT(&dvlist[i]);
         BLO_write_struct_array(writer, MDeformWeight, dvlist[i].totweight, dvlist[i].dw);
       }
     }
diff --git a/source/blender/editors/gpencil/gpencil_data.c b/source/blender/editors/gpencil/gpencil_data.c
index 96b0296a7de..9fd74ef2c46 100644
--- a/source/blender/editors/gpencil/gpencil_data.c
+++ b/source/blender/editors/gpencil/gpencil_data.c
@@ -2642,6 +2642,7 @@ int ED_gpencil_join_objects_exec(bContext *C, wmOperator *op)
                     dvert->dw->def_nr = idx;
                   }
                 }
+                BKE_defvert_array_sort_weights(gps->dvert, gps->totpoints);
               }
             }
           }
diff --git a/source/blender/makesdna/DNA_meshdata_types.h b/source/blender/makesdna/DNA_meshdata_types.h
index cc2ba3fb999..a4299d3c6a2 100644
--- a/source/blender/makesdna/DNA_meshdata_types.h
+++ b/source/blender/makesdna/DNA_meshdata_types.h
@@ -286,6 +286,7 @@ typedef struct MDeformWeight {
 } MDeformWeight;
 
 typedef struct MDeformVert {
+  /* Mut be sorted by def_nr due to binary search. */
   struct MDeformWeight *dw;
   int totweight;
   /** Flag is only in use as a run-time tag at the moment. */