2012-01-13 4 views
21

Durante il debug, ho fatto spesso un passo nell'implementazione dell'assemblaggio scritto a mano di memcpy e memset. Questi sono di solito implementati utilizzando istruzioni di streaming se disponibili, loop srotolato, allineamento ottimizzato, ecc ... Ho anche recentemente incontrato questo 'bug' due to memcpy optimization in glibc.Perché la memcpy/memset è complessa?

La domanda è: perché i produttori di hardware (Intel, AMD) non è in grado di ottimizzare il caso specifico di

rep stos 

e

rep movs 

di essere riconosciuto come tale, e fare la più veloce riempire e copiare il più possibile su la propria architettura?

+3

Risposta di uscita: perché semplicemente non lo fanno, e come risultato nessuno scrive codice in questo modo, e quindi non c'è motivo per farlo ... (il ciclo continua) –

+1

@BillyONeal: non lo faccio pensa così Per ogni nuova funzionalità che aggiungono, non è ancora stato scritto alcun codice che lo utilizza. – ybungalobill

+1

Sì, ma quando viene aggiunta una nuova funzione, questa viene aggiunta per mostrare prestazioni migliori in un'area o nell'altra. Ottimizzare questo non ha senso per i fornitori di CPU perché i compilatori non emetteranno il codice come esso. –

risposta

23

Costo.

Il costo dell'ottimizzazione di memcpy nella libreria C è piuttosto ridotto, forse qualche settimana di tempo di sviluppo qua e là. Dovrai creare una nuova versione ogni parecchi anni circa quando le caratteristiche del processore cambiano abbastanza da giustificare una riscrittura. Ad esempio, GNU glibc e Apple libSystem hanno entrambi uno memcpy che è specificamente ottimizzato per SSE3.

Il costo dell'ottimizzazione nell'hardware è molto più alto. Non solo è più costoso in termini di costi di sviluppo (la progettazione di una CPU è molto più difficile rispetto alla scrittura del codice di assemblaggio spazio utente), ma aumenterebbe il conteggio dei transistor del processore.Che potrebbe avere una serie di effetti negativi:

  • maggior consumo di corrente
  • Aumento unità costare
  • maggiore latenza per determinati sottosistemi CPU
  • Bassa massima velocità di clock

In teoria, potrebbe avere un impatto negativo generale sul rendimento e sul costo unitario.

Maxim: Non farlo in hardware se la soluzione software è sufficiente.

Nota: Il bug che hai citato non è un bug in glibc w.r.t. la specifica C È più complicato Fondamentalmente, la gente di glibc dice che memcpy si comporta esattamente come pubblicizzato nello standard, e alcune altre persone si lamentano che lo memcpy debba essere sostituito con lo memmove.

tempo per una storia: Mi ricorda di una denuncia che un gioco sviluppatore Mac aveva quando correva il suo gioco su un processore al posto di un 601 (questo è dal 1990) 603. Il 601 aveva il supporto hardware per carichi e negozi non allineati con penalità di prestazioni minime. Il 603 ha semplicemente generato un'eccezione; scaricando nel kernel immagino che l'unità di carico/archivio potrebbe essere resa molto più semplice, rendendo probabilmente il processore più veloce ed economico nel processo. Il nanokernel di Mac OS gestiva l'eccezione eseguendo l'operazione di caricamento/archiviazione richiesta e restituendo il controllo al processo.

Ma questo sviluppatore aveva una routine personalizzata di scrittura per scrivere pixel sullo schermo che conteneva carichi e negozi non allineati. Le prestazioni del gioco andavano bene sul 601 ma erano abominevoli sul 603. La maggior parte degli altri sviluppatori non si sono accorti se avessero usato la funzione di blitting di Apple, dal momento che Apple poteva semplicemente reimplementarlo per i nuovi processori.

La morale della storia è che prestazioni migliori derivano sia da miglioramenti software che hardware.

