[Bf-blender-cvs] [0b3183d] master: writefile: remove SDNA last-hit, optimize DNA reconstruct
Campbell Barton
noreply at git.blender.org
Tue Jul 12 05:00:25 CEST 2016
Commit: 0b3183d13cdbdcb06317fd1dd9b04ccd93a767c1
Author: Campbell Barton
Date: Tue Jul 12 11:48:04 2016 +1000
Branches: master
https://developer.blender.org/rB0b3183d13cdbdcb06317fd1dd9b04ccd93a767c1
writefile: remove SDNA last-hit, optimize DNA reconstruct
- Move last-hit index out of SDNA struct
(allows for access by multiple threads).
- Replace O(n^2) search with hash lookup in DNA reconstruction.
===================================================================
M source/blender/blenloader/intern/readfile.c
M source/blender/makesdna/DNA_genfile.h
M source/blender/makesdna/DNA_sdna_types.h
M source/blender/makesdna/intern/dna_genfile.c
===================================================================
diff --git a/source/blender/blenloader/intern/readfile.c b/source/blender/blenloader/intern/readfile.c
index 68cc060..27a119a 100644
--- a/source/blender/blenloader/intern/readfile.c
+++ b/source/blender/blenloader/intern/readfile.c
@@ -1844,7 +1844,7 @@ void blo_add_library_pointer_map(ListBase *old_mainlist, FileData *fd)
/* ********** END OLD POINTERS ****************** */
/* ********** READ FILE ****************** */
-static void switch_endian_structs(struct SDNA *filesdna, BHead *bhead)
+static void switch_endian_structs(const struct SDNA *filesdna, BHead *bhead)
{
int blocksize, nblocks;
char *data;
diff --git a/source/blender/makesdna/DNA_genfile.h b/source/blender/makesdna/DNA_genfile.h
index 77877f7..1b558b1 100644
--- a/source/blender/makesdna/DNA_genfile.h
+++ b/source/blender/makesdna/DNA_genfile.h
@@ -79,10 +79,13 @@ struct SDNA *DNA_sdna_from_data(
bool do_endian_swap, bool data_alloc);
void DNA_sdna_free(struct SDNA *sdna);
-int DNA_struct_find_nr(struct SDNA *sdna, const char *str);
-void DNA_struct_switch_endian(struct SDNA *oldsdna, int oldSDNAnr, char *data);
-char *DNA_struct_get_compareflags(struct SDNA *sdna, struct SDNA *newsdna);
-void *DNA_struct_reconstruct(struct SDNA *newsdna, struct SDNA *oldsdna, char *compflags, int oldSDNAnr, int blocks, void *data);
+int DNA_struct_find_nr_ex(const struct SDNA *sdna, const char *str, unsigned int *index_last);
+int DNA_struct_find_nr(const struct SDNA *sdna, const char *str);
+void DNA_struct_switch_endian(const struct SDNA *oldsdna, int oldSDNAnr, char *data);
+char *DNA_struct_get_compareflags(const struct SDNA *sdna, const struct SDNA*newsdna);
+void *DNA_struct_reconstruct(
+ const struct SDNA *newsdna, const struct SDNA *oldsdna,
+ char *compflags, int oldSDNAnr, int blocks, void *data);
int DNA_elem_array_size(const char *str);
int DNA_elem_offset(struct SDNA *sdna, const char *stype, const char *vartype, const char *name);
diff --git a/source/blender/makesdna/DNA_sdna_types.h b/source/blender/makesdna/DNA_sdna_types.h
index 791aca7..26ea5cd 100644
--- a/source/blender/makesdna/DNA_sdna_types.h
+++ b/source/blender/makesdna/DNA_sdna_types.h
@@ -35,12 +35,12 @@
#
#
typedef struct SDNA {
- const char *data; /* full copy of 'encoded' data */
+ const char *data; /* full copy of 'encoded' data (when data_alloc is set, otherwise borrowed). */
int datalen; /* length of data */
bool data_alloc;
int nr_names; /* total number of struct members */
- const char **names; /* struct member names */
+ const char **names; /* struct member names */
int pointerlen; /* size of a pointer in bytes */
@@ -57,11 +57,6 @@ typedef struct SDNA {
struct GHash *structs_map; /* ghash for faster lookups,
* requires WITH_DNA_GHASH to be used for now */
-
- /* wrong place for this really, its a simple
- * cache for findstruct_nr.
- */
- int lastfind;
} SDNA;
#
diff --git a/source/blender/makesdna/intern/dna_genfile.c b/source/blender/makesdna/intern/dna_genfile.c
index 9135d7b..1d9e971 100644
--- a/source/blender/makesdna/intern/dna_genfile.c
+++ b/source/blender/makesdna/intern/dna_genfile.c
@@ -39,6 +39,7 @@
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
+#include <limits.h>
#include "MEM_guardedalloc.h" // for MEM_freeN MEM_mallocN MEM_callocN
@@ -280,37 +281,16 @@ static void printstruct(SDNA *sdna, short strnr)
#endif
/**
- * Returns a pointer to the start of the struct info for the struct with the specified name.
- */
-static short *findstruct_name(SDNA *sdna, const char *str)
-{
- int a;
- short *sp = NULL;
-
-
- for (a = 0; a < sdna->nr_structs; a++) {
-
- sp = sdna->structs[a];
-
- if (strcmp(sdna->types[sp[0]], str) == 0) {
- return sp;
- }
- }
-
- return NULL;
-}
-
-/**
* Returns the index of the struct info for the struct with the specified name.
*/
-int DNA_struct_find_nr(SDNA *sdna, const char *str)
+int DNA_struct_find_nr_ex(const SDNA *sdna, const char *str, unsigned int *index_last)
{
const short *sp = NULL;
- if (sdna->lastfind < sdna->nr_structs) {
- sp = sdna->structs[sdna->lastfind];
+ if (*index_last < sdna->nr_structs) {
+ sp = sdna->structs[*index_last];
if (strcmp(sdna->types[sp[0]], str) == 0) {
- return sdna->lastfind;
+ return *index_last;
}
}
@@ -323,7 +303,7 @@ int DNA_struct_find_nr(SDNA *sdna, const char *str)
if (index_p) {
a = GET_INT_FROM_POINTER(*index_p);
- sdna->lastfind = a;
+ *index_last = a;
}
else {
a = -1;
@@ -339,7 +319,7 @@ int DNA_struct_find_nr(SDNA *sdna, const char *str)
sp = sdna->structs[a];
if (strcmp(sdna->types[sp[0]], str) == 0) {
- sdna->lastfind = a;
+ *index_last = a;
return a;
}
}
@@ -348,6 +328,12 @@ int DNA_struct_find_nr(SDNA *sdna, const char *str)
#endif
}
+int DNA_struct_find_nr(const SDNA *sdna, const char *str)
+{
+ unsigned int index_last_dummy = UINT_MAX;
+ return DNA_struct_find_nr_ex(sdna, str, &index_last_dummy);
+}
+
/* ************************* END DIV ********************** */
/* ************************* READ DNA ********************** */
@@ -358,16 +344,21 @@ int DNA_struct_find_nr(SDNA *sdna, const char *str)
static void init_structDNA(SDNA *sdna, bool do_endian_swap)
{
int *data, *verg, gravity_fix = -1;
- intptr_t nr;
short *sp;
- char str[8], *cp;
+ char str[8];
verg = (int *)str;
data = (int *)sdna->data;
strcpy(str, "SDNA");
- if (*data == *verg) {
-
+ if (*data != *verg) {
+ printf("SDNA error in SDNA file\n");
+ return;
+ }
+ else {
+ intptr_t nr;
+ char *cp;
+
data++;
/* load names array */
@@ -515,37 +506,52 @@ static void init_structDNA(SDNA *sdna, bool do_endian_swap)
nr++;
}
+ }
- /* finally pointerlen: use struct ListBase to test it, never change the size of it! */
- sp = findstruct_name(sdna, "ListBase");
- /* weird; i have no memory of that... I think I used sizeof(void *) before... (ton) */
-
- sdna->pointerlen = sdna->typelens[sp[0]] / 2;
-
- if (sp[1] != 2 || (sdna->pointerlen != 4 && sdna->pointerlen != 8)) {
- printf("ListBase struct error! Needs it to calculate pointerize.\n");
- exit(1);
- /* well, at least sizeof(ListBase) is error proof! (ton) */
- }
-
+ {
/* second part of gravity problem, setting "gravity" type to void */
if (gravity_fix > -1) {
- for (nr = 0; nr < sdna->nr_structs; nr++) {
+ for (intptr_t nr = 0; nr < sdna->nr_structs; nr++) {
sp = sdna->structs[nr];
if (strcmp(sdna->types[sp[0]], "ClothSimSettings") == 0)
sp[10] = SDNA_TYPE_VOID;
}
}
+ }
#ifdef WITH_DNA_GHASH
+ {
/* create a ghash lookup to speed up */
sdna->structs_map = BLI_ghash_str_new_ex("init_structDNA gh", sdna->nr_structs);
- for (nr = 0; nr < sdna->nr_structs; nr++) {
+ for (intptr_t nr = 0; nr < sdna->nr_structs; nr++) {
sp = sdna->structs[nr];
BLI_ghash_insert(sdna->structs_map, sdna->types[sp[0]], SET_INT_IN_POINTER(nr));
}
+ }
#endif
+
+ /* Calculate 'sdna->pointerlen' */
+ {
+ intptr_t nr = DNA_struct_find_nr(sdna, "ListBase");
+
+ /* should never happen, only with corrupt file for example */
+ if (UNLIKELY(nr == -1)) {
+ printf("ListBase struct error! Not found.\n");
+ exit(1);
+ }
+
+ /* finally pointerlen: use struct ListBase to test it, never change the size of it! */
+ sp = sdna->structs[nr];
+ /* weird; i have no memory of that... I think I used sizeof(void *) before... (ton) */
+
+ sdna->pointerlen = sdna->typelens[sp[0]] / 2;
+
+ if (sp[1] != 2 || (sdna->pointerlen != 4 && sdna->pointerlen != 8)) {
+ printf("ListBase struct error! Needs it to calculate pointerize.\n");
+ exit(1);
+ /* well, at least sizeof(ListBase) is error proof! (ton) */
+ }
}
}
@@ -557,8 +563,6 @@ SDNA *DNA_sdna_from_data(
bool do_endian_swap, bool data_alloc)
{
SDNA *sdna = MEM_mallocN(sizeof(*sdna), "sdna");
-
- sdna->lastfind = 0;
sdna->datalen = datalen;
if (data_alloc) {
@@ -623,7 +627,7 @@ static void recurs_test_compflags(const SDNA *sdna, char *compflags, int structn
* - 1 Struct is the same (can be loaded with straight memory copy after any necessary endian conversion)
* - 2 Struct is different in some way (needs to be copied/converted field by field)
*/
-char *DNA_struct_get_compareflags(SDNA *oldsdna, SDNA *newsdna)
+char *DNA_struct_get_compareflags(const SDNA *oldsdna, const SDNA *newsdna)
{
int a, b;
const short *sp_old, *sp_new;
@@ -640,14 +644,19 @@ char *DNA_struct_get_compareflags(SDNA *oldsdna, SDNA *newsdna)
/* we check all structs in 'oldsdna' and compare them with
* the structs in 'newsdna'
*/
+ unsigned int newsdna_index_last = 0;
for (a = 0; a < oldsdna->nr_structs; a++) {
sp_old = oldsdna->structs[a];
/* search for type in cur */
- sp_new = findstruct_name(newsdna, oldsdna->types[sp_old[0]]);
-
- if (sp_new) {
+ int sp_new_index = DNA_struct_find_nr_ex(newsdna, oldsdna->types[sp_old[0]], &newsdna_index_last);
+
+ /* The next indices will almost always match */
+ newsdna_index_last++;
+
+ if (sp_new_index != -1) {
+ sp_new = newsdna->structs[sp_new_index];
/* initial assumption */
compflags[a] = SDNA_CMP_NOT_EQUAL;
@@ -1037,8 +1046,8 @@ static void reconstruct_elem(
* \param cur Where to put converted struct contents
*/
static void reconstruct_struct(
- SDNA *newsdna,
- SDNA *oldsdna,
+ const SDNA *newsdna,
+ const SDNA *oldsdna,
const char *compflags,
int oldSDNAnr,
@@ -1056,6 +1065,10 @@ static void reconstruct_struct(
char *cpo, *cpc;
const char *name, *nameo;
+ unsigned int oldsdna_index_last = UINT_MAX;
+ unsigned int cursdna_index_last = UINT_MAX;
+
+
if (oldSDNAnr == -1) return;
if (curSDNAnr == -1) return;
@@ -1090,8 +1103,8 @@ static void reconstruct_struct(
cpo = find_elem(oldsdna, type, name, spo, data, &sppo);
if (cpo) {
- oldSDNAnr = DNA_struct_find_nr(oldsdna, type);
- curSDNAnr = DNA_struct_find_nr(newsdna, type);
+ oldSDNAnr = DNA_struct_find_nr_ex(oldsdna, type, &oldsdna_index_last);
+ curSDNAnr = DNA_struct_find_nr_ex(newsdna, type, &cursdna_index_last);
/* array!
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list