Latency numbers every programmer should know

https://gist.github.com/2841832

by friggeri • 14 years ago

265 134 14 years ago

gist.github.com

yuvadam• 14 years ago

Is a single-text-file-github-gist the best way to disseminate this piece of knowledge (originally by Peter Norvig, BTW)?

What about a comprehensive explanation as to why those numbers actually matter?

Meh.

willvarfar• 14 years ago

http://www.infoq.com/presentations/Lock-free-Algorithms early-on gives good numbers on-machine.

I like this visualisation too: http://news.ycombinator.com/item?id=702713

matthavener2• 14 years ago

For anyone thinking about watching: the presentation is incredibly good. The name is kinda misleading -- they talk more about modern x86 architecture and actual numbers of various algorithms than the lock free algorithms themselves. Both of those guys have a high emphasis on measuring and testing to improve performance.

jgrahamc• 14 years ago

I believe that this originally comes from Norvig's "Teach Yourself to Program in Ten Years" article: http://norvig.com/21-days.html

alecco3• 14 years ago

That's from 2011. Amazon's James Hamilton wrote about it in 2009, and it comes from a presentation that year by Google's Jeff Dean:

http://perspectives.mvdirona.com/2009/10/17/JeffDeanDesignLe...

EDIT: this is wrong, Norvig's page pre-dates Dean's presentation http://wayback.archive.org/web/*/http://norvig.com/21-days.h...

tjr• 14 years ago

I make no claim as to who first assembled that particular table of data, but Norvig's article is dated 2001.

Symmetry• 14 years ago

In practice any out of order processor worth its salt ought to be able to entirely hide L1 cache latencies.

matthavener2• 14 years ago

Agreed, I think the real lesson is: reading is 10x cheaper than branching, so if you can do something with 10 non-branching ops it'll be just as fast as a single branch.

seabee3• 14 years ago

Conversely: if you can do something with a branch that's correctly predicted 90% of the time it'll be just as fast as 10 non-branching ops.

Branch prediction is a tool like any other - don't neglect it when it can help you.

gcp• 14 years ago

Now extend that to making memory reads predictable and prefetchable, and RAM is suddenly also free.

jedbrown• 14 years ago

Depends on data dependencies and the number of registers, but yes, L1 latency is rarely the bottleneck (more likely to be load/store throughput, in-register shuffles, or arithmetic dependencies for such tight kernels).

luckydude12• 14 years ago

The lmbench loop for measuring memory latency is

while (n--)p = *p;

Out of order does not help, it can't. That was the key insight in that benchmark.

larsberg2• 14 years ago

Honestly, I'd rather programmers know how to _measure_ these numbers than just have them memorized.

I mean, if I told them that their machine had L3 cache now, what would they do find out how that changes things? (This comment is also a shameless plug for the fantastic CS:APP book out of CMU).

nhebb• 14 years ago

+1 to CS: APP (Computer Systems: A Programmer's Perspective, by Bryant and O'Hallaron). I thought Computer Architecture: A Quantitative Approach by Hennessey was dry and better suited to EE's. CS: APP, on the other hand, really sucked me in - and I'm not the kind of guy that typically gets enthralled by CS texts.

apaprocki• 14 years ago

DTrace lets you measure L# cache hits/misses along with lots of other useful things.

adobriyan• 14 years ago

It lets you measure a number of cache hits, not the latency.

memset• 14 years ago

Honest question: how would you measure an L2 cache lookup? (What program would I need to write which ensures that a value is stored in L2, such that when I read it later, I would know the lookup time to indeed be the L2 time?)

At that, how would one measure this kind of thing at the nanoseconds level? Would using C's clock_gettime() functions be good enough? Is there any other facility to count cycles which have passed between two operations?

Swizec• 14 years ago

cracks knuckles Let's see if I remember enough of what I'm supposed to know in an exam in a couple of months or so.

You need to know the size of a page in your L1 cache. Then you can write a program that goes through a big enough chunk of memory that an "out of space" error occurs predictably in L1 cache, but not in L2 cache.

That way you can know when specifically your program went to L2 cache to swap out a page of L1 cache when it was needed.

The caveat being that you can probably only do this well enough in some sort of assembler code (for your architecture) and that you would have to be running a single-process system without interrupts enabled. Otherwise all sorts of things can mess up your cache lookups.

