5 minutes for 20k lines? What is the process doing? Is it really running on the CPU then? Is it waiting for I/O? Do you have a tool like HP's glance available to inspect the running process? What's the breakdown in wallclock, systemtime and usertime for the 5 second and 5 minute runs?

Obviously it's not a well-known feature that Perl sometimes runs 60 times slower than other times on the same input. So, before getting a useful answer, you need to supply more data.

Abigail