In generale, la tendenza sembra essere nella direzione opposta rispetto al tipo di ottimizzazioni hardware menzionate. Mentre in x86 è facile scrivere memcpy in assembly, alcune architetture più recenti offloadano ancora più lavoro sul software. Di particolare rilievo sono le architetture VLIW: Intel IA64 (Itanium), TI TMS320C64x DSP e Transmeta Efficeon sono esempi. Con VLIW, la programmazione degli assembly diventa molto più complicata: devi selezionare in modo esplicito quali unità di esecuzione ottengono quali comandi e quali comandi possono essere eseguiti allo stesso tempo, qualcosa che un x86 moderno farà per te (a meno che non sia un Atom). Quindi scrivere memcpy diventa improvvisamente molto, molto più difficile.

Questi trucchi architettonici ti consentono di tagliare un'enorme quantità di hardware dai tuoi microprocessori pur mantenendo i vantaggi prestazionali di un design superscalare. Immagina di avere un chip con un footprint più vicino a un Atom ma una performance più vicina a un Xeon. Sospetto che la difficoltà di programmare questi dispositivi sia il fattore principale che impedisce un'adozione più ampia.

+1

Non ho detto che era un bug, quindi le virgolette. Ho citato un commento specifico dal thread. E la mia opinione personale: glibc ha ragione, Linus Torvalds ha torto. – ybungalobill

+0

Buona risposta. O come lo riassumerei: "Non fare cose nell'hardware, se puoi farlo con la stessa efficienza del software". A proposito di cosa glibc: Torvalds è chiaramente quello pratico qui: gli utenti non si preoccupano del perché qualcosa non funzioni. E in qualche modo dubito che 'memmove' abbia un notevole successo in termini di prestazioni rispetto a' memcpy' in questi giorni .. dovrà testarlo. – Voo

+0

@ybungalobill: stavo semplicemente aggiungendo il contesto, poiché anche se potreste conoscere la storia di glibc 'memcpy', i visitatori del sito potrebbero non farlo. –

5

General Purpose vs. Specialized

Un fattore è che tali istruzioni (Avviso di rep prefisso/stringa) sono di uso generale, in modo che sarà gestire qualsiasi allineamento, qualsiasi numero di byte o parole e faranno avere un determinato comportamento relativo alla cache e/o allo stato dei registri, ecc. ovvero effetti collaterali ben definiti che non possono essere modificati.

La copia di memoria specializzata può funzionare solo per determinati allineamenti, dimensioni e può avere un comportamento diverso rispetto alla cache.

L'assembly scritto a mano (o nella libreria o uno sviluppatore può implementare se stessi) può sovvertire l'implementazione dell'istruzione di stringa per i casi speciali in cui viene utilizzato. I compilatori hanno spesso diverse implementazioni di memcpy per casi speciali e quindi lo sviluppatore può avere un caso "molto speciale" in cui eseguono il proprio.

Non ha senso fare questa specializzazione a livello hardware. Troppa complessità (= costo).

La legge dei rendimenti decrescenti

Un altro modo di pensare a questo proposito è che, quando vengono introdotte nuove funzionalità, ad esempio, SSE, i progettisti apportano modifiche architettoniche per supportare queste funzionalità, ad es. un'interfaccia di memoria a larghezza di banda più ampia o più ampia, modifiche alla pipeline, nuove unità di esecuzione, ecc. A questo punto, il progettista è improbabile tornare alla parte "legacy" del progetto per cercare di portarlo alle ultime caratteristiche . Sarebbe controproducente. Se segui questa filosofia potresti chiederti perché abbiamo bisogno di SIMD in primo luogo, il progettista non può semplicemente fare in modo che le istruzioni strette funzionino alla stessa velocità di SIMD per quei casi in cui qualcuno utilizza SIMD? Di solito la risposta è che non ne vale la pena perché è più facile inserire una nuova unità di esecuzione o istruzioni.

+0

Ho i seguenti problemi con questa risposta: "quelle istruzioni sono di uso generale" così è la 'memcpy' nella libreria. Può funzionare con qualsiasi allineamento, ecc ... "un certo comportamento relativo alla cache e/o allo stato dei registri" la semantica dei "rep stos" è molto più semplice della 'memcpy' basata su SIMD. Conoscete gli effetti collaterali anche prima dell'esecuzione del comando, è solo "esi + = ecx, edi + = ecx, ecx = 0'. Niente altro è cambiato, al contrario della versione di SIMD in cui si utilizza praticamente quasi tutto sulla CPU. – ybungalobill