MichaelGG3• 14 years ago

What you could do is write a program that uses increasing amounts of memory. Measure the time it takes to complete a few million iterations of some function that accesses that memory. As the total usage increases, you'll see steps in the timing. For example, you might see a jump at ~32K, then ~2MB, then ~8MB.

AlisdairO• 14 years ago

I don't know how you actually measure how long a lookup takes, but just FYI if you're interested in the number of lookups you're doing from the various caches (and in things like number of missed branch predictions you're causing), you can use OProfile or Cachegrind. OProfile is a bit more complicated to set up because the flags you need to set are processor-specific, but it causes much less slowdown.

ob• 14 years ago

> Honest question: how would you measure an L2 cache lookup?

Like this: https://github.com/ob/cache/blob/master/cache.c

kjhughes2• 14 years ago

Measure vs memorize misses the point.

It's understanding the relative order of magnitude differences between the activities that's important.

larsberg2• 14 years ago

My problem with the memorization approach is that the technology is still moving quickly enough that the orders of magnitude still "wiggle," particularly in the middle numbers.

For example, at a glance, the disk seek numbers are off by orders of magnitude for SSD drives. And the 1MB of RAM read numbers appear not to have used the SSE streaming load/store instructions. I don't know anything about datacenters, but I'd certainly want to measure that one myself before building a system assuming that number was in its correct place in the hierarchy.

joe_the_user• 14 years ago

I've love to able to either measure or use all this lovely information in my running Linux desktop GUI app. But I happen to know that would probably not be worth my time except some rather specific cases. Plus the direction of PC architecture seems to be towards more and more levels of cache and that implies more and more work if you actually take these into account.

Just finding the time that library calls take is quite a pain in Linux.

Given all this, I'm inclined to think that I'd rather architect cache-oblivious data structures than root-around endless when background threads and other stuff suddenly get slow...

Morg12• 14 years ago

Someone should add basic numbers like ns count for 63 cycles modulo and that type of stuff - That'll help bad devs realize why putting another useless cmp inside a loop is dumb, and why alt rows in a table should NEVER be implemented by use of a modulo, for example.

Yes I know that's not latency per se but in the end it is too.

teach2• 14 years ago

I think if you're worried about whether or not you use modulo to calculate alternating table rows (and you don't work for Facebook), then you're almost certainly optimizing prematurely.

Morg12• 14 years ago

IT DOES NOT COST MORE TIME TO CODE CORRECTLY

Some approaches are NOT acceptable, it's not about optimizing prematurely, it's about coding obvious crap.

While you may be used to the usual "code crap, fix later" and "waste cycles, there are too many of it" , it doesn't mean you're right.

Everyone says it but you're still running on C (linux, unix), you're still going nuts over scaling issues (lol nosql for everyone) and you're still paying your amazon cloud bill.

jeltz• 14 years ago

Actually it does not matter if you are facebook or not. What really matters is how tight the loop is and how much time is spent in it.

EDIT: I agree with Morg. If coding right also results in faster code there is no reason not to do that.

recursive2• 14 years ago

How should they be implemented?

And per se should NEVER be spelled "per say".

Morg12• 14 years ago

Indeed it should never be spelled wrong, as it means in itself in latin, my bad really.

Alt rows are a simple concept, the first row is odd, the next is even, etc.

A good step forward is an if/then/else or a switch or an unrolled loop - a huge step forward in terms of performance too, as a mod takes 63 cycles and a cmp takes almost nothing.

an example could be

rowClass='even'; loop if(rowClass=='odd'){ rowClass='even'; }else{ rowClass='odd'; } endloop

debacle• 14 years ago

In general, there are very few things you actually need a modulo for. It's highly inefficient.

bitwize• 14 years ago

A lot of compilers are smart enough these days to optimize modulo by n, n a power of 2, to bitwise AND the complement of n-1.

peteretep• 14 years ago

Took me forever to find this, but:

https://plus.google.com/112493031290529814667/posts/LvhVwngP...

hellerbarde2• 14 years ago

From that link, this brilliant visualisation: http://i.imgur.com/X1Hi1.gif

al_james• 14 years ago

What stands out here is how long a disk read takes (especially compared to network latency). Indeed, disk is the new tape.

