Question About Caching Strategies

[pjkaufman]

Hello,
I am working on Obsidian Linter. In it, there is a performance issue with parsing the abstract syntax trees (ASTs). This can be costly and really unperformant especially when there are no changes made in a file and many rules are run against it since it currently parses the file for each rule being run no matter what. I would like to cache the AST possibly just while running the linter or maintain a cache in local storage like I see has been done here with dataview.

Is there a recommended strategy for this or do you have any pointers on how to go about doing this?

The linter can run against all files in the vault, all of them in a specific folder, or just the current file. I am thinking a cache like the one done in dataview probably is better for that scenario.

The cache would have to be updated each time a file is modified, created, deleted, or moved.

All suggestions and recommendations are very welcome.

Please let me know if this is not the place to ask this.

[blacksmithgu]

A few notes:

1. Consider parallelism / worker threads to split up the work in parallel for large lint operations.
2. You probably don't actually need to cache the AST - generally, linter rules should only need to be applied to files which have changed since the last time a linter has been applied. All you need to do is track the list of files + last modified (or maybe a content hash), and then only apply the lint rules to files which have changed since the last lint attempt. You can do this tracking in a JSON file in the plugin metadata directory, or alternatively in localstorage (using an easy api like localForage).

If you do want an AST cache, such as for skipping re-parsing the AST for multiple rules on the same file, you can probably do something easy by holding a small LRU cache in-memory (implemented with just a Map<(file name, content hash), AST>.

[pjkaufman]

Thanks for the response!

I like the idea of using web workers, but I am not sure that I can use them on the contents of a file. I say this because some lint rules can affect other lint rules and generally speaking it does not keep track of what the rule changed and updates the text of the file. Some can be run in parallel and it would be interesting to see them run in parallel, assuming it would be worth the work given that many probably would not be able to.

Another thing is that rules can be turned on and off which would prevent me from being able to know when I can and cannot lint a file based on hash content. However, I could use the hash and if a setting is changed via the UI, I could then allow rerunning the linter for all applicable files on the next run.

I definitely like the LRU idea as that was similar to my initial idea without the hashing.

I guess that means I should do the following:

1. Evaluate which rules can be run in parallel if any
2. If applicable, break the running of them into operations that work as groups in parallel where possible
3. Use an LRU for AST parsing
4. Hash file content and hash settings to help determine when a change is needed and do a run on any file that has a different hash either in content or for the rules
5. Add a force refresh just in case it is needed

Am I missing anything that may have been mentioned or that you think may help?

As a fellow dev, this has been greatly helpful in getting my brain going around this.

[blacksmithgu]

The parallelism would be across files, probably - lint rules would run sequentially on a single file but could be run in parallel across files (unless you have lints which look at multiple files). This would mostly be an optimization for faster lints in big vaults.

Otherwise, I think your list is good - you can consider speeding up things more by tracking file modified time instead of just hashes. In this case, you would first:

0. If the settings have changed since last lint in a way that would cause files to need to be re-run (like enabling new lints), just immediately start running the lint. Otherwise...
1. Check modified time of file since your last lint time; if it hasn't changed since the lint, no need to even check the hash. This skips a file read, which is good for perf.
2. If the file has been modified, hash the contents and see if the contents have actually changed.
3. If the contents have changed, then actually do the linting using a small in-memory LRU for the AST parser.

Definitely add a force refresh; caches always do weird things sometimes and having an escape button that is easy to use is a big plus.

[pjkaufman]

Thanks for the the help on this. I definitely do want to put the web workers into effect across multiple files. I have put that into my list of things to do, but I have not quite made the time to go ahead and add it. I may end up doing so soon and focus a little more on performance to let me get a break from the UI since that is something that takes me a bit longer and while necessary can be a lot more draining for me.

I also like the suggestion about the date modified. That can definitely be a useful check to help improve performance. I guess I would likely go with a similar approach using local storage and cache information there (not the LRU).

For rule changes things get tricking since enabling a rule likely requires re-linting the next time the user invokes a lint while removing a rule as active could have the same result, but it is not easily ascertained as to whether or not that is the case since several of the rules could affect each other even though in reality they should not (at least most of them are not designed to interact).