7 ms·

Attack of the Killer Microseconds

89 points by jgrahamc 10y ago

YZF 10y ago
Really? We are good at nanoseconds and milliseconds but not at microseconds? Last I checked a microsecond was 1000 nanoseconds so you can't really be good at nanoseconds but somehow bad at microseconds. This ties in a little to the recent HN discussions about the cost of a context switch. I think what they're trying to say, and not very well, is that there is somewhat of a discontinuity when you move between different levels of abstraction. There's examples of this phenomena in operating systems where the overhead of making a system call can be so high you can't get the latency down or in programming languages, e.g. running over a virtual machine or an interpreter. But this is far from new and there's a continuum of solutions from hardware like DSPs through real time operating systems, lightweight threads, lower lever languages, kernel bypass. Abstractions have cost, you want protected/virtual memory there's a cost and you pay that cost in your context switches. Not sure you can have your cake and eat it here but there's plenty of different choices on the menu for different situations.
- dom0 10y ago
  As I've said before, a context switch is really cheap on modern hardware. What kills it if you need to drag all sorts of dirt through all the caches. I.e. cold caches kill performance. Hardly news.
  - jacquesm 10y ago
    A context switch is only cheap if the task you switch to doesn't do anything. Even 2 decades ago you could to upwards of 100K task switches per second on relatively anemic hardware. That's never been the problem.
    - dom0 10y ago
      In terms of cycles the switch has become more expensive since a lot of registers were added that need saving/restoring. (But since frequencies have increased a lot the absolute time shrank when we reached the "3 GHz era"; I think it's been pretty much constant for the last ~10 years or so). But you are right that the switch itself on modern-era (=32+ bit few-chip systems with MMU) hardware was never really that expensive (on the order of 10-20 us).
  - Dylan16807 10y ago
    Thousands of instructions is not "really cheap". You can cause a lot of slowdown by accidentally calling into the kernel in a tight loop, even if L1 is big enough for both. A different CPU design could make context switches essentially free.
    - deleted 10y ago
      [deleted]
- caf 10y ago
  This is probably the best summary paragraph from the article that answers your question: Techniques optimized for nanosecond or millisecond time scales do not scale well for this microsecond regime. Superscalar out-of-order execution, branch prediction, prefetching, simultaneous multithreading, and other techniques for nanosecond time scales do not scale well to the microsecond regime; system designers do not have enough instruction-level parallelism or hardware-managed thread contexts to hide the longer latencies. Likewise, software techniques to tolerate millisecond-scale latencies (such as software-directed context switching) scale poorly down to microseconds; the overheads in these techniques often equal or exceed the latency of the I/O device itself. To expand a bit: the reason you can be good at nanoseconds but bad at microseconds is that you need to throw a thousand times more resources at the problem to solve it using the same techniques. You can get good instruction-level parallelism with current memory latencies using a reorder buffer with a hundred or so entries, but can you really just scale that up to a ROB with 100,000 entries?
  - YZF 10y ago
    What's the problem that you're trying to solve? OOE, branch prediction, prefetching, are to allow a CPU to execute multiple instructions per cycle on a GHz clock. I.e. within a nanosecond. Memory latency all the way out to DRAM is more than enough to do things in microseconds and the caches are big enough to get you a lot of concurrency within that. It's true that when you're coding over a modern OS in a high level language you can't get e.g. a GPIO pin to update in a microsecond. But that's life. Use a real-time OS you can do better. Get rid of the OS and you'll do even better. Use a different CPU or an FGPA and you may do better. The various techniques used to get a CPU to execute 20 instructions in a nanosecond aren't the limiting factor in that stack. EDIT: Once upon a time there was a UART called the 8250. You could either poll it or if you wanted to do something else concurrently you'd use interrupts. Only interrupts have to do a context switch (in this case pushing a few things onto the stack) so they cost a little more. Once serial rates became high enough interrupts started consuming more and more cycles. So they added a buffer, and we got the 16550 (or one of its cousins). Now the thing would only interrupt above a certain watermark and we can cut the number of interrupts by 10 so we can get higher throughput at the expense of higher latency. Same thing happens with network interfaces. You can drive a 10Gbps network because a lot of stuff is buffered and/or hardware offloaded. It doesn't make sense to bitbang 10G Ethernet out of a general purpose CPU. These sorts of tradeoffs in different parts of the system are unavoidable but yet the tools to solve problems down to GHz clocks are out there both for software and hardware.
angry_octet 10y ago
This is a timely analysis. The virtual memory system, with its concept of paging to disk, is obsolete in the sense that hardly anybody that does bigger-than-ram computations rely on the kernel's algorithms to manage it (https://scholar.google.com.au/scholar?q=out+of+core+algorithms https://scholar.google.com.au/scholar?q=out+of+core+algorith...). The current paging system doesn't have a sensible mechanism for flash-as-core memory (10x RAM latency, e.g. DDR4 12ns for first word, so 120ns), persistent memory in general, or using SSDs as an intermediate cache for data on disk. ZFS has some SSD caching but it is not really taking advantage of the very large and very fast devices now available. So we do need new paradigms to use this effectively. I'd like to be able to reboot and keep running a program from its previous state, because it all sits in flash-core. Also there is huge potential to move to more garbage collected memory storage systems. This goes hand in hand with systems which can progress concurrently, without the overhead of difficult multi-threaded code, such as parallel Haskell. On the negative side, I find the use of the term 'warehouse scale computing' to be stupidly buzzwordy. From https://gist.github.com/jboner/2841832 https://gist.github.com/jboner/2841832 L1 cache reference 0.5 ns Branch mispredict 5 ns L2 cache reference 7 ns 14x L1 cache Mutex lock/unlock 25 ns Main memory reference 100 ns 20x L2 cache, 200x L1 cache Compress 1K bytes with Zippy 3,000 ns 3 us Send 1K bytes over 1 Gbps network 10,000 ns 10 us Read 4K randomly from SSD* 150,000 ns 150 us ~1GB/sec SSD Read 1 MB sequentially from memory 250,000 ns 250 us Round trip within same datacenter 500,000 ns 500 us Read 1 MB sequentially from SSD* 1,000,000 ns 1,000 us 1 ms ~1GB/sec SSD, 4X memory Disk seek 10,000,000 ns 10,000 us 10 ms 20x datacenter roundtrip Read 1 MB sequentially from disk 20,000,000 ns 20,000 us 20 ms 80x memory, 20X SSD Send packet CA->Netherlands->CA 150,000,000 ns 150,000 us 150 ms
- YZF 10y ago
  IMO part of the reason is that DRAM is cheap and you can get a lot of it. How many applications have a working set that is in that relatively small region between DRAM and SSD. I close the lid of my laptop and my memory is saved to SSD, I open it and it comes back pretty much immediately, what more do I need from that perspective? One thing that tends to happen with caches is that you tend to get smaller returns as they grow larger. You're saying my 64GB RAM can be another level of cache for my 500GB SSD but I'm not quite sure what we'd do with that and why we need more than what we can already do with this SSD at the application layer. I agree that SSD paging can probably be improved. Maybe support can be moved out of the OS into hardware to get better latency. I'd still think that if you're thrashing the SSD you're likely not getting good performance just like if you're thrashing DRAM you're not doing as good as you could be doing.
bullen 10y ago
This is bad for Google: 1) They don't understand IO-wait. Async-to-async HTTP is going to be very important once you manage to make it work: https://github.com/tinspin/rupy/wiki/Fuse https://github.com/tinspin/rupy/wiki/Fuse 2) They don't understand the end of Moore's law combined with Peak Hydrocarbons. CPU is the bottleneck not network, memory or disk. Tip to YC: force comment on downvote.
- icebraining 10y ago
  I didn't downvote you, but I have to say your comment neither explains what async-to-async HTTP means (and the link doesn't help either), nor why it's important, nor why the article shows that Google doesn't understand it. Frankly, if you want to claim that Google research engineers don't understand something regarding computing, you need to make a good case for it, rather than a short comment.
  - bullen 10y ago
    Watch the video and you will understand that/why google chooses sync. development. As to why it's important, you will see eventually, or you can try to figure it out by reading the link again in a couple of months. The brain needs time to understand things that are hidden by self preservation, like how money is created f.ex.
    - icebraining 10y ago
      I understand why Google chooses a synchronous model of development, that wasn't what I said you should explain. If you believe your explanation is crystal clear and complete, and people just need time, then good luck. But I suggest you try reformulating it. By the way, "Money creation in the modern economy" wasn't hard to understand. In my experience, most things aren't, if they're well explained and you have the foundation knowledge. "The brain needs time to adjust" tends to be an excuse used by people selling perpetual motion machines.
      - bullen 10y ago
