I'm sure there will be a fair number of people giving specific code advice. I'll give programming advice:
Once you know you have speed problems, profile. Don't assume you know what is fast and what is slow, and don't assume you know what is being run the most often.
There is an adequate profiler that comes with Perl, that being Devel::DProf. Read up, and see what the basics are. It will help in many cases, but isn't all that extensive.
A better profiler is available in Devel::NYTProf, which will tell you exactly how many times each line of code (or block, or subroutine) is called, and how long it took. Feed your program to that with a representative sample of your data, and work out ways to avoid the slowest operations.