24 ms·

Zed Shaw: "poll, epoll, science, and superpoll" with R

• kqueue 16y ago
  Lets assume we have 20k opened FDs. In case of poll(), you have to transfer this array of FDs from the userland vm to the kernel vm each time you call poll(). Now compare this with epoll() (let's assume we are using EPOLLET trigger), when you only have to transfer the file descriptors once. You might say the copying won't matter, but it will matter when you have a lot of events coming on the 20k FDs which eventually leads to calling xpoll() at a higher rate, hence more copying of data between the userland and kernel (4bytes * 20k, ~80kbytes each call).
  • FooBarWidget 16y ago
    Why would there by any copying? The kernel can directly read userspace memory.
    • kqueue 16y ago
      For the kernel to execute a system call, it has to place the arguments on its stack. a system call doesn't execute in the userland.
      • FooBarWidget 16y ago
        Yes but the argument to poll is a pointer. The pointer would be copied but the kernel can still follow the pointer to userspace, right?
        • kqueue 16y ago
          The pointer referred to by the process is not accessible by the kernel because when the user process was running, it had a different vm space than the kernel vm space. So if it just passes the pointer (without copying the pointer's data), then the kernel will point to a virtual address that won't exist until the user process gets swapped in again.
          • FooBarWidget 16y ago
            This sounds really strange to me. The kernel has full access to the page tables so can't it lookup things in userspace?
            • kqueue 16y ago
              When the kernel is executing a function call placed on the stack, all the addresses on the stack are assumed in the same vm space. It does not know that an address is actually a virtual memory address belonging to process X and tries to figure out the value in the physical memory.
              • FooBarWidget 16y ago
                Yeah but it's possible to look up things in userspace right? So just change poll() to assume that the pointer points to userspace. I don't see the need for copying.
                • kqueue 16y ago
                  When the kernel calls poll, poll will access memory in the kernel address space because that's where it is running. All the addresses accessed in any system call are in the kernel address space. They don't go back and forth and swap vm pointers to fetch data from other processes. That's not how kernels work. And no you cannot change poll().. You write epoll/kqueue
  • zedshaw 16y ago
    Yep, that's what I thought too, that at least epoll would be as fast. Turns out it's not though, but then I could be wrong. Also, your assumption of EPOLLET is potentially wrong. I think (unproven) that the extra overhead and complexity of using edge trigger right makes EPOLLET pointless.
    • kqueue 16y ago
      Sorry, I meant level-triggered. :) I think edge-triggered does add an extra overhead as you stated.
    • pphaneuf 16y ago
      Why would there be extra overhead when using edge triggered? There's definitely extra complexity on the client side, but it's close to what you're trying to do with super-poll (the extra complexity is basically to find out when an fd isn't busy anymore). I think it might even be faster, kernel-side. From what I remember of the implementation, both modes have to walk the same list of ready fds, but that list is shorter in edge triggered mode, because they get removed from the list as it goes. Edge triggered might have more overhead if many fds change between ready/not-ready quickly, but that's quite the wacky situation (and if it has an even distribution, would ensure your ATR is about 0.5, so probably still winning).
• jaekwon 16y ago
  0.6 is so arbitrary. it should be 1.0/golden-ratio.
  • zedshaw 16y ago
    I was hoping for e, but alas no luck.
    • aston 16y ago
      It's pretty darn close to 1 - 1/e.
      • mhd 16y ago
        The first four digits of 1/0.6 would be 1666, the Annus Mirabilis. So you could compare Mongrel2's multiple request handlers to Isaac Newton first splitting light with a prism.
    • pphaneuf 16y ago
      The best would be if it would be possible to code up superpoll to be adaptive, and in effect, benchmark itself to come to the same conclusion, dynamically. So if one day the kernel people fixed epoll to be better all the time, Mongrel2 would magically not use poll() much on systems using that kernel, and favour epoll. Of course, that's often Kinda Hard To Do (tm). ;-)
