9

I have a file with about one million lines, like this:

"ID" "1" "2"
"00000687" 0 1
"00000421" 1 0
"00000421" 1 0
"00000421" 1 0

with the last line repeated more than one million times. Taking inspiration from this question, I've tried some of the proposed solutions to see which one is faster. I was expecting that the solutions with only one process would have been faster than those with a pipeline, because they only use one process. But those are the results of my tests:

  • tail -n +2 file.txt | tr -d \"

    $ time tail -n +2 file.txt | tr -d \" 1> /dev/null
    
    real    0m0,032s
    user    0m0,020s
    sys     0m0,028s
    
  • sed '1d;s/"//g' file.txt

    $ time sed '1d;s/"//g' file.txt 1> /dev/null
    
    real    0m0,410s
    user    0m0,399s
    sys     0m0,011s
    
  • perl -ne ' { s/"//g; print if $. > 1 }' file.txt

    $ time perl -ne ' { s/"//g; print if $. > 1 }' file.txt 1> /dev/null
    
    real    0m0,379s
    user    0m0,367s
    sys     0m0,013s
    

I repeated the tests many times and I have always obtained similar numbers. As you can see, tail -n +2 file.txt | tr -d \" is much faster than the others. Why?

11

It boils down to the amount of work being done.

Your tail | tr command ends up doing the following:

  • in tail:
    • read until a newline;
    • output everything remaining, without caring about newlines;
  • in tr, read, without caring about newlines, and output everything apart from ‘"’ (a fixed character).

Your sed command ends up doing the following, after interpreting the given script:

  • read until a newline, accumulating input;
  • if this is the first line, delete it;
  • replace all double quotes with nothing, after interpreting the regular expression;
  • output the processed line;
  • loop until the end of the file.

Your Perl command ends up doing the following, after interpreting the given script:

  • read until a newline, accumulating input;
  • replace all double quotes with nothing, after interpreting the regular expression;
  • if this is not the first line, output the processed line;
  • loop until the end of the file.

Looking for newlines ends up being expensive on large inputs.

| improve this answer | |
  • 2
    "Your Perl|sed command ends up doing the following" - You forgot: Interpret the program. Both languages are quite rich in contrast to what the tools tail and tr do. – rexkogitans May 22 at 6:46
  • 1
    @rexkogitans that’s why I wrote “ends up doing”, I’m only describing the processing work that’s done. I didn’t measure the interpretation time, I don’t know how significant it is when handling a million lines. I guess I’ll have to check... – Stephen Kitt May 22 at 7:39
  • Actually, the way the perl interpreter is implemented does mater a lot. Perl isn't using any kind of bytecode -- it turns the source script into a syntax tree and then executes it by "walking" the syntax tree via pointers. If you tried the similar code with an interpreter which is using some kind of bytecode (e.g. mawk -- not gawk!) you would notice that is twice or thrice as fast for a case like the OP's. – Uncle Billy May 22 at 15:10
7

Mainly because perl and sed process each line separately.

If you let perl process the input by larger blocks, and simplify it a bit (see note), you can make it much faster -- yet nowhere as fast as tr:

time perl -ne ' { s/"//g; print if $. > 1 }' file.txt 1> /dev/null

real    0m0.617s
user    0m0.612s
sys     0m0.005s

time perl -pe 'BEGIN{<>;$/=\40960} s/"//g' file.txt >/dev/null

real    0m0.186s
user    0m0.177s
sys     0m0.009s

time tail -n +2 file.txt | tr -d \" 1> /dev/null

real    0m0.033s
user    0m0.031s
sys     0m0.023s

note: don't use perl -ne '... if $. > 1' or awk 'NR == 1 { ... } /foo/ { ... }'.

Use BEGIN{<>} and BEGIN{getline} instead.

After you have read the first line, you can be pretty darn sure that no subsequent line will be the first line anymore: no need to check again and again.

| improve this answer | |
2

I get the feeling you would like to use perl but it is too slow.

perl is a general tool, and it will not be as fast as a specialized tool like tr. You can get close, though:

$ tail -n +2 file.txt | tr -d \" >/dev/null;
real    0m0.040s
user    0m0.030s
sys     0m0.032s

$ perl -e 'while(sysread(STDIN,$b,1)) {$b eq "\n" and last}
           while(sysread(STDIN,$b,131072)) {
             $b=~tr/\"//d; print $b
           }' < file.txt > /dev/null;
real    0m0.049s
user    0m0.045s
sys     0m0.004s

You can avoid the tail and go even faster:

$ time (read; tr -d \") < file.txt >/dev/null
real    0m0.033s
user    0m0.021s
sys     0m0.012s
| improve this answer | |
  • And what is this:131072 ? – rastafile May 22 at 9:18
  • 2^17. It is on my machine the optimal block size to read (maybe it fits perfectly in my CPU cache - who knows?) – Ole Tange May 22 at 9:19
  • 1
    You're right, I need better glasses. – Uncle Billy May 22 at 15:36
2

tail_lines() from tail.c:

      /* Use file_lines only if FD refers to a regular file for
         which lseek (... SEEK_END) works.  */

      if ( ! presume_input_pipe
           && S_ISREG (stats.st_mode)
           && (start_pos = lseek (fd, 0, SEEK_CUR)) != -1
           && start_pos < (end_pos = lseek (fd, 0, SEEK_END)))

This end_pos = lseek (fd, 0, SEEK_END) is where the contents of the file are skipped. In file_lines() there is backwards scan counting the newlines.

lseek() is quite a simple system call, to reposition the file offset for read/write.


Oh it seems I missed the subtlety in this Q ;) It is all about reading linewise vs. blockwise. Normally it is a good idea to combine several passes into one complex pass. But here the algorithm only needs the very first newline.

Ole's two-parted perl script with sysread() illustrates how he switches from searching for the first newline(s) to reading a maximum block.

When tail works normal backways, it reads the last block and counts the newlines. It prints from there or reads in the next-to-last block.

| improve this answer | |
  • 4
    Except that in this use case, tail is counting from the beginning, not the end (from_start is set). – Stephen Kitt May 21 at 22:28

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.