Graph Storage for Query Cache

[alexfigliolia]

Has anyone thought to experiment with Graph/Trie storage for the query cache?

I have a small proof of concept working with benchmarks that show it being ~4x faster per cache read/write. I'm running the benchmark on an M4 Max Mac with 32GB of ram (which should actually be minimizing the potential performance gain here).

The memory usage is of course higher than using a ~flat hashtable, but at ~4x faster, conceptually, this might be worth allowing developers to enable behind a config option or something.

If interested, the code lives here. Inside src/Cache/Cache.ts and src/Cache/Graph.ts you'll find the brunt of the working concept.

If you wish to reproduce the results locally you can clone, pnpm i, then run pnpm bench.

If you wish to visualize the storage structure you can also run pnpm visualize

If you're interested in why Graph/Trie storage works here, it's largely due to dodging JSON.stringify() when doing cache interactions. Instead of flat storage with a stringified key, query keys are traversed into a deterministic list of JavaScript primitives (compatible as object keys) that are then used as edges between Trie/Graph nodes. The bottom most node then contains the cache entry and value.

Memory usage is higher due to the intermediary nodes in the Trie/Graph structure, but the runtime performance perhaps makes the overhead worth it.

Some related background

I have a decent size app glued to a not-so-popular state manager. It works and it's probably right for the app's use-case, but something like tanstack-query would be interesting for it as well. The migration cost for this app would actually higher than if I were to just build something similar to tanstack-query - compatible with the not-so-popular state manager I mentioned earlier.

So I did - and eventually found myself toying a few different approaches to storing the query data. I'm probably going to stick with the Graph/Trie, but I'm obviously not looking at the same level of developer usage as tanstack-query is.

Either way, I wanted to share the proof of concept with you guys. Because React specifically tends to be a little trigger-happy on the topic of re-renders, this approach will likely yield further performance improvement there. I'll finish up the framework bindings asap and post some benchmarks.

I'm sure in @tannerlinsley's hands this can probably be more performant than I realize.

🚀

[alexfigliolia]

Updated the original post with more accurate benchmarks and better language