Limit stosu

Niedawno przetestowałem limit stosu na trzech urządzeniach z różnymi systemami operacyjnymi (przez limit rozumiem maksymalną liczbę poziomów, jaką może mieć stos), i zauważyłem, że za każdym razem, gdy osiągam 2 ^ 16 poziomów, daje mi to błąd przepełnienia, a gdy wstawię 2 ^ 16-1, działa poprawnie.

Więc moje pytanie brzmi - czy to prawda? Czy stos ma z definicji maksymalny limit 2 ^ 16-1, czy zależy to od systemu operacyjnego?

Jest silnie specyficzny dla systemu operacyjnego (i specyficzny dla komputera), aw niektórych systemach operacyjnych masz kilka sposobów na skonfigurowanie (a nawet zwiększenie) limitu. Jest nawet specyficzny dla kompilatora (lub specyficzny dla implementacji twojego języka programowania), ponieważ niektóre kompilatory (w tym najnowszy GCC dla pewnego ograniczonego rodzaju kodu C) są w stanie zoptymalizować niektóre wywołania tail .

^{(niektóre specyfikacje języka programowania wymagają optymalizacji połączeń ogonowych, np. R5RS )}

Nie jestem pewien, czy twoje pytanie ma sens (a na pewno nie limit 2 ¹⁶ ). Na moim komputerze z systemem Linux (Debian / Sid / x86-64, jądro Linux 4.9, 32 GB pamięci RAM, Intel i5-4690S) mogę mieć stos wywołań do 8 megabajtów (i mógłbym zwiększyć ten limit, jeśli naprawdę chciałbym ).

Wielowątkowość i ASLR sprawiają, że twoje pytanie jest znacznie bardziej złożone . Zobacz np. Pthread_attr_setstack (3) . Przeczytaj także o podzielonych stosach (często używanych przez implementacje Go ) oraz o stylu przekazywania kontynuacji . Zobacz także tę odpowiedź.

Za to, co jest warte, wypróbowałem następujący kod C99 (a także C11):

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void recfun(int x, int d) {
  printf("start recfun x=%d d=%d\n", x, d);
  fflush(NULL);
  if (d>0)
    recfun(x+1, d-1);
  printf("end recfun x=%d d=%d\n", x, d);
}

int main(int argc, char**argv) {
  int md = argc>1?atoi(argv[1]):10000;
  printf ("start md=%d\n", md);
  recfun(0, md);
  printf("end md=%d clock=%ld µs\n", md, clock());
}    
// eof recur.c

i mogłem uruchomić ten recurprogram (skompilowany z GCC 6 as gcc -Wall -O recur.c -o recur) jako recur 161000 (znacznie powyżej limitu 2 ¹⁶ ). Z recur 256000tym też działało. Z recur 456000awarią (z przepełnieniem stosu dla poziomu x=272057). Nie mam cierpliwości do innych testów. Wypróbuj to na swoim komputerze. Nie zapomnij poprosić o optymalizację.

Zasadą (dla komputerów stacjonarnych, laptopów, tabletów) może być utrzymywanie stosu połączeń poniżej jednego megabajta.

Przekazując również -fstack-usage do gcc , otrzymuję następujący recur.suplik (liczby są w bajtach, zgodnie z intuicją mojego stosu 8 Mb; nie zapomnij mainramki wywołania, a co ważniejsze, początkowego układu stosu, instalowanego przez jądro podczas wykonywania exec (2) ) ..., dla crt0 ):

 recur.c:5:10:recfun    32  static
 recur.c:13:9:main  16  static

PS. Moje Arduino ma Atmega328 z zaledwie 2 KB pamięci RAM, więc na pewno nie będzie tak wiele. Wydaje mi się, że tylko kilkaset ramek stosu jest co najwyżej praktycznie możliwe na Arduinos.

Rozmiar stosu dla głównego wątku procesu Windows jest ustawiany przez konsolidator. Domyślnie jest to 1 MB, ale można go zmienić za pomocą przełącznika / STACK. Wątki utworzone później mogą korzystać z parametru dwStackSize funkcji CreateThread.

Więc ... jeśli testujesz różne systemy operacyjne Windows, wszystkie mają ten sam domyślny rozmiar stosu od co najmniej NT4.0.