How intelligent are unix utilities?

Question

Unix utilities like sort, find, grep, diff et al are very handy to perform quick tasks, sometimes without writing any code at all.

I wanted to know what algorithms do they internally use and how do intelligently decide a specific algorithm for a specific task? For example if sort gets a huge input file, will it use different algorithms for different data sizes?

Does grep intelligently switch algorithms while searching different data sets?

Answer 1

Unix is just a standard, it specifies what the implementations should do, but not how they should do it.

Therefore implementations of grep/sort/find will most likely use different approaches on different systems (and even one system, like Linux, there are concurrent implementations).

For Linux, you can always look into the source code.

Answer 2

You may be interested in this mailing list post by the original GNU grep author which explains a few of the GNU grep optimizations. Another enjoyable exploration by ridiculous_fish (author of Hex Fiend)

Answer 3

I wanted to know what algorithms do they internally use and how do intelligently decide a specific algorithm for a specific task? For example if sort gets a huge input file, will it use different algorithms for different data sizes?

That is an interesting question (+1 for that). I have no clue as to what the answer is, but if I were you, I'd look at the source code of typical GNU utilities to get an idea of their algorithms.

Does grep intelligently switch algorithms while searching different data sets?

I don't think so. Don't quote me since I cannot really tell you with 100% certainty, but I really don't think so. The UNIX philosophy of things is that one thing does one thing and one thing only. That's why we have several versions of grep (grep, egrep, fgrep).

Also, the idea is to do one thing and only one thing at run-time. Different behavior and algorithms can be configured as command-line arguments, so that the same program can act slightly differently (and possibly slightly more optimized) between runs. Good examples are the wc and diff command.

However, the behavioral adaptation is configuration-based (via cmd line arguments); they don't change/adapt behavior at run-time. It is typically an unnecessary complexity for the type of artifacts the UNIX tools aim to be.

Such complexity is more appropriate of more complex, less general purpose tools IMO.

Answer 4

The UNIX standard doesn't specify implementation details for the standard system tools, except for really rare cases. You can find the latest Single Unix Specification vesion here(warning: registration required).

With that in mind, every UNIX(System V and direct descendants like BSD, Solaris, Mac OS X, etc..) or UNIX based Operating System (far descendants or alikes: Linux, Minix) has its own implementations of the utilities described in the UNIX specification. For eg. take a look at FreeBSD's and Linux/GNU Coreutils. Beware that some tools are separate whole project by themselves like GNU diff or GNU grep. Also another fact is that some implementations of these tools might find their way into other UNIX like systems as standard then the ones they were initially written for, for e.g. some gnu coreutils in freebsd or GCC.

Bonus: To wrap your head around the UNIX family tree, take a look at this graph.

Answer 5

Does grep intelligently switch algorithms while searching different data sets?

I don't think so, but it does switch to the "fast" non-RE algorithm when given the -f flag (or invoked as fgrep).