search

mcollina / async-cache-dedupe

Async cache with dedupe support
MIT License
640 stars 40 forks source link

Investigate a faster hashing algorithm that JSON stable stringify #8

Closed mcollina closed 2 years ago

mcollina commented 2 years ago

A quick analysis with a flamegraph shows that safe-stable-stringify is the major bottleneck for this cache.

We should investigate if we could come up with a faster algorithm for hashing objects but with the same properties.

simoneb commented 2 years ago

What about this one? https://github.com/epoberezkin/fast-json-stable-stringify

mcollina commented 2 years ago

See the benchmarks at https://github.com/BridgeAR/safe-stable-stringify#performance--benchmarks

zbo14 commented 2 years ago

@mcollina any way you can share the analysis or provide instructions to repro?

safe-stable-stringify seems pretty fast compared to other stringify options and v8 serialization. We could try a different approach, e.g. cache array lengths and lists of top-level object keys as well. This might help detect cache misses more quickly before stringifying giant nested objects. I'm not sure this addresses a cause of the bottleneck you mentioned though.

mcollina commented 2 years ago

Essentially those are the kind of logic we might want to consider.

Just run a flamegraph against https://github.com/mercurius-js/cache/tree/main/bench and you'll see the bottleneck.

zbo14 commented 2 years ago

another option would be to modify the serialize() function so it constructs/returns a string instead of an object that's later stringified. Not sure if this is feasible though.

@mcollina does the following screenshot corroborate your findings?

_home_zach_Projects_cache_1576762 0x_flamegraph html (1)

mcollina commented 2 years ago

Yes, exactly. It gets worse as the parameters size grows.

zbo14 commented 2 years ago

I've tried using yieldable-json and worker threads with pinscina for stringification. Both approaches under-perform safe-stable-stringify. Unless there are other benchmarks indicating that safe-stable-stringify is a serious performance concern, perhaps it makes sense to optimize mercurius cache serialization instead?

Also, mercurius-js/cache is still using v0.5.0 of async-cache-dedupe. Perhaps we can revisit when it has the newer code?

mcollina commented 2 years ago

Also, mercurius-js/cache is still using v0.5.0 of async-cache-dedupe. Perhaps we can revisit when it has the newer code?

It has been updated this week.

mcollina commented 2 years ago

I'll close this for now./