standard - gcc c++ 17




Perché std:: reduce è stato aggiunto in C++ 17? (2)

Stavo cercando una spiegazione esaustiva del significato della descrizione "Valore restituito" per std::reduce , che secondo cppreference.com è:

Forse dopo aver percepito correttamente l'idea alla base della sezione "Valore restituito", posso determinare meglio dove dovrei scegliere std::reduce su std::accumulate .


Dato che hai chiesto una spiegazione esaustiva, e la risposta precedente copre solo le basi, mi sto prendendo la libertà di aggiungerne una più approfondita.

std::reduce è progettato per eseguire il secondo importante passo del modello di programmazione MapReduce . L'idea di base è che la piattaforma (in questo caso, l'implementazione C ++) fornisce queste due primitive operazioni di mappa e riduzione, e il programmatore fornisce operazioni di callback per ciascuno dei due che eseguono il "lavoro effettivo".

Fondamentalmente, il callback per l'operazione mappa mappa un valore di input su un valore intermedio. Il callback per la riduzione combina due valori intermedi in un valore intermedio. L'ultimo valore intermedio rimasto diventa l'output dell'intera MapReduce. Sembra essere un modello molto restrittivo in sé, ma ha ancora una vasta gamma di applicazioni.

La piattaforma deve fare di più, naturalmente, come "shuffling" (distribuendo gli input, solitamente in gruppi, a diverse unità di elaborazione) e la pianificazione, ma questo è di scarsa importanza per il programmatore dell'applicazione.

A proposito, nella libreria standard C ++, l'operazione "map" è chiamata transform . Ha ricevuto anche il supporto per il parallelismo in C ++ 17, ma entrerò nel parallelismo più tardi.

Ecco un esempio inventato: diciamo che abbiamo una funzione che converte un numero intero in una rappresentazione di stringa. Ora, data una lista di numeri interi, vogliamo che la rappresentazione testuale contenga il più alto rapporto di consonanti con le voci. Per esempio

  • Ingresso: 1, 17, 22, 4, 8
  • Uscita: ventidue

(Provalo tu stesso se non credi a questo risultato.)

Potremmo usare MapReduce qui usando la nostra funzione int-to-text come callback to map (rsp. std::transform ), e una funzione che conta il numero di consonanti e di voci e quindi seleziona la mano sinistra o la mano destra argomento di conseguenza. Ci sono alcune inefficienze qui, in particolare, il "rapporto" dovrebbe essere memorizzato nella cache, ma questi sono dettagli.

Ora la tua domanda potrebbe e dovrebbe essere: perché dovrei aver cura di me? Dopotutto, finora non hai guadagnato molto std::transform e std::reduce in questo modo, e potresti aver usato anche std::accumulate al posto di quest'ultimo. La risposta, naturalmente, dato un numero sufficientemente grande di valori di input , sono le politiche di esecuzione: i primi due modelli di funzioni standard hanno sovraccarichi che consentono il parallelismo implicito. Ma questo continua a chiedersi perché si dovrebbe usare MapReduce e non un pool di thread o std::async e un mucchio di loop scritti a mano? Innanzitutto, soprattutto per i calcoli "puri" su vettori di grandi dimensioni o altri contenitori, senza I / O, è spesso più conveniente scrivere i due callback MapReduce perché non è necessario gestire tutti i dettagli di come i dati di input sono sparsi per fili diversi e poi combinati.

In secondo luogo, MapReduce incoraggia una disciplina di strutturazione dei calcoli in un modo che può essere parallelizzato in modo molto efficace. Ovviamente, in un linguaggio di programmazione che supporta il paradigma imperativo, come il C ++, è comunque possibile creare problemi bloccando una serie di mutex, o qualunque altro modo si possa avere interferendo con altri thread. Ma il paradigma MapReduce incoraggia la scrittura di callback di mapping indipendenti. Come semplice regola empirica, se queste attività condividono i dati, dovrebbe essere di sola lettura in modo che le copie di esso possano essere memorizzate in più cache della CPU contemporaneamente. Compiti ben scritti, combinati con un'efficiente implementazione della piattaforma degli algoritmi sottostanti, possono scalare fino a centinaia o persino migliaia di core CPU, come dimostrato dalle piattaforme MapReduce già in uso comune (come Apache Hadoop, ma prendetelo solo come necessario esempio e non come pubblicità gratuita).

