Una delle cose più difficili in informatica è avere un’idea a priori sul tempo di esecuzione di un programma.

Mentre ci sono ovviamente tecniche che permettono di studiare l’andamento di un algoritmo, il problema cambia quando si parla di implementazioni.

A volte infatti può succedere che due programmi che implementano due algoritmi per risolvere lo stesso problema, potrebbero avere un andamento diverso rispetto a quello che ci aspettiamo.

Di recente mi è ricapitata sotto mano la tabella con i numeri che ogni programmatore dovrebbe conoscere. Questa tabella, inizialmente stillata da Jeff Dean per un evento di Google, fornisce un’idea del tempo necessario per eseguire delle comuni operazioni.

La colonna di destra indica la distanza che percorribile alla velocità nel dato lasso di tempo e potrebbe essere utile per capire le proporzioni fra una operazione e l’altra

OperationTimeDistance
3.3 GHz CPU Cycle0.3 ns9 cm
Referenza ad un dato in cache L10.5 ns15 cm
Predizione Branch sbagliata5 ns1.5 m
Referenza ad un dato in Cache L27 ns2.1 m
Mutex lock/unlock100 ns30 m
Referenza ad un dato in memoria principale100 ns30 m
Comprimere 1Kbytes di dati10,000 ns3 km
Inviare 2Kbytes su una rete da 1Gbps20,000 ns6 km
Lettura sequenziale di 1MB dalla memoria250,000 ns75 km
Round trip nello stesso datacenter500,000 ns150 km
Effettuare una seek sul disco10,000,000 ns3000 km
Lettura sequenziale di 1 MB dal disco30,000,000 ns9000 km
Invio di un pacchetto California-Olanda-California150,000,000 ns45000 km

Una tabella aggiornata annualmente è disponibile qui.