Papan Peringkat - JIT Dikompilasi (Lebih Rendah Lebih Baik)
- es1024 - 81.2 poin (termasuk kompiler yang berfungsi!)
- Kieth Randall - 116 poin
- Ell - 121 poin
Papan - Ditafsirkan (Lebih rendah lebih baik)
- Martin Büttner - 706654 poin (sekitar 2 jam).
- criptych - 30379 poin (97 detik)
Misi Anda, jika Anda memilih untuk menerimanya, adalah untuk menulis bytecode interpreter / VM terkecil. VM / interpreter menggunakan arsitektur CISC kecil (ukuran operasi dapat bervariasi), dengan bahasa yang ditentukan di bawah ini. Setelah selesai, Anda harus mencetak nilai 3 register CPU untuk membuktikan bahwa output yang benar dicetak (3.126.900.366).
Penyusun
Jika Anda ingin membuat tes sendiri, kompiler diposting di bawah ini. Jangan ragu untuk memposting tes Anda dengan jawaban Anda.
Spesifikasi "VM"
VM memiliki 3 register integral 32 32 bit yang tidak ditandai: R0, R1, R2. Mereka direpresentasikan dalam hex sebagai 0x00, 0x01, dan 0x02.
Operasi berikut harus didukung:
Formatnya adalah [nama] [... operan ...], [kode-heksadesimal] [... operan diulang ...]
- LOAD [daftar] [nilai 4 byte], 0x00 [daftar] [nilai 4 byte]
- PUSH [daftar], 0x02 [daftar]
- POP [daftar], 0x03 [daftar]
- TAMBAH [daftar, 1 byte] [daftar, 1 byte], 0x04 [daftar] [daftar]
- SUB [daftar, 1 byte] [daftar, 1 byte], 0x05 [daftar] [daftar]
- MULI [daftar, 1 byte] [daftar, 1 byte], 0x06 [daftar] [daftar]
- DIV [daftar, 1 byte] [daftar, 1 byte], 0x07 [daftar] [daftar]
- JMP [baris kode, 4 byte], 0x08 [nomor baris kode 4 byte]
- CMP [daftar, 1 byte] [daftar, 1 byte], 0x09 [daftar] [daftar]
- BRANCHLT [baris kode, 4 byte], 0x0a [nomor baris kode 4 byte]
Beberapa catatan:
- Operasi matematika di atas menambahkan nilai 2 register bersama-sama, menempatkan output di register pertama.
- CMP, operator pembanding, harus membandingkan nilai 2 register dan menyimpan output dalam beberapa flag internal (ini bisa khusus implementasi) untuk digunakan di masa depan pada instruksi cabang.
- Jika BRANCH dipanggil sebelum CMP, kecuali BRANCHEQ dipanggil, "VM" seharusnya tidak bercabang.
- PUSH / POP secara tak terduga mendorong atau mengeluarkan nomor dari tumpukan.
- Lompat dan Cabang operator melompat ke operasi tertentu (baris kode), bukan alamat biner.
- Operasi cabang tidak melakukan perbandingan. Sebaliknya, mereka mengambil output dari perbandingan terakhir untuk dieksekusi.
- Operator Branch and Jump menggunakan sistem pengindeksan angka garis berbasis nol. (Misalnya JMP 0 melompat ke baris pertama)
- Semua operasi harus dilakukan pada angka yang tidak ditandatangani yang melimpah ke nol dan tidak membuang pengecualian pada bilangan bulat bilangan bulat.
- Pembagian dengan nol tidak diperbolehkan dan dengan demikian, perilaku program tidak didefinisikan. Anda dapat (misalnya) ...
- Hancurkan program.
- Akhiri pelaksanaan VM dan kembalikan ke kondisi saat ini.
- Tampilkan pesan "ERR: Division by 0".
- Pengakhiran program didefinisikan sebagai ketika penunjuk instruksi mencapai akhir program (program yang tidak kosong dapat diasumsikan).
Output Keluaran harus persis seperti ini (termasuk baris baru)
R0 3126900366
R1 0
R2 10000
Poin
Poin dihitung berdasarkan rumus berikut:Number Of Characters * (Seconds Needed To Run / 2)
Untuk menghindari perbedaan perangkat keras yang menyebabkan waktu yang berbeda, setiap tes akan dijalankan di komputer saya (i5-4210u, ram 8GB) di server ubuntu atau Windows 8, jadi cobalah untuk tidak menggunakan beberapa runtime gila-eksotik yang hanya dikompilasi pada Dual G5 Mac Pro dengan tepat 762,66 mb RAM gratis.
Jika Anda menggunakan runtime / bahasa khusus, silakan kirim tautannya.
- Untuk pihak yang berkepentingan, saya telah memposting kode pengujian (ditulis dalam C #) di sini: http://pastebin.com/WYCG5Uqu
Program Tes
Ide itu datang dari sini , jadi kami akan menggunakan versi program mereka yang agak dimodifikasi.
Output yang benar untuk program ini adalah: 3.126.900.366
Dalam C:
int s, i, j;
for (s = 0, i = 0; i < 10000; i++) {
for (j = 0; j < 10000; j++)
s += (i * j) / 3;
}
Dalam kode: [R0 mewakili s, R1 j, R2 i]
LOAD R0 0
LOAD R2 0 <--outer loop value
LOAD R1 0 <--inner loop value
--Begin inner loop--
PUSH R1 <--push inner loop value to the stack
MUL R1 R2 <--(i*j)
PUSH R2
LOAD R2 3
DIV R1 R2 <-- / 3
POP R2
ADD R0 R1 <-- s+=
POP R1
PUSH R2
LOAD R2 1
ADD R1 R2 <--j++
POP R2
PUSH R2
LOAD R2 10000
CMP R1 R2 <-- j < 10000
POP R2
BRANCHLT 3 <--Go back to beginning inner loop
--Drop To outer loop--
LOAD R1 1
ADD R2 R1 <--i++
LOAD R1 10000
CMP R2 R1 <-- i < 10000
LOAD R1 0 <--Reset inner loop
BRANCHLT 2
Dalam biner / hex:
0x00 0x00 0x00 0x00 0x00 0x00
0x00 0x02 0x00 0x00 0x00 0x00
0x00 0x01 0x00 0x00 0x00 0x00
0x02 0x01
0x06 0x01 0x02
0x02 0x02
0x00 0x02 0x00 0x00 0x00 0x03
0x07 0x01 0x02
0x03 0x02
0x04 0x00 0x01
0x03 0x01
0x02 0x02
0x00 0x02 0x00 0x00 0x00 0x01
0x04 0x01 0x02
0x03 0x02
0x02 0x02
0x00 0x02 0x00 0x00 0x27 0x10
0x09 0x01 0x02
0x03 0x02
0x0a 0x00 0x00 0x00 0x03
0x00 0x01 0x00 0x00 0x00 0x01
0x04 0x02 0x01
0x00 0x01 0x00 0x00 0x27 0x10
0x09 0x02 0x01
0x00 0x01 0x00 0x00 0x00 0x00
0x0a 0x00 0x00 0x00 0x02
Poin Bonus (Efek diterapkan multiplikasi) Misalnya jika Anda memenuhi syarat untuk ketiganya, itu akan menjadi ((karakter * 0,50) * 0,75) * 0,90
- 50% berkurang jika penerjemah sebenarnya adalah kompiler JIT
- Penurunan 25% jika menerapkan segala bentuk pengulangan membuka gulungan / optimasi yang berarti.
- Penurunan 10% jika Anda memperpanjang VM dengan
- BRANCHEQ [baris kode, 4 byte] (Cabang jika sama - opcode 0x0b)
- BRANCHGT [kode baris, 4 byte] (Cabang jika lebih besar dari - opcode 0x0c)
- BRANCHNE [kode baris, 4 byte] (Cabang jika tidak sama - opcode 0x0d)
- RLOAD [register 1] [register 2] (pindahkan nilai register 2 ke register 1 - opcode 0x01).
Tidak diizinkan
- Mengompilasi kasus uji ke dalam program dilarang. Anda harus menerima bytecode dari STDIN atau dari file (Tidak masalah yang mana).
- Mengembalikan output tanpa menjalankan program.
- Cara lain yang dapat Anda pikirkan untuk menipu persyaratan VM.
sumber
CMP
memeriksa kurang dari atau setara? Dan apa yang terjadi pada hasilnya?MUL
danDIV
juga tidak ditentukan. Haruskah mereka ditandatangani atau tidak ditandatangani? Apa yang terjadi pada multiplication overflow?Jawaban:
C, 752 (589 + 163 untuk flag yang ditentukan) * 0,5 (JIT) * 0,9 (ekstensi) * (optimasi 0,75) * (0,64 detik / 2) = 81,216
Mengambil kode (
LOAD R0
, dll), tidak ada karakter trailing, spasi tunggal, tidak ada baris kosong di tengah, tidak ada komentar, dll. Trailing newline diperlukan.Ini kemudian dikonversi ke bytecode 80386 dan dieksekusi.
Memuat
0
ke register digantikan olehxor
ing register dengan dirinya sendiri bukanmov
ing0
ke dalam register, yang merupakan tiga byte pendek di bytecode yang dihasilkan, dan mungkin sangat sedikit lebih cepat.Kompilasi dengan:
Diperlukan OS yang mendukung POSIX.
Input dibaca dari STDIN (gunakan
./bytecode < file
untuk menyalurkan dari file).Bytecode yang dihasilkan untuk program uji:
Tidak Disatukan:
sumber
C, Skor = 854 byte × (~ 0,8 detik / 2) × 0,5 [JIT] × 0,9 [Ekstensi] = ~ 154 byte detik
Kompilasi dengan
gcc vm.c -ovm -m32 -w
OS yang kompatibel dengan POSIX x86.Jalankan dengan
./vm < program
, di manaprogram
file program biner.Pergi untuk kecepatan. Program ini melakukan terjemahan program input yang sangat mudah ke kode mesin x86 dan memungkinkan CPU melakukan sisanya.
Misalnya, inilah terjemahan dari program pengujian.
ecx
,esi
danedi
sesuai denganR0
,R1
danR2
, masing-masing;bh
memegang bendera status;eax
danedx
merupakan register awal; tumpukan panggilan sesuai dengan tumpukan VM:Tidak disatukan
Tampilkan cuplikan kode
sumber
CJam,
222187185 byte * (terlalu lambat / 2)Saya hanya ingin melihat seberapa pendek saya bisa mendapatkan bytecode VM dengan menulisnya di CJam. Kurang dari 200 byte tampaknya cukup baik. Ini sangat lambat, karena CJam sendiri ditafsirkan. Butuh waktu lama untuk menjalankan program pengujian.
Untuk menjalankannya, unduh Java interpreter di tautan sourceforge ini , simpan kodenya
vm.cjam
dan jalankan bersamaProgram ini mengharapkan bytecode pada STDIN. Saya belum menemukan cara untuk menyalurkan data biner ke dalam sebuah program, tanpa PowerShell menambahkan jeda baris tambahan dan mengubahnya
0x0a
menjadi0x0d 0x0a
, yang benar-benar menjengkelkan. Kode ini mencakup 4 byte untuk memperbaikinya (D-);
), yang belum saya sertakan dalam jumlah total, karena itu bukan sesuatu yang harus dilakukan oleh program jika ia benar-benar menerima bytecode itu sendiri di STDIN, alih-alih beberapa versi yang dikodekan secara aneh dari kode itu. . Jika seseorang mengetahui perbaikan untuk itu, beri tahu saya.Sedikit tidak berbulu:
Saya akan menambahkan penjelasan yang tepat besok.
Singkatnya, saya menyimpan semua register, pointer instruksi dan flag perbandingan dalam variabel, sehingga saya bisa menjaga stack CJam bebas untuk digunakan sebagai stack VM.
sumber
python / c ++, skor = 56,66
1435 karakter * .234 / 2 detik * .5 [JIT] * .75 [Optimasi] * .90 [Instruksi tambahan]
Mengkompilasi program input ke c ++, menjalankan gcc di atasnya, lalu menjalankan hasilnya. Sebagian besar waktu dihabiskan di dalam gcc.
Salah satu optimasi yang saya lakukan adalah mengurangi operasi stack menjadi variabel eksplisit jika diizinkan secara semantik. Ini sangat membantu, sekitar 10x lebih baik runtime dari kode yang dikompilasi (sekitar 0,056 detik untuk benar-benar menjalankan biner yang dihasilkan). Saya tidak yakin apa yang dilakukan gcc yang membuat Anda mendapatkan peningkatan itu, tapi itu bagus.
Bisa dipastikan golf lagi.
sumber
Lua 5.2 (atau LuaJIT), 740 byte
Pertama coba, hanya golf minimal. Versi ini berfungsi (setidaknya pada program pengujian), dan mengimplementasikan opcode tambahan, tetapi tidak menjunjung tinggi persyaratan matematika yang tidak ditandatangani dan tidak terlalu cepat. Sebagai bonus, ini adalah VM yang berjalan dalam VM, dan ditulis sedemikian rupa sehingga dapat diinterpretasikan (dijalankan dengan PUC-Lua) atau semacam-JIT (dijalankan dengan LuaJIT; masih ditafsirkan, tetapi interpreternya sekarang JITted).
EDIT: Golf lebih baik, masih besar.
EDIT: Memperbaiki kesalahan utama, dan sekarang membatasi aritmatika ke
unsigned long
rentang. Namun, entah bagaimana berhasil menjaga ukuran agar tidak lepas kendali, tetapi tetap saja memberikan jawaban yang salah.EDIT: Ternyata, hasilnya benar tetapi hasilnya tidak. Beralih ke pencetakan dengan
%u
alih - alih%d
dan semuanya baik-baik saja. Juga beralih register berbasis tabel untuk variabel untuk meningkatkan ukuran dan kecepatan agak.EDIT: Menggunakan
goto
pernyataan Lua 5.2 (juga tersedia di LuaJIT) Saya telah mengganti penerjemah dengan "JIT-to-Lua," menghasilkan kode yang dijalankan langsung oleh Lua VM itu sendiri. Tidak yakin apakah ini benar-benar dianggap sebagai JIT, tetapi itu meningkatkan kecepatan.Ini versi aslinya yang dapat dibaca.
sumber
<
di loop saya alih-alih<=
, sehingga instruksi cabang terakhir ditinggalkan. Masih mendapat jawaban yang salah, tetapi sekarang perlu beberapa menit untuk melakukannya. :)C #
15051475 byteIni adalah versi penerjemah saya, ditulis dalam bahasa C # dapat dioptimalkan / golf lebih saya pikir, tapi saya tidak benar-benar tahu di mana;)
versi golf:
sunting
menghapus beberapa yang tidak perlu
public
danprivate
pengubah:panggil dengan
executable.exe filename
manafilename
file yang berisi kode yang akan ditafsirkan"Program pengujian" saya:
Penerjemah tidak tahu nama variabel, kelas, ...
sumber