Ma la domanda era principalmente su std::reduce - potevamo ancora eseguire questa mappatura altamente scalabile e quindi eseguire std::accumulate sui risultati intermedi, giusto? Ed è qui che arriviamo a ciò che ha scritto in precedenza François Andrieux. accumulate ciò che i matematici chiamano una piega sinistra. Se si visualizzano le operazioni e i loro operandi come un albero binario, questo sarebbe un albero pendente a sinistra, ad esempio per aggiungere 1, 2, 3 e 4:

   +
  / \
  + 4
 / \
 + 3
/ \
1 2

Come puoi vedere, il risultato di ogni operazione è uno degli argomenti della prossima operazione. Ciò significa che esiste una catena lineare di dipendenze dei dati, e questa è la rovina di tutto il parallelismo. Per aggiungere un milione di numeri, hai bisogno di un milione di operazioni consecutive, che bloccherà un singolo core, e non puoi fare uso di core aggiuntivi. Non avranno nulla da fare la maggior parte del tempo e il sovraccarico della comunicazione supererà di gran lunga il costo dei calcoli. (In realtà è peggio di così perché le moderne CPU possono eseguire più calcoli semplici per orologio, ma questo non funziona quando ci sono così tante dipendenze di dati, quindi la maggior parte delle ALUs o FPU non vengono utilizzate.)

Sollevando la restrizione che deve essere utilizzata una piega a sinistra, std::reduce consente alla piattaforma di utilizzare in modo più efficiente le risorse computazionali. Anche se si utilizza il sovraccarico a thread singolo , la piattaforma potrebbe, ad esempio, utilizzare SIMD per aggiungere un milione di numeri interi in meno di un milione di operazioni e il numero di dipendenze dei dati sarà notevolmente ridotto. Un 10x di accelerazione su una riduzione di un intero ben scritto non mi sorprenderebbe. Certo, questo particolare caso speciale potrebbe probabilmente essere ottimizzato sotto la regola as-if perché l'implementazione C ++ "sa" che l'aggiunta di un intero è (quasi, vedi sotto) associativa.

Ma la riduzione va oltre, come si è detto, sostenendo le politiche di esecuzione, cioè nella maggior parte dei casi il parallelismo multi-core. In teoria, potrebbe essere usato un albero binario bilanciato di operazioni. (Ricorda che un albero è bilanciato se la profondità è o meno di due, o la profondità del sottostruttura di sinistra è diversa dalla profondità della sottostruttura di destra di almeno 1.) Tale albero ha solo la profondità logaritmica. Se abbiamo un milione di interi, la profondità minima dell'albero è 20, quindi - teoricamente - dati abbastanza core e nessun overhead di comunicazione, potremmo ottenere un fattore 50.000 di accelerazione anche con il calcolo ottimizzato a thread singolo. Certo, in pratica, questo è un carico di pio desiderio, ma possiamo ancora aspettarci grandi aumenti di velocità.

Detto ciò, lasciatemi aggiungere un breve disclaimer / promemoria che le prestazioni non sono le stesse dell'efficienza. L'utilizzo di 64 core per 100 ms ciascuno significa prestazioni molto più elevate rispetto all'utilizzo di un core per 1.000 ms, ma molto meno dell'efficienza della CPU. Un altro modo per dirlo è che le prestazioni sono efficienza nel senso di ridurre al minimo il tempo trascorso, ma ci sono altre misure di efficienza: tempo totale della CPU utilizzato, RAM utilizzata, energia utilizzata e così via. La principale motivazione della parallela MapReduce è fornire prestazioni più elevate. Se riduce il tempo di CPU o il consumo di energia non è chiaro, e molto probabilmente aumenterà l'utilizzo massimo della RAM.