• jacquesm 16y ago
  In real-life web serving situations, and not in benchmarks, the majority of the fds is not active. It's the slow guys that kill you. A client on a fast connection will come in and will pull the data as fast as the server can spit it out, keeping the process and the buffers occupied for the minimum amount of wall clock time and the number of times the 'poll' cycle is done is very small. But the slowpokes, the ones on dial up and on congested lines will get you every time. They keep the processes busy far longer than you'd want and you have to hit the 'poll' cycle far more frequently, first to see if they've finally completed sending you a request, then to see if they've finally received the last little bit of data that you sent them. The impact of this is very easy to underestimate, and if you're benchmarking web servers for real world conditions you could do a lot worse than to run a test across a line that is congested on purpose.
  • dminor 16y ago
    Mongrel2 is supposed to handle WebSockets as well as HTTP, so I think open connections with sporadic traffic are a use case Zed has to worry about.
  • jakevoytko 16y ago
    For simple testing purposes, it is easy to set up a forwarding proxy that drops n% of the packets it receives - for some high value of n. The World Wide Web is far more sadistic, but it still uncovers some performance or usability problems that are invisible over normal `localhost` traffic. I bet you can also use web servers with traffic shaping to mimic lots of slow connections at once, but I haven't tried that
  • terra_t 16y ago
    Yeah, but there's a fetishization of "high concurrency" (being able to support a huge number of connections) rather than absolute performance. For instance, you might have a system which has a latency of 1 second, and at a given workload, you have 10,000 connections. In the Java culture, people think you're a genius if you can increase those connections to 100,000 and increase the latency to 10 seconds. End users, on the other hand, would be happier if you cut the latency to 0.1 seconds, but there are a lot of people who'll then think you're a loser who can only manage to handle 1000 concurrent connections. Of course, getting that latency down is a holistic process that requires you to think about the client, the server, and what exactly goes over the wire.
• FooBarWidget 16y ago
  Zed isn't the only one who has found epoll to be slower than poll. The author of libev basically says the same thing. See http://pod.tst.eu/http://cvs.schmorp.de/libev/ev.pod http://pod.tst.eu/http://cvs.schmorp.de/libev/ev.pod and search for EVBACKEND_EPOLL. I wonder how kqueue behaves compares to poll and epoll. Kqueue has a less stupid interface because it allows you to perform batch updates with a single syscall.
• pmjordan 16y ago
  Pardon my ignorance, I haven't built high performance servers at this low a level, but I'm intrigued: What exactly is the definition of an "active" file descriptor in this context? My best guess after reading the man pages is that poll() takes an array of file descriptors to monitor and sets flags in the relevant array entries, which your code then needs to scan linearly for changes, whereas epoll_wait() gives you an array of events, thus avoiding checking file descriptors which haven't received any events. Active file descriptors would therefore be those that did indeed receive an event during the call. EDIT: thanks for pointing out Zed's "superpoll" idea. I somehow completely missed that paragraph in the article, which makes the following paragraph redundant. If this is correct, it sounds to me (naive as I am) as if some kind of hybrid approach would be the most efficient: stuff the idling/lagging connections into an epoll pool and add the pool's file descriptor to the array of "live" connections you use with poll(). That of course assumes you can identify a set of fds which are indeed most active.
  • jacquesm 16y ago
    An active file descriptor is a filedescriptor that you want to read from that has data available and one that you want to write to that has buffer space available. To put it in another way, if you were to use blocking IO then an operation on an active descriptor would not block. Of course poll and epoll are all about asynchronous IO (so non-blocking by definition) but that's a good way to describe the difference. Zed's 'superpoll' is precisely what you suggest.
    • pmjordan 16y ago
      Thanks for the explanation, I didn't think of the part about the socket being free for writing vs. whether there was data available. Zed's 'superpoll' is precisely what you suggest. Facepalm. Thanks, I mysteriously missed that part of the article.
  • FooBarWidget 16y ago
    An active file descriptor is one that you can read from or write to without blocking or getting EAGAIN as error. The whole point of poll/epoll/kqueue/select is to figure out which file descriptors are in such a state. The difference between poll and epoll is that, given an input of N file descriptors, poll returns all N file descriptors and you need to loop through each one of them to check whether the 'active' flag is set on there. epoll just returns all the active file descriptors so that you don't need to loop through the inactive ones. A hybrid approach, as Zed has suggested, would appear to be more efficient on the surface. It remains to be seen whether it can actually be implemented efficiently because migrating fds from/to epoll is extremely expensive, requiring a single syscall per fd. But if you ask me, the real solution is to have the kernel team fix their epoll implementation performance issues instead of forcing people to work around it with hybrid approaches. Other than the stupid single-syscall-per-fd requirement, there's nothing in epoll's interface that would force it to perform worse than poll when the active/total ratio is high.
