From 0c3455d3290fa03da8c01c135dd7126a80ed28a8 Mon Sep 17 00:00:00 2001 From: Nicolas Williams Date: Thu, 21 Oct 2021 00:15:12 -0500 Subject: Fix accidentally quadratic behavior in setpath We need to be careful to not grab an extra reference when mutating data structures because that means we make extra copies. Doing that every time in `jv_setpath()` is really painful, as that function is used in `_modify/2`, which is used in `|=` and all modify-assign operators. `_modify` also grabs additional references, so this is not the only fix needed for the modify-assign operators to not be accidentally quadratic. --- src/jv_aux.c | 32 ++++++++++++++++++++++++++++++-- 1 file changed, 30 insertions(+), 2 deletions(-) diff --git a/src/jv_aux.c b/src/jv_aux.c index eca2345f..994285a5 100644 --- a/src/jv_aux.c +++ b/src/jv_aux.c @@ -351,8 +351,36 @@ jv jv_setpath(jv root, jv path, jv value) { } jv pathcurr = jv_array_get(jv_copy(path), 0); jv pathrest = jv_array_slice(path, 1, jv_array_length(jv_copy(path))); - return jv_set(root, pathcurr, - jv_setpath(jv_get(jv_copy(root), jv_copy(pathcurr)), pathrest, value)); + + /* + * We need to be careful not to make extra copies since that leads to + * quadratic behavior (e.g., when growing large data structures in a + * reduction with `setpath/2`, i.e., with `|=`. + */ + if (jv_get_kind(pathcurr) == JV_KIND_OBJECT) { + // Assignment to slice -- dunno yet how to avoid the extra copy + return jv_set(root, pathcurr, + jv_setpath(jv_get(jv_copy(root), jv_copy(pathcurr)), pathrest, value)); + } + + jv subroot = jv_get(jv_copy(root), jv_copy(pathcurr)); + if (!jv_is_valid(subroot)) { + jv_free(pathcurr); + jv_free(pathrest); + jv_free(value); + return subroot; + } + + // To avoid the extra copy we drop the reference from `root` by setting that + // to null first. + root = jv_set(root, jv_copy(pathcurr), jv_null()); + if (!jv_is_valid(root)) { + jv_free(pathcurr); + jv_free(pathrest); + jv_free(value); + return root; + } + return jv_set(root, pathcurr, jv_setpath(subroot, pathrest, value)); } jv jv_getpath(jv root, jv path) { -- cgit v1.2.3