londons_explore 10y ago
One might imagine this being solved by forcing all "malloc" operations to specify for which thread or request that memory will be used by. The malloc library or OS can then mark those pages with specific thread numbers. When that thread then blocks on millisecond IO (such as a remote network request), allow that memory to be moved via RDMA to a remote store (a microsecond level delay). When the thread unblocks, move the memory back again. The key benefit here over regular paging is that it's on a per-thread basis rather than a per-page basis, so latency isn't so critical. It's also RDMA rather than to local disk, so it can go anywhere in the warehouse, allowing perfect RAM utilization. Now, for warehouse level computing you no longer need to worry about where your CPU's or RAM are - you can efficiently move RAM about between machines (effectively paging), as long as at any point in time enough threads across your warehouse have reasonably long blocking times (milliseconds or more), and you have enough thread/request specific memory usage, which can be moved about far more easily than shared memory.

89 points by jgrahamc 10y ago

YZF 10y ago

Really? We are good at nanoseconds and milliseconds but not at microseconds? Last I checked a microsecond was 1000 nanoseconds so you can't really be good at nanoseconds but somehow bad at microseconds. This ties in a little to the recent HN discussions about the cost of a context switch. I think what they're trying to say, and not very well, is that there is somewhat of a discontinuity when you move between different levels of abstraction. There's examples of this phenomena in operating systems where the overhead of making a system call can be so high you can't get the latency down or in programming languages, e.g. running over a virtual machine or an interpreter. But this is far from new and there's a continuum of solutions from hardware like DSPs through real time operating systems, lightweight threads, lower lever languages, kernel bypass. Abstractions have cost, you want protected/virtual memory there's a cost and you pay that cost in your context switches. Not sure you can have your cake and eat it here but there's plenty of different choices on the menu for different situations.

