but I'm more interested in how to make expressions work faster

Then I'll try to give you a few general hints:

• Learn about backtracking, and make sure you avoid it wherever possible
  • Anchor your regexes if possible
  • Try to avoid .*? and .*
  • Use backtracking-suppressing groups whenever possible
• Try to use literal strings where possible. The regex engine is smart enough to anchor them automatically as an optimization (in certain cases)
• Only capture (with (...)) when you actually need it

Regexp::Assemble promises (among other things) to bring the power of trie optimizations to earlier perls, maybe it's worth a try (and less hassle than updating your perl version).