Take the 2-minute tour ×
Unix & Linux Stack Exchange is a question and answer site for users of Linux, FreeBSD and other Un*x-like operating systems.. It's 100% free, no registration required.

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?

share|improve this question
2  
They are so intelligent they will one day take over the Earth. But for now you have to decide which ones you are going to use, such as grep, egrep, or fgrep. –  Keith Mar 15 '11 at 10:27
1  
But if you use egrep regularly and then suddenly switch to fgrep, it might decide to kill you in your sleep for being unfaithful. –  Shadur Mar 15 '11 at 11:47
1  
They are as intelligent as the hands that wield them. –  luis.espinal Mar 15 '11 at 12:06
add comment

5 Answers

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.

share|improve this answer
2  
To complete your answer: gnu.org/software/coreutils –  sahid Mar 15 '11 at 11:49
    
Why would you need to look at the source code? greps algorithms are well known and documented. It's even in the Wikipedia page for grep. link –  Deleted Account Mar 15 '11 at 14:07
    
@Deleted I think that you are mistaking principles with implementation. –  Let_Me_Be Mar 15 '11 at 14:22
    
@Let_Me_Be: The algorithm and even the implementation is well known and documented. link link –  Deleted Account Mar 15 '11 at 14:31
    
@Deleted Maybe I don't understand what you are trying to say, but that Linux grep from coreutils is using a specific algorithm, doesn't mean that all implementations use this algorithm. And yes, you are correct in that algorithms tend to be well known (since that's the point of designing them). –  Let_Me_Be Mar 15 '11 at 15:07
show 2 more comments

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)

share|improve this answer
add comment

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.

share|improve this answer
2  
The theme here is more of No, they are actually dumb!. You have to tell them exactly what the must do. Anyways, we don't want them be too smart on us you know. –  Tshepang Mar 17 '11 at 4:57
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
    
i.e. not really intelligent :) –  Tshepang Mar 17 '11 at 5:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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