Saya mengajukan pertanyaan ini untuk mengetahui cara meningkatkan ukuran tumpukan panggilan runtime di JVM. Saya mendapat jawaban untuk ini, dan saya juga mendapat banyak jawaban dan komentar berguna yang relevan dengan cara Java menangani situasi di mana tumpukan runtime yang besar diperlukan. Saya telah memperpanjang pertanyaan saya dengan ringkasan tanggapan.
Awalnya saya ingin meningkatkan ukuran tumpukan JVM sehingga program seperti berjalan tanpa file StackOverflowError
.
public class TT {
public static long fact(int n) {
return n < 2 ? 1 : n * fact(n - 1);
}
public static void main(String[] args) {
System.out.println(fact(1 << 15));
}
}
Pengaturan konfigurasi yang sesuai adalah tanda java -Xss...
baris perintah dengan nilai yang cukup besar. Untuk program di TT
atas, ia bekerja seperti ini dengan JVM OpenJDK:
$ javac TT.java
$ java -Xss4m TT
Salah satu jawaban juga menunjukkan bahwa -X...
flag bergantung pada implementasi. Saya menggunakan
java version "1.6.0_18"
OpenJDK Runtime Environment (IcedTea6 1.8.1) (6b18-1.8.1-0ubuntu1~8.04.3)
OpenJDK 64-Bit Server VM (build 16.0-b13, mixed mode)
Dimungkinkan juga untuk menentukan tumpukan besar hanya untuk satu utas (lihat di salah satu jawaban caranya). Ini disarankan java -Xss...
untuk menghindari pemborosan memori untuk utas yang tidak membutuhkannya.
Saya ingin tahu seberapa besar tumpukan yang dibutuhkan program di atas, jadi saya telah menjalankannya n
meningkat:
- -Xss4m bisa cukup untuk
fact(1 << 15)
- -Xss5m sudah cukup untuk
fact(1 << 17)
- -Xss7m sudah cukup untuk
fact(1 << 18)
- -Xss9m sudah cukup untuk
fact(1 << 19)
- -Xss18m sudah cukup untuk
fact(1 << 20)
- -Xss35m sudah cukup untuk
fact(1 << 21)
- -Xss68m sudah cukup untuk
fact(1 << 22)
- -Xss129m sudah cukup untuk
fact(1 << 23)
- -Xss258m sudah cukup untuk
fact(1 << 24)
- -Xss515m sudah cukup untuk
fact(1 << 25)
Dari angka-angka di atas, tampaknya Java menggunakan sekitar 16 byte per stack frame untuk fungsi di atas, ini wajar.
Pencacahan di atas berisi bisa cukup, bukan cukup , karena persyaratan tumpukan tidak deterministik: menjalankannya beberapa kali dengan file sumber yang sama dan -Xss...
terkadang sama berhasil dan terkadang menghasilkan StackOverflowError
. Misalnya untuk 1 << 20, -Xss18m
sudah cukup dalam 7 habis dari 10, dan -Xss19m
tidak selalu cukup juga, tetapi -Xss20m
sudah cukup (di semua 100 dari 100). Apakah pengumpulan sampah, JIT yang bekerja, atau sesuatu yang lain menyebabkan perilaku nondeterministik ini?
Pelacakan tumpukan yang dicetak di StackOverflowError
(dan mungkin juga di pengecualian lain) hanya menampilkan 1024 elemen terbaru dari tumpukan runtime. Jawaban di bawah ini menunjukkan bagaimana menghitung kedalaman yang dicapai dengan tepat (yang mungkin jauh lebih besar dari 1024).
Banyak orang yang menanggapi telah menunjukkan bahwa adalah praktik pengkodean yang baik dan aman untuk mempertimbangkan alternatif, implementasi yang tidak terlalu haus tumpukan dari algoritme yang sama. Secara umum, dimungkinkan untuk mengonversi ke satu set fungsi rekursif ke fungsi iteratif (menggunakan Stack
objek eg , yang diisi di heap dan bukan di stack runtime). Untuk fact
fungsi khusus ini , cukup mudah untuk mengubahnya. Versi iteratif saya akan terlihat seperti ini:
public class TTIterative {
public static long fact(int n) {
if (n < 2) return 1;
if (n > 65) return 0; // Enough powers of 2 in the product to make it (long)0.
long f = 2;
for (int i = 3; i <= n; ++i) {
f *= i;
}
return f;
}
public static void main(String[] args) {
System.out.println(fact(1 << 15));
}
}
FYI, seperti yang ditunjukkan oleh solusi berulang di atas, fact
fungsi tersebut tidak dapat menghitung faktorial angka yang tepat di atas 65 (sebenarnya, bahkan di atas 20), karena tipe bawaan Java long
akan meluap. Refactoring fact
sehingga akan mengembalikan a, BigInteger
bukan long
akan menghasilkan hasil yang tepat untuk input yang besar juga.
sumber
Jawaban:
Hmm ... ini berfungsi untuk saya dan dengan tumpukan kurang dari 999MB:
(Windows JDK 7, VM klien build 17.0-b05, dan Linux JDK 6 - informasi versi yang sama seperti yang Anda posting)
sumber
Saya berasumsi Anda menghitung "kedalaman 1024" dengan garis berulang di jejak tumpukan?
Jelas, panjang array pelacakan tumpukan di Throwable tampaknya dibatasi hingga 1024. Coba program berikut:
sumber
Jika Anda ingin bermain dengan ukuran tumpukan utas, Anda akan ingin melihat opsi -Xss di Hotspot JVM. Ini mungkin sesuatu yang berbeda pada VM non Hotspot karena parameter -X ke JVM spesifik untuk distribusi, IIRC.
Di Hotspot, ini terlihat seperti
java -Xss16M
jika Anda ingin membuat ukuran 16 MB.Tipe
java -X -help
jika Anda ingin melihat semua parameter JVM spesifik distribusi yang dapat Anda berikan. Saya tidak yakin apakah ini berfungsi sama pada JVM lain, tetapi akan mencetak semua parameter spesifik Hotspot.Untuk apa nilainya - saya akan merekomendasikan membatasi penggunaan metode rekursif Anda di Java. Tidak terlalu bagus dalam mengoptimalkannya - untuk satu JVM tidak mendukung rekursi ekor (lihat Apakah JVM mencegah pengoptimalan panggilan ekor? ). Coba lakukan pemfaktoran ulang kode faktorial Anda di atas untuk menggunakan loop sementara, bukan panggilan metode rekursif.
sumber
Satu-satunya cara untuk mengontrol ukuran tumpukan dalam proses adalah memulai yang baru
Thread
. Tapi Anda juga bisa mengontrol dengan membuat proses sub Java yang memanggil sendiri dengan-Xss
parameter.sumber
java -Xss...
.Tambahkan opsi ini
ke perintah spark-submit Anda akan memperbaiki masalah ini.
sumber
Sulit untuk memberikan solusi yang masuk akal karena Anda sangat ingin menghindari semua pendekatan yang waras. Refactoring satu baris kode adalah solusi yang senible.
Catatan: Menggunakan -Xss menyetel ukuran tumpukan setiap utas dan merupakan ide yang sangat buruk.
Pendekatan lain adalah manipulasi kode byte untuk mengubah kode sebagai berikut;
diberikan setiap jawaban untuk n> 127 adalah 0. Hal ini untuk menghindari perubahan kode sumber.
sumber
fact
fungsi dalam pertanyaan tersebut dapat difaktorkan ulang untuk menggunakan lebih sedikit ruang tumpukan.Aneh! Anda mengatakan bahwa Anda ingin membuat rekursi 1 << 15 kedalaman ??? !!!!
Saya sarankan JANGAN mencobanya. Ukuran tumpukan akan menjadi
2^15 * sizeof(stack-frame)
. Saya tidak tahu apa ukuran stack-frame itu, tetapi 2 ^ 15 adalah 32,768. Cukup banyak ... Nah, jika berhenti pada 1024 (2 ^ 10) Anda harus membuatnya 2 ^ 5 kali lebih besar, itu, 32 kali lebih besar daripada dengan pengaturan Anda yang sebenarnya.sumber
Poster lain telah menunjukkan bagaimana meningkatkan memori dan bahwa Anda dapat mengingat panggilan. Saya menyarankan bahwa untuk banyak aplikasi, Anda dapat menggunakan rumus Stirling untuk mendekati n besar! sangat cepat tanpa jejak memori.
Lihatlah posting ini, yang memiliki beberapa analisis fungsi dan kode:
http://threebrothers.org/brendan/blog/stirlings-approximation-formula-clojure/
sumber
Saya melakukan latihan Anagram , yang seperti masalah Perubahan Hitung tetapi dengan 50.000 denominasi (koin). Saya tidak yakin itu bisa dilakukan berulang-ulang , saya tidak peduli. Saya hanya tahu bahwa opsi -xss tidak berpengaruh - Saya selalu gagal setelah 1024 stack frame (mungkin scala melakukan pekerjaan yang buruk untuk mengirim ke batasan java atau printStackTrace. Saya tidak tahu). Ini adalah pilihan yang buruk, seperti yang dijelaskan. Anda tidak ingin semua utas yang masuk ke aplikasi menjadi mengerikan. Namun, saya melakukan beberapa eksperimen dengan Thread baru (ukuran tumpukan). Ini memang berhasil,
Anda melihat bahwa tumpukan dapat tumbuh lebih dalam secara eksponensial dengan lebih banyak tumpukan yang dialokasikan ke utas secara eksponensial.
sumber