Undo: resolve inefficient edit-mesh memory use with multiple objects

When editing more than 1 object at a time, complete copies of each mesh
were being stored. Now the most recent undo-data for each mesh is used
(when available).

source/blender/editors/mesh/editmesh_undo.c

@@ -520,11 +520,63 @@ static void um_arraystore_free(UndoMesh *um)
 
 /** \} */
 
+/* -------------------------------------------------------------------- */
+/** \name Array Store Utilities
+ * \{ */
+
+/**
+ * Create an array of #UndoMesh from `objects`.
+ *
+ * where each element in the resulting array is the most recently created
+ * undo-mesh for the object's mesh.
+ * When no undo-mesh can be found that array index is NULL.
+ *
+ * This is used for de-duplicating memory between undo steps,
+ * failure to find the undo step will store a full duplicate in memory.
+ * define `DEBUG_PRINT` to check memory is de-duplicating as expected.
+ */
+static UndoMesh **mesh_undostep_reference_elems_from_objects(Object **object, int object_len)
+{
+  /* Map: `Mesh.id.session_uuid` -> `UndoMesh`. */
+  GHash *uuid_map = BLI_ghash_ptr_new_ex(__func__, object_len);
+  UndoMesh **um_references = MEM_callocN(sizeof(UndoMesh *) * object_len, __func__);
+  for (int i = 0; i < object_len; i++) {
+    const Mesh *me = object[i]->data;
+    BLI_ghash_insert(uuid_map, POINTER_FROM_INT(me->id.session_uuid), &um_references[i]);
+  }
+  int uuid_map_len = object_len;
+
+  /* Loop backwards over all previous mesh undo data until either:
+   * - All elements have been found (where `um_references` we'll have every element set).
+   * - There are no undo steps left to look for. */
+  LinkData *link = um_arraystore.local_links.last;
+  while (link && uuid_map_len != 0) {
+    UndoMesh *um_iter = link->data, **um_p;
+    if ((um_p = BLI_ghash_popkey(uuid_map, POINTER_FROM_INT(um_iter->me.id.session_uuid), NULL))) {
+      *um_p = um_iter;
+      uuid_map_len--;
+    }
+    link = link->prev;
+  }
+  BLI_assert(uuid_map_len == BLI_ghash_len(uuid_map));
+  BLI_ghash_free(uuid_map, NULL, NULL);
+  if (uuid_map_len == object_len) {
+    MEM_freeN(um_references);
+    um_references = NULL;
+  }
+  return um_references;
+}
+
+/** \} */
+
 #endif /* USE_ARRAY_STORE */
 
 /* for callbacks */
 /* undo simply makes copies of a bmesh */
-static void *undomesh_from_editmesh(UndoMesh *um, BMEditMesh *em, Key *key)
+/**
+ * \param um_ref: The reference to use for de-duplicating memory between undo-steps.
+ */
+static void *undomesh_from_editmesh(UndoMesh *um, BMEditMesh *em, Key *key, UndoMesh *um_ref)
 {
   BLI_assert(BLI_array_is_zeroed(um, 1));
 #ifdef USE_ARRAY_STORE_THREAD
@@ -560,12 +612,6 @@ static void *undomesh_from_editmesh(UndoMesh *um, BMEditMesh *em, Key *key)
 
 #ifdef USE_ARRAY_STORE
   {
-    /* We could be more clever here,
-     * the previous undo state may be from a separate mesh. */
-    const UndoMesh *um_ref = um_arraystore.local_links.last ?
-                                 ((LinkData *)um_arraystore.local_links.last)->data :
-                                 NULL;
-
     /* Add ourselves. */
     BLI_addtail(&um_arraystore.local_links, BLI_genericNodeN(um));
 
@@ -583,6 +629,8 @@ static void *undomesh_from_editmesh(UndoMesh *um, BMEditMesh *em, Key *key)
     um_arraystore_compact_with_info(um, um_ref);
 #  endif
   }
+#else
+  UNUSED_VARS(um_ref);
 #endif
 
   return um;
@@ -749,6 +797,12 @@ static bool mesh_undosys_step_encode(struct bContext *C, struct Main *bmain, Und
   us->elems = MEM_callocN(sizeof(*us->elems) * objects_len, __func__);
   us->elems_len = objects_len;
 
+  UndoMesh **um_references = NULL;
+
+#ifdef USE_ARRAY_STORE
+  um_references = mesh_undostep_reference_elems_from_objects(objects, objects_len);
+#endif
+
   for (uint i = 0; i < objects_len; i++) {
     Object *ob = objects[i];
     MeshUndoStep_Elem *elem = &us->elems[i];
@@ -756,12 +810,22 @@ static bool mesh_undosys_step_encode(struct bContext *C, struct Main *bmain, Und
     elem->obedit_ref.ptr = ob;
     Mesh *me = elem->obedit_ref.ptr->data;
     BMEditMesh *em = me->edit_mesh;
-    undomesh_from_editmesh(&elem->data, me->edit_mesh, me->key);
+    undomesh_from_editmesh(
+        &elem->data, me->edit_mesh, me->key, um_references ? um_references[i] : NULL);
     em->needs_flush_to_id = 1;
     us->step.data_size += elem->data.undo_size;
+
+#ifdef USE_ARRAY_STORE
+    /** As this is only data storage it is safe to set the session ID here. */
+    elem->data.me.id.session_uuid = me->id.session_uuid;
+#endif
   }
   MEM_freeN(objects);
 
+  if (um_references != NULL) {
+    MEM_freeN(um_references);
+  }
+
   bmain->is_memfile_undo_flush_needed = true;
 
   return true;