Saya ingin membandingkan baris-baris input string dari stdin menggunakan Python dan C ++ dan terkejut melihat kode C ++ saya menjalankan urutan besarnya lebih lambat daripada kode Python yang setara. Karena C ++ saya berkarat dan saya belum menjadi ahli Pythonista, tolong beri tahu saya jika saya melakukan sesuatu yang salah atau jika saya salah mengerti sesuatu.
(Jawaban TLDR: sertakan pernyataan: cin.sync_with_stdio(false)
atau gunakan fgets
saja.
Hasil TLDR: gulirkan semuanya ke bawah pertanyaan saya dan lihat tabel.)
Kode C ++:
#include <iostream>
#include <time.h>
using namespace std;
int main() {
string input_line;
long line_count = 0;
time_t start = time(NULL);
int sec;
int lps;
while (cin) {
getline(cin, input_line);
if (!cin.eof())
line_count++;
};
sec = (int) time(NULL) - start;
cerr << "Read " << line_count << " lines in " << sec << " seconds.";
if (sec > 0) {
lps = line_count / sec;
cerr << " LPS: " << lps << endl;
} else
cerr << endl;
return 0;
}
// Compiled with:
// g++ -O3 -o readline_test_cpp foo.cpp
Setara Python:
#!/usr/bin/env python
import time
import sys
count = 0
start = time.time()
for line in sys.stdin:
count += 1
delta_sec = int(time.time() - start_time)
if delta_sec >= 0:
lines_per_sec = int(round(count/delta_sec))
print("Read {0} lines in {1} seconds. LPS: {2}".format(count, delta_sec,
lines_per_sec))
Inilah hasil saya:
$ cat test_lines | ./readline_test_cpp
Read 5570000 lines in 9 seconds. LPS: 618889
$cat test_lines | ./readline_test.py
Read 5570000 lines in 1 seconds. LPS: 5570000
Saya harus mencatat bahwa saya sudah mencoba keduanya di Mac OS X v10.6.8 (Snow Leopard) dan Linux 2.6.32 (Red Hat Linux 6.2). Yang pertama adalah MacBook Pro, dan yang terakhir adalah server yang sangat gemuk, bukan berarti ini terlalu relevan.
$ for i in {1..5}; do echo "Test run $i at `date`"; echo -n "CPP:"; cat test_lines | ./readline_test_cpp ; echo -n "Python:"; cat test_lines | ./readline_test.py ; done
Test run 1 at Mon Feb 20 21:29:28 EST 2012
CPP: Read 5570001 lines in 9 seconds. LPS: 618889
Python:Read 5570000 lines in 1 seconds. LPS: 5570000
Test run 2 at Mon Feb 20 21:29:39 EST 2012
CPP: Read 5570001 lines in 9 seconds. LPS: 618889
Python:Read 5570000 lines in 1 seconds. LPS: 5570000
Test run 3 at Mon Feb 20 21:29:50 EST 2012
CPP: Read 5570001 lines in 9 seconds. LPS: 618889
Python:Read 5570000 lines in 1 seconds. LPS: 5570000
Test run 4 at Mon Feb 20 21:30:01 EST 2012
CPP: Read 5570001 lines in 9 seconds. LPS: 618889
Python:Read 5570000 lines in 1 seconds. LPS: 5570000
Test run 5 at Mon Feb 20 21:30:11 EST 2012
CPP: Read 5570001 lines in 10 seconds. LPS: 557000
Python:Read 5570000 lines in 1 seconds. LPS: 5570000
Adendum dan rekap benchmark kecil
Untuk kelengkapan, saya pikir saya akan memperbarui kecepatan baca untuk file yang sama pada kotak yang sama dengan kode C ++ asli (disinkronkan). Sekali lagi, ini untuk file baris 100 juta pada disk cepat. Inilah perbandingannya, dengan beberapa solusi / pendekatan:
Implementation Lines per second
python (default) 3,571,428
cin (default/naive) 819,672
cin (no sync) 12,500,000
fgets 14,285,714
wc (not fair comparison) 54,644,808
<iostream>
kinerja menyebalkan. Bukan pertama kali itu terjadi. 2) Python cukup pintar untuk tidak menyalin data dalam for for loop karena Anda tidak menggunakannya. Anda dapat menguji ulang mencoba menggunakanscanf
dan achar[]
. Sebagai alternatif, Anda dapat mencoba menulis ulang loop sehingga ada sesuatu yang dilakukan dengan string (mis. Simpan huruf 5 dan hasilkan sebagai hasilnya).cin.eof()
!! Masukkangetline
panggilan ke dalam pernyataan 'jika`.wc -l
cepat karena membaca aliran lebih dari satu baris sekaligus (mungkinfread(stdin)/memchr('\n')
kombinasi). Hasil python berada dalam urutan yang sama besarnya misalnya,wc-l.py
Jawaban:
Secara default,
cin
disinkronkan dengan stdio, yang menyebabkannya menghindari buffering input. Jika Anda menambahkan ini ke bagian atas utama Anda, Anda akan melihat kinerja yang jauh lebih baik:Biasanya, ketika aliran input buffer, alih-alih membaca satu karakter pada suatu waktu, aliran akan dibaca dalam potongan yang lebih besar. Ini mengurangi jumlah panggilan sistem, yang biasanya relatif mahal. Namun, karena
FILE*
berbasisstdio
daniostreams
sering memiliki implementasi terpisah dan oleh karena itu memisahkan buffer, ini dapat menyebabkan masalah jika keduanya digunakan bersama. Sebagai contoh:Jika lebih banyak input dibaca
cin
daripada yang sebenarnya dibutuhkan, maka nilai integer kedua tidak akan tersedia untukscanf
fungsi, yang memiliki buffer independen sendiri. Ini akan menghasilkan hasil yang tidak terduga.Untuk menghindari ini, secara default, stream disinkronkan dengan
stdio
. Satu cara umum untuk mencapai ini adalahcin
membaca setiap karakter satu per satu sesuai kebutuhan menggunakanstdio
fungsi. Sayangnya, ini memperkenalkan banyak overhead. Untuk sejumlah kecil input, ini bukan masalah besar, tetapi ketika Anda membaca jutaan baris, penalti kinerja sangat signifikan.Untungnya, perancang perpustakaan memutuskan bahwa Anda juga harus dapat menonaktifkan fitur ini untuk mendapatkan peningkatan kinerja jika Anda tahu apa yang Anda lakukan, jadi mereka menyediakan
sync_with_stdio
metode tersebut.sumber
fscanf
panggilan, karena itu cukup sederhana tidak berfungsi seperti halnya Python. Python harus mengalokasikan memori untuk string, mungkin beberapa kali karena alokasi yang ada dianggap tidak memadai - persis seperti pendekatan C ++std::string
. Tugas ini hampir pasti I / O terikat dan ada terlalu banyak FUD berkeliling tentang biaya membuatstd::string
objek di C ++ atau menggunakan<iostream>
dalam dan dari dirinya sendiri.sync_with_stdio()
ini adalah fungsi anggota statis, dan panggilan ke fungsi ini pada objek streaming mana pun (mis.cin
) Mengaktifkan atau menonaktifkan sinkronisasi untuk semua objek iostream standar.Hanya karena penasaran saya telah melihat apa yang terjadi di bawah tenda, dan saya telah menggunakan dtruss / strace pada setiap tes.
C ++
syscalls
sudo dtruss -c ./a.out < in
Python
syscalls
sudo dtruss -c ./a.py < in
sumber
Saya beberapa tahun di belakang sini, tetapi:
Dalam 'Edit 4/5/6' dari pos asli, Anda menggunakan konstruksi:
Ini salah dalam beberapa cara berbeda:
Anda sebenarnya menentukan waktu pelaksanaan
cat
, bukan tolok ukur Anda. Penggunaan CPU 'pengguna' dan 'sistem' yang ditampilkan olehtime
mereka adalahcat
, bukan program yang Anda patok. Lebih buruk lagi, waktu 'nyata' juga belum tentu akurat. Bergantung pada implementasicat
dan jalur pipa di OS lokal Anda, ada kemungkinan bahwacat
menulis buffer raksasa terakhir dan keluar jauh sebelum proses pembaca menyelesaikan pekerjaannya.Penggunaan
cat
tidak perlu dan pada kenyataannya kontraproduktif; Anda menambahkan bagian yang bergerak. Jika Anda menggunakan sistem yang cukup lama (yaitu dengan satu CPU dan - pada generasi komputer tertentu - I / O lebih cepat dari CPU) - fakta yangcat
berjalan secara substansial dapat mewarnai hasil. Anda juga tunduk pada buffering input dan output apa pun dan pemrosesan lainnya yangcat
dapat dilakukan. (Ini kemungkinan akan memberi Anda penghargaan 'Penggunaan Kucing Tidak Berguna' jika saya adalah Randal Schwartz.Konstruksi yang lebih baik adalah:
Dalam pernyataan ini, itu adalah shell yang membuka big_file, meneruskannya ke program Anda (yah, sebenarnya
time
yang kemudian menjalankan program Anda sebagai subprocess) sebagai deskriptor file yang sudah terbuka. 100% pembacaan file sepenuhnya merupakan tanggung jawab program yang Anda coba patok. Ini membuat Anda membaca nyata kinerjanya tanpa komplikasi palsu.Saya akan menyebutkan dua kemungkinan, tetapi sebenarnya salah, 'perbaikan' yang juga dapat dipertimbangkan (tapi saya 'beri nomor' secara berbeda karena ini bukan hal-hal yang salah di pos asli):
A. Anda dapat 'memperbaiki' ini dengan menentukan waktu hanya program Anda:
B. atau dengan mengatur waktu seluruh pipa:
Ini salah karena alasan yang sama dengan # 2: mereka masih menggunakan yang
cat
tidak perlu. Saya menyebutkannya karena beberapa alasan:mereka lebih 'alami' untuk orang-orang yang tidak sepenuhnya nyaman dengan fasilitas pengalihan I / O dari shell POSIX
mungkin ada kasus di mana
cat
yang diperlukan (misalnya: file untuk dibaca memerlukan semacam hak istimewa untuk mengakses, dan Anda tidak ingin memberikan yang istimewa untuk program yang akan mengacu:sudo cat /dev/sda | /usr/bin/time my_compression_test --no-output
)dalam prakteknya , pada mesin modern, penambahan
cat
dalam pipa mungkin tidak ada konsekuensi nyata.Tetapi saya mengatakan hal terakhir itu dengan ragu-ragu. Jika kami memeriksa hasil terakhir di 'Sunting 5' -
- klaim ini yang
cat
mengonsumsi 74% CPU selama pengujian; dan memang 1,34 / 1,83 adalah sekitar 74%. Mungkin serangkaian:akan hanya mengambil 0,49 detik tersisa! Mungkin tidak: di
cat
sini harus membayar untukread()
panggilan sistem (atau yang setara) yang mentransfer file dari 'disk' (sebenarnya buffer cache), serta pipa menulis untuk mengirimkannyawc
. Tes yang benar masih harus melakukan ituread()
panggilan panggilan itu; hanya panggilan write-to-pipe dan read-from-pipe yang akan disimpan, dan itu seharusnya cukup murah.Namun, saya memperkirakan Anda akan dapat mengukur perbedaan antara
cat file | wc -l
danwc -l < file
dan menemukan perbedaan yang nyata (persentase 2 digit). Setiap tes yang lebih lambat akan membayar penalti yang sama dalam waktu absolut; namun jumlah yang lebih kecil dari total waktu yang lebih besar.Sebenarnya saya melakukan beberapa tes cepat dengan file sampah 1,5 gigabyte, pada sistem Linux 3.13 (Ubuntu 14.04), memperoleh hasil ini (ini sebenarnya hasil 'terbaik dari 3'; setelah melakukan priming cache, tentu saja):
Perhatikan bahwa kedua hasil pipeline mengklaim telah mengambil lebih banyak waktu CPU (pengguna + sistem) daripada waktu jam dinding yang sebenarnya. Ini karena saya menggunakan perintah 'waktu' built-in shell (bash), yang sadar akan pipeline; dan saya menggunakan mesin multi-core di mana proses terpisah dalam suatu pipeline dapat menggunakan core terpisah, mengakumulasi waktu CPU lebih cepat daripada realtime. Menggunakan
/usr/bin/time
Saya melihat waktu CPU lebih kecil dari waktu nyata - menunjukkan bahwa itu hanya dapat mengatur waktu elemen pipa tunggal dilewatkan ke itu pada baris perintah. Juga, output shell memberikan milidetik sementara/usr/bin/time
hanya memberikan seperseratus detik.Jadi pada tingkat efisiensi
wc -l
,cat
membuat perbedaan besar: 409/283 = 1,453 atau 45,3% lebih realtime, dan 775/280 = 2,768, atau 177% lebih banyak menggunakan CPU! Pada kotak uji acak-nya-ada-pada-saat-itu.Saya harus menambahkan bahwa setidaknya ada satu perbedaan signifikan antara gaya pengujian ini, dan saya tidak bisa mengatakan apakah ini merupakan keuntungan atau kesalahan; Anda harus memutuskan ini sendiri:
Ketika Anda menjalankan
cat big_file | /usr/bin/time my_program
, program Anda menerima input dari pipa, tepat pada kecepatan yang dikirim olehcat
, dan dalam potongan tidak lebih besar dari yang ditulis olehcat
.Ketika Anda menjalankan
/usr/bin/time my_program < big_file
, program Anda menerima deskriptor file terbuka ke file aktual. Program Anda - atau dalam banyak kasus, perpustakaan I / O dari bahasa tempat penulisan itu - dapat mengambil tindakan yang berbeda ketika disajikan dengan deskriptor file yang merujuk file biasa. Ini dapat digunakanmmap(2)
untuk memetakan file input ke ruang alamatnya, daripada menggunakanread(2)
panggilan sistem eksplisit . Perbedaan ini dapat memiliki efek yang jauh lebih besar pada hasil benchmark Anda daripada biaya kecil menjalankancat
biner.Tentu saja ini merupakan hasil tolok ukur yang menarik jika program yang sama memiliki kinerja yang berbeda secara signifikan antara kedua kasus tersebut. Ini menunjukkan bahwa, memang, program atau perpustakaan I / O -nya melakukan sesuatu yang menarik, seperti menggunakan
mmap()
. Jadi dalam praktiknya mungkin lebih baik menjalankan benchmark dua arah; mungkin mengabaikancat
hasil oleh beberapa faktor kecil untuk "memaafkan" biaya menjalankannyacat
sendiri.sumber
$ < big_file time my_program
$ time < big_file my_program
Ini harus bekerja di setiap shell POSIX (yaitu bukan `csh `dan saya tidak yakin tentang eksotika seperti` rc`:)time
mengukur seluruh pipa bukannya program pertama.time seq 2 | while read; do sleep 1; done
mencetak 2 detik,/usr/bin/time seq 2 | while read; do sleep 1; done
mencetak 0 detik.Saya mereproduksi hasil asli di komputer saya menggunakan g ++ di Mac.
Menambahkan pernyataan berikut ke versi C ++ tepat sebelum
while
loop membawanya sejajar dengan versi Python :sync_with_stdio meningkatkan kecepatan menjadi 2 detik, dan pengaturan buffer yang lebih besar membawanya ke 1 detik.
sumber
getline
, operator aliran,scanf
bisa nyaman jika Anda tidak peduli tentang waktu pemuatan file atau jika Anda memuat file teks kecil. Tetapi, jika kinerja adalah sesuatu yang Anda pedulikan, Anda harus benar-benar hanya buffer seluruh file ke dalam memori (dengan asumsi itu akan cocok).Ini sebuah contoh:
Jika mau, Anda dapat membungkus aliran di sekitar buffer itu untuk akses yang lebih nyaman seperti ini:
Juga, jika Anda mengendalikan file, pertimbangkan untuk menggunakan format data biner datar alih-alih teks. Ini lebih dapat diandalkan untuk membaca dan menulis karena Anda tidak harus berurusan dengan semua ambiguitas ruang putih. Ini juga lebih kecil dan lebih cepat untuk diurai.
sumber
Kode berikut ini lebih cepat untuk saya daripada kode lain yang diposting di sini sejauh ini: (Visual Studio 2013, 64-bit, 500 MB file dengan panjang garis seragam di [0, 1000)).
Ini mengalahkan semua upaya Python saya dengan lebih dari satu faktor 2.
sumber
read
syscalls unbuffered menjadi buffer statis dengan panjangBUFSIZE
atau melaluimmap
syscall yang sesuai , lalu mencambuk buffer yang menghitung baris baru à lafor (char *cp = buf; *cp; cp++) count += *cp == "\n"
. Anda harus menyetelBUFSIZE
untuk sistem Anda, stdio mana yang sudah dilakukan untuk Anda. Tetapifor
loop itu harus dikompilasi ke instruksi bahasa assembler cepat berteriak luar biasa untuk perangkat keras kotak Anda.Ngomong-ngomong, alasan jumlah baris untuk versi C ++ lebih besar dari jumlah untuk versi Python adalah bahwa bendera bukti hanya akan ditetapkan ketika upaya dilakukan untuk membaca di luar bukti. Jadi loop yang benar adalah:
sumber
while (getline(cin, input_line)) line_count++;
++line_count;
dan tidakline_count++;
.long
, dan kompilernya cukup mampu mengatakan bahwa hasil kenaikannya tidak digunakan. Jika tidak menghasilkan kode yang identik untuk postincrement dan preincrement, itu rusak.++line_count;
bukannyaline_count++;
tidak ada salahnya :)while
, kan? Apakah penting jika ada kesalahan dan Anda ingin memastikanline_count
itu benar? Saya hanya menebak tetapi saya tidak mengerti mengapa itu penting.Dalam contoh kedua Anda (dengan scanf ()) alasan mengapa ini masih lebih lambat mungkin karena scanf ("% s") mem-parsing string dan mencari spasi spasi (spasi, tab, baris baru).
Juga, ya, CPython melakukan caching untuk menghindari pembacaan harddisk.
sumber
Unsur pertama jawaban:
<iostream>
lambat. Sangat lambat. Saya mendapatkan peningkatan kinerja besar denganscanf
seperti di bawah ini, tetapi masih dua kali lebih lambat dari Python.sumber
Yah, saya melihat bahwa dalam solusi kedua Anda, Anda beralih dari
cin
kescanf
, yang merupakan saran pertama yang akan saya buat (cin is sloooooooooooow). Sekarang, jika Anda beralih dariscanf
kefgets
, Anda akan melihat peningkatan kinerja lainnya:fgets
adalah fungsi C ++ tercepat untuk input string.BTW, tidak tahu tentang hal sinkronisasi itu, bagus. Tetapi Anda harus tetap mencoba
fgets
.sumber
fgets
akan salah (dalam hal jumlah baris, dan dalam hal memisahkan garis di loop jika Anda benar-benar perlu menggunakannya) untuk garis yang cukup besar, tanpa pemeriksaan tambahan untuk garis yang tidak lengkap (dan mencoba untuk mengkompensasi untuk itu melibatkan alokasi buffer besar yang tidak perlu) , di manastd::getline
menangani realokasi untuk mencocokkan input aktual dengan mulus). Cepat dan salah itu mudah, tetapi hampir selalu layak untuk menggunakan "sedikit lebih lambat, tetapi benar", yang mematikansync_with_stdio
membuat Anda.