Per completare il tutto, ecco alcuni avvertimenti . Come accennato, la reduce non è deterministica se le operazioni non sono associative o non commutative. Fortunatamente, le operazioni aritmetiche più importanti come addizione e moltiplicazione sono associative e commutative, giusto? Sappiamo tutti che l'aggiunta in virgola mobile e in virgola mobile, ad esempio, hanno entrambe queste proprietà. E, naturalmente, mi sto comportando da faceto. In C ++, né l'aggiunta di interi con segno né l'aggiunta di virgola mobile sono associati. Per i numeri in virgola mobile, ciò è dovuto alle possibili differenze nell'arrotondamento dei risultati intermedi. Questo è facilmente visualizzabile se, ad esempio, selezioniamo un semplice formato decimale a virgola mobile con due cifre significative e consideriamo la somma 10 + 0,4 + 0,4. Se questo viene fatto dalle normali regole di sintassi del C ++ come una piegatura a sinistra, otteniamo (10 + 0.4) + 0.4 = 10 + 0.4 = 10 perché ogni volta che il risultato viene arrotondato per difetto a 10. Ma se lo facciamo come 10 + (0,4 + 0,4), il primo risultato intermedio è 0,8 e 10 + 0,8 viene arrotondato a 11. Inoltre, gli errori di arrotondamento possono essere notevolmente ingranditi da una profondità elevata dell'albero delle operazioni, quindi fare una piega a sinistra è in realtà uno delle cose peggiori che si possono fare quando si tratta di precisione. Esistono diversi modi per gestire questo comportamento, che vanno dall'ordinamento e al raggruppamento degli input fino all'utilizzo di una precisione intermedia aumentata, ma quando si tratta di reduce , potrebbe semplicemente non esserci modo di ottenere una coerenza run-for-run del 100%.

L'altra osservazione, forse più sorprendente, è che l'aggiunta di un intero con segno non è associativa in C ++. La ragione di ciò è la possibilità di overflow, per dirla senza mezzi termini: (-1) + 1 + INT_MAX . In base alle normali regole di sintassi o accumulate , il risultato è INT_MAX . Ma se si utilizza reduce , questo potrebbe essere riscritto come (-1) + (1 + INT_MAX) che contiene un overflow intero e quindi un comportamento non definito . Infatti, poiché la reduce può arbitrariamente modificare l'ordine degli operandi, questo è vero anche se gli input sono { INT_MAX, -1, 1 } .

La mia raccomandazione qui è di garantire che il callback da reduce non possa produrre un overflow. Questo può essere fatto limitando l'intervallo di input consentito (ad es. Se aggiungi 1000 int , assicurati che nessuno di questi sia maggiore di INT_MAX / 1000 o inferiore a INT_MIN / 1000 , arrotondato per INT_MIN / 1000 ), ad esempio, o, equivalentemente, utilizzando un tipo intero più grande o, come ultima risorsa assoluta (perché questo è sia costoso che difficile da gestire correttamente), ponendo controlli aggiuntivi nella reduce callback. Nella maggior parte dei casi pratici, tuttavia, la reduce è marginalmente meno sicura per quanto riguarda l'overflow dei numeri interi rispetto accumulate .


std::accumulate iterazioni sul contenitore in ordine in cui come std:reduce potrebbe non. Poiché l'ordine non è garantito, std::reduce introduce requisiti aggiuntivi:

Il comportamento non è deterministico se binary_op non è associativo o non commutativo. Il comportamento non è definito se binary_op modifica un elemento o invalida qualsiasi iteratore in [first; ultimo], incluso l'iteratore finale.

Tuttavia, std::reduce fornisce sovraccarichi che supportano la parallelizzazione che non sono disponibili con std::accumulate . std::reduce consente di parallelizzare automaticamente l'operazione, purché soddisfi i requisiti sopra menzionati.





c++17