Still don't understand why just changing the one line... caused it to slow down SO much.

Just off the top of my head, I suspect it may be a bad interaction between the " *" and the " +" causing the regex engine to backtrack excessively because they're separated only by an optional element, so a string of multiple spaces can match in multiple ways (no spaces/5 spaces, 1 space/4 spaces, etc.) which then multiplies the number of potential matches for the full string, each of which needs to be evaluated until the engine is satisfied that it either found one that's good enough or that no match exists. The capturing parens on foo may also be contributing.

If you want to test this theory, you could try changing the regex to $allfile =~ s/^( *foo)? +$_\n//mn; (leaving the capturing parens intact) or $allfile =~ s/^(?: *foo)? +$_\n//mn; (non-capturing parens, since you're really only using them for grouping) and seeing if that restores the original performance.