Прежде всего хочу отметить, что большинство sed скриптов вовсе не нуждаются в оптимизации по быстродействию: связано это с очень медленным чтением файлов с жёсткого диска. Например, ваш файл читается за 100 секунд, а sed-скрипт выполняется 2 секунды, таким образом, всё это вместе выполнится за 100 секунд (ага, не за 102, потому как чтение файла и обработку sed выполняет одновременно). Даже если мы и улучшим свой скрипт (например перепишем его на assembler'е), время работы не изменится, как было 100, так 100 и останется. Даже если скрипт сработает не за 2, а скажем за 0.2 секунды.

Многие будут спорить с такими тезисами - дескать они проверили, и у них получилось не так. Специально для них напомню про кеширование: сначала файл читается с диска в память, а потом он обрабатывается. Вот только из памяти его никто не стирает, у нас не маздай. Если запустить скрипт ещё раз, он не станет читать файл с диска, он прочитает его из памяти. Это займёт не 100 секунд, а 5. И при этом распараллелить процессы будет невозможно, потому общее время выполнения скрипта будет равно 5+2==7 секунд. Так-же будет если вы только-что создали тестовый файл (может он даже на диск не записался, а так и висит в памяти - в любом случае, он будет браться именно из памяти).

Проблема в том, что на практике скрипты выполняются именно за 100 секунд, а не за 7, как в тестах. Потому, к тестам надо относится очень подозрительно...

Скрипты в sed выполняются в разы быстрее, чем в других скриптовых языках (на практике в 2-3 раза быстрее, а для bash - в 20-30). Это связано с тем, что все команды в sed-скриптах состоят из одной буквы, и наш процессор просто передаёт управление в нужный участок кода в зависимости от первого байта команды. Это намного быстрее, чем сначала выделять нужную команду из текста, а потом рассчитывать её хеш (как приходится делать в любых других языках). Тем не менее, мы с лёгкостью можем написать скрипт, который выполняется вечно, кроме того, многие задачи в sed не решаются обычным простым путём, и их приходится решать более медленными способами. Например: для выравнивания текста по правому краю с шириной строки N, нам достаточно добавить к строке слева N-n пробелов (n - длинна текущей строки). В sed так сделать не получается, и приходится сначала добавлять к строке слева N пробелов, а после этого, откусывать N символов справа (см. пример).

Очень сложно сказать, что будет работать быстрее на практике. Конечно, мы можем написать специализированную программу на ассемблере, и она отработает быстрее (может быть, а может быть и нет, выше я уже писал про скрипт, который выполняется за 0 секунд - по причине того, что он работает параллельно с заведомо более долгим процессом чтения с HDD), однако, нашу программу будет невозможно собрать на другом компьютере. Программа на С может и соберётся, но ведь её ещё и собирать надо! Кроме того, программа на С потребует компилятора, и прочих девелоперских штучек. Например необходимы будут библиотеки для работы с текстом, а их как раз и нет на подавляющем большинстве систем. Точнее есть, но уже собранные, а нам нужны их исходные тексты, или хотя-бы заголовочные файлы, что-бы заюзать уже собранные библиотеки. А их-то и нет. И опять бегинеры будут хаять нас, нашу программу и GNU в целом - дескать

На выпады подобного рода я уже многократно отвечал в том духе, что дескать «сам юзер муд.к, и руки у него из ж.пы», однако согласитесь, для того, что-бы юзер самостоятельно выравнял свой текст, намного быстрее дать ему sed-скрипт, чем заставлять собирать программу. (Быстрее и нам и юзеру-идиоту. В конце концов - собирать программы - вовсе не его задача).

Регулярные выражения в sed выполняются обычно намного быстрее, чем в любых других языках: это связано с нерегулируемой жадностью и с тем, что sed всегда просматривает строки всего-лишь один раз.

Однако, следует учитывать то, что строка просматривается хоть и один раз, но всегда целиком, т.е. выражение /^X/ будет просматриваться для всей строки, что конечно не слишком быстро если в строке 10 000 000 000 символов, к тому-же, это и не нужно.

$ sed -i '' /dev/stdin
sed: couldn't edit /dev/stdin: is a terminal

$ sed-4.0.9 -i '' /dev/stdin
sed-4.0.9: Couldn't open temporary file /dev//sed1V5U24: Permission denied

Данные команды призваны удалять строки. Однако они на самом деле ничего не удаляют: команда d попросту завершает работу всего скрипта, даже без обычного вывода буфера (потому, в примитивных скриптах вроде sed '7d' кажется, что выбранная строка удаляется). Такое поведение несколько затрудняет написание скриптов, в сложном случае необходимо учитывать прерывание - никакие команды скрипта не будут выполнятся после выполнения команды d. Это не хорошо и не плохо, просто об этом надо помнить, например:

#!/bin/sed -f
/XXX/{
	# если в строке есть XXX, то она не выводится, и работа скрипта прерывается
	d
}
# а эта часть скрипта выполняется только для строк, в которых XXX нету

Что касается команды D, то она работает по другому: Прежде всего производится поиск первого символа '\n' в буфере. Если такого символа нет, то команда работает в точности как команда d, а таких символов в строке никогда и не бывает, кроме случая, когда мы его сами туда вставили, командами s, N, G, или H (последняя команда тоже вставляет \n, но не туда, впрочем это потом всё равно извлекается в буфер). Если в буфере есть символ \n, то команда D работает совершенно по другому: она отрезает все символы в строке до первого \n и передаёт управление первой команде скрипта. При этом отрезание происходит просто сдвигом позиции начала строки, т.е. первая подстрока так и остаётся в памяти, хотя получить к ней доступ совершенно невозможно.

Однако эта "удалённая" первая подстрока недолго будет висеть в памяти: команда D обычно работает в паре с командой N (или с G или H), которая добавляет к буферу новую подстроку. На самом деле для буфера выделяется 50 байтов, потому для новой строки обычно хватает места (строчки обычно короче, а если строчки длиннее, то и буфер соответственно увеличивается). Однако рано или поздно наступает момент, когда грузить строчку некуда - и именно тогда, активные строчки сдвигаются в начало буфера, при этом затирая то, что было "удалённо" командой D. Возможен конечно и вариант, когда команда D очистила недостаточно место, и только в этом крайнем случае выполняется вызов функции REALLOC (точнее макроса), а уж работа этой функции зависит от конкретной OS.

Пример типичного использования команд D и N.