Kenapa kita begitu lambat?

Mengapa utilitas wc sangat lambat?

Ketika saya menjalankannya pada file besar, dibutuhkan sekitar 20 kali lebih lama dari md5sum:

MyDesktop:/tmp$ dd if=/dev/zero bs=1024k count=1024 of=/tmp/bigfile
1024+0 records in
1024+0 records out
1073741824 bytes (1.1 GB) copied, 0.687094 s, 1.6 GB/s

MyDesktop:/tmp$ time wc /tmp/bigfile 
         0          0 1073741824 /tmp/bigfile

real    0m45.969s
user    0m45.424s
sys     0m0.424s

MyDesktop:/tmp$ time md5sum /tmp/bigfile 
cd573cfaace07e7949bc0c46028904ff  /tmp/bigfile

real    0m2.520s
user    0m2.196s
sys     0m0.316s

Ini bukan hanya kondisi tepi aneh yang disebabkan oleh file yang penuh dengan nol, saya melihat perbedaan kinerja yang sama bahkan jika file diisi dengan data acak atau file teks.

(ini ada di Ubuntu 13.04, 64 bit)

performance wc Johnny
sumber

Catatan untuk mereka yang hanya peduli dengan jumlah baris: wc-l <filename> jauh lebih cepat pada file yang sangat besar.

Jawaban:

Jadi saya pergi ke sumbernya, dan sepertinya kelambanan dalam menangani karakter byte ganda. Intinya, untuk setiap karakter yang dibaca, perlu memanggil mbrtowc()untuk mencoba mengubahnya menjadi karakter lebar, maka karakter lebar itu diuji untuk melihat apakah itu pemisah kata, pemisah garis, dll.

Memang, jika saya mengubah LANGvariabel lokal saya dari default en_US.UTF-8(UTF-8 adalah set karakter multibyte) dan mengaturnya ke " C" (set karakter byte tunggal sederhana), wcdapat menggunakan optimasi byte tunggal, yang mempercepatnya jauh, hanya membutuhkan sekitar seperempat selama sebelumnya.

Selain itu, ia hanya perlu memeriksa setiap karakter jika itu menghitung kata ( -w), panjang baris ( -L) atau karakter ( -m). Jika hanya melakukan byte dan / atau jumlah baris, itu dapat melewati penanganan karakter lebar dan kemudian berjalan sangat cepat - lebih cepat dari md5sum.

Aku berlari melalui gprof, dan fungsi-fungsi yang digunakan untuk menangani karakter multibyte ( mymbsinit(), mymbrtowc(), myiswprint(), dll) yang mengambil sekitar 30% dari waktu eksekusi saja, dan kode bahwa langkah-langkah melalui buffer jauh lebih kompleks karena harus menangani langkah-langkah berukuran variabel melalui buffer untuk karakter berukuran variabel, serta menjejalkan setiap karakter yang diselesaikan sebagian yang span buffer kembali ke awal buffer sehingga dapat ditangani di waktu berikutnya.

Sekarang saya tahu apa yang harus dicari, saya menemukan beberapa posting menyebutkan lambatnya utf-8 dengan beberapa utilitas:

/programming/13913014/grepping-a-huge-file-80gb-any-way-to-speed-it-up http://dtrace.org/blogs/brendan/2011/12/08 / 2000x-performance-win /

Johnny
sumber

Oh, baru sadar kamu OP. : p

Ivan Chau

Meskipun ini adalah jawaban yang paling banyak dipilih, itu tidak relevan. md5sumtidak akan pernah mengizinkan Anda untuk menghitung nomor kata dan wctidak akan menghitung hash md5 dari file! Ini seperti bertanya mengapa mobil saya sangat lambat dibandingkan dengan mesin tik saya saat menulis teks.

user49468

@ user49468: Masuk akal untuk menganggap bahwa keduanya terikat IO, karena keduanya harus membaca setiap byte dari file input. Jawaban ini membuktikan bahwa wcsebenarnya terikat CPU, saat memproses karakter multi-byte.

MSalters

