Merge pull request adafruit#1052 from dhalbert/speed-up-dict-long-lived

tannewt · web-flow · commit 08def6b51ecb · 2018-07-23T18:17:08.000-07:00
Prevent repetitive recursive scanning of dicts when making them long-…
diff --git a/py/gc_long_lived.c b/py/gc_long_lived.c
@@ -91,6 +91,13 @@ mp_obj_dict_t *make_dict_long_lived(mp_obj_dict_t *dict, uint8_t max_depth) {
     if (dict == NULL || max_depth == 0) {
         return dict;
     }
+    // Don't recurse unnecessarily. Return immediately if we've already seen this dict.
+    if (dict->map.scanning) {
+        return dict;
+    }
+    // Mark that we're processing this dict.
+    dict->map.scanning = 1;
+
     // Update all of the references first so that we reduce the chance of references to the old
     // copies.
     dict->map.table = gc_make_long_lived(dict->map.table);
@@ -100,7 +107,10 @@ mp_obj_dict_t *make_dict_long_lived(mp_obj_dict_t *dict, uint8_t max_depth) {
             dict->map.table[i].value = make_obj_long_lived(value, max_depth - 1);
         }
     }
-    return gc_make_long_lived(dict);
+    dict = gc_make_long_lived(dict);
+    // Done recursing through this dict.
+    dict->map.scanning = 0;
+    return dict;
 }
 
 mp_obj_str_t *make_str_long_lived(mp_obj_str_t *str) {
diff --git a/py/obj.h b/py/obj.h
@@ -359,7 +359,9 @@ typedef struct _mp_map_t {
     size_t all_keys_are_qstrs : 1;
     size_t is_fixed : 1;    // a fixed array that can't be modified; must also be ordered
     size_t is_ordered : 1;  // an ordered array
-    size_t used : (8 * sizeof(size_t) - 3);
+    size_t scanning : 1;    // true if we're in the middle of scanning linked dictionaries,
+                            // e.g., make_dict_long_lived()
+    size_t used : (8 * sizeof(size_t) - 4);
     size_t alloc;
     mp_map_elem_t *table;
 } mp_map_t;

Original file line number	Diff line number	Diff line change
`@@ -91,6 +91,13 @@ mp_obj_dict_t make_dict_long_lived(mp_obj_dict_t dict, uint8_t max_depth) {`
`91`	`91`	`if (dict == NULL \|\| max_depth == 0) {`
`92`	`92`	`return dict;`
`93`	`93`	`}`
	`94`	`+ // Don't recurse unnecessarily. Return immediately if we've already seen this dict.`
	`95`	`+ if (dict->map.scanning) {`
	`96`	`+ return dict;`
	`97`	`+ }`
	`98`	`+ // Mark that we're processing this dict.`
	`99`	`+ dict->map.scanning = 1;`
	`100`	`+`
`94`	`101`	`// Update all of the references first so that we reduce the chance of references to the old`
`95`	`102`	`// copies.`
`96`	`103`	`dict->map.table = gc_make_long_lived(dict->map.table);`
`@@ -100,7 +107,10 @@ mp_obj_dict_t make_dict_long_lived(mp_obj_dict_t dict, uint8_t max_depth) {`
`100`	`107`	`dict->map.table[i].value = make_obj_long_lived(value, max_depth - 1);`
`101`	`108`	`}`
`102`	`109`	`}`
`103`		`- return gc_make_long_lived(dict);`
	`110`	`+ dict = gc_make_long_lived(dict);`
	`111`	`+ // Done recursing through this dict.`
	`112`	`+ dict->map.scanning = 0;`
	`113`	`+ return dict;`
`104`	`114`	`}`
`105`	`115`
`106`	`116`	`mp_obj_str_t make_str_long_lived(mp_obj_str_t str) {`