2012-11-15 3 views
7

Il seguente programma chiamerà fun 2^(MAXD + 1) volte. La massima profondità di ricorsione non dovrebbe mai andare oltre il MAXD, anche se (se il mio pensiero è corretto). Quindi potrebbe volerci del tempo per compilare, ma non dovrebbe mangiare la mia RAM.Perché questo codice constexpr causa che GCC mangi tutta la mia RAM?

#include<iostream> 

const int MAXD = 20; 

constexpr int fun(int x, int depth=0){ 
    return depth == MAXD ? x : fun(fun(x + 1, depth + 1) + 1, depth + 1); 
} 

int main(){ 
    constexpr int i = fun(1); 
    std::cout << i << std::endl; 
} 

Il problema è che mangiare la mia RAM è esattamente quello che fa. Quando gira MAXD fino a 30, il mio laptop inizia a cambiare dopo che GCC 4.7.2 assegna rapidamente 3 GB circa. Non ho ancora provato con clang 3.1, in quanto non ho accesso ad esso in questo momento.

La mia unica ipotesi è che questo abbia qualcosa a che fare con GCC che cerca di essere troppo intelligente e memoize le chiamate alle funzioni, come con i modelli. Se è così, non sembra strano che non abbiano un limite alla quantità di memoizzazione che fanno, come le dimensioni di una tabella di cache MRU o qualcosa del genere? Non ho trovato un interruttore per disabilitarlo.

Perché dovrei farlo? Mi piace l'idea di creare una libreria di tempo di compilazione avanzata, come la programmazione genetica o qualcosa del genere. Dal momento che i compilatori non hanno l'ottimizzazione della coda di coda compilata, sono preoccupato che qualsiasi cosa abbia bisogno di ricorsione e (anche se alzo il massimo parametro di profondità di ricorsione, che sembra leggermente brutto da richiedere) allocherò rapidamente tutta la mia RAM e riempirò con cornici stack inutili. Così mi è venuta in mente la soluzione di cui sopra per ottenere arbitrariamente molte chiamate di funzione senza uno stack profondo. Tale funzione potrebbe essere utilizzata per piegare/avvolgere o trampollare.

EDIT: Ora l'ho provato in clang 3.1, e non perderà memoria, non importa per quanto tempo lo faccio funzionare (cioè quanto alto faccio MAXD). L'utilizzo della CPU è quasi del 100% e l'utilizzo della memoria è quasi dello 0%, proprio come previsto. Forse questo è solo un bug in GCC allora.

+0

mi hanno confermato che lo stack non va mai oltre MAXD (come previsto), eseguendo la funzione runtime e osservando che mentre posso farlo funzionare per un lungo periodo, non usa affatto RAM. – Gurgeh

+1

Potrebbe essere necessario segnalarlo come raccomandato in http://gcc.gnu.org/bugs/? – osgx

+0

@osgx In realtà non è un bug, vero? Secondo lo standard, suppongo che possano fare ciò che vogliono nella mia RAM. Inoltre, vorrei qualcuno che sappia cosa stanno facendo (tu sai chi sei), dicendomi quale sia la ragione. – Gurgeh

risposta

1

La tua risposta è nel tuo commento "eseguendo la funzione runtime e osservando che mentre posso farlo funzionare per un lungo periodo", che è causato dalla tua chiamata ricorsiva più ricettiva al divertimento (x + 1, profondità + 1).

Quando lo si è modificato in una funzione di runtime piuttosto che in una funzione di compilazione del tempo, rimuovendo constexpr e osservato che ha funzionato a lungo, è un indicatore del fatto che si ripercuote molto profondamente.

Quando la funzione viene eseguita dal compilatore deve recurse in profondità, ma non utilizza lo stack per la ricorsione poiché non sta effettivamente generando ed eseguendo codice macchina.

+0

ovviamente lo farà. Ritorna bene. Hai provato il codice? – Gurgeh

+0

La ricorsività profonda non è l'unico metodo mediante il quale qualcosa può essere eseguito per molto tempo. Può anche diramarsi ampiamente, che è quello che fa il mio codice. – Gurgeh

+0

Il tuo codice non si estende in senso lato. Ha solo un ramo e prende lo stesso lato del ramo su ogni ricorsione finché non si arresta. –

2

Questo non può essere il documento definitivo per quanto riguarda constexpr, ma è il doc primario legato alla dalla gcc constexpr wiki.

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2235.pdf

... e si dice ...

Noi (ancora) proibisce la ricorsione in tutte le sue forme in costante espressione. Questo non è strettamente necessario perché un limite di implementazione nella profondità di ricorsione nella valutazione delle espressioni costanti ci salverebbe da la possibilità che il compilatore ricorsivi per sempre. Tuttavia, fino a quando non visualizzeremo un caso di utilizzo convincente per la ricorsione, non proponiamo di consentirci l' .

Quindi, mi aspetto che stai urtando contro il confine linguistico e il modo in cui gcc ha scelto di attuare constexpr (forse il tentativo di generare l'intera linea funzione, quindi la valutazione/eseguirla)

+0

@Downvoter - cura di spiegare? – Roddy

+0

Quel documento è troppo vecchio, penso. Lo standard non proibisce la ricorsione, ma suggerisce un limite predefinito su 512 ricorsioni, qualcosa che rispetta sia gcc che clang, ma consente all'utente di ignorare. Potresti avere ragione che il problema non è la memoizzazione (anche se so che gcc lo fa a constexprs) ma che espande il codice in linea. – Gurgeh

+0

@Gurgeh - Sì: sembra essere un problema comune con gli standard ISO che il Web è disseminato di tutti i documenti possibili tranne lo standard vero e proprio :-) Il limite consigliato per il "numero di ricorsività" o la profondità di ricorsione? come nel tuo caso la profondità è 20, ma il "numero di ricorsioni" potrebbe essere considerato come 2^MAXD-1 come dici tu ... – Roddy