компиляция регулярок относится не только к перлу , тем более, что это preg_*
Так вот на первом вызове preg_replace происходит компилация регулярного выражения, что и вызывает замедление по времени, на последующие вызовы среда выполнения работает уже со скомпилированным выражением, значительно ускоряя работу. Тем более, я не думаю что речь идет об веб-сервисе где каждая миллисекунда дорога. Так что, честно говоря, я не понимаю почему подымается вопрос скорости. Есть более насущные проблемы - preg_replace это одна команда + мощь регэкспов, что означает простоту большую мощь кода при меньших затратах со стороны программиста, а что важно. Потом любой поиск по документу перерастает в поиск регулярному выражению, поэтому применять их изначально правильно.