I've been trying your optimized code on my machine (an old Duron 700MHz, under medium load):

$ time ./bench.pl
187692

real    17m12.507s
user    10m3.640s
sys     0m1.300s

so it's still very slow compared to what it does.
Then, I've tried to compile it:

$ perlcc -O -o bench bench.pl
$ time ./bench
187692

real    12m35.665s
user    6m1.480s
sys     0m0.720s

It still is definitely slow, but you get an evident boost in performance just by compiling it into C code... something to remember for situations in which you really need Perl for doing lengthy tasks.