12

I have to read a large file and before I start reading it, I need to know the total number of lines in the file (which are in millions).

I have implemented a lot of solutions and have found one. But during my search I was thinking to look at how wc -l works. I couldn't find anything on Google.

Though I have found a solution to my problem, I would still like to know how wc -l works since it can calculate the number of lines of a file with 92 Million lines in a few seconds!

How?

1

3 Answers 3

22

It reads the entire file and counts the number of line-endings. Counting line endings is really cheap; most of the time spent is reading the file. If the file happens to be (mostly) in the buffer cache, that will be cheap too. Otherwise, it will depend on the speed of your file storage.

In other words, there is no magic.

2
  • It reads the entire file and counts number of line endings? To get to the line ending, doesn't it basically read the whole line till it reaches the end? And that would mean it read the whole file, right? Jul 8, 2013 at 23:48
  • @detraveller: yes, it reads the entire file, like I said. It doesn't read it line by line, or all at once, but it reads every character and counts how many of those characters are line-end characters.
    – rici
    Jul 9, 2013 at 0:31
8

WC just reads the file in blocks of raw bytes (preferable in multiples of the natural block-size of the underlying filesystem on which the file is located).
Then it just scans through the buffer counting the end-of-line characters. (It also counts spaces, tabs, form-feeds and other special characters, just in case you wanted other information than the -l output.)

Reading from disk is the costly part in terms of speeds. The scanning of the buffer takes neglect-able time compared to that.

Say you've got a 90 million lines with on average 100 characters per line.
That is around 9.000.000.000 characters or about 860 MB.
A decent PC with a SATA-3Gb/s drive will do that under 10 seconds. Even on a relatively slow filesystem with some other activity going on at the same time.
A fast machine with some performance tuning and a optimized filesystem can do it under 5 seconds, even without having to resort to SATA-6G and a SSD drive.

3
  • it just scans through the buffer counting the end-of-line (\n) characters -- "-l, --lines print the newline counts\n\" -- extracted from wc.c Jul 12, 2013 at 18:24
  • @RahulPatil Most implementations do a lot more than just counting newlines. See the example mentioned in the top comment above. That is the source of wc as used in the Linux core utilities.
    – Tonny
    Jul 12, 2013 at 19:16
  • yes.. I have seen that.. just I mention because, question about wc -l.. sorry... Jul 12, 2013 at 19:18
3

Welcome to the world of free software. You can always look at the source code

Although I must admit that I'm not a C programmer, so I'm not the one that can really explain the code for you (and I would be insterested myself).

What I know is that since wc does not open the file itself, but asks OS to do it, this largely depends on the OS, and of course, how the file is stored. Apart from that, I'd expect that correct programming practices must be in place, e.g. not trying to read the file as whole at once, etc.

6
  • What do you mean by saying 'not trying to read the whole file at once'? Jul 8, 2013 at 17:36
  • I mean loading the file to memory, say, to a single string / array. In Perl community this is called slurping, and it's a quick & dirty solution which is OK when you know you will be reading few lines, but feeding really huge file into memory at once is seldom a good idea. Jul 8, 2013 at 17:43
  • 1
    On the other hand, you can read, say, 64 KiB, count newlines and throw it away, repeat... That way you'll eat up something over 64 KiB at most, no matter how huge the file is. (It's less easy when you realize that newline can have 2 bytes and thus become split between 2 chunks; now that's where the fun starts) Jul 8, 2013 at 17:45
  • Not too important, but: "since wc does not open the file itself, but asks OS to do it" -- not sure what you mean by that, but I doubt this is correct. It's certainly reading all characters by itself.
    – Arjan
    Jul 8, 2013 at 17:49
  • 2
    @Arjan Although, to be really correct: excluding embedded systems, programs hardly really do the reading themselves, whole point of Kernel and OS is that it does the job for them. In fact, open(), close(), read() (be it Linux, Windows, socket or file) are all system calls that actual programs have no idea of inner workings. Jul 8, 2013 at 17:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .