Kích thước ngăn xếp tối đa C/C++

Question

Tôi muốn thực hiện DFS trên một mảng 100 X 100. (Nói các phần tử của mảng biểu diễn các nút đồ thị) Vì vậy, giả sử trường hợp xấu nhất, độ sâu của các cuộc gọi hàm đệ quy có thể lên tới 10000 với mỗi cuộc gọi chiếm tối đa 20 byte. Vì vậy, nó là phương tiện khả thi là có một khả năng stackoverflow?

Kích thước tối đa của ngăn xếp trong C/C++ là bao nhiêu?

Hãy xác định cho gcc cho cả
1) Cygwin trên Windows
2) Unix

các giới hạn chung là gì?

Answer 1

Trong Visual Studio kích thước ngăn xếp mặc định là 1 MB tôi nghĩ, vì vậy với độ sâu đệ quy 10.000 mỗi khung ngăn xếp có thể tối đa ~ 100 byte, đủ cho thuật toán DFS.

Hầu hết các trình biên dịch bao gồm Visual Studio cho phép bạn chỉ định kích thước ngăn xếp. Trên một số (tất cả?) Hương vị Linux kích thước ngăn xếp không phải là một phần của thực thi nhưng một biến môi trường trong hệ điều hành. Sau đó, bạn có thể kiểm tra kích thước ngăn xếp bằng ulimit -s và đặt giá trị đó thành một giá trị mới với ví dụ ulimit -s 16384.

Dưới đây là một link với ngăn xếp kích thước mặc định cho gcc.

DFS mà không đệ quy:

std::stack<Node> dfs; 
dfs.push(start); 
do { 
    Node top = dfs.top(); 
    if (top is what we are looking for) { 
     break; 
    } 
    dfs.pop(); 
    for (outgoing nodes from top) { 
     dfs.push(outgoing node); 
    } 
} while (!dfs.empty()) 

Answer 2

Platform-phụ thuộc, toolchain phụ thuộc, ulimit phụ thuộc, thông số phụ thuộc vào .... Nó không phải là ở tất cả các quy định, và có rất nhiều tài sản tĩnh và năng động có thể ảnh hưởng nó.

Answer 3

Có, có khả năng tràn ngăn xếp. Tiêu chuẩn C và C++ không quy định những thứ như độ sâu ngăn xếp, thường là vấn đề môi trường.

môi trường phát triển khá lớn và/hoặc hệ điều hành sẽ cho phép bạn chỉnh kích thước ngăn xếp của một quá trình, hoặc tại liên kết hoặc thời gian tải.

Bạn nên chỉ định hệ điều hành và môi trường phát triển bạn đang sử dụng để được hỗ trợ nhắm mục tiêu nhiều hơn.

Ví dụ, dưới Ubuntu Karmic Koala, mặc định cho gcc là 2M và 4K cam kết nhưng điều này có thể thay đổi khi bạn liên kết chương trình. Sử dụng tùy chọn --stack của ld để làm điều đó.

Answer 4

ngăn xếp cho chủ đề thường nhỏ. Bạn có thể thay đổi mặc định tại thời gian liên kết, hoặc thay đổi tại thời gian chạy. Để tham khảo một số giá trị mặc định là:

• glibc i386, x86_64 7.4 MB
• Tru64 5.1 5.2 MB
• Cygwin 1.8 MB
• Solaris 7..10 1 MB
• hệ điều hành MacOS X 10.5 460 KB
• AIX 5 98 KB
• OpenBSD 4.0 64 KB
• HP-UX 11 16 KB

Answer 5

Tôi không chắc chắn những gì bạn có nghĩa là bằng cách làm một tìm kiếm theo chiều sâu trên một mảng hình chữ nhật, nhưng tôi giả sử bạn biết những gì bạn đang làm.

Nếu giới hạn ngăn xếp là một vấn đề, bạn sẽ có thể chuyển đổi giải pháp đệ quy của bạn thành một giải pháp lặp để đẩy giá trị trung gian lên một ngăn xếp được phân bổ từ vùng heap.

Answer 6

Tôi vừa hết công việc, nó là một cơ sở dữ liệu và nó đang chạy một số chủ đề, về cơ bản, nhà phát triển trước đó đã ném một mảng lớn lên ngăn xếp và ngăn xếp thấp. Phần mềm đã được biên soạn bằng Microsoft Visual Studio 2015.

Mặc dù chủ đề đã hết hàng, nó không thành công và tiếp tục, nó chỉ bị tràn tràn khi truy cập nội dung dữ liệu trên ngăn xếp.

Lời khuyên tốt nhất tôi có thể đưa ra là không khai báo các mảng trên ngăn xếp - đặc biệt là trong các ứng dụng phức tạp và đặc biệt trong các chủ đề, thay vào đó hãy sử dụng đống. Đó là những gì nó có cho;)

Cũng chỉ cần ghi nhớ nó có thể không thất bại ngay lập tức khi tuyên bố ngăn xếp, nhưng chỉ khi truy cập. Tôi đoán là trình biên dịch tuyên bố ngăn xếp dưới cửa sổ "lạc quan", tức là nó sẽ giả định rằng ngăn xếp đã được khai báo và đủ kích cỡ cho đến khi nó được sử dụng và sau đó phát hiện ra rằng ngăn xếp không có.

Các hệ điều hành khác nhau có thể có các chính sách kê khai ngăn xếp khác nhau. Vui lòng để lại nhận xét nếu bạn biết chính sách này là gì.