Pertanyaan Kinerja predikat Prolog bawaan (adalah) / 2


Pembaruan: 11.6.2016

Perbedaan kinerja yang membingungkan yang saya amati dengan SICStus Prolog 4.3.2 benar-benar menghilang dengan SICStus Prolog 4.3.3 yang baru saja dirilis. Pujian!

Saya memperbarui tabel "runtimes" di bawah ini untuk menyertakan SICStus Prolog 4.3.3. Sorotan meliputi:

  • (is)/2 aku s hingga 10x lebih cepat daripada sebelumnya.
  • val_of/2 telah sangat cepat juga, hampir 2x lipat!

MEGO ;-)


Kapan  menjawab pertanyaan "Ukuran Prosedur dalam Bahasa Prolog" SO-pengguna @ThanosTintinidis mengusulkan cara yang sangat sederhana1 memperkenalkan pemula untuk menurunkan length/2:

[...] Juga perhatikan itu E perlu dipakai hanya karena akan mengevaluasi ekspresi. Anda dapat menulis sesuatu seperti ini:

ukuran ([], 0).
size ([_ | Xs], 1 + E): - size (Xs, E).

dan jika Anda menyebutnya:

? - ukuran ([_, _], E).
E = 1+ (1 + 0).

Menyenangkan, bukan? Anda mungkin ingin mengevaluasi yang terakhir E, yaitu panggilan ?- size([1,2], E), N is E. [...]

Menyenangkan?  Sangat menyenangkan! Sejumlah eksperimen menarik terbentang di depan:

  • Kiri-condong vs pohon yang condong ke kanan

    list_sizL([], 0). % left-condong
    list_sizL ([_ | Es], N + 1): - list_sizL (Es, N).
    
    list_sizR([], 0). % rcondong ke depan
    list_sizR ([_ | Es], 1 + N): - list_sizR (Es, N).
    
  • built-in (is)/2 vs val_of/2

    val_of (V, E): - (E = E1 + E2 -> val_of (V1, E1), val_of (V2, E2), V adalah V1 + V2
                    ; angka (E) -> V = E
                    ).
    

Untuk mengukur runtime, saya berlari go(2000000) menggunakan prosesor Prolog yang berbeda2:

pergi (L): -
   panjang (Xs, L),
   anggota (B_2, [list_sizL, list_sizR]),
   panggilan (B_2, Xs, E),
   anggota (P_2, [adalah, val_of]),
    call_time(panggilan (P_2, N, E), T),
   (L = N -> writeq (B_2 + P_2 = T), nl; throw (up)).

Pada Intel Core i7-4700MQ Saya mengamati runtime berikut dengan SICStus dan SWI:

                          | SWI | SICStus | SICStus |
                          | 7.3.20 | 4.3.2 | 4.3.3 |
       ------------------- + -------- + --------- + --------- |
       list_sizL + (is) | 208 ms | 650 ms | 60 mdtk | 3.4x
       list_sizL + val_of | 381 ms | 100 mdetik 60 mdtk 6.3x
       ------------------- + -------- + --------- + --------- |
       list_sizR + (is) | 88 ms | 660 mdtk 70 mdtk | 1,2x
       list_sizR + val_of | 346 ms | 100 mdetik 60 mdtk 5,7x
       ------------------- + -------- + --------- + --------- |

Saya bingung dengan hasil-hasil ini (dapat direproduksi) ... Dapatkah seseorang memberi tahu saya apa yang terjadi?


Catatan kaki 1: Demi keringkasan dan keterbacaan, nama-nama variabel sedikit disesuaikan.
Catatan kaki 2: Menjalankan SWI-Prolog 7.3.20 dengan argumen baris perintah yang sesuai swipl -G2G -L2G -O.


5
2018-05-11 19:05


asal


Jawaban:


Saya dapat mengkonfirmasi fakta mengejutkan bahwa, di SICStus Prolog, val_of/2 jauh lebih cepat daripada is/2 ketika ekspresi adalah istilah majemuk yang besar, yaitu ketika is/2 menafsirkan ekspresi.

Dalam implementasi SICStus saat ini dikompilasi is/2 perlu melarikan diri ke kode Prolog ketika argumen ke operator aritmatika bukan angka. Ketika menafsirkan ekspresi yang dalam, pelarian ini terjadi untuk semua argumen, secara rekursif, yang jauh lebih lambat dari apa val_of/2 tidak, yaitu Prolog biasa ke panggilan Prolog.

Saya melakukan perbaikan proof-of-concept untuk masalah yang mendasarinya, itu membuat is/2 kasus dalam program di atas tentang kecepatan yang sama val_of/2. Perubahan ini telah dimasukkan dalam rilis SICStus Prolog saat ini (4.3.3).


7
2018-05-12 12:00



Anda membandingkan dua penerapan yang sangat berbeda (is)/2. SWI mendeteksi kesalahan instantiasi dan ekspresi siklik sebelum evaluasi aktual. SICStus tidak. Coba ini dengan:

?- E=(1/0)+_, X is E.
?- E=(1/0)+E, X is E.

SWI menghasilkan kesalahan instantiasi dan kesalahan tipe (karena pohon yang tidak terbatas), sedangkan SICStus selalu mengevaluasi 1/0 dan menghasilkan kesalahan evaluasi dalam kedua kasus. Dan (setidaknya untuk contoh ini), keduanya saling menyesuaikan.

Perbedaan kecepatan antara mengevaluasi dua struktur pohon adalah karena optimasi rekursi ekor di ground/1 dan acyclic_term/1 di SWI. Algoritme saat ini menggunakan tumpukan dan argumen kunjungan dari kiri ke kanan. Dengan demikian, pohon bersarang ke kanan membutuhkan ruang tambahan konstan dan dengan demikian jauh lebih cepat.

SICStus menggunakan Deutsch-Schorr-Waite untuk acyclic_term/1 dan ground/1, dan dengan demikian tidak memiliki tumpukan eksplisit dan dengan demikian tidak ada TRO. Setidaknya, keduanya memiliki kecepatan yang sama untuk kiri dan kanan.


4
2018-05-12 07:23



Secara sederhana, saya berpikir bahwa SWI-Prolog mengabdikan lebih banyak pengoptimalan ke aritmatika, sementara SICStus memiliki pembuatan kode yang lebih baik untuk aliran kontrol umum.

Mungkin beberapa kinerja yang lebih baik dapat diperoleh dari SWI-Prolog dengan cara Evaluasi Sebagian, yang diperkenalkan dengan sangat baik oleh Pereira-Shieber di bab 6 dari Prolog dan Analisis Bahasa Alami.

Anda juga harus memberi kesempatan kepada YAP: ini telah dilaporkan sebagai Prolog berbasis WAM tercepat. Saya ingat Jan Wielemaker mencatat pada daftar SWI-Prolog bahwa sebagian besar kecepatan YAP diperoleh dari penulisan ulang besar-besaran - katakanlah, inlining. Sesuatu yang saya pikir itu didirikan pada (evaluasi sebagian yang diimplementasikan dengan baik, tentu saja).


2
2018-05-11 21:45