Perché non vediamo (più) l'adozione diffusa di allocatori di memoria dinamica senza blocco? [chiuso]

Question

Perché non vediamo (più) l'adozione diffusa di allocatori di memoria dinamica senza blocco? [chiuso]

#1 da (4 voti)
#2 da (1 voti)

1

In un ambiente di programmazione con multithreading, il contenimento del blocco sull'heap è spesso un collo di bottiglia delle prestazioni.

In teoria, almeno, la soluzione crema-del-raccolto per questo problema è di avere l'allocatore scalabile / parallelo [izing] completamente privo di blocco. Tuttavia, mi sembra che oltre a pochi documenti di ricerca (ad es. [1] [2] [5]), che contengono risultati sperimentali promettenti, gli allocatori interamente privi di lock non siano passati agli ambienti di produzione. Sarei felice se tu potessi dimostrarmi in errore con contro-esempi però. Quindi quali sono le ragioni pratiche per questa lenta (o inesistente) adozione di allocatori lock-free? Si noti che gli allocatori scalabili più diffusi come quello della TBB di Intel non sono privi di blocco nonostante utilizzino blocchi a grana fine (cfr. 315 in [3]).

Per quel che vale, ho anche trovato un progetto / carta per studenti CMU [4], che afferma di aver implementato un allocatore lock-free che è "leggermente migliore di [Google's] tcmalloc" su un massimo di 64 core. Un altro punto interessante di questo articolo è che "llalloc in questi test è l'allocatore LockLess di Lockless Inc., che non è bloccato al 100% (ha un blocco attorno all'heap globale)". jemalloc e ptmalloc sono anche testati qui.

References:

[1] Michael, Maged M. "Allocazione dinamica della memoria dinamica senza blocco. " ACM Sigplan Avvisi 39.6 (2004): 35-46. Ho trovato un'implementazione [re] indipendente dell'algoritmo di Michael al link

[2] Huang, Xiaohuang, et al. "Xmalloc: un allocatore di memoria dinamico senza blocco scalabile per macchine a molti core." Computer and Information Technology (CIT ), 2010 Conferenza internazionale IEEE su. IEEE, 2010. Versione gratuita del documento come tesi di laurea .

[3] Kukanov, Alexey e Michael J. Voss. "I fondamenti per software scalabile multi-core in Intel Threading Building Blocks. " Intel Technology Journal 11.4 (2007).

[4] Alex Podolsky, Nah Lock: un Allocatore di memoria Lock-Free ; apparentemente scritto nel 2013 in base ai timestamp della directory madre e al suffisso "S13" nel nome del corso.

[5] Gidenstam, Anders, Marina Papatriantafilou e Philippas Tsigas. "NBmalloc: allocazione della memoria in modo bloccato" Algorithmica 58.2 (2010 ): 304-338. Codice sorgente disponibile per questo.

Come nota a piè di pagina, vedo che ci sono 4 voti chiusi in sospeso per questa domanda, ma non vedo nessuno per Perché la grafica vettoriale con accelerazione hardware non viene rimossa? . Sarebbe interessante se qualcuno potesse spiegare perché una domanda che potrebbe potenzialmente essere risolta con numeri di prestazione un po 'oggettivi è più basata sull'opinione di quella in cui il fattore principale è l'orientamento al mercato di 2-3 grandi aziende.

multithreading locks malloc

posta Fizz 22.01.2015 - 07:08

fonte

2 risposte

Leggi altre domande sui tag multithreading locks malloc

Quanto ti aiuta in altre lingue? [duplicare] Riprova il metodo per generare codice univoco

score 4 · Answer 1

Ecco alcune risposte possibili:

IBM ha brevettato il loro allocatore lock-free ... Ma poi supportano anche Linux ecc., quindi potrebbero avere un incentivo a fornire almeno un'implementazione. E anche i ragazzi di XMalloc hanno presentato un brevetto per loro . Ma non ho [ancora] trovato alcun brevetto (o domanda di brevetto) per NBmalloc.
Un problema più localizzato è che M. Michael sembra aver cessato di pubblicare su IBM proprio dopo quel documento. Non sono sicuro che sia ancora in IBM, ma averlo lasciato o cambiare focus potrebbe essere una ragione per cui IBM non ha provato a produrre il suo allocatore, come IBM ha fatto con i precedenti allocatori di Watson / Watson2 che lo hanno trasformato in AIX. Gli altri allocatori lock-free non sembrano avere connessioni con una grande azienda che potrebbe spingerli in un prodotto.
Infine, un motivo più generale sarebbe il rapporto relativo tra complessità del codice e benefici prestazionali. Citando da "Provando che gli algoritmi non bloccanti non si bloccano" di A. Gotsman et al.

Non-blocking data structures are generally much more complex than their lock-based counterparts, but can provide better performance in the presence of high contention between threads.

Quindi, la complessità del codice dovrebbe essere giustificata da significativi guadagni in termini di prestazioni. Mentre alcuni documenti di allocatore bloccati hanno affermato che ... altri documenti hanno prodotto risultati contrari o di lavaggio dei desideri. In particolare, il documento Streamflow , i cui autori hanno reimplementato l'algoritmo di Michael, dichiara di averlo battuto in modo sano utilizzando un allocatore che non era privo di blocco. Il testo del corso di Podolsky è venuto solo con miglioramenti relativamente marginali. Quindi immagino che la giuria sia ancora fuori se gli allocatori senza lock valgono lo sforzo extra.

score 1 · Answer 2

Come fai a sapere che gli allocatori / deallocatori senza lock non vengono utilizzati? Ad esempio, prendi malloc su MacOS X e iOS. Sai che è senza serratura o no? (La loro documentazione dice che chiamare malloc e liberare sullo stesso thread in breve sequenza è molto veloce, e questo è il caso che ti preoccupi).