È una buona ragione per usare alloca?

Question

Ho la seguente funzione:

double 
neville (double xx, size_t n, const double *x, const double *y, double *work); 

che esegue l'interpolazione di Lagrange a xx base alle n punti memorizzati nel x e y. L'array work ha la dimensione 2 * n. Dal momento che questo è l'interpolazione polinomiale, n è nel campo da baseball di ~ 5, molto raramente più di 10.

Questa funzione è aggressivo ottimizzata, e dovrebbe essere chiamato in cicli stretti. La profilazione suggerisce che l'heap che alloca l'array di lavoro nel ciclo non è corretto. Sfortunatamente, dovrei comprimerlo in una classe simile alla funzione, e i client devono essere inconsapevoli della matrice di lavoro.

Per ora, utilizzare un argomento di template intero per il grado e std::array evitare l'allocazione dinamica della matrice work:

template <size_t n> 
struct interpolator 
{ 
    double operator() (double xx) const 
    { 
     std::array<double, 2 * n> work; 
     size_t i = locate (xx); // not shown here, no performance impact 
           // due to clever tricks + nice calling patterns 

     return neville (xx, n, x + i, y + i, work.data()); 
    }   

    const double *x, *y; 
}; 

Sarebbe stato possibile memorizzare la matrice lavoro come membro mutevole della classe, ma si suppone che operator() venga utilizzato contemporaneamente da più thread. Questa versione è OK se conosci n in fase di compilazione.

Ora, ho bisogno del parametro n da specificare in fase di esecuzione. Mi chiedo a qualcosa di simile:

double operator() (double xx) const 
{ 
    auto work = static_cast<double*> (alloca (n * sizeof (double))); 
    ... 

Alcuni campane suonano quando si utilizza alloca: sto ovviamente intenzione di avere un tetto n per evitare la chiamata alloca traboccare (in ogni caso è abbastanza stupido da usare grado 100 interpolazione polinomiale).

Sono abbastanza scomodo con l'approccio però:

• Mi sto perdendo qualche pericolo evidente di alloca?
• C'è un modo migliore per evitare l'allocazione dell'heap qui?

Answer 1

Sono abbastanza scomodo con l'approccio però:

• Mi sto perdendo qualche pericolo evidente di alloca?

lei ha l'unico vero pericolo out: comportamento overflow dello stack non è definito per alloca. Inoltre, alloca non è in realtà standardizzato. Ad esempio, Visual C++ ha invece _alloca e GCC by default defines it as a macro. Questo problema può essere aggirato abbastanza facilmente, tuttavia, fornendo un involucro sottile attorno alle poche implementazioni esistenti.

• C'è un modo migliore per evitare l'allocazione dell'heap qui?

Non proprio. C++ 14 avrà un (potenzialmente!) Tipo di array a lunghezza variabile assegnato allo stack.Ma fino ad allora, e se consideri che std::array non sia una buona idea, vai su alloca in casi come il tuo.

Minore nitpick però: nel codice manca un cast del valore restituito di alloca. Non dovrebbe nemmeno compilare.

Answer 2

ci sono sempre un sacco di note da aggiungere a qualsiasi uso della memoria stack. Come fai notare, le pile hanno dimensioni finite e comportamenti scorretti abbastanza gravi quando lo spazio si esaurisce. Si spera che l'overflow dello stack si arresti in modo anomalo se sono presenti pagine di protezione, ma su alcune piattaforme e ambienti di threading a volte può trattarsi di un danneggiamento non presidiato (danneggiato) o di un problema di sicurezza (peggio).

Ricordare inoltre che lo stack allocazione è molto veloce rispetto a malloc, (è solo una sottrazione dal registro puntatore dello stack). Ma lo utilizza la memoria di quella memoria potrebbe non esserlo. L'effetto collaterale di spingere la cornice dello stack verso il basso di grandi quantità è che le linee della cache delle funzioni foglia che stai per chiamare non sono più residenti. Pertanto, qualsiasi utilizzo di tale memoria deve passare all'ambiente SMP per riportare le linee cache in uno stato esclusivo (nello stato MESI). Il bus SMP è un ambiente molto (!) Più limitato rispetto alla cache L1 e, se si sta inviando spam ai propri stack, questo può rappresentare un vero problema di scalabilità.

Inoltre, per quanto riguarda la sintassi, si noti che sia gcc che clang (e il compilatore Intel credo) supportano la sintassi dell'array di lunghezza variabile C99 come estensione C++. Potrebbe non essere necessario chiamare effettivamente la routine libc alloca().

Infine, notare che malloc non è poi così lento. Se hai a che fare con singoli buffer del regno di dozzine di kilobyte o più grandi, la larghezza di banda della memoria necessaria per riparare qualsiasi lavoro tu stia facendo su di loro sta per inondare qualsiasi overhead da malloc.

Fondamentalmente: alloca() è carino, e ha i suoi usi, ma a meno che tu non abbia un benchmark pronto a dimostrare che ne hai bisogno, probabilmente non lo farai e dovresti semplicemente attenersi all'assegnazione tradizionale.

Answer 3

ne dite di questo:

double operator() (double xx) const 
{ 
    double work_static[STATIC_N_MAX]; 
    double* work = work_static; 
    std::vector<double> work_dynamic; 

    if (n > STATIC_N_MAX) { 
     work_dynamic.resize(n); 
     work = &work_dynamic[0]; 
    } 

    ///... 

Nessuna caratteristica non portatili, sicuro rispetto alle eccezioni, e degrada con grazia quando n è troppo grande. Naturalmente, è possibile effettuare work_static a std::array, ma non sono sicuro di quale vantaggio si possa vedere in questo.