RNA: Use hash lookups for structs
authorCampbell Barton <ideasman42@gmail.com>
Fri, 11 Aug 2017 07:51:38 +0000 (17:51 +1000)
committerCampbell Barton <ideasman42@gmail.com>
Fri, 11 Aug 2017 08:11:25 +0000 (18:11 +1000)
Adding structs was checking for duplicates
causing approx 75k string comparisons on startup.

While overall speedup is minimal,
Python access to `bpy.types` will now use a hash lookup
instead of a full linked list search.

See D2774

source/blender/makesrna/intern/makesrna.c
source/blender/makesrna/intern/rna_access.c
source/blender/makesrna/intern/rna_define.c
source/blender/makesrna/intern/rna_internal_types.h
source/blender/makesrna/intern/rna_rna.c

index de436172bfdbaa818a3b5b9381027f8a0e5cc7c4..9471d0e3fcf1e7fb7bf134f31bdd4962ed8a3377 100644 (file)
@@ -2583,17 +2583,23 @@ static void rna_generate_blender(BlenderRNA *brna, FILE *f)
 {
        StructRNA *srna;
 
-       fprintf(f, "BlenderRNA BLENDER_RNA = {");
-
+       fprintf(f,
+               "BlenderRNA BLENDER_RNA = {\n"
+               "\t.structs = {"
+       );
        srna = brna->structs.first;
-       if (srna) fprintf(f, "{&RNA_%s, ", srna->identifier);
-       else fprintf(f, "{NULL, ");
+       if (srna) fprintf(f, "&RNA_%s, ", srna->identifier);
+       else      fprintf(f, "NULL, ");
 
        srna = brna->structs.last;
-       if (srna) fprintf(f, "&RNA_%s}", srna->identifier);
-       else fprintf(f, "NULL}");
+       if (srna) fprintf(f, "&RNA_%s},\n", srna->identifier);
+       else      fprintf(f, "NULL},\n");
 
-       fprintf(f, "};\n\n");
+       fprintf(f,
+               "\t.structs_map = NULL,\n"
+               "\t.structs_len = 0,\n"
+               "};\n\n"
+       );
 }
 
 static void rna_generate_property_prototypes(BlenderRNA *UNUSED(brna), StructRNA *srna, FILE *f)
index 5a4db47d281860f88ebe89c3b1aceb2c47080c31..89348bb8f6ce4c78baebccd50502b9a5040bdebf 100644 (file)
@@ -76,6 +76,9 @@ void RNA_init(void)
        StructRNA *srna;
        PropertyRNA *prop;
 
+       BLENDER_RNA.structs_map = BLI_ghash_str_new_ex(__func__, 2048);
+       BLENDER_RNA.structs_len = 0;
+
        for (srna = BLENDER_RNA.structs.first; srna; srna = srna->cont.next) {
                if (!srna->cont.prophash) {
                        srna->cont.prophash = BLI_ghash_str_new("RNA_init gh");
@@ -86,6 +89,8 @@ void RNA_init(void)
                                }
                        }
                }
+               BLI_ghash_insert(BLENDER_RNA.structs_map, (void *)srna->identifier, srna);
+               BLENDER_RNA.structs_len += 1;
        }
 }
 
@@ -513,13 +518,7 @@ static const char *rna_ensure_property_name(const PropertyRNA *prop)
 
 StructRNA *RNA_struct_find(const char *identifier)
 {
-       StructRNA *type;
-       if (identifier) {
-               for (type = BLENDER_RNA.structs.first; type; type = type->cont.next)
-                       if (STREQ(type->identifier, identifier))
-                               return type;
-       }
-       return NULL;
+       return BLI_ghash_lookup(BLENDER_RNA.structs_map, identifier);
 }
 
 const char *RNA_struct_identifier(const StructRNA *type)
index 42c0344f46ea3687b44773f41dc5acfc9ca9a560..5a1aec593622cb39a2627633c5db39b8b9afa861 100644 (file)
@@ -135,6 +135,19 @@ void rna_freelistN(ListBase *listbase)
        listbase->first = listbase->last = NULL;
 }
 
