Grep -e, Sed -e – Performa Rendah Saat '[x]{1,9999}' Digunakan, Tapi Mengapa?

Ketika grep atau sed digunakan dengan opsi --extended-regexp dan pola {1,9999} adalah bagian dari regexp yang digunakan, kinerja perintah ini menjadi rendah. Agar lebih jelas, di bawah ini diterapkan beberapa pengujian.

• Kinerja relatif grep -E , egrep dan sed -E hampir sama, jadi hanya tes yang dilakukan dengan grep -E disediakan.

Uji 1

$ time grep -E '[0-9]{1,99}' < /dev/null

real    0m0.002s

Uji 2

$ time grep -E '[0-9]{1,9999}' < /dev/null

> real    0m0.494s

Uji 3

$ time grep -E '[0123456789]{1,9999}' < /dev/null

> real    21m43.947s

Uji 4

$ time grep -E '[0123456789]+' < /dev/null
$ time grep -E '[0123456789]*' < /dev/null
$ time grep -E '[0123456789]{1,}' < /dev/null
$ time grep -P '[0123456789]{1,9999}' < /dev/null

real    0m0.002s       

Apa alasan perbedaan kinerja yang signifikan ini?

Jawaban yang Diterima:

Perhatikan bahwa bukan pencocokan yang membutuhkan waktu, tetapi pembangunan RE. Anda akan menemukan bahwa ia menggunakan cukup banyak RAM juga:

$ valgrind grep -Eo '[0-9]{1,9999}' < /dev/null
==6518== HEAP SUMMARY:
==6518==     in use at exit: 1,603,530,656 bytes in 60,013 blocks
==6518==   total heap usage: 123,613 allocs, 63,600 frees, 1,612,381,621 bytes allocated
$ valgrind grep -Eo '[0-9]{1,99}' < /dev/null
==6578==     in use at exit: 242,028 bytes in 613 blocks
==6578==   total heap usage: 1,459 allocs, 846 frees, 362,387 bytes allocated
$ valgrind grep -Eo '[0-9]{1,999}' < /dev/null
==6594== HEAP SUMMARY:
==6594==     in use at exit: 16,429,496 bytes in 6,013 blocks
==6594==   total heap usage: 12,586 allocs, 6,573 frees, 17,378,572 bytes allocated

Jumlah alokasi tampaknya secara kasar sebanding dengan jumlah iterasi, tetapi memori yang dialokasikan tampaknya tumbuh secara eksponensial.

Itu tergantung bagaimana GNU regexps diimplementasikan. Jika Anda mengkompilasi GNU grep dengan CPPFLAGS=-DDEBUG ./configure && make , dan jalankan perintah tersebut, Anda akan melihat efek eksponensial beraksi. Lebih dalam dari itu berarti mempelajari banyak teori tentang DFA dan menyelami implementasi regexp gnulib.

Di sini, Anda dapat menggunakan PCRE yang tampaknya tidak memiliki masalah yang sama:grep -Po '[0-9]{1,65535}' (maksimum, meskipun Anda selalu dapat melakukan hal-hal seperti [0-9](?:[0-9]{0,10000}){100} untuk 1 hingga 1.000.001 pengulangan) tidak membutuhkan lebih banyak waktu atau memori daripada grep -Po '[0-9]{1,2}' .