ryandetzel• 14 years ago

Interesting but unnecessary for most programmers today. I'd rather my programmers know the latency of redis vs memcached vs mysql and data type ranges.

snotrockets2• 14 years ago

Every programmer that understands (rather than "knows") the number mentioned in the link would know the numbers you are looking for (or at least, the relationships between those.)

I'm not sure this relation holds for the opposite direction.

aristus• 14 years ago

These are good rules of thumb, but need more context. Plugging an article I wrote about this & other things a couple of years ago for FB engineering: https://www.facebook.com/note.php?note_id=461505383919

The "DELETE FROM some_table" example is bogus, but the rest is still valid.

kjhughes2• 14 years ago

Anyone who hasn't heard Rear Admiral Grace Murray Hopper describe a nanosecond should check out her classic explanation:

http://www.youtube.com/watch?v=JEpsKnWZrJ8

stiff• 14 years ago

I present to you Grace Hopper handing people nanoseconds out:

http://www.youtube.com/watch?v=JEpsKnWZrJ8

CookWithMe3• 14 years ago

What about L3 Cache?

What about Memory Access on another NUMA Node?

What about SSD?

Does a mobile phone programmer need to know the access time for disks?

Does an embedded system programmer need to know anything of these numbers?

Every programmer should know what memory hierarchy and network latency is. (If you learn it by looking at these numbers, fine...)

jbooth• 14 years ago

I'm not an expert, but:

L3 is generally on the order of the same time as main memory - it's main purpose is to reduce the total amount of requests in order to conserve bandwidth

SSDs are on the order of 0.1ms, so 100,000 ns, give or take a factor of 10.

Someone smarter than me will have to answer the NUMA node question.

MichaelGG3• 14 years ago

I think L3 is much faster; perhaps 1/3rd of main memory, assuming the line is available and not in another core. Here are some numbers for L3 cache, from Intel (probably specific to the 5500 series)[1]:

  L3 CACHE hit, line unshared ~40 cycles 
  L3 CACHE hit, shared line in another core ~65 cycles 
  L3 CACHE hit, modified in another core ~75 cycles 
  remote L3 CACHE ~100-300 cycles 
  Local Dram ~60 ns 
  Remote Dram ~100 ns

60ns at 2.4GHz is ~144 cycles, right?

1: http://software.intel.com/sites/products/collateral/hpc/vtun...

CookWithMe3• 14 years ago

Sorry, these were rhetorical questions :)

I was trying to make the point that these numbers are somewhat arbitrary (i.e. why do I need to know the access speed to disc, when I keep everything in memory on a NUMA system?) and don't apply to all programmers (e.g. embedded systems may not have discs, L2 Caches or internet access).

zippie• 14 years ago

These numbers by Jeff Dean are relatively true but need to be refreshed for modern DRAM modules & controllers. Specifically, the main memory latency numbers are more applicable to DDR2 RAM vs the now widely deployed DDR3/DDR4 RAM (more channels = more latency). This has been a industry trend for a while and theres no change on the horizon. Additionally, memory access becomes more expensive because of CPU cross chatter when validating data loads across caches.

A potential pitfall with these numbers is they give engineers a false sense of security. They serve as a great conceptual aid - network/disk I/O are expensive and memory access is relatively cheap but engineers take that to an extreme, and get lackadaisical about memory access.

When utilizing a massive index (btree) our search engine failed to meet SLA because of memory access patterns. Our engineers tried things at the system (numa policy) and application level (different userspace memory managers, etc.)

Ultimately, it all came down to improving the efficiency around memory access. We used Low-Level Data Structure to get the 2x improvements in memory latency:

https://github.com/johnj/llds

lallysingh• 14 years ago

If this is your cup of tea, have a look at Agner Fog's resources: http://agner.org/optimize/

Also, I'd have a look at Intel's VTune or the 'perf' tool that ships with the linux kernel.

dsr_2• 14 years ago

Scaling up to human timeframes, one billion to one:

Pull the trigger on a drill in your hand 0.5s Pick up a drill from where you put it down 5s Find the right bit in the case 7s Change bits 25s Go get the toolkit from the truck 100s Go to the store, buy a new tool 3000s Work from noon until 5:30 20000s Part won't be in for three days 250000s Part won't be in until next week 500000s Almost four months 10000000s 8 months 20000000s Five years. 150000000s

