Butuh sesuatu yang lebih cepat daripada "wc -l"

12

Untuk file yang sangat besar seperti 1GB wc -lterjadi lambat. Apakah kita memiliki cara yang lebih cepat menghitung jumlah baris baru untuk file tertentu?

prosti
sumber
25
Beli disk yang lebih cepat? Mengingat bahwa setiap byte input harus diperiksa untuk 0x0Ainesnya, I / O tidak diragukan lagi adalah hambatannya.
thrig
2
Jika Anda menduga wcmemiliki terlalu banyak overhead, Anda dapat mencoba menerapkannya sendiri foreach byte in file: if byte == '\n': linecount++. Jika diimplementasikan dalam C atau assembler saya tidak berpikir itu akan menjadi lebih cepat, kecuali mungkin dalam ruang kernel pada RTOS dengan prioritas tertinggi (atau bahkan menggunakan interupsi untuk itu - Anda tidak dapat melakukan hal lain dengan sistem. .. baiklah, saya ngelantur ;-))
Murphy
3
Dan hanya untuk merasakan skala saya melakukan cepat time wc -l some_movie.avipada file yang tidak di-cache, menghasilkan 5172672 some_movie.avi -- real 0m57.768s -- user 0m0.255s -- sys 0m0.863s. Yang pada dasarnya membuktikan @ thrig benar, I / O menghancurkan kinerja Anda dalam hal ini.
Murphy
10
Cara terbaik untuk menunjukkan itu adalah bottlneck IO disk, lakukan time wc -l some_large_file_smaller_than_cachedua kali berturut-turut dengan cepat dan lihat seberapa cepat operasi kedua, lalu time wc -l some_large_file_larger_than_cachedan lihat bagaimana waktu tidak berubah di antara proses yang berjalan. Untuk file ~ 280MB di sini, waktunya berubah dari 1,7 detik menjadi 0,2 detik, tetapi untuk file 2GB adalah 14 detik dua kali.
EightBitTony
1
Seberapa lambat terlalu lambat untuk Anda? Apa yang /usr/bin/time wc -l <file>dikatakan? Apa perangkat keras Anda? Apakah lebih cepat jika Anda menjalankan perintah berulang kali? Kami benar-benar memerlukan informasi lebih lanjut;)
marcelm

Jawaban:

21

Anda dapat mencoba menulis dalam 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;
}

Simpan dalam mis. wcl.c, Kompilasi mis. Dengan gcc wcl.c -O2 -o wcldan jalankan dengan

<yourFile ./wcl

Ini menemukan baris baru ditaburi dalam file 1GB di sistem saya di sekitar 370ms (berjalan berulang). (Meningkatkan ukuran buffer sedikit meningkatkan waktu, yang diharapkan - BUFSIZ harus mendekati optimal). Ini sangat sebanding dengan ~ 380ms yang saya dapatkan wc -l.

Mmaping memberi saya waktu yang lebih baik sekitar 280ms , tetapi tentu saja memiliki keterbatasan untuk dibatasi pada file nyata (tidak ada FIFOS, tidak ada input terminal, dll.):

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

Saya membuat file pengujian dengan:

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

dan menambahkan beberapa baris baru uji dengan:

 $ echo >> 1GB 

dan hex editor.

PSkocik
sumber
Saya terkejut dengan hasil mmap TBH. Saya dulu berpikir mmaping lebih cepat daripada membaca / menulis, tetapi kemudian saya melihat beberapa tolok ukur linux yang menunjukkan sebaliknya. Sepertinya ini sangat benar dalam kasus ini.
PSkocik
4
mmap akan mendapatkan hasil yang jauh lebih baik di linux karena ia akan memetakan ke halaman besar hari ini, dan kehilangan TLB adalah sloooowwwwwww.
jthill
Mungkin ada beberapa manfaat untuk membaca bagian-bagian berbeda dari file dalam utas terpisah (mis. Dengan forloop OpenMP ) sehingga beberapa kemajuan dapat dibuat sementara satu utas terhenti menunggu input. Tetapi di sisi lain, itu mungkin menghambat penjadwalan I / O, jadi yang bisa saya rekomendasikan adalah mencobanya, dan ukur!
Toby Speight
The read()Versi dapat mengambil manfaat dari membaca-depan.
Barmar
1
@TobySpeight Ya, multithreading mungkin mempercepatnya. Juga mencari pemindaian dua byte sekaligus melalui tabel pencarian 2 ^ 16 memberikan kecepatan yang cukup baik terakhir kali saya bermain dengannya.
PSkocik
18

Anda dapat meningkatkan solusi yang disarankan oleh @pskocik dengan mengurangi jumlah panggilan read. Ada banyak panggilan untuk membaca BUFSIZpotongan dari file 1Gb. Pendekatan yang biasa dilakukan adalah dengan meningkatkan ukuran buffer:

  • hanya untuk bersenang-senang, cobalah meningkatkan ukuran buffer dengan faktor 10. Atau 100. Pada Debian 7 saya, BUFSIZadalah 8192. Dengan program asli, itu 120 ribu operasi baca. Anda mungkin dapat membeli buffer input 1Mb untuk menguranginya dengan faktor 100.
  • untuk pendekatan yang lebih optimal, aplikasi dapat mengalokasikan buffer sebesar file, membutuhkan operasi baca tunggal. Itu bekerja cukup baik untuk file "kecil" (meskipun beberapa pembaca memiliki lebih dari 1Gb pada mesin mereka).
  • akhirnya, Anda bisa bereksperimen dengan I / O yang dipetakan dengan memori, yang menangani alokasi seperti itu.

Saat membandingkan berbagai pendekatan, Anda mungkin perlu diingat bahwa beberapa sistem (seperti Linux) menggunakan sebagian besar memori mesin Anda yang tidak digunakan sebagai cache disk. Beberapa waktu yang lalu (hampir 20 tahun yang lalu, disebutkan dalam FAQ keji ), saya bingung dengan hasil yang tidak terduga baik dari algoritma paging (tidak terlalu baik) yang telah saya kembangkan untuk menangani kondisi memori rendah dalam editor teks. Dijelaskan kepada saya bahwa itu berjalan cepat karena program ini bekerja dari buffer memori yang digunakan untuk membaca file, dan bahwa hanya jika file tersebut dibaca ulang atau ditulis akan ada perbedaan dalam kecepatan.

Hal yang sama berlaku untuk mmap(dalam kasus lain masih dalam daftar tugas saya untuk dimasukkan ke dalam FAQ, pengembang melaporkan hasil yang sangat baik dalam skenario di mana cache disk adalah alasan sebenarnya untuk perbaikan). Mengembangkan tolok ukur membutuhkan waktu dan perhatian untuk menganalisis alasan kinerja yang baik (atau buruk).

Bacaan lebih lanjut:

Thomas Dickey
sumber
2
Anda melebih-lebihkan pengaruh ukuran buffer di atas ambang tertentu. Biasanya, meningkatkan ukuran buffer melampaui 4KB-ish tidak banyak membantu, dan mungkin malah merugikan karena dapat mendorong buffer keluar dari cache L1. Di komputer saya, pengujian dengan dd, menggunakan buffer 1MB lebih lambat dari 8KB. Nilai default 8KB untuk wc sebenarnya dipilih dengan cukup baik, itu akan mendekati optimal untuk berbagai sistem.
marcelm