Why is `sed` no op much faster than `awk` in this case
awk
has a wider feature set than sed
, 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:
NR==100001
and see the effects of that in gprof
(GNU awk 4.0.1):
% cumulative self self total time seconds seconds calls s/call s/call name 55.89 19.73 19.73 1 19.73 35.04 interpret 8.90 22.87 3.14 500000000 0.00 0.00 cmp_scalar 8.64 25.92 3.05 1000305023 0.00 0.00 free_wstr 8.61 28.96 3.04 500105014 0.00 0.00 mk_number 6.09 31.11 2.15 500000001 0.00 0.00 cmp_nodes 4.18 32.59 1.48 500200013 0.00 0.00 unref 3.68 33.89 1.30 500000000 0.00 0.00 eval_condition 2.21 34.67 0.78 500000000 0.00 0.00 update_NR
~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:
- Fetch the built-in variable "NR" (
update_NR
). - Convert the string "100001" (
mk_number
). - Compare them (
cmp_nodes
,cmp_scalar
,eval_condition
). - Discard any temporary objects needed for the comparison (
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), and sed
can tell from the first character whether it's an address or command. In the example, it's
100001
...a single numerical address. The profile (GNU sed 4.2.2) shows
% cumulative self self total time seconds seconds calls s/call s/call name 52.01 2.98 2.98 100000 0.00 0.00 execute_program 44.16 5.51 2.53 1000000000 0.00 0.00 match_address_p 3.84 5.73 0.22 match_an_address_p [...] 0.00 5.73 0.00 5000 0.00 0.00 in_integer
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
improvements
The 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, GNU sed
treats the "start block" command
100001{...}
as a negated branch to the end of the block
100001!b end; ... :end
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 in execute_program
.
So that sed
expression would be even faster if it omitted the unused ;b
, and the resulting unnecessary {...}
, leaving only 100001p
.
% cumulative self self total time seconds seconds calls s/call s/call name 71.43 1.40 1.40 500000000 0.00 0.00 match_address_p 24.49 1.88 0.48 100000 0.00 0.00 execute_program 4.08 1.96 0.08 match_an_address_p
That halves the number of match_address_p
calls, and also cuts most of the time spent in execute_program
(because the address match never succeeds).