hellerbarde2• 14 years ago

I forked the gist and did something similar. Would you mind if I took some of your suggestions into my fork?

https://gist.github.com/2843375

dsr_2• 14 years ago

Fine by me.

CamperBob22• 14 years ago

This is the same basic advice that I try to keep in mind when writing English text. A word that the reader already knows is in "L1." A word they have to stop and think about is an L1 miss. If they have to reach for the dictionary, it's an L2 miss -- and probably several more cycles for a line fill, as they get distracted reading the next few entries in the dictionary.

As programmers, Strunk & White might have made the list of the all-time greats.

EternalFury• 14 years ago

Considering that so many programmers are currently enthralled with JavaScript, Ruby, Python and other very very high level languages, the top half of this chart must look very mysterious and unattainable.

luckydude12• 14 years ago

Most of these latencies were measured and written up for a bunch of systems by Carl Staelin and I back in the 1990's. There is a usenix paper that describes how it was done and the benchmarks are open source, you can apt-get them.

http://www.bitmover.com/lmbench/lmbench-usenix.pdf

If you look at the memory latency results carefully, you can easily read off L1, L2, L3, main memory, memory + TLB miss latencies.

If you look at them harder, you can read off cache sizes and associativity, cache line sizes, and page size.

Here is a 3-D graph that Wayne Scott did at Intel from a tweaked version of the memory latency test.

http://www.bitmover.com/lmbench/mem_lat3.pdf

His standard interview question is to show the candidate that graph and say "tell me everything you can about this processor and memory system". It's usually a 2 hour conversation if the candidate is good.

ajross• 14 years ago

Pedantic quip: I have a hard time believing you guys were measuring half nanosecond cache latencies on a machine with a 100MHz clock. :)

And actually the cache numbers seem optimistic, if anything. My memory is that a L1 cache hit on SNB is 5 cycles, which is 2-3x as long as that table shows.

luckydude12• 14 years ago

We didn't believe it either until we put a logic analyzer on the bus and found that the numbers were spot with respect to the number of cycles. I don't remember how far off they were but it wasn't much, all the hardware dudes were amazed that software could get that close.

tl;dr: the numbers were accurate to the # of cycles, might have been as much as 1/2 of 1 cycle off.

Edit: I should add this was almost 20 years ago, I dunno how well it works today. Sec, lemme go test on a local machine.

