Be more selective about cache invalidation, instead of always wiping the entire thing.

[CameronBieganek]

I just came across this while playing around in the REPL. I could see it potentially coming up in real life if somebody is using @memoize in a script.

julia> using Memoization

julia> @memoize function foo(x::Int)
           println("Computing...")
           return 2x
       end
foo (generic function with 1 method)

julia> foo(3)
Computing...
6

julia> foo(3)
6

julia> Memoization.caches[(typeof(foo), IdDict)]
IdDict{Any,Any} with 1 entry:
  ((3,), NamedTuple()) => 6

julia> @memoize function foo(x::String)
           println("Computing...")
           return x * "asdf"
       end
foo (generic function with 2 methods)

julia> foo("hello")
Computing...
"helloasdf"

julia> foo("hello")
"helloasdf"

julia> Memoization.caches[(typeof(foo), IdDict)]
IdDict{Any,Any} with 1 entry:
  (("hello",), NamedTuple()) => "helloasdf"

julia> foo(3)
Computing...
6

julia> Memoization.caches[(typeof(foo), IdDict)]
IdDict{Any,Any} with 2 entries:
  (("hello",), NamedTuple()) => "helloasdf"
  ((3,), NamedTuple())       => 6

[marius311]

This is kind of intentional, the idea being that you don't want a later-defined method to lead to an incosistent memoized result. Instead, you always want the memoized thing returned to be exactly what you'd get if you actually called the function, e.g.

@memoize foo(x) = "original"
foo(1) # memoizes 1 -> "original"
@memoize foo(x::Int) = "something else"
foo(1) # would return "original" if we didn't clear the cache just above

However, your example brings up a point I hadn't thought of which is that its possible to be more selective than wiping the entire cache. Ie if you define foo(::Int) and then foo(::String), then because typeintersect(Int,String)=Union{} you don't need to clear the cache at all (conversely above, typeintersect(Int,Any)=Int, so you know there's the potential for an invalid cached result). Even if there were some non-null intersection, I think you could in theory scan through the cache and only delete certain entries that you knew need to be invalidated, I think all the information is there in the method signature and the types of the memoized arguments. This would be something cool to have. I've changed the title of this issue to reflect that and put it on my todo / wishlist (more than happy to take a PR too should you be interested in it).

[marius311]

Actually the ultimate solution here is to use backedges to just piggyback off of Julia method invalidations, which would mean we're being as selective as possible (see e.g. https://www.oxinabox.net/2021/02/13/Julia-1.6-what-has-changed-since-1.0.html#manually-created-back-edges-for-lowered-code-generated-functions). Doubt I myself have time to work on this in the near future but would be really cool to have.