Come migliorare il tempo di compilazione per una gigantesca espressione booleana?

Question

Ho bisogno di eseguire un controllo piuttosto complesso su un vettore e devo ripeterlo migliaia e milioni di volte. Per renderlo più efficiente, traduco la formula data in codice sorgente C++ e la compilo in binario fortemente ottimizzato, che chiamo nel mio codice. La formula è sempre puramente booleana: solo & &, || e ! Usato. codice sorgente tipico è simile al seguente:

#include <assert.h> 
#include <vector> 

using DataType = std::vector<bool>; 

static const char T = 1; 
static const char F = 0; 
const std::size_t maxidx = 300; 

extern "C" bool check (const DataType& l); 

bool check (const DataType& l) { 
    assert (l.size() == maxidx); 
    return (l[0] && l[1] && l[2]) || (l[3] && l[4] && l[5]); //etc, very large line with && and || everywhere 
} 

compilo come segue:

g++ -std=c++11 -Ofast -march=native -fpic -c check.cpp 

prestazioni del binario risultante è di fondamentale importanza.

Ha funzionato perfettamente con il recente test case con il gran numero di variabili (300, come potete vedere sopra). Con questo test case, g ++ consuma più di 100 GB di memoria e si blocca per sempre.

La mia domanda è piuttosto semplice: come posso semplificare quel codice per il compilatore? Dovrei usare alcune variabili aggiuntive, eliminare il vettore o qualcos'altro?

MODIFICA 1: Ok, ecco lo screenshot dal programma di utilità superiore.

cc1plus è occupato con il mio codice. La funzione controllo dipende da 584 variabili (mi dispiace per un numero impreciso nell'esempio sopra) e contiene 450'000 espressioni.

Sono d'accordo con il commento di @ akakatak qui sotto. Sembra che g ++ esegua qualcosa O (N^2).

Answer 1

È un po 'necro-posting, ma dovrei comunque condividere i miei risultati.

La soluzione proposta da Thilo nei commenti sopra è la migliore. È molto semplice e fornisce un miglioramento misurabile del tempo di compilazione. Basta dividere la tua espressione in pezzi della stessa dimensione. Ma, secondo la mia esperienza, devi scegliere con attenzione una lunghezza di espressione secondaria appropriata - puoi riscontrare un calo significativo delle prestazioni di esecuzione in caso di un numero elevato di espressioni secondarie; un compilatore non sarà in grado di ottimizzare perfettamente l'intera espressione.

Answer 2

L'ovvio ottimizzazione è quello di buttare fuori il vettore e usare un po 'di campo, sulla base del più veloce tipo intero possibili:

uint_fast8_t item [n]; 

si potrebbe scrivere questo come

#define ITEM_BYTES(items) ((items)/sizeof(uint_fast8_t)) 
#define ITEM_SIZE(items) (ITEM_BYTES(items)/CHAR_BIT + (ITEM_BYTES(items)%CHAR_BIT!=0)) 
... 
uint_fast8_t item [ITEM_SIZE(n)]; 

Ora avere un pezzo di memoria con i segmenti n, dove ogni segmento è la dimensione ideale per la tua CPU. In ogni segmento, imposta i bit su 1 = vero o 0 = falso, utilizzando operatori bit a bit.

A seconda di come si desidera ottimizzare, si raggruppano i bit in modi diversi. Vorrei suggerire di memorizzare 3 bit di dati in ogni segmento, dal momento che si desidera sempre controllare 3 numeri booleani adiacenti. Questo significa che "n" nell'esempio di cui sopra sarà il numero totale di booleani diviso per 3.

Si può poi semplicemente scorrere la matrice come:

bool items_ok() 
{ 
    for(size_t i=0; i<n; i++) 
    { 
    if((item[i] & 0x7u) == 0x7u) 
    { 
     return true; 
    } 
    } 
    return false; 
} 

---

Con il metodo sopra di voi ottimizzazione:

• La dimensione dei dati in cui vengono effettuati i confronti e con i possibili problemi di allineamento.
• Uso memoria generale.
• Il numero di rami necessari per i confronti.

Questo esclude anche i rischi di inefficacia causati dalla solita programmazione meta C++. Non mi fiderei mai di std::vector, std::array o std::bitfield per produrre codice ottimale.

Una volta che hai funzionato sopra, puoi sempre verificare se i contenitori std::bitfield ecc. Restituiscono lo stesso codice macchina efficace. Se scopri che hanno generato qualsiasi forma di follia non correlata nel tuo codice macchina, non usarli.