OK, I ran on a Intel(R) Core(TM) i7-3930K CPU @ 3.20GHz (I think that's a Sandy Bridge) that is overclocked to 4289 MHz according to mhz, and it looks to me like that machine takes 4 cycles to do a L1 load. That sound right? lmbench says 4.05 cycles.

I poked a little more and I get

L1 4 cycles, ~48K L2 12 cycles, ~256K L3 16 cycles, ~6M

Off to google and see how far off I am. Whoops, work is calling, will check back later.

WayneS4• 14 years ago

You realize he is measuring averages right? Setup 1 million L1 cache hits, divide by total time...

alecco3• 14 years ago

Interesting. What do you think of Agner Fog's work?

luckydude12• 14 years ago

Wasn't aware of it, so thanks for the question. I took a quick look and it looks like Agner is using performance counters, which, while being more accurate, are platform specific. One of the goals of lmbench was to be accurate across different platforms and CPU architectures. So it's all userland software only.

You can get pretty far that way, Carl wrote a userland tool called mhz that has been working without modification since around 1998 (when the fastest clock rate was 600mhz on an alpha). Still pretty accurate to this day when CPUs have clock rates 7x faster and fairly different architectures.

Carl wrote up how it works, might be interesting to people who think about CPUs: http://www.bitmover.com/lmbench/mhz-usenix.pdf

luckydude12• 14 years ago

One other thing that is worth mentioning:

lmbench was trying to give you both bandwidths and latencies of everything in a computer system, not just memory. This is one place where it is actually worth memorizing the rough numbers, they help immensely when you are sketching out a design. lmbench tried to give you insight into latency/bw of network, disks, memory, etc.

Do you know, to the nearest order of magnitude

round trip time over the network

bandwidth over your data center's network

seek time end to end (not the silly 1/3rd seek / no rot delay)

bandwidth at the fast end

bandwidth at the slow end

memory read / write / bcopy bandwidth

random read from memory

I've sat in hundreds of design meetings where someone was claiming they'd build an XYZ server that did $BIG_NUMBER of ops/sec and I'd just stare at the ceiling, think about the network, and go "Maybe" or "not possible" based on the numbers. There must have been some time that I was wrong but I don't remember it.

It's somewhat harder today because all the big machines have multiple cores so it's not as simple as knowing what 1 core, with 1 network interface can do, but you should at least know that, you can assume linear scaling as an upper bound and have some idea of the capacity of the machine.

It's always amazed me how easy it is to get a feel for these numbers and yet many people in the biz don't take the time to do so. I can only guess they think it is harder than it actually is.

Retric• 14 years ago

Latency does not prevent X opps/second. It's not that hard to build a server that does a simple transaction 100,000 times a second. Keeping synchronized across several machines at that throughput level can be next to impossible.

notaddicted• 14 years ago

That mem_lat3 is pretty interesting, is there more info about it anywhere? Do you know what "Latency" refers to? Is that for Sandy Bridge consumer quad core? (hence ending at 8MB since that is L3$ size...)?

luckydude12• 14 years ago

That data is old, it's when Wayne was still working at Intel, he's been working here since 2001, so I'm guessing that is a pentium pro or similar.

I'll ping him and he'll probably answer tomorrow, it's late in his day in Indiana.

bunderbunder• 14 years ago

I find myself thinking of figures like these every time I see results for benchmarks that barely touch the main memory brought up in debates about the relative merits of various programming languages.

hobbyist• 14 years ago

How is mutex lock/unlock different from any other memory access?

wmf• 14 years ago

It requires more cache coherence.

SeanLuke• 14 years ago

How is a mutex lock less expensive than a memory access? Are such things done only in registers nowadays? This doesn't sound right.

haberman4• 14 years ago

Less expensive than a main memory access. It must be that an uncontended lock/unlock can happen in cache.

JoeAltmaier7• 14 years ago

No definitely not. A full memory fence surrounds lock/unlock.

a-priori• 14 years ago

I assume that the mutex's memory is warmed, so the processor doesn't have to go to RAM. But, it does have to synchronize with any other processors/cores in the machine to prevent them from locking the mutex at the same time.

In a Intel Nahalem or Sandy Bridge system, this goes over the QuickPath Interconnect which has a latency of ~20ns. HyperTransport fills the same role in AMD systems, and probably has a similar latency, but I don't have numbers for that.

I'm basing this on this presentation, especially the architecture diagram at 2m 40s:

http://www.infoq.com/presentations/Lock-free-Algorithms

CookWithMe3• 14 years ago

Also, these numbers don't mean much on their own. E.g. L2 Cache is faster than main memory, but that doesn't help you if you don't know how big your L2 Cache is. Same for main memory vs. disc.

E.g. I optimized a computer vision algorithm for using L2 and L3 caches properly (trying to reuse images or parts of images still in the caches). Started off with an Intel Xeon: 256KB L2 Cache, 12MB L3 Cache. Moved on to an AMD Opteron: 512KB L2 Cache (yay), 6MB L3 Cache (damn).

Also, the concept of the L2 Cache has changed. Before multi-cores it was bigger and the last-level-cache. Now it has become smaller and the L3 Cache is the last-level-cache, but has some extra issues due to the sharing with other cores.

The important concepts every programmer should know are memory hierarchy and network latency. The individual numbers can be looked up on a case-by-case basis.

patrickmay• 14 years ago

When working on low latency distributed systems I more than once had to remind a client that it's a minimum of 19 milliseconds from New York to London, no matter how fast our software might be.

sciurus• 14 years ago

One of my favorite writeups on this topic is Gustavo Duarte's "What Your Computer Does While You Wait"

http://duartes.org/gustavo/blog/post/what-your-computer-does...

dockd• 14 years ago

Does anyone feel like this is sort of an apples to oranges table? It compares reading one item from L1 cache to reading 1M byte from memory, without adjusting for the amount of data being read (10^6 more). It looks like the data was chosen to minimize the number of digits in the right column.

JoeAltmaier7• 14 years ago

Network transmit time is almost irrelevant. It takes orders of magnitude more time to call the kernel, copy data, and reschedule after the operation completes than the wiretime.

This paradox was the impetus behind Infiniband, virtual adapters, and a host of other paradigm changes that never caught on.

Peaker• 14 years ago

Infiniband has caught on, at least in the high-end.

luckydude12• 14 years ago

Huh. Data please.

Part of the reason I wrote lmbench was to make sure that what you are saying is not true. And it is not in Linux, kernel entry and exit is well under 50 nanoseconds. Passing a token back and forth, round trip, in an AF_UNIX socket is 30 usecs. A ping over gig ether is 120 usecs.

Unless I'm completely misunderstanding, you are saying that the OS overhead should be "orders of magnitude" more than the network time, that's not at all what I'm seeing on Linux.

I guess what you are saying is that given an infinitely fast network, the overhead of actually doing something with the data is going to be the dominating term. Yeah, true, but when do we care about the infinitely fast network in a vacuum? We always want that data to do something so we have to pay something to actually deliver it to a user process. Linux is hands down the best at doing so, it's not free but it is way closer to free than any other OS I've seen.

Getahobby2• 14 years ago

This may be ignorant and please correct if I am off base but given the same physical medium isn't sending 2k across the network the same cost whether you are at fastE or gigE? Given the network is not saturated?

JoeAltmaier7• 14 years ago

Linux sounds fast. 50ns is blazingly fast. Benchmarks I surveyed show figures around 1-10usec but they are old and processors are faster now.

Kernel entry and exit are of course contributors to i/o overhead. Also include data copy time (2K times all those main memory flushes), ip stack time (well into scores of usec now) and driver overhead.

Add the latency of the result being signalled to your user-mode application. Interrupt latency, user-mode task scheduling time and if a receive then data copy time again.

Of course router delays are negligible on the backbone, but your local cable modem etc will add something.

I think we're over 16usec now, which if I did the math right is the wire time.

Another way to estimate all this is to benchmark achieved transfer rate peer-to-peer on an otherwise idle link. Folks report from 100mbit to 300mbit depending on other bottlenecks (disk speed, bus etc), but that's often using very large block sizes, not our 2K. Even so we see most of the Gigabit rate whittled away.

mmukhin• 14 years ago

2kB over 1Gbps is actually 16ns (i guess they round up to 20)

some1else• 14 years ago

John Carmack recently used a camera to measure that it takes longer to paint the screen in response to user input, than send a packet accross the Atlantic: http://superuser.com/questions/419070/transatlantic-ping-fas...

I came across the post when I was looking for USB HID latency (8ms).

perlpimp• 14 years ago

Such items are important to web developers and they can use them to justify looking at one or other technology. Or perhaps attempt at least benchmarking and have them as one of the guides in configuring and setting up services. Comes to mind why is Redis can be better then mongodb and in what configuration.

As well in discussion about this and that these can be of help too.

Adding misaligned memory penalties such as on word boundary and page boundary can enhance such document. This might be a good cheatsheet if one inclined to research and make one.

xb95• 14 years ago

This reminds me of one of the pages that Google has internally that, very roughly, breaks down the cost of various things so you can calculate equivalencies.

As an example of what I mean (i.e., these numbers and equivalencies are completely pulled out of thin-air and I am not asserting these in any way):

  * 1 Engineer-year = $100,000
  * 25T of RAM = 1 Engineer-week
  * 1ms of display latency = 1 Engineer-year

This allows engineeers to calculate tradeoffs when they're building things and to optimize their time for business impact. E.g.: it's not worth optimizing memory usage by itself, Latency is king, Don't waste your time shaving yaks, etc etc.

Morg12• 14 years ago

Yet everyone uses much slower RAM in servers and will likely continue to do so, all the while caches swell, etc.

Optimizing memory usage is almost irrelevant today, until it starts being a bandwidth problem, and that's still solvable but only through complex scaling strategies that also cost several engineer-years.

balloot• 14 years ago

The thing here that is eye opening to me, and relevant to any web programmer, is that accessing something from memory from another box in the same datacenter is about 25x times as fast as accessing something from disk locally. I would not have guessed that!

hboon• 14 years ago

That's why tools like memcached work like they do.

chmike• 14 years ago

Lz4 is faster than zippy and much easier to use. It's a single .h .c file.

Latency numbers every programmer should know

Related Stories