I am trying to understand some performance issues related to sed
and awk
, and I did the following experiment,
$ seq 100000 > test
$ yes 'NR==100001{print}' | head -n 5000 > test.awk
$ yes '100001{p;b}' | head -n 5000 > test.sed
$ time sed -nf test.sed test
real 0m3.436s
user 0m3.428s
sys 0m0.004s
$ time awk -F@ -f test.awk test
real 0m11.615s
user 0m11.582s
sys 0m0.007s
$ sed --version
sed (GNU sed) 4.5
$ awk --version
GNU Awk 4.2.1, API: 2.0 (GNU MPFR 3.1.6-p2, GNU MP 6.1.2)
Here, since the test file only contains 100000 lines, all the commands in test.sed
and test.awk
are no-ops. Both programs only need to match the line number with the address (in sed
) or NR
(in awk
) to decide that the command does not need to be executed, but there is still a huge difference in the time cost. Why is it the case? Are there anyone with different versions of sed
and awk
installed that gives a different result on this test?
Edit:
The results for mawk
(as suggested by @mosvy), original-awk
(the name for "one true awk" at debian based systems, suggested by @GregA.Woods) and perl
are given below,
$ time mawk -F@ -f test.awk test
real 0m5.934s
user 0m5.919s
sys 0m0.004s
$ time original-awk -F@ -f test.awk test
real 0m8.132s
user 0m8.128s
sys 0m0.004s
$ yes 'print if $.==100001;' | head -n 5000 > test.pl
$ time perl -n test.pl test
real 0m33.245s
user 0m33.110s
sys 0m0.019s
$ mawk -W version
mawk 1.3.4 20171017
$ perl --version
This is perl 5, version 28, subversion 1 (v5.28.1) built for x86_64-linux-thread-multi
Replacing -F@
with -F ''
does not make observable changes in the case of gawk
and mawk
. original-awk
does not support empty FS
.
Edit 2
The test by @mosvy gives different results, 21s for sed
and 11s for mawk
, see the comment below for details.
Best Answer
awk
has a wider feature set thansed
, with a more flexible syntax. So it's not unreasonable that it'll take longer both to parse its scripts, and to execute them.As your example command (the part inside the braces) never runs, the time-sensitive part should be your test expression.
awk
First, look at the test in the
awk
example:and see the effects of that in
gprof
(GNU awk 4.0.1):~50% of the time is spent in "interpret", the top-level loop to run the opcodes resulting from the parsed script.
Every time the test is run (ie. 5000 script lines * 100000 input lines),
awk
has to:update_NR
).mk_number
).cmp_nodes
,cmp_scalar
,eval_condition
).free_wstr
,unref
)Other
awk
implementations won't have the exact same call flow, but they will still have to retrieve variables, automatically convert, then compare.sed
By comparison, in
sed
, the "test" is much more limited. It can only be a single address, an address range, or nothing (when the command is the first thing on the line), andsed
can tell from the first character whether it's an address or command. In the example, it's...a single numerical address. The profile (GNU sed 4.2.2) shows
Again, ~50% of the time is in the top-level
execute_program
. In this case, it's called once per input line, then loops over the parsed commands. The loop starts with an address check, but that's not all it does in your example (see later).The line numbers in the input script were parsed at compile-time (
in_integer
). That only has to be done once for each address number in the input, ie. 5000 times, and doesn't make a significant contribution to the overall running time.That means that the address check,
match_address_p
, only compares integers that are already available (through structs and pointers).further
sed
improvementsThe profile shows that
match_address_p
is called 2*5000*100000 times, ie. twice per script-line*input-line. This is because, behind the scenes, GNUsed
treats the "start block" commandas a negated branch to the end of the block
This address match succeeds on every input line, causing a branch to the end of the block (
}
). That block-end has no associated address, so it's another successful match. That explains why so much time is spent inexecute_program
.So that
sed
expression would be even faster if it omitted the unused;b
, and the resulting unnecessary{...}
, leaving only100001p
.That halves the number of
match_address_p
calls, and also cuts most of the time spent inexecute_program
(because the address match never succeeds).