Answer one: Use Memoize. It's already been tested, so you know it works, and it's a core module, so you know it's there.

Answer two: Use Memoize's method. If you look in the Memoize distribution, there's a test called "speed.t". It works by taking a naive fib implementation, calling it with larger and larger numbers until it takes some given time to execute. Once you've seen it take that amount of time, memoize it, and see if it gets faster. In your own foo() example, break out the $result computation into a separate sub that you can time separately.

Answer three: Pass in a tied scalar as your $arg. Specifically, make a tied scalar that counts the number of times it's been accessed. If you get fewer accesses to it the second time, you know that it was used only to look up the cached result and not to compute the result itself (depending on the algorithm involved, of course). See A heap of medians: efficiency vs. speed for an example. This may not work if your algorithm doesn't actually access the $arg any more than "return $cache{$arg} if exists $cache{$arg}" does. It also might not work if the algorithm copies the scalar once and never uses it again. You might have to overload something so that even the copies exhibit the behavior you want. Implementing and testing this test method might be more trouble than using it to test your foo().

Answer four: Use Memoize.

As an aside, you might find it useful to read When to use Prototypes?