+0

"La copia di memoria specializzata ..." Non parlo di specialista. "L'assemblea scritta a mano potrebbe emulare l'implementazione della libreria ..." cosa? L'implementazione della libreria * è * scritta a mano. – ybungalobill

+0

@ybungalobill: alcune persone scrivono le proprie funzioni di copia di mem e quindi ci sono implementazioni di librerie specializzate. Non mi era chiaro di quali stavi parlando. Chiarirò la mia risposta. –

1

Nei sistemi embedded, è comune disporre di hardware specializzato che memcpy/memset. Normalmente non è fatto come una speciale istruzione CPU, piuttosto è una periferica DMA che si trova sul bus di memoria. Scrivi un paio di registri per dirgli gli indirizzi e HW fa il resto. In realtà non garantisce una particolare istruzione della CPU poiché si tratta solo di un problema di interfaccia di memoria che non ha realmente bisogno di coinvolgere la CPU.

1

Se non si rompe non ripararlo. Non è rotto.

Un problema principale sono gli accessi non allineati. Passano da cattivi a pessimi a seconda dell'architettura su cui si sta eseguendo. Molto ha a che fare con i programmatori, alcuni con i compilatori.

Il modo più economico per correggere memcpy è di non utilizzarlo, mantenere i dati allineati su confini piacevoli e utilizzare o creare un meme di alternativa che supporti solo copie di blocco perfettamente allineate. Ancora meglio sarebbe avere un interruttore del compilatore per sacrificare lo spazio del programma e ram per motivi di velocità. persone o linguaggi che utilizzano molte strutture in modo tale che il compilatore generi internamente chiamate a memcpy o qualunque sia l'equivalente di una lingua, le loro strutture cresceranno in modo tale che vi sia un pad interposto o inserito all'interno. Una struttura di 59 byte potrebbe invece diventare 64 byte. malloc o un'alternativa che fornisce solo puntatori a un indirizzo allineato come specificato. ecc. ecc.

È molto più semplice fare tutto da solo. Un malloc allineato, strutture che sono multipli della dimensione dell'allineamento. La tua memcpy che è allineata, ecc. Essendo così semplice perché l'hardware dovrebbe rovinare i loro progetti, compilatori e utenti? non esiste un caso aziendale per questo.

Un'altra ragione è che le cache hanno modificato l'immagine. il tuo dram è accessibile solo in una dimensione fissa, 32 bit a 64 bit, qualcosa del genere, qualsiasi accesso diretto più piccolo di quello è un enorme successo in termini di prestazioni. Metti la cache di fronte al risultato della performance che va giù, qualsiasi lettura-modifica-scrittura avviene nella cache con la modifica che consente di modificare più volte per una singola lettura e scrittura di dram. Si vuole comunque ridurre il numero di cicli di memoria nella cache, sì, e si può ancora vedere il guadagno di prestazioni lisciando quello con la cosa del cambio (8 bit prima marcia, 16 bit seconda marcia, 32 bit terza marcia, 64 velocità di crociera bit, 32 bit spostamento verso il basso, a 16 bit scalare, 8 bit scalare)

Non posso parlare per Intel, ma so che gente come ARM hanno fatto ciò che si sta chiedendo un

ldmia r0!,{r2,r3,r4,r5} 

per esempio è ancora quattro trasferimenti a 32 bit se il core utilizza un'interfaccia a 32 bit. ma per le interfacce a 64 bit se allineato su un boundry a 64 bit diventa un trasferimento a 64 bit con una lunghezza di due, un insieme di trattative tra le parti e due parole a 64 bit spostate. Se non è allineato su un limite a 64 bit, diventa tre trasferimenti un singolo 32 bit, un singolo 64 bit e un singolo 32 bit. Bisogna stare attenti, se questi sono registri hardware che potrebbero non funzionare a seconda del progetto della logica di registro, se supporta solo trasferimenti a 32 bit singoli non si può usare quella istruzione contro quello spazio di indirizzamento. Non capisco perché proverai comunque qualcosa del genere.

