[ANN] Purses.jl 👛

[Evey]

Purses.jl

Does this describe you or someone you know?

Do you often find yourself writing a bunch of composable functions that end up calling the same expensive function on the same single input several times? Does this slow your code down? Have you tried solving this problem by pre-computing the expensive function, but then wondered how to pass it to the function? Have you, in an attempt to solve this problem, then implemented your own wrapper where you put the pre-computed value? For example, does your code take a vector as an input, but internally calls sum(vector) ten times in total, and so you implemented a wrapper struct where you overloaded Base.sum and a bunch of other base functions to make your wrapper usable? Something like

struct VectorWithSum{T,S}
    vector::Vector{T}
    sum::S
end
Base.sum(v::VectorWithSum) = v.sum
Base.:+(v::VectorWithSum, x) = v.vector + x
Base.:*(v::VectorWithSum, x) = v.vector*x
...

Did you then find out that for one of your other inputs, your excessive number of calls to sqrt followed by inv was preventing your code from running as fast as it possibly could? Did you then implement a new wrapper, where you pre-computed sqrt? Was it annoying? Was it time-consuming? Was it energy-draining?

It sounds like you need a purse!

With a purse you won’t ever have to store your cache in a make-shift wrapper again. Each purse is hand-crafted and tailored to your needs, and you can access your cached value at any time with no overhead whatsoever(†). We know exactly where your cache is stored, oftentimes before you do, and we know how to access it in the fastest way possible.

We offer two kinds of purses for two kinds of people. If you are in a hurry, we have the standard, sleek Purse with room for one value and as much cache as you desire. Even if you have time, most people will want to explore this option first to see what a purse can do for them. For the more creative people, we also offer the more fleixble AbstractPurse where you decide where and how you want to store your value and cache. This option requires you to implement some of the details yourself, but it will give your purse your own, unique personal touch.

What are you waiting for? add Purses and get your purse today, or visit us at Purses.jl.

Your value, your cache, your purse

(†) Only guaranteed if the purse is used in a type-stable environment.

[Pbellive]

This looks cool! Thanks for posting. I’m curious about how this package differs from Memoization.jl and Memoize.jl? It seems like they provide similar functionality and I’m wondering why one might choose one over the other. I must confess I haven’t actually tried any of these packages so I’m probably missing some key distinctions.

[Evey]

Thanks for your interest!

The approach in Purses.jl is actually what you could describe as “reverse memoisation”. With memoisation, you annotate a function which then creates a closure over that function with a Dict or something similar. When the function is then called with a specific input, the function decides whether it has seen the input before or not, and then either calculates it or retrieves it. With memoisation, you don’t need to know anything about the values you are going to call your function with. This kind of approach is designed for people who write functions and only works if you own the method that you are memoising. You cannot, without being a type pirate—and you shouldn’t be a type pirate—override Base.sum(::Vector{Float64}). Also, if you really need to squeeze out that last drop of performance, the price paid for hashing the input and looking it up in a Dict may actually end up being a bottleneck. This price was actually the reason I ended up writing Purses.jl.

With a purse, the relationship is reversed in two ways. First: the purse decides whether it recognises the function or not. Second, you compute the values you know you are going to use before you need them. A purse can wrap any value, and since defining methods for a wrapped value isn’t type piracy, you avoid being a type pirate. If the purse does not recognise a given function, it defaults to simply unwrapping and calling the original method with the wrapped value (provided the function is registered by Purses.jl). This kind of approach is for people who have values and who call functions. It is also for people who write many small functions, and don’t want to worry about calling a potentially expensive function in several different places. Unlike memoisation, this “reverse memoisation” can in Julia theoretically become “much” faster, since a function is a singleton type. While memoisation needs to hash the input and then look up if it has seen it before, the singleton nature of the function means that Julia can look up where to find the cache in the purse at compile time. This becomes as fast as simply passing the cached value directly in almost all cases. (Almost here referring to the fact that the purse takes up more memory than the cached value itself, and thus fewer purses can fit in the CPU cache.)

If it helps in understanding, then a purse is essentially just a struct with field access through specific function calls. The point of Purses.jl is to automate writing such a struct.

[Pbellive]

Nice explanation. I get the distinction now between this and memoization. Thanks.