It all depends on how much RAM you have and if you need a regex to cross a newline boundary. And grep/awk/sed won't necessarily be faster, depending on the regex.

In the general case, you will want to read it line by line, applying the regex to each line as needed. Though, I would consider look at File::ReadBackwards if you just want to deal with the tail end. Plus, have you considered putting stuff in a database?