L'ultimo commento è ... fa male quando faccio questo ... beh, non farlo. Non un singolo passaggio nelle copie di memoria. il corollario di questo è che nessuno può modificare il design dell'hardware per rendere più semplice l'uso di una copia di memoria per l'utente, che il caso d'uso è così piccolo che non esiste. Prendi tutti i computer utilizzando quel processore in esecuzione a piena velocità giorno e notte, misurato rispetto al fatto che tutti i computer siano passati da una copia mem a un altro codice ottimizzato per le prestazioni. È come paragonare un granello di sabbia alla larghezza della terra. Se sei single stepping, dovrai comunque fare un passo avanti per qualunque sia la nuova soluzione, se ce ne fosse una. per evitare enormi latenze di interrupt, la memcpy accordata a mano inizierà comunque con un if-then-else (se una copia troppo piccola va inserita in un piccolo insieme di codice srotolato o un ciclo di copia in byte), quindi inserire una serie di copie di blocco a una certa velocità ottimale senza orribili dimensioni di latenza. Dovrai ancora fare un passo avanti.

fare debugging a step singolo da compilare avvitato, lento, codice comunque, il modo più semplice per risolvere un singolo passo attraverso il problema memcpy è quello di avere il compilatore e il linker quando gli viene detto di compilare per il debug, compilare e collegamento con una memcpy non ottimizzata o una libreria alternativa non ottimizzata in generale. gnu/gcc e llvm sono open source, puoi farli fare quello che vuoi.

1

C'era una volta rep movsbera la soluzione ottimale.

Il PC IBM originale aveva un processore 8088 con un bus dati a 8 bit e nessuna cache. Quindi il programma più veloce era generalmente quello con il minor numero di byte di istruzioni. Avere istruzioni speciali ha aiutato.

Al giorno d'oggi, il programma più veloce è quello che può utilizzare il maggior numero di funzioni della CPU in parallelo. Per quanto possa sembrare strano all'inizio, avere codice con molte semplici istruzioni può effettivamente essere eseguito più velocemente di una singola istruzione fai-da-tutto.

Intel e AMD mantengono le vecchie istruzioni principalmente per compatibilità con le versioni precedenti.

15

Una cosa che vorrei aggiungere alle altre risposte è che rep movs non è in realtà lento su tutti i processori moderni. Per esempio,

Di solito, l'istruzione REP MOVS ha una grande testa per la scelta e impostare il metodo giusto. Pertanto, non è ottimale per piccoli blocchi di dati. Per i grandi blocchi di dati, potrebbe essere abbastanza efficace quando vengono soddisfatte determinate condizioni per l'allineamento, ecc. Queste condizioni di dipendono dalla CPU specifica (vedere pagina 143). Su processori Intel Nehalem e Sandy Bridge, questo è il metodo più rapido per lo spostamento di grandi blocchi di dati, anche se i dati non sono allineati.

[L'evidenziazione è mia.] Riferimento: Agner Fog, Optimizing subroutines in assembly language An optimization guide for x86 platforms., p. 156 (e vedi anche la sezione 16.10, pag 143) [versione del 2011-06-08].

+0

Sembra buono! Grazie. – ybungalobill

+4

REP MOVS utilizza una funzionalità di protocollo cache che non è disponibile per il codice normale. Fondamentalmente come gli archivi di streaming SSE, ma in un modo che è compatibile con le normali regole di ordinamento della memoria, ecc. // Il "grande overhead per la scelta e l'impostazione del metodo giusto" è principalmente dovuto alla mancanza di previsione dei branch dei microcodici. Desideravo da tempo che avessi implementato REP MOVS usando una macchina a stati hardware piuttosto che un microcodice, che avrebbe potuto eliminare completamente il sovraccarico. –

+0

A proposito, ho da tempo affermato che una delle cose che l'hardware può fare meglio/più velocemente del software è una complessa rete a più vie. –