dom0 10y ago
As I've said before, a context switch is really cheap on modern hardware. What kills it if you need to drag all sorts of dirt through all the caches. I.e. cold caches kill performance. Hardly news.
- jacquesm 10y ago
  A context switch is only cheap if the task you switch to doesn't do anything. Even 2 decades ago you could to upwards of 100K task switches per second on relatively anemic hardware. That's never been the problem.
  - dom0 10y ago
    In terms of cycles the switch has become more expensive since a lot of registers were added that need saving/restoring. (But since frequencies have increased a lot the absolute time shrank when we reached the "3 GHz era"; I think it's been pretty much constant for the last ~10 years or so). But you are right that the switch itself on modern-era (=32+ bit few-chip systems with MMU) hardware was never really that expensive (on the order of 10-20 us).
- Dylan16807 10y ago
  Thousands of instructions is not "really cheap". You can cause a lot of slowdown by accidentally calling into the kernel in a tight loop, even if L1 is big enough for both. A different CPU design could make context switches essentially free.
  - deleted 10y ago
    [deleted]
caf 10y ago
This is probably the best summary paragraph from the article that answers your question: Techniques optimized for nanosecond or millisecond time scales do not scale well for this microsecond regime. Superscalar out-of-order execution, branch prediction, prefetching, simultaneous multithreading, and other techniques for nanosecond time scales do not scale well to the microsecond regime; system designers do not have enough instruction-level parallelism or hardware-managed thread contexts to hide the longer latencies. Likewise, software techniques to tolerate millisecond-scale latencies (such as software-directed context switching) scale poorly down to microseconds; the overheads in these techniques often equal or exceed the latency of the I/O device itself. To expand a bit: the reason you can be good at nanoseconds but bad at microseconds is that you need to throw a thousand times more resources at the problem to solve it using the same techniques. You can get good instruction-level parallelism with current memory latencies using a reorder buffer with a hundred or so entries, but can you really just scale that up to a ROB with 100,000 entries?
- YZF 10y ago
  What's the problem that you're trying to solve? OOE, branch prediction, prefetching, are to allow a CPU to execute multiple instructions per cycle on a GHz clock. I.e. within a nanosecond. Memory latency all the way out to DRAM is more than enough to do things in microseconds and the caches are big enough to get you a lot of concurrency within that. It's true that when you're coding over a modern OS in a high level language you can't get e.g. a GPIO pin to update in a microsecond. But that's life. Use a real-time OS you can do better. Get rid of the OS and you'll do even better. Use a different CPU or an FGPA and you may do better. The various techniques used to get a CPU to execute 20 instructions in a nanosecond aren't the limiting factor in that stack. EDIT: Once upon a time there was a UART called the 8250. You could either poll it or if you wanted to do something else concurrently you'd use interrupts. Only interrupts have to do a context switch (in this case pushing a few things onto the stack) so they cost a little more. Once serial rates became high enough interrupts started consuming more and more cycles. So they added a buffer, and we got the 16550 (or one of its cousins). Now the thing would only interrupt above a certain watermark and we can cut the number of interrupts by 10 so we can get higher throughput at the expense of higher latency. Same thing happens with network interfaces. You can drive a 10Gbps network because a lot of stuff is buffered and/or hardware offloaded. It doesn't make sense to bitbang 10G Ethernet out of a general purpose CPU. These sorts of tradeoffs in different parts of the system are unavoidable but yet the tools to solve problems down to GHz clocks are out there both for software and hardware.

angry_octet 10y ago

This is a timely analysis. The virtual memory system, with its concept of paging to disk, is obsolete in the sense that hardly anybody that does bigger-than-ram computations rely on the kernel's algorithms to manage it (https://scholar.google.com.au/scholar?q=out+of+core+algorithms https://scholar.google.com.au/scholar?q=out+of+core+algorith...). The current paging system doesn't have a sensible mechanism for flash-as-core memory (10x RAM latency, e.g. DDR4 12ns for first word, so 120ns), persistent memory in general, or using SSDs as an intermediate cache for data on disk. ZFS has some SSD caching but it is not really taking advantage of the very large and very fast devices now available. So we do need new paradigms to use this effectively. I'd like to be able to reboot and keep running a program from its previous state, because it all sits in flash-core. Also there is huge potential to move to more garbage collected memory storage systems. This goes hand in hand with systems which can progress concurrently, without the overhead of difficult multi-threaded code, such as parallel Haskell. On the negative side, I find the use of the term 'warehouse scale computing' to be stupidly buzzwordy. From https://gist.github.com/jboner/2841832 https://gist.github.com/jboner/2841832 L1 cache reference 0.5 ns Branch mispredict 5 ns L2 cache reference 7 ns 14x L1 cache Mutex lock/unlock 25 ns Main memory reference 100 ns 20x L2 cache, 200x L1 cache Compress 1K bytes with Zippy 3,000 ns 3 us Send 1K bytes over 1 Gbps network 10,000 ns 10 us Read 4K randomly from SSD* 150,000 ns 150 us ~1GB/sec SSD Read 1 MB sequentially from memory 250,000 ns 250 us Round trip within same datacenter 500,000 ns 500 us Read 1 MB sequentially from SSD* 1,000,000 ns 1,000 us 1 ms ~1GB/sec SSD, 4X memory Disk seek 10,000,000 ns 10,000 us 10 ms 20x datacenter roundtrip Read 1 MB sequentially from disk 20,000,000 ns 20,000 us 20 ms 80x memory, 20X SSD Send packet CA->Netherlands->CA 150,000,000 ns 150,000 us 150 ms

YZF 10y ago
IMO part of the reason is that DRAM is cheap and you can get a lot of it. How many applications have a working set that is in that relatively small region between DRAM and SSD. I close the lid of my laptop and my memory is saved to SSD, I open it and it comes back pretty much immediately, what more do I need from that perspective? One thing that tends to happen with caches is that you tend to get smaller returns as they grow larger. You're saying my 64GB RAM can be another level of cache for my 500GB SSD but I'm not quite sure what we'd do with that and why we need more than what we can already do with this SSD at the application layer. I agree that SSD paging can probably be improved. Maybe support can be moved out of the OS into hardware to get better latency. I'd still think that if you're thrashing the SSD you're likely not getting good performance just like if you're thrashing DRAM you're not doing as good as you could be doing.

bullen 10y ago

This is bad for Google: 1) They don't understand IO-wait. Async-to-async HTTP is going to be very important once you manage to make it work: https://github.com/tinspin/rupy/wiki/Fuse https://github.com/tinspin/rupy/wiki/Fuse 2) They don't understand the end of Moore's law combined with Peak Hydrocarbons. CPU is the bottleneck not network, memory or disk. Tip to YC: force comment on downvote.

