Need something that is faster than "wc -l"

Question

For a really big file like 1GB wc -l happens to be slow. Do we have a faster way calculating the number of newlines for a particular file?

Answer 1

You can try to write in C:

#include <unistd.h>
#include <stdio.h>
#include <string.h>
int main(){
  char buf[BUFSIZ];
  int nread;
  size_t nfound=0;
  while((nread=read(0, buf, BUFSIZ))>0){
    char const* p;
    for(p=buf; p=memchr(p,'\n',nread-(p-buf)); nfound++,p++) {;}
  }
  if(nread<0) { perror("Error"); return 1; }
  printf("%lu\n", nfound);
  return 0;
}

Save in e.g., wcl.c, compile e.g., with gcc wcl.c -O2 -o wcl and run with

<yourFile ./wcl

This finds newlines sprinkled in a 1GB file on my system in about 370ms (repeated runs). (Increasing buffer sizes slightly increases the time, which is to be expected -- BUFSIZ should be close to optimal). This is very comparable to the ~380ms I'm getting from wc -l.

Mmaping gives me a better time of about 280ms, but it of course has the limitation of being limited to real files (no FIFOS, no terminal input, etc.):

#include <stdio.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <unistd.h>
int main(){
  struct stat sbuf;
  if(fstat(0, &sbuf)<0){ perror("Can't stat stdin"); return 1; }

  char* buf = mmap(NULL, sbuf.st_size, PROT_READ, MAP_PRIVATE, 0/*stdin*/, 0/*offset*/);
  if(buf == MAP_FAILED){ perror("Mmap error"); return 1; } 

  size_t nread = sbuf.st_size, nfound=0;
  char const* p;
  for(p=buf; p=memchr(p,'\n',nread-(p-buf)); nfound++,p++) {;}

  printf("%lu\n", nfound);
  return 0;
}

I created my test file with:

 $ dd if=/dev/zero of=file bs=1M count=1042 

and added some test newlines with:

 $ echo >> 1GB 

and a hex editor.

Answer 2

You can improve on the solution suggested by @pskocik by reducing the number of calls to read. There are a lot of calls to read BUFSIZ chunks from a 1Gb file. The usual approach to doing this is by increasing the buffer size:

• just for fun, try increasing the buffer-size by a factor of 10. Or 100. On my Debian 7, BUFSIZ is 8192. With the original program, that's 120 thousand read operations. You can probably afford a 1Mb input buffer to reduce that by a factor of 100.
• for a more optimal approach, applications may allocate a buffer as large as the file, requiring a single read operation. That works well enough for "small" files (though some readers have more than 1Gb on their machine).
• finally, you could experiment with memory-mapped I/O, which handles the allocation as such.

When benchmarking the various approaches, you might keep in mind that some systems (such as Linux) use most of your machine's unused memory as a disk cache. A while back (almost 20 years ago, mentioned in the vile FAQ), I was puzzled by unexpectedly good results from a (not very good) paging algorithm which I had developed to handle low-memory conditions in a text editor. It was explained to me that it ran fast because the program was working from the memory buffers used to read the file, and that only if the file were re-read or written would there be a difference in speed.

The same applies to mmap (in another case still on my to-do list to incorporate into an FAQ, a developer reported very good results in a scenario where the disk cache was the actual reason for improvement). Developing benchmarks takes time and care to analyze the reasons for the good (or bad) performance.

Further reading:

• Is using a bigger buffer useful?
• mmap() vs. reading blocks
• mmap, munmap - map or unmap files or devices into memory (shows a sample program)
• 13.7 Memory-mapped I/O (The GNU C Library)
• How to purge disk I/O caches on Linux
• How do you empty the buffers and cache on a Linux system?