writefile: remove SDNA last-hit, optimize DNA reconstruct
authorCampbell Barton <ideasman42@gmail.com>
Tue, 12 Jul 2016 01:48:04 +0000 (11:48 +1000)
committerCampbell Barton <ideasman42@gmail.com>
Tue, 12 Jul 2016 01:56:45 +0000 (11:56 +1000)
- 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.

source/blender/blenloader/intern/readfile.c
source/blender/makesdna/DNA_genfile.h
source/blender/makesdna/DNA_sdna_types.h
source/blender/makesdna/intern/dna_genfile.c

index 68cc060b0104df5867606ff0bebec1486a59b9e4..27a119a453267c52ee793c763316aa755bef1993 100644 (file)
@@ -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;
index 77877f7bada982514c06ce81cf86c5f7d8cc8f41..1b558b11cf0bda8593b167f5f59f69f5a6a05614 100644 (file)
@@ -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);
index 791aca77558e434a4c490c5288f238c8329ccf50..26ea5cd4e935e42d4f51a2c9f1073be82cfcd568 100644 (file)
 #
 #
 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;
 
 #
index 9135d7bab7d7a6709100ffc757843e03b8a296b4..1d9e97185283c02836bcbbfe5fe30657ee0e7d76 100644 (file)
@@ -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
 
@@ -279,38 +280,17 @@ 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! */
                                mul = DNA_elem_array_size(name);
@@ -1132,7 +1145,7 @@ static void reconstruct_struct(
  * \param oldSDNAnr  Index of struct info within oldsdna
  * \param data  Struct data
  */
-void DNA_struct_switch_endian(SDNA *oldsdna, int oldSDNAnr, char *data)
+void DNA_struct_switch_endian(const SDNA *oldsdna, int oldSDNAnr, char *data)
 {
        /* Recursive!
         * If element is a struct, call recursive.
@@ -1141,6 +1154,7 @@ void DNA_struct_switch_endian(SDNA *oldsdna, int oldSDNAnr, char *data)
        const short *spo, *spc;
        char *cur;
        const char *type, *name;
+       unsigned int oldsdna_index_last = UINT_MAX;
 
        if (oldSDNAnr == -1) return;
        firststructtypenr = *(oldsdna->structs[0]);
@@ -1165,7 +1179,7 @@ void DNA_struct_switch_endian(SDNA *oldsdna, int oldSDNAnr, char *data)
                        /* where does the old data start (is there one?) */
                        char *cpo = find_elem(oldsdna, type, name, spo, data, NULL);
                        if (cpo) {
-                               oldSDNAnr = DNA_struct_find_nr(oldsdna, type);
+                               oldSDNAnr = DNA_struct_find_nr_ex(oldsdna, type, &oldsdna_index_last);
                                
                                mul = DNA_elem_array_size(name);
                                elena = elen / mul;
@@ -1223,7 +1237,9 @@ void DNA_struct_switch_endian(SDNA *oldsdna, int oldSDNAnr, char *data)
  * \param data  Array of struct data
  * \return An allocated reconstructed struct
  */
-void *DNA_struct_reconstruct(SDNA *newsdna, SDNA *oldsdna, char *compflags, int oldSDNAnr, int blocks, void *data)
+void *DNA_struct_reconstruct(
+        const SDNA *newsdna, const SDNA *oldsdna,
+        char *compflags, int oldSDNAnr, int blocks, void *data)
 {
        int a, curSDNAnr, curlen = 0, oldlen;
        const short *spo, *spc;
@@ -1263,7 +1279,6 @@ void *DNA_struct_reconstruct(SDNA *newsdna, SDNA *oldsdna, char *compflags, int
  */
 int DNA_elem_offset(SDNA *sdna, const char *stype, const char *vartype, const char *name)
 {
-       
        const int SDNAnr = DNA_struct_find_nr(sdna, stype);
        const short * const spo = sdna->structs[SDNAnr];
        const char * const cp = find_elem(sdna, vartype, name, spo, NULL, NULL);
@@ -1273,7 +1288,6 @@ int DNA_elem_offset(SDNA *sdna, const char *stype, const char *vartype, const ch
 
 bool DNA_struct_elem_find(SDNA *sdna, const char *stype, const char *vartype, const char *name)
 {
-       
        const int SDNAnr = DNA_struct_find_nr(sdna, stype);
        
        if (SDNAnr != -1) {