7

I thought about whether this question is suitable for SE or not, I hope you agree it is.

Some time ago I asked on SE how to find text in files and leave the file with only the matching lines that contain the text I was searching for. The question is here: How to find text in files and only keep the respective matching lines using the terminal on OS X?

While the answer worked perfectly I now wonder, how come sed is so fast? In my use case, I had quite a lot of files which in total were about 30 Gb in size. The sed command ran in about 12 seconds which I never would have believed (working with a normal HDD). Within 12 seconds the command read through 30 Gb of text, truncating each file to only keep the respective lines I was filtering for. How does this work? (or: what is this sorcery?)

The actual command was:

find . -type f -exec sed -i'' '/\B\/foobar\b/!d' {} \;
  • What command you actually ran? – cuonglm Sep 12 '14 at 7:56
  • find . -type f -exec sed -i'' '/\B\/foobar\b/!d' {} \; – Alex Sep 12 '14 at 7:56
  • 1
    This seems like a rather general question. What kind of answer were you looking for? sed is written in C, and presumably optimized for speed. – Faheem Mitha Sep 12 '14 at 8:23
  • For a general answer :-) but more indepth maybe, some technical aspects, what it does that is it so fast? If there is a better place to ask this please advice me so – Alex Sep 12 '14 at 8:26
  • 1
2

The likely answer is that:

  1. The 30Gb file was not fragmented (or had very little fragmentation): all hard drives perform much better with sequential access (SSDs included) because they are able to cache large chunks of the file. This allows them to approach their maximum performance. Sequential access will help with all levels of caches.
  2. sed is a stream editor; it only processes one line at a time. This means that its memory footprint is minuscule. Unlike a text editor such as emacs or vim, it does not need to maintain the entire copy of the file in memory.
  3. You are editing the file in-place (with -i) which (as demonstrated by @Ramesh and also stated on wikipedia page) creates a temporary files which then becomes the old file.

All of this means that sed is able to perform almost the bare minimum of file operations: each line of the original file is read once, and only the lines that are matched are written.

Your choice of regular expressions also impacts performance, sometimes in very bad ways.: coding horror blog.

3

One wonderful example is sed uses a temporary file to actually save the contents and then replaces the original file. For example, you can do a simple testing to find this.

cat test
This is a test file. 

Now, run ls -li to check the inode number.

ls -li test
2368770 -rw-r--r-- 1 root root 22 Sep 12 08:46 test

Now, issue the below sed command to add a blank line.

sed -i 's/2/B/' test

After changing the file, issue the ls command again and check the inode number.

ls -li test
2368753 -rw-r--r-- 1 root root 22 Sep 12 08:48 test

We can see that the inode number has infact changed. So instead of copying to the same file sed creates a new temporary file and copies the contents to the new temp file and then deletes the original file and renames the tmp file in sync with the original file which is one reason why the file operations are really faster.

Quoting from wikipedia page,

sed is a line-oriented text processing utility: it reads text, line by line, from an input stream or file, into an internal buffer called the pattern space. Each line read starts a cycle. To the pattern space, sed applies one or more operations which have been specified via a sed script. sed implements a programming language with about 25 commands that specify the operations on the text. For each line, after running the script sed ordinarily outputs the pattern space (the input line as modified by the script) and begins the cycle again with the next line.

To understand more on the pattern space and hold space concepts of sed, you should read the answer here.

When sed reads a file line by line, the line that has been currently read is inserted into the pattern buffer (pattern space). Pattern buffer is like the temporary buffer, the scratchpad where the current information is stored. When you tell sed to print, it prints the pattern buffer.

Hold buffer / hold space is like a long-term storage, such that you can catch something, store it and reuse it later when sed is processing another line. You do not directly process the hold space, instead, you need to copy it or append to the pattern space if you want to do something with it.

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.