• axod 16y ago
  Sounds like premature optimization to me. Is this really the bottleneck? Is the extra complexity and logic really going to be a net win?
  • statictype 16y ago
    Looks like he's already written a large bulk of his server's code, so maybe this optimization isn't really premature :) You're probably right that when you actually use Mongrel2 as your app server your app-specific code higher up will be a larger bottleneck, but that's code that you have to deal with and this is code that he has to deal with so optimizing the hell out of it doesn't sound like a bad idea.
    • axod 16y ago
      Lets say 95% of time is in your code, and 5% is in Mongrel2. Lets say that within Mongrel2, 10% of time is in this poll/epoll stuff. That's 0.5% of your total time being spent here. So even if it's made twice as fast, your app will only speed up by say 100ms -> 99.75ms Find the big things that matter and optimize them. Adding extra complexity to small things that don't matter is a recipe for more bugs and more issues.
      • pmjordan 16y ago
        I haven't actually used Mongrel2 yet, but I get the impression you can use it as a front-end for multiple physical servers, in which case the relative load of the M2 process on its server increases. Besides, unless Zed is writing your application and this is eating away at his time for that, it's not clear what exactly your complaint is.
        • rbanffy 16y ago
          > it's not clear what exactly your complaint is. Any complexity introduced in the code increases its long term maintenance cost. I strongly suspect this is one of those cases where the performance gain will not justify the long-term effort of maintaining a more complex architecture. I remember having a similar discussion circa 1992 about advantages and disadvantages of using ODBC versus native MS SQL/Sybase libraries. I instrumented the program I was writing and showed it spent 99+% of the time idling, 1-% of the time computing and, of that time, about 78% waiting for the database to return something. Using native libraries would yield a minuscule improvement at the cost of a huge headache.
• jfager 16y ago
  It is worth pointing out that the original epoll benchmarks were focused on how performance scaled with the number of dead connections, not performance in general: http://www.xmailserver.org/linux-patches/nio-improve.html http://www.xmailserver.org/linux-patches/nio-improve.html And as jacquesm points out, in a web-facing server, that's the case you should care about. A 15-20% performance hit in a situation a web-facing server is never going to see doesn't matter when you consider that the 'faster' method is 80% slower (or worse) in lots of real world scenarios. I'll be interested to see how the superpoll approach ends up working, but my first impression is 'more complexity, not much more benefit'.
  • zedshaw 16y ago
    > And as jacquesm points out, in a web-facing server, that's the case you should care about. Yes, but where's the evidence what people see for active/total ratios in the real world? I'm showing that unless it's below about 60% (probably more like 50%) then poll is the way to go. 60% active isn't entirely unrealistic at all. I can see quite a few servers hitting those thresholds, so in that cases, poll vs. epoll doesn't matter. I think what's more important in what I'm finding is that you really need both. It's entirely possible that you have servers that are at 80-90% ATR all the time. Others that are 10% ATR. The key is either you have to measure that, which nobody does, or you have to make a server that can adapt.
    • neilc 16y ago
      It's entirely possible that you have servers that are at 80-90% ATR all the time I'd be curious if you have any evidence that this occurs in practice. Even a busy server with clients of uniform + low latency, intuitively I'd expect fairly low ATRs. I think what's more important in what I'm finding is that you really need both. I'm not sure you do: the performance advantage of poll seems marginal at best. When ATR is high, you're presumably doing enough real work that the slight overhead of epoll vs. poll is probably not super important.
      • zedshaw 16y ago
        This is the point where talking about it does nothing. Go measure it like I have. In fact, I'll give you your hypothesis to test: "There are no servers that have an ATR of > 80%." That's easy to test, and I'm damn positive you could find some that disprove your assertion. More importantly though, you have this assertion: "Using both poll and epoll has no advantage in performance." Again, who knows, that's why I'm testing and trying out. That's the science part, since I've got no idea, but I'll give it a shot. And now that I've done an analysis that tells me what really matters, I'll be able to do very good tests for the different kinds of loads. Incidentally, when people run performance tests against web servers to see how fast they serve files they're testing the server with an ATR at around 100%. Food for thought.
• deleted 16y ago
  [deleted]
  • jerf 16y ago
    You know, I don't really like this sort of comment. Someone goes to great effort to empirically verify something, something that is against common wisdom, then someone gets to just float in with 20/20 hindsight and say "Well, yeah, duh." If it was so "yeah, duh", where's comment your about how blindingly obvious it was that common wisdom was wrong that dates from before somebody demonstrated it with concrete data and large test runs? All you'd have to do to improve your comment is remove the last "Stop the presses" snark.
