I concur with Zaxo++. Just look at your absolute rates: even the "slow" method is producing nearly 40,000 date strings per second. I can't imagine that being a real bottleneck under any but the highest load situations. Remember that what's true for Java is not directly applicable in Perl. String processing in general tends to be, well, not quite blazing fast in Java while it's what Perl does best.

In other notes, you may be interested in Dominus' article on memoization. See also his Memoize module.

Makeshifts last the longest.