+static void rna_brna_structs_add(BlenderRNA *brna, StructRNA *srna)
+{
+       rna_addtail(&brna->structs, srna);
+       brna->structs_len += 1;
+
+       /* This exception is only needed for pre-processing.
+        * otherwise we don't allow empty names. */
+       if (srna->identifier[0] != '\0') {
+               BLI_ghash_insert(brna->structs_map, (void *)srna->identifier, srna);
+       }
+
+}
+
 StructDefRNA *rna_find_struct_def(StructRNA *srna)
 {
        StructDefRNA *dsrna;
@@ -534,6 +547,8 @@ BlenderRNA *RNA_create(void)
        const char *error_message = NULL;
 
        BLI_listbase_clear(&DefRNA.structs);
+       brna->structs_map = BLI_ghash_str_new_ex(__func__, 2048);
+
        DefRNA.error = 0;
        DefRNA.preprocess = 1;
 
@@ -654,6 +669,9 @@ void RNA_free(BlenderRNA *brna)
        StructRNA *srna, *nextsrna;
        FunctionRNA *func;
 
+       BLI_ghash_free(brna->structs_map, NULL, NULL);
+       brna->structs_map = NULL;
+
        if (DefRNA.preprocess) {
                RNA_define_free(brna);
 
@@ -747,7 +765,7 @@ StructRNA *RNA_def_struct_ptr(BlenderRNA *brna, const char *identifier, StructRN
        if (!srnafrom)
                srna->icon = ICON_DOT;
 
-       rna_addtail(&brna->structs, srna);
+       rna_brna_structs_add(brna, srna);
 
        if (DefRNA.preprocess) {
                ds = MEM_callocN(sizeof(StructDefRNA), "StructDefRNA");
@@ -819,10 +837,8 @@ StructRNA *RNA_def_struct(BlenderRNA *brna, const char *identifier, const char *
 
        if (from) {
                /* find struct to derive from */
-               for (srnafrom = brna->structs.first; srnafrom; srnafrom = srnafrom->cont.next)
-                       if (STREQ(srnafrom->identifier, from))
-                               break;
-
+               /* Inline RNA_struct_find(...) because it wont link from here. */
+               srnafrom = BLI_ghash_lookup(brna->structs_map, from);
                if (!srnafrom) {
                        fprintf(stderr, "%s: struct %s not found to define %s.\n", __func__, from, identifier);
                        DefRNA.error = 1;
@@ -901,10 +917,7 @@ void RNA_def_struct_nested(BlenderRNA *brna, StructRNA *srna, const char *struct
        StructRNA *srnafrom;
 
        /* find struct to derive from */
-       for (srnafrom = brna->structs.first; srnafrom; srnafrom = srnafrom->cont.next)
-               if (STREQ(srnafrom->identifier, structname))
-                       break;
-
+       srnafrom = BLI_ghash_lookup(brna->structs_map, structname);
        if (!srnafrom) {
                fprintf(stderr, "%s: struct %s not found for %s.\n", __func__, structname, srna->identifier);
                DefRNA.error = 1;
index df591659fdb7f48e84f50a47bfe71de437775a4d..b52f6c78f3a87d42e9d34d875dd9b79bedb55d1a 100644 (file)
@@ -413,6 +413,9 @@ struct StructRNA {
 
 struct BlenderRNA {
        ListBase structs;
+       struct GHash *structs_map;
+       /* Needed because types with an empty identifier aren't included in 'structs_map'. */
+       unsigned int  structs_len;
 };
 
 #define CONTAINER_RNA_ID(cont) (*(const char **)(((ContainerRNA *)(cont))+1))
index abded187b33132c13cb060df10b8cfc3b85760bc..bbd0fe2486ea45394f0fd5c787e57fd497cfe119 100644 (file)
@@ -985,19 +985,22 @@ static int rna_Function_use_self_type_get(PointerRNA *ptr)
 
 static void rna_BlenderRNA_structs_begin(CollectionPropertyIterator *iter, PointerRNA *ptr)
 {
-       rna_iterator_listbase_begin(iter, &((BlenderRNA *)ptr->data)->structs, NULL);
+       BlenderRNA *brna = ptr->data;
+       rna_iterator_listbase_begin(iter, &brna->structs, NULL);
 }
 
 /* optional, for faster lookups */
 static int rna_BlenderRNA_structs_length(PointerRNA *ptr)
 {
-       return BLI_listbase_count(&((BlenderRNA *)ptr->data)->structs);
+       BlenderRNA *brna = ptr->data;
+       BLI_assert(brna->structs_len == BLI_listbase_count(&brna->structs));
+       return brna->structs_len;
 }
 static int rna_BlenderRNA_structs_lookup_int(PointerRNA *ptr, int index, PointerRNA *r_ptr)
 {
-       StructRNA *srna = BLI_findlink(&((BlenderRNA *)ptr->data)->structs, index);
-
-       if (srna) {
+       BlenderRNA *brna = ptr->data;
+       StructRNA *srna = index < brna->structs_len ? BLI_findlink(&brna->structs, index) : NULL;
+       if (srna != NULL) {
                RNA_pointer_create(NULL, &RNA_Struct, srna, r_ptr);
                return true;
        }
@@ -1007,12 +1010,11 @@ static int rna_BlenderRNA_structs_lookup_int(PointerRNA *ptr, int index, Pointer
 }
 static int rna_BlenderRNA_structs_lookup_string(PointerRNA *ptr, const char *key, PointerRNA *r_ptr)
 {
-       StructRNA *srna = ((BlenderRNA *)ptr->data)->structs.first;
-       for (; srna; srna = srna->cont.next) {
-               if (key[0] == srna->identifier[0] && STREQ(key, srna->identifier)) {
-                       RNA_pointer_create(NULL, &RNA_Struct, srna, r_ptr);
-                       return true;
-               }
+       BlenderRNA *brna = ptr->data;
+       StructRNA *srna = BLI_ghash_lookup(brna->structs_map, (void *)key);
+       if (srna != NULL) {
+               RNA_pointer_create(NULL, &RNA_Struct, srna, r_ptr);
+               return true;
        }
 
        return false;