Good question. I guess using ^ to match newlines is probably just not very well optimized in the engine.

The usual trick to make regexes faster is to be as explicit as you can be (like spelling out the newlines) and it helped here. I don't know enough about perl's regex internals to really explain why it works as well as it does in this case.