[Bf-blender-cvs] [441a440] master: readfile: optimization for undo
Campbell Barton
noreply at git.blender.org
Tue Jun 7 09:26:09 CEST 2016
Commit: 441a440cbbb700511d6d1ec01e2f149355adcc02
Author: Campbell Barton
Date: Tue Jun 7 16:07:13 2016 +1000
Branches: master
https://developer.blender.org/rB441a440cbbb700511d6d1ec01e2f149355adcc02
readfile: optimization for undo
Was using O(n^2) lookup on ID's with undo.
This caused undo to hang with 1000's of data-blocks
(especially with heavy scenes & outliner-space, which doesn't even need to be visible to cause a slow-down).
Internally this uses a ghash per id-type, which is lazy-initialized.
Each key uses the name and library since there may be name collisions between libraries.
Developer Notes:
- Adds small `BKE_main_idmap_*` API.
- Needed to change linking order for this to build.
===================================================================
M build_files/cmake/macros.cmake
A source/blender/blenkernel/BKE_library_idmap.h
M source/blender/blenkernel/CMakeLists.txt
A source/blender/blenkernel/intern/library_idmap.c
M source/blender/blenloader/intern/readfile.c
===================================================================
diff --git a/build_files/cmake/macros.cmake b/build_files/cmake/macros.cmake
index d34b55e..3aa938b 100644
--- a/build_files/cmake/macros.cmake
+++ b/build_files/cmake/macros.cmake
@@ -552,11 +552,11 @@ function(SETUP_BLENDER_SORTED_LIBS)
bf_modifiers
bf_bmesh
bf_gpu
+ bf_blenloader
bf_blenkernel
bf_physics
bf_nodes
bf_rna
- bf_blenloader
bf_imbuf
bf_blenlib
bf_depsgraph
diff --git a/source/blender/blenkernel/BKE_library_idmap.h b/source/blender/blenkernel/BKE_library_idmap.h
new file mode 100644
index 0000000..971586e
--- /dev/null
+++ b/source/blender/blenkernel/BKE_library_idmap.h
@@ -0,0 +1,50 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#ifndef __BKE_LIBRARY_IDMAP_H__
+#define __BKE_LIBRARY_IDMAP_H__
+
+/** \file BKE_library_idmap.h
+ * \ingroup bke
+ */
+
+#include "BLI_compiler_attrs.h"
+
+struct ID;
+struct Main;
+struct IDNameLib_Map;
+
+struct IDNameLib_Map *BKE_main_idmap_create(
+ struct Main *bmain)
+ ATTR_WARN_UNUSED_RESULT ATTR_NONNULL();
+void BKE_main_idmap_destroy(
+ struct IDNameLib_Map *id_typemap)
+ ATTR_NONNULL();
+struct Main *BKE_main_idmap_main_get(
+ struct IDNameLib_Map *id_typemap)
+ ATTR_WARN_UNUSED_RESULT ATTR_NONNULL();
+struct ID *BKE_main_idmap_lookup(
+ struct IDNameLib_Map *id_typemap,
+ short id_type, const char *name, const struct Library *lib)
+ ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 3);
+struct ID *BKE_main_idmap_lookup_id(
+ struct IDNameLib_Map *id_typemap, const struct ID *id)
+ ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2);
+
+#endif /* __BKE_LIBRARY_IDMAP_H__ */
diff --git a/source/blender/blenkernel/CMakeLists.txt b/source/blender/blenkernel/CMakeLists.txt
index afab0cc..8626422 100644
--- a/source/blender/blenkernel/CMakeLists.txt
+++ b/source/blender/blenkernel/CMakeLists.txt
@@ -121,6 +121,7 @@ set(SRC
intern/lamp.c
intern/lattice.c
intern/library.c
+ intern/library_idmap.c
intern/library_query.c
intern/linestyle.c
intern/mask.c
@@ -244,6 +245,7 @@ set(SRC
BKE_lamp.h
BKE_lattice.h
BKE_library.h
+ BKE_library_idmap.h
BKE_library_query.h
BKE_linestyle.h
BKE_main.h
diff --git a/source/blender/blenkernel/intern/library_idmap.c b/source/blender/blenkernel/intern/library_idmap.c
new file mode 100644
index 0000000..fd78d9b
--- /dev/null
+++ b/source/blender/blenkernel/intern/library_idmap.c
@@ -0,0 +1,174 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#include <string.h>
+#include <stdlib.h>
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_utildefines.h"
+#include "BLI_ghash.h"
+#include "BLI_listbase.h"
+
+#include "DNA_ID.h"
+
+#include "BKE_idcode.h"
+#include "BKE_library.h"
+#include "BKE_library_idmap.h" /* own include */
+
+/** \file blender/blenkernel/intern/library_map.c
+ * \ingroup bke
+ *
+ * Utility functions for faster ID lookups.
+ */
+
+/** \name BKE_main_idmap API
+ *
+ * Cache ID (name, library lookups).
+ * This doesn't account for adding/removing data-blocks,
+ * and should only be used when performing many lookups.
+ *
+ * \note GHash's are initialized on demand,
+ * since its likely some types will never have lookups run on them,
+ * so its a waste to create and never use.
+ * \{ */
+
+struct IDNameLib_Key {
+ /** ``ID.name + 2``: without the ID type prefix, since each id type gets it's own 'map' */
+ const char *name;
+ /** ``ID.lib``: */
+ const Library *lib;
+};
+
+struct IDNameLib_TypeMap {
+ GHash *map;
+ short id_type;
+ /* only for storage of keys in the ghash, avoid many single allocs */
+ struct IDNameLib_Key *keys;
+};
+
+/**
+ * Opaque structure, external API users only see this.
+ */
+struct IDNameLib_Map {
+ struct IDNameLib_TypeMap type_maps[MAX_LIBARRAY];
+ struct Main *bmain;
+};
+
+static struct IDNameLib_TypeMap *main_idmap_from_idcode(struct IDNameLib_Map *id_map, short id_type)
+{
+ for (int i = 0; i < MAX_LIBARRAY; i++) {
+ if (id_map->type_maps[i].id_type == id_type) {
+ return &id_map->type_maps[i];
+ }
+ }
+ return NULL;
+}
+
+struct IDNameLib_Map *BKE_main_idmap_create(struct Main *bmain)
+{
+ struct IDNameLib_Map *id_map = MEM_mallocN(sizeof(*id_map), __func__);
+
+ int index = 0;
+ while (index < MAX_LIBARRAY) {
+ id_map->type_maps[index].map = NULL;
+ id_map->type_maps[index].id_type = BKE_idcode_iter_step(&index);
+ }
+ BLI_assert(index == MAX_LIBARRAY);
+
+ id_map->bmain = bmain;
+
+ return id_map;
+}
+
+struct Main *BKE_main_idmap_main_get(struct IDNameLib_Map *id_map)
+{
+ return id_map->bmain;
+}
+
+static unsigned int idkey_hash(const void *ptr)
+{
+ const struct IDNameLib_Key *idkey = ptr;
+ unsigned int key = BLI_ghashutil_strhash(idkey->name);
+ if (idkey->lib) {
+ key ^= BLI_ghashutil_ptrhash(idkey->lib);
+ }
+ return key;
+}
+
+static bool idkey_cmp(const void *a, const void *b)
+{
+ const struct IDNameLib_Key *idkey_a = a;
+ const struct IDNameLib_Key *idkey_b = b;
+ return strcmp(idkey_a->name, idkey_b->name) || (idkey_a->lib != idkey_b->lib);
+}
+
+ID *BKE_main_idmap_lookup(struct IDNameLib_Map *id_map, short id_type, const char *name, const Library *lib)
+{
+ struct IDNameLib_TypeMap *type_map = main_idmap_from_idcode(id_map, id_type);
+
+ if (UNLIKELY(type_map == NULL)) {
+ return NULL;
+ }
+
+ /* lazy init */
+ if (type_map->map == NULL) {
+ ListBase *lb = which_libbase(id_map->bmain, id_type);
+ const int lb_len = BLI_listbase_count(lb);
+ if (lb_len == 0) {
+ return NULL;
+ }
+ type_map->map = BLI_ghash_new_ex(idkey_hash, idkey_cmp, __func__, lb_len);
+ type_map->keys = MEM_mallocN(sizeof(struct IDNameLib_Key) * lb_len, __func__);
+
+ GHash *map = type_map->map;
+ struct IDNameLib_Key *key = type_map->keys;
+
+ for (ID *id = lb->first; id; id = id->next, key++) {
+ key->name = id->name + 2;
+ key->lib = id->lib;
+ BLI_ghash_insert(map, key, id);
+ }
+ }
+
+ const struct IDNameLib_Key key_lookup = {name, lib};
+ return BLI_ghash_lookup(type_map->map, &key_lookup);
+}
+
+ID *BKE_main_idmap_lookup_id(struct IDNameLib_Map *id_map, const ID *id)
+{
+ return BKE_main_idmap_lookup(id_map, GS(id->name), id->name + 2, id->lib);
+}
+
+void BKE_main_idmap_destroy(struct IDNameLib_Map *id_map)
+{
+ struct IDNameLib_TypeMap *type_map = id_map->type_maps;
+ for (int i = 0; i < MAX_LIBARRAY; i++, type_map++) {
+ if (type_map->map) {
+ BLI_ghash_free(type_map->map, NULL, NULL);
+ type_map->map = NULL;
+ MEM_freeN(type_map->keys);
+ }
+ }
+
+ MEM_freeN(id_map);
+}
+
+/** \} */
diff --git a/source/blender/blenloader/intern/readfile.c b/source/blender/blenloader/intern/readfile.c
index fd105f6..621088c 100644
--- a/source/blender/blenloader/intern/readfile.c
+++ b/source/blender/blenloader/intern/readfile.c
@@ -124,6 +124,7 @@
#include "BKE_global.h" // for G
#include "BKE_group.h"
#include "BKE_library.h" // for which_libbase
+#include "BKE_library_idmap.h"
#include "BKE_library_query.h"
#include "BKE_idcode.h"
#include "BKE_material.h"
@@ -211,6 +212,9 @@
/* use GHash for BHead name-based lookups (speeds up linking) */
#define USE_GHASH_BHEAD
+/* Use GHash for restoring pointers by name */
+#define USE_GHASH_RESTORE_POINTER
+
/***/
typedef struct OldNew {
@@ -6389,68 +6393,96 @@ typedef enum ePointerUserMode {
USER_REAL = 1, /* ensure at least one real user (fake user ignored) */
} ePointerUserMode;
-static bool restore_pointer(ID *id, ID *newid, ePointerUserMode user)
+static void restore_pointer_user(ID *id, ID *newid, ePointerUserMode user)
{
- if (STREQ(newid->name + 2, id->name + 2)) {
- if (newid->lib == id->lib) {
- if (user == USER_REAL) {
- id_us_ensure_real(newid);
+ BLI_assert(STREQ(newid->name + 2, id->name + 2));
+ BLI_assert(newid->lib == id->lib);
+ UNUSED_VARS_NDEBUG(id);
+
+ if (user == USER_REAL) {
+ id_us_ensure_real(newid);
+ }
+}
+
+#ifndef USE_GHASH_RESTORE_POINTER
+/**
+ * A version of #restore_pointer_by_name that performs a full search (slow!).
+ * Use only for limited lookups, when the overhead of
+ * creating a #IDNameLib_Map for a single lookup isn't worthwhile.
+ */
+static void *restore_pointer_by_name_main(Main *mainp, ID *id, ePointerUserMode user)
+{
+ if (id) {
+ ListBase *lb = which_libbase(mainp, GS(id->name));
+ if (lb) { /* there's still risk of checking corrupt mem (freed Ids in oops) */
+ ID *idn = lb->first;
+ for (; idn; idn = idn->next) {
+ if (STREQ(idn->name + 2, id->name + 2)) {
+ if (idn->lib == id->lib) {
+ restore_pointer_user(id, idn, user);
+ break;
+ }
+ }
}
- return true;
+ return idn;
}
}
- return false;
+ return NULL;
}
+#endif
/**
* Only for undo files, or to restore a screen after reading without UI...
*
- * us
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list