Quadratic space/time complexity due to deepcopy of __cache_children

[tomtomjhj]

mkdir -p test/dir
cd test/dir
seq 1000 | xargs touch
cd ..
vim .

In vim, do fern-action-expand on dir/. This is quite slow.
If you increase the number of files, you can see that the time spent and memory usage of vim is quadratic wrt the number of files under dir/.

Notable results from :profile (with 2000 files)

FUNCTION  <lambda>501()
    Defined: /path/to/vim-fern/autoload/fern/internal/node.vim:87
Called 2000 times
Total time:   6.792857494
 Self time:   6.792857494

count     total (s)      self (s)
                                  return deepcopy(v) 

vim-fern/autoload/fern/internal/node.vim

Lines 87 to 90 in a675dff

	return s:AsyncLambda.map(
	\ a:node.concealed.__cache_children,
	\ { v -> deepcopy(v) },
	\)

If I change this deepcopy() to copy(), this quadratic behavior does not happen anymore (and the sorting is the next most signficant bottleneck).

[lambdalisue]

Thank you. I’ve managed to reproduce the issue, and I’ll take a closer look at it.

[tomtomjhj]

__cache_children doesn't seem to be used in a meaningful way. I tried removing all its occurrences and it's been working fine.

diff --git a/autoload/fern/internal/node.vim b/autoload/fern/internal/node.vim
index 1fe1203..f87e862 100644
--- a/autoload/fern/internal/node.vim
+++ b/autoload/fern/internal/node.vim
@@ -82,12 +82,6 @@ function! fern#internal#node#children(node, provider, token, ...) abort
         \}, a:0 ? a:1 : {})
   if a:node.status is# s:STATUS_NONE
     return s:Promise.reject('leaf node does not have children')
-  elseif has_key(a:node.concealed, '__cache_children') && options.cache
-    " Return a fresh copy of cached children so that status won't be cached
-    return s:AsyncLambda.map(
-          \ a:node.concealed.__cache_children,
-          \ { v -> deepcopy(v) },
-          \)
   elseif has_key(a:node.concealed, '__promise_children')
     return a:node.concealed.__promise_children
   endif
@@ -102,7 +96,6 @@ function! fern#internal#node#children(node, provider, token, ...) abort
         \     '__owner': a:node,
         \   })
         \ }))
-        \.then({ v -> s:Lambda.pass(v, s:Lambda.let(a:node.concealed, '__cache_children', v)) })
         \.finally({ -> Done() })
         \.finally({ -> Profile() })
   let a:node.concealed.__promise_children = p
@@ -199,7 +192,6 @@ function! fern#internal#node#collapse(node, nodes, provider, comparator, token)
         \.finally({ -> Done() })
         \.finally({ -> Profile() })
   call p.then({ -> s:Lambda.let(a:node, 'status', s:STATUS_COLLAPSED) })
-        \.then({ -> s:Lambda.unlet(a:node.concealed, '__cache_children') })
   let a:node.concealed.__promise_collapse = p
         \.finally({ -> s:Lambda.unlet(a:node.concealed, '__promise_collapse') })
   return p

---

Additionally, it seems that the __owner field leads to space usage that is quadratic wrt height of the tree.

[lambdalisue]

Hum... I see. Then, please create a PR and I'll try. Let see if that breaks things or not.

[lambdalisue]

Closed via #509