icebraining 10y ago
I didn't downvote you, but I have to say your comment neither explains what async-to-async HTTP means (and the link doesn't help either), nor why it's important, nor why the article shows that Google doesn't understand it. Frankly, if you want to claim that Google research engineers don't understand something regarding computing, you need to make a good case for it, rather than a short comment.
- bullen 10y ago
  Watch the video and you will understand that/why google chooses sync. development. As to why it's important, you will see eventually, or you can try to figure it out by reading the link again in a couple of months. The brain needs time to understand things that are hidden by self preservation, like how money is created f.ex.
  - icebraining 10y ago
    I understand why Google chooses a synchronous model of development, that wasn't what I said you should explain. If you believe your explanation is crystal clear and complete, and people just need time, then good luck. But I suggest you try reformulating it. By the way, "Money creation in the modern economy" wasn't hard to understand. In my experience, most things aren't, if they're well explained and you have the foundation knowledge. "The brain needs time to adjust" tends to be an excuse used by people selling perpetual motion machines.
    - bullen 10y ago

londons_explore 10y ago

One might imagine this being solved by forcing all "malloc" operations to specify for which thread or request that memory will be used by. The malloc library or OS can then mark those pages with specific thread numbers. When that thread then blocks on millisecond IO (such as a remote network request), allow that memory to be moved via RDMA to a remote store (a microsecond level delay). When the thread unblocks, move the memory back again. The key benefit here over regular paging is that it's on a per-thread basis rather than a per-page basis, so latency isn't so critical. It's also RDMA rather than to local disk, so it can go anywhere in the warehouse, allowing perfect RAM utilization. Now, for warehouse level computing you no longer need to worry about where your CPU's or RAM are - you can efficiently move RAM about between machines (effectively paging), as long as at any point in time enough threads across your warehouse have reasonably long blocking times (milliseconds or more), and you have enough thread/request specific memory usage, which can be moved about far more easily than shared memory.