@ user49468: wc dan md5sum dapat melakukan hal yang berbeda, tetapi keduanya membaca file dan melakukan perhitungan yang relatif sederhana, satu menghitung checksum, satu menghitung byte, pemisah kata, dan baris baru. Yah, saya pikir itu sederhana, tetapi tidak memperhitungkan kompleksitas tambahan set karakter multibyte. Ini lebih seperti bertanya "Mengapa mobil saya 20 kali lebih cepat pergi ke toko daripada minivan saya?" Anda akan mengharapkan beberapa perbedaan antara keduanya, tetapi tidak perbedaan 20X.

Johnny

@Johnny you car / minivan perbandingan tidak memiliki aspek yang dirancang untuk membawa Anda ke toko. Jadi ada perbandingan kecepatan. Membandingkan mobil Anda dengan kendaraan melukis garis lebih cocok. Hanya karena keduanya menggunakan jalan-jalan, kecepatan mereka tidak relevan karena pelukis garis tidak cocok untuk berbelanja dan sebaliknya.

user49468

Hanya tebakan tetapi Anda agak membandingkan apel dengan jeruk sehubungan dengan apa wcyang dilakukan vs apa md5sumyang dilakukan.

tugas md5sum

Saat md5summemproses file, ia hanya membuka file sebagai stream dan kemudian mulai menjalankan stream melalui fungsi MD5 checksum yang membutuhkan memori sangat sedikit. Ini pada dasarnya CPU & disk I / O terikat.

tugas wc

Saat wcdijalankan, ia melakukan lebih dari sekadar mengurai file karakter pada satu waktu. Itu harus benar-benar menganalisis struktur file, garis pada satu waktu membuat penentuan di mana batas antara karakter dan apakah itu kata batas atau tidak.

Contoh

Pikirkan string berikut dan bagaimana masing-masing algoritma harus bergerak melalui mereka ketika mereka menguraikannya:

“Hello! Greg”
“Hello!Greg”
“Hello\nGreg”
“A.D.D.”
“Wow, how great!”
“wow     \n\n\n    great”
“it was a man-eating shark.”

Untuk MD5, itu secara sepintas bergerak melalui string ini karakter pada suatu waktu. Untuk wcitu harus memutuskan apa kata & garis batas dan melacak jumlah kemunculan yang dilihatnya.

Diskusi wc tambahan

Saya menemukan tantangan pengkodean ini dari 2006 yang membahas implementasi wcdi .NET. Kesulitannya cukup jelas ketika Anda melihat beberapa kode semu, jadi ini mungkin membantu untuk mulai menjelaskan mengapa wctampaknya jauh lebih lambat daripada operasi lain.

slm
sumber

Anda menggambarkan sesuatu yang berbeda dari perintah standar Unix wc (setidaknya, bukan yang datang dengan Ubuntu). Itu wc tidak menghitung kata - kata unik , hanya kata-kata, jadi "halo halo dunia" adalah 3 kata, bukan 2.

Johnny

Berdasarkan teori ini, itu terdengar seperti tugas yang lebih sederhana, seperti menghitung garis, akan berjalan lebih cepat. Apakah mengubah 'wc' untuk menentukan jumlah baris memodifikasi hasil secara substansial? 'wc-l'

Joshua Miller

@ Johnny - Saya tidak pernah mengatakan itu menghitung kata-kata unik yang Anda katakan. wcmenghitung banyak hal saat mem-parsing file. Itu menghitung jumlah kata, baris, dan byte saat mem-parsing file. Baca halaman manual!

slm

@ JoshuaMiller - Tidak jelas apakah wchanya menghitung garis membatasi penguraian internal sehingga hanya menghitung hal-hal ini atau hanya melaporkan hasil garis, meskipun masih menghitung semuanya.

slm

@slm Anda memang mengatakan itu menghitung kata-kata unik, contoh Anda mengatakan “Halo! Greg ”menghasilkan Halo 1, Greg 1 , yaitu jumlah untuk setiap kata. Dan proyek Net yang Anda tautkan dengan mengatakan "Salah satu tugas utamanya adalah untuk pergi melalui serangkaian data dan menghitung jumlah pengulangan kata yang diberikan. Misalnya diberi kalimat" Halo, ya halo "itu akan memberi tahu Anda bahwa kata Halo digunakan dua kali dan kata ya digunakan sekali. " Padahal pada kenyataannya hasil gema "Halo, ya halo" | wc --words , is "3", not "Hello: 2, Yes: 1"

Johnny