Potrzebujesz czegoś, co jest szybsze niż „wc -l”

W przypadku naprawdę dużego pliku, takiego jak 1 GB, wc -ldzieje się to powoli. Czy mamy szybszy sposób obliczania liczby nowych linii dla określonego pliku?

Możesz spróbować napisać w 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;
}

Zapisz np., wcl.cSkompiluj np. Z gcc wcl.c -O2 -o wcli uruchom z

<yourFile ./wcl

To powoduje, że nowe linie są posypane plikiem 1 GB w moim systemie w około 370 ms (powtarzane przebiegi). (Zwiększenie rozmiarów buforów nieznacznie wydłuża czas, którego należy się spodziewać - BUFSIZ powinien być bliski optymalnego). Jest to bardzo porównywalne do ~ 380 ms, z którego otrzymuję wc -l.

Mmaping daje mi lepszy czas około 280 ms , ale oczywiście ma ograniczenie polegające na ograniczeniu się do rzeczywistych plików (bez FIFOS, bez wejścia na terminal itp.):

#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;
}

Plik testowy utworzyłem za pomocą:

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

i dodał kilka nowych linii testowych z:

 $ echo >> 1GB 

i edytor szesnastkowy.

Możesz ulepszyć rozwiązanie sugerowane przez @pskocik, zmniejszając liczbę połączeń z read. Istnieje wiele wywołań do odczytu BUFSIZfragmentów z pliku 1 Gb. Zwykłym podejściem do tego jest zwiększenie rozmiaru bufora:

• dla zabawy spróbuj zwiększyć rozmiar bufora 10 razy. Lub 100. W moim Debianie 7 BUFSIZjest 8192. W przypadku oryginalnego programu jest to 120 tysięcy operacji odczytu. Prawdopodobnie możesz sobie pozwolić na bufor wejściowy 1 Mb, aby zmniejszyć to o współczynnik 100.
• dla bardziej optymalnego podejścia aplikacje mogą przydzielić bufor tak duży jak plik, co wymaga pojedynczej operacji odczytu. Działa to wystarczająco dobrze w przypadku „małych” plików (choć niektóre czytniki mają na swoim komputerze więcej niż 1 Gb).
• wreszcie możesz eksperymentować z I / O zamapowanymi w pamięci, które obsługują alokację jako taką.

Podczas porównywania różnych podejść możesz mieć na uwadze, że niektóre systemy (takie jak Linux) wykorzystują większość nieużywanej pamięci komputera jako pamięć podręczną dysku. Jakiś czas temu (prawie 20 lat temu, wspomniane w nikczemnym FAQ ), byłem zaskoczony nieoczekiwanie dobrymi wynikami z (niezbyt dobrego) algorytmu stronicowania, który opracowałem do obsługi warunków niskiej pamięci w edytorze tekstu. Wyjaśniono mi, że działał szybko, ponieważ program działał z buforów pamięci używanych do odczytu pliku, i że tylko jeśli plik zostanie ponownie odczytany lub zapisany, będzie różnica prędkości.

To samo dotyczy mmap(w innym przypadku, który wciąż znajduje się na mojej liście rzeczy do zrobienia w celu włączenia do FAQ, deweloper zgłosił bardzo dobre wyniki w scenariuszu, w którym pamięć podręczna dysku była faktycznym powodem poprawy). Opracowanie testów porównawczych wymaga czasu i staranności, aby przeanalizować przyczyny dobrej (lub złej) wydajności.

Dalsza lektura:

• Czy używanie większego bufora jest przydatne?
• mmap () vs. bloki odczytu
• mmap, munmap - mapuj lub usuwaj mapowanie plików lub urządzeń do pamięci (pokazuje przykładowy program)
• 13.7 We / wy odwzorowane w pamięci (biblioteka GNU C)
• Jak wyczyścić pamięć podręczną we / wy dysku w systemie Linux
• Jak opróżniasz bufory i pamięć podręczną w systemie Linux?