Using your "realistic time" data set profile your code (see Devel::Profile) and see where energy needs to be focused to improve performance. You can then measure performance improvements and change focus as appropriate.

Yet another guess at performance improvement is to simply read the entire file into memory. With multiple gigabytes of memory in most typical computers that really shouldn't be an issue. You can then run a regex over the whole thing to edit lines in place then print the result in one hit.