• kunley 16y ago
  Cool experiment Mr Zed, but what about kqueue? It seems superior to both *poll minions. Would be great if you proved/falsified this thesis as well.
  • silentbicycle 16y ago
    kqueue is on OpenBSD and FreeBSD, while epoll is from Linux. (poll and select are on both)
    • kunley 16y ago
      I'm aware of it (you forgot to mention that kqueue is on the OS X as well). So what? There are probably hordes of people who will be willing to run Mongrel2 on *BSD platforms, precisely because of the performance reasons. And Zed is a famous tinkerer rather than a religious zealot, so very probably he could be interested in checking kqueue as well. "Why not" is also a good reason for a hacker when he's lacking other reasons.
      • silentbicycle 16y ago
        My point was that comparing something that only runs on Linux against something that only runs on (various) BSDs adds a lot of other noise to the comparison - it's no longer the same hardware, install, and tuning, with just a different kernel call.
        • kunley 16y ago
          I see your point. Still it would be useful to see some typical BSD/kqueue in action compared to typical Linux/*poll. I bet Zed is not doing a big sysctl tuning at this stage. Just leaving default system settings as they are still is some starting point for further investigations.
    • bch 16y ago
      NetBSD also supports kqueue
    • 16y ago
• frognibble 16y ago
  The blog post does not say if the epoll code uses level triggering or edge triggering. It would be interesting to see the results for both modes. The smaller number of system calls required for edge triggering might make a difference in performance.
  • zedshaw 16y ago
    That's entirely possible, but then you pay a penalty in complexity because you have to keep track of missed events yourself. I think (unproven) that it's actually a wash because of this.
    • frognibble 16y ago
      At most, you need to track a couple of booleans per socket, one for read and one for write. Depending on what you are doing, you might not even need to track these booleans. For example, on the read side you can ignore read events when you are not interested in reading. When you switch back to read interest, you can read the socket to see if data arrived while you ignored events. A similar strategy can be used on the write side.
• 16s 16y ago
  Very nice write-up. Little details such as this should make Mongrel2 very solid. It's nice to see how he analyzed the issues around poll and epoll and then figured out how to make use of both for optimum performance no matter what happens in production. Many other programs could benefit from this sort of analysis although at different levels... e.g. Sorted vectors may be better for smaller containers but hash tables better for larger containers, etc.
• KirinDave 16y ago
  Is it just me, or did Zed not describe his testing methodology in any detail? I can't even find a reference to his OS configuration and version details that he's developing on, which seems to me like a critical detail.
  • zedshaw 16y ago
    There's the pipetest.c file that everyone uses (since 2002) linked off that blog post, but I got tired and went to sleep. Today I'm crafting how I ran the tests and releasing all the code and asking everyone to test my results. I am completely assuming I am wrong so looking for other people to test it. Incidentally, if you google for "pipetest.c" you'll it's kind of the gold standard for this comparison, so if that code is wrong, then the entire assumption that epoll is better needs to be redone.
    • KirinDave 16y ago
      Okay. And I appreciate that, I'll look. To make your process scientific, I'd like to suggest you add the following things to the post when you find it convenient: 1. A detailed explanation of your methodology, preferably with source code. This is so we can reproduce the tests. The ability to reproduce your work is a critical part of any process calling itself science. 2. A detailed list of the hardware you used & its deployment. (For reasons listed above). 3. Your raw data should be made available upon request so other people can work it as well. P.S., aren't you concerned about I/O overhead with your superpoll proposal? It seems like the added resource allocation and the time spent in zeromq is going to eat up the small advantages you gain?
• phintjens 16y ago
  Zed, whats with all the premature optimization? Surely Mongrel2 should first be able to make coffee, build you an island and f@!in transform into a jet and fly you there, before you start to make it faster! Just kidding. It's always nice to see science in action. Great work! I suspect there's an impact on ZeroMQ's own poll/epoll strategy.
• lukesandberg 16y ago
  interesting article! Is 'super-poll' done yet? i would have liked to see a super poll line on some of those graphs to see how it compares to just vanilla poll and ePoll at different ATRs. Though i guess you would also have to test for situations where ATR varies over time (so that you could measure the impact of moving fds back and forth).
• pphaneuf 16y ago
  Question: as the ATR is going higher, so would the proportional time spent in poll or epoll, no? So if you have a thousand fds, and they're all active, you have to deal with a thousand fds, which would make the difference between poll and epoll insignificant (only twice as fast, not even an order of magnitude!)? This would make the micro-benchmark quite micro! Annoyingly enough, I think that means that the real way to find out would be an httpperf run, with each backends. A lot more work...
• deleted 16y ago
  [deleted]
• c00p3r 16y ago
  It is a little wonder why this kind of people think that everyone else are just stupid to realize such things. What they want is a fame and followers. (btw, don't you forget to donate!) hint: nginx/src/event/modules/ngx_epoll_module.c May be one should learn how to use epoll and, perhaps, how to program? ^_^