Thursday, November 18, 2010

Numbers Everybody Should Know

Julian Hyde graciously transcribed the following table from Jeff Dean's Stanford talk:

L1 cache reference0.5 ns
Branch mispredict 5 ns
L2 cache reference 7 ns
Mutex lock/unlock 25 ns
Main memory reference 100 ns
Compress 1K bytes w/ cheap algorithm 3,000 ns
Send 2K bytes over 1 Gbps network 20,000 ns
Read 1 MB sequentially from memory 250,000 ns
Round trip within same datacenter 500,000 ns
Disk seek 10,000,000 ns
Read 1 MB sequentially from disk 20,000,000 ns
Send packet CA->Netherlands->CA150,000,000 ns


For more details: Agner's Software optimization resources.

7 comments:

Big Directory said...

really like the list. dont know if every programmer needs to knowj all these numbers... just how to derive them is all that is needed. useful though.

Anonymous said...

also: log_2(1000) = ~10, log_2(1000000) = ~20

Joe Wright said...

Wouldn't disk seek be changed for SSDs?

Nelson said...

In the US, a Google search end to end is about 200,000ns. To your desktop.

Nelson said...

Argh, my apologies. 200,000,000ns for a Google search. 200ms.

samh said...

Obviously this is all hardware dependant, but should give a rough idea of the relative costs.

crowding said...

Consider a line graph, with latency of access on the Y-axis, and something like "problem size" on the X axis.

If Moore's Law ever had meaning, it tracked how fast the left end of the curve has fallen over time, but I think you'd come to different answers if you looked at different points on the curve.