5

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.

  • 2
    I also suggest you try it with mawk ;-) – mosvy Mar 17 at 23:02
  • 2
    Without any testing, I wonder if awk is doing more work per line because of the -F@ field splitting. – Jeff Schaller Mar 18 at 1:24
  • One should always test Awk performance and compatability against The One True Awk. github.com/onetrueawk/awk – Greg A. Woods Mar 19 at 0:23
  • @JeffSchaller I try to figure out a way so that awk does not do any field splitting at all, but at least failed for GNU awk. Setting FS to empty string seems to cause awk to split each individual character as a field. – Weijun Zhou Mar 19 at 6:09
  • @GregA.Woods Updated. – Weijun Zhou Mar 19 at 12:25
7

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).

  • JiggilyNaga, what was the command to get the output like that, please? – Tagwint Mar 19 at 17:42
  • 1
    @Tagwint I recompiled awk and sed with profiling enabled, then used gprof (part of binutils). Though the large numbers meant I had to realign the columns manually. – JigglyNaga Mar 19 at 18:04
1

Actually the above script is not a noop for awk:

Even if you do not use the contents of the fields, according to GAWK manual for each record that is read in the following steps are inevitably performed:

  • scanning for all occurrences of the FS
  • field splitting
  • updating th NF variable

If you are not using this information it just gets discarded afterwards.

If a field separator does not occur within the record, awk still has to assign text to $0 (and in your case to $1, too), and set NF to the actual number of obtained fields (1 in the sample above)

  • 2
    all that doesn't really make a difference -- try time gawk '$1=$1+$1' test >/dev/null; it's really the big unrealistic script that's blowing it up. Also notice that (at least the original awk) does not do splitting until the $1, ... fields are first used. – mosvy Mar 19 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.