| L1 cache reference | 0.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->CA | 150,000,000 ns |
Everyone who wants to design high-performance, scalable systems should memorize these numbers. There are many, many lessons to be learned.
3 comments:
There are many questions to this table. The data depends on clock frequency, a microarchitecture, number of cores, system bus frequency, RAM type, system bus saturation, HDD type, number of processes in OS, internet traffic and so on.
So, these numbers are not constant. And they will be different for any reader.
Of course. These numbers are only correct within a factor of two at best, sometimes a factor of ten. (In an earlier version of Dean's talk, some of the numbers were indeed different.)
But engineering decisions -- such as whether to store a particular piece of data in memory, on disk, or in the memory of a neighboring machine -- are usually not very sensitive to these parameters. (If they were sensitive, you would be building a system that would only work well in certain circumstances. No one wants such a finicky system, so you should throw away your design.)
The wrong conclusion to draw from these numbers is to say, "We don't have the exact numbers. Let's ignore the numbers and just build the system that we think will work best." In other words, go by intuition. Well, my intuition is just not capable of understanding the factor of 10 million difference between referencing a byte in L1 cache versus disk.
Great engineers know when to use informed intuition, otherwise known as the back-of-the-envelope calculation. They use results of those calculations to challenge their assumptions, and when the results of those calculations produce surprises, they change their own intuition.
Actually, there are two problems with this set of numbers. As I've said, I'm not concerned with the accuracy, because an order of magnitude is good enough. But the numbers don't take into account cost, and they don't take into account how the performance and cost are trending over time.
For instance, the cost of storing a byte on disk gets much cheaper every year; the time to access that byte also reduces every year, but not by anywhere as much. Flash memory is reducing in cost much faster than either disk or RAM, and its access times are lower than disk reducing. As a result, a new tier is appearing in the memory/storage hierarchy: registers, L1 cache, L2 cache, RAM, flash, disk, offline storage.
Another current trend is the rise of cache-efficient algorithms and data structures; driven by the widening gap between RAM speed and L1/L2 cache access times. (Interestingly, some of those algorithms and data structures look similar to those we used 20 years ago for organizing data on disk.)
I recommend that you read The 5 minute rule by Jim Gray and Gianfranco Putzolu, and its sequels "The 5 minute rule ten years later" by Jim Gray and Goetz Graefe, and "The 5 minute rule twenty years later", by Goetz Graefe. These papers are truly a masterclass in back-of-the-envelope calculations, how cost is as important as speed in engineering practical systems, and how those calculations change over time.
An excellent post - I'm sure google engineers working on their main product (search) must know these back to front.
Post a Comment