> Странно. grep (2.27) у меня отрабатывает чуть, а gawk (4.1.4) и вовсе  в полтора раза быстрее перла (5.24).

А что тут странного? Собственно сэта новость о новой версии, в которой определенные операции ускорили в 9 раз. Между 2.20(у меня) и 2.27(у вас) вполне могли оптимизировать поиск фиксированных строк.

> Третий питон по скорости cравним с перлом. Второй быстрее третьего, в два раза.

У меня тоже вариант с вторым питоном отрабатывает в два раза быстрее, чем с perl

> Крайне выгодно для grep было бы искать эти 5 миллионов паттернов в файле с более свободным форматом.

Ну было бы в perl и python поиск подстроки вместо сравнения строк, принципиально бы ничего не изменилось. А вот если бы стояла задача поиска с более интересными критериями, например в данном случае убрать из второго файла все  строки, где числа между 1000000000000 и 1000005000000, то варианты perl/python выполнились бы быстрее и потребовали минимум памяти.

Но вообще я никогда не выбирал perl вместо grep или awk из-за скорости. Просто удобней выучить один раз его, чем синтаксис и ключи кучи разных утилит, которые к тому же будут по разному работать в зависимости от версии и реализации(awk может предоставляться gawk, а может mawk). А однострочник на perl у меня сработает одинаково, что на древней centos 5, что на последней ubuntu.