I'm a bit surprized that none of the answers so far have mentioned or asked about Devel::DProf. So: have you tried to run your script under the profiler ?
In my experience, it might sometimes come as a surprize to see where most of the time is spent.