[WIP] improve graph performance

pderaaij commented 2 months ago

Based on some performance findings found #1375 I started to experiment with some improvements. I've noticed the functionlistByIdentifier being called alot by other functions. In this function, there is a foreach loop running over all resources. A function which works fine for small notebooks, but large notebooks seems to be hit exponentionally.

In this concept I've added a new state object that lists all resources for an identifier. In this case, I choose the identifier to be the file-name of the note. Using that identifier, I list all resource paths with that same identifier. Using this I can remove the foreach loop and just use the identifier to list a small set of resources.

For the 10000 linked notes folder from this repo (https://github.com/rcvd/interconnected-markdown/tree/main/Markdown) this reduces the startup time to:

Foam Logging: info
[info - 21:39:06] Starting Foam
[info - 21:39:07] Loading from directories:
[info - 21:39:07] - /Users/paulderaaij/projects/interconnected-markdown/Markdown/10000s/10000
[info - 21:39:07]   Include: **/*
[info - 21:39:07]   Exclude: **/.foam/**,**/.vscode/**/*,**/_layouts/**/*,**/_site/**/*,**/node_modules/**/*,**/.git,**/.svn,**/.hg,**/CVS,**/.DS_Store,**/Thumbs.db
[info - 21:39:15] Workspace loaded in 7755ms
[info - 21:39:15] Graph loaded in 660ms
[info - 21:39:15] Tags loaded in 4ms
[info - 21:39:15] Loaded 10001 resources

Using the current master the numbers are:

Foam Logging: info
[info - 21:46:53] Starting Foam
[info - 21:46:53] Loading from directories:
[info - 21:46:53] - /Users/paulderaaij/projects/interconnected-markdown/Markdown/10000s/10000
[info - 21:46:53]   Include: **/*
[info - 21:46:53]   Exclude: **/.foam/**,**/.vscode/**/*,**/_layouts/**/*,**/_site/**/*,**/node_modules/**/*,**/.git,**/.svn,**/.hg,**/CVS,**/.DS_Store,**/Thumbs.db
[info - 21:47:01] Workspace loaded in 8147ms
[info - 21:47:27] Graph loaded in 25513ms
[info - 21:47:27] Tags loaded in 2ms
[info - 21:47:27] Loaded 10001 resources

A delta of almost 25 seconds for loading the graph. Not only a performance improvement for loading the workspace, but also for some other operations that uses listByIdentifier directly or via find. This should make several UI components work better and more responsive.

The downside is that it adds a new stateful object, but I don't see an other way to increase the performance of the foreach loop.

@riccardoferretti curious to your thoughts on this.

riccardoferretti commented 2 months ago

This is amazing @pderaaij ! I am back from holidays (you know, italy + august = holiday) so will look a bit more into the PR this week

riccardoferretti commented 2 months ago

Sharing some high level thoughts here. As I was doing some research in the approach, I came across the trie data structure, which fundamentally feels like what we are kinda implementing here. As I looked into it, I realized that using the reversed path (similar to what we do in getShortestIdentifier) and saving in in a trie would be the cleanest solution, as it would out of the box replace the existing indexing while giving us the features and performance we want.

What do you think? Again, this was at a cursory look, I might be missing something

pderaaij commented 2 months ago

Never really looked into the trie datastructure. Will do some research and fiddle around!

pderaaij commented 2 months ago

I need a bit more time to figure out the right approach. Have been looking into tie data structures, but most implementation I found are immutable. A characteristic we don't want for our use case here. So, I need to find an implementation that does allow mutations. Did a quick checkout of https://rimbu.org, but couldn't find a right data structure off the bat for our use case. So, I require some more time to look around and find a solution. Ideas welcome of course.