On Mon, Mar 23, 2020 at 02:44:58AM +0800, CandyMi <[email protected]> wrote: > >"While other data structures are possible and I vaguely plan some minor > optimisations" > > I'm very happy to hear what you said! Because every optimization of > Timer makes it easy for developers to use without having to hold hands in > some cases (I wrote a lot of code for this). > I mentioned in my email last year: "About the choice of the data > structure of the timer watcher". But I didn't get a reply, I want to > communicate with you about this possibility here.
First of all, your mails arrive very garbled here, as if you mailer sent html instead of text - could you work on improving that= That makes reading and understanding your mails unnecessarily hard. As for optimisations, there is a limit to that - libev cannot know how your timers are used, and trying ti find out will slow it down so much that it isn't worth optimizing for many important cases. The biggest savings are to be done on the application side. > Of course, there is a simpler "ev_once" available. But when managing > more than 100,000 network connections, the overhead of the data structure > itself already occupies a very high user space. That's a very good example - ev_once does a (costly) malloc each time, and there is no good way aorund that (it could speed up the allocation, but it will have to allocate). Real savings can be done on the application side, by arranging its own data structures in a way that avoids extra memory allocastions altogether. > My current solution is the same as what you said: "Once you need to > stop the timer, mark it in timer-> data!", Wait for the real timeout > before calling ev_timer_stop to stop it. That's not what I said (in fact, I personally do not use the data field very often, and wish there was a nice way to get rid of it, but there isn't, unless you compile libev yourself). What I meant is more clearly explained in http://pod.tst.eu/http://cvs.schmorp.de/libev/ev.pod#Be_smart_about_timeouts, part 3 (Let the timer time out, but then re-arm it as required.) - basically, if you have an inactivity timeout of, say, 60 seconds, you can have a timer that runs at least every 60 seconds, and then calculates the real timeout. That way, when there is activity (typically much more often than once per minute), you only need to do a single assignment instead of rearming the timer. And that needs to be done on the application side. If you have many sockets with identical timeouts, you can be much more efficient. For example, you could have a list sorted by activity and a single timer for all connections. And if you don't need super-exact timeout, but have lots of connections, you could have a timer that runs every n seconds and reaps connections. A generic event library can't know this and/or do this for you. I did play with the thought of having many more watcher types, such as a watcher type that has it's own container in which all timers have the same timeout, which could be used for that, but that was when I was under the influence of Perl's Event module API, and in the end, the more minimal libevent way of doing things won over. Most importantly, libev tries to allow applications to do all of this themselves without forcing them into a particular style, which isd what I learned from other event loops which aren't as generic. > if (timer->data->closed == 1) { > ev_timer_again(...); // only need to stop timer. > return ; > } > > timer->data->closed = 1; // now That doesn't seem like an advantage - if you know the timer is no longer needed, it should be cheaper to stop it directly and be done with it. > Can libev provide a "painless" way for developers to use > "ev_timer_start" at will without having to consider using "trick" to simplify > the complexity of the algorithm? I think it already does, to the extent possible. I think your specific trick is actually malking it worse, but I could be convinced on the opposite by a benchmark :) But I suspect the conditions under which it could be better would have to be very specific. The reason why it is likely worse is that a lot of timers increase the timer heap size, and effectively the same work has to be done as when calling ev_io_stop, plus extra work because the heap is larger and the operations likely have worse cache locality. > I have observed that a timer called "Timer-wheel" is provided in the > Linux kernel, and its algorithm complexity is currently constant. This may be > a good reference. I know how the kernel does it - however, while it suits the kernel, it cannot emulate libev timers, and just because it might be O(1) on some operations does not mean it is faster than a good heap. And most importantly, you can't have both a timer wheel (which requires your application to design aorund it) and a timer implementation that just works for every application (as in libev), i.e. your goal of being generic and easy to use directly contradicts using a hardwired algorithm such as a timer wheel. > Have you considered optimizing by changing the data structure, or do > you still have other "killer" ways to optimize? Will this affect the > stability? I don't think there are much better data structures - while there or asymptotically better data structures, they are often much more complicated and dynamic, and are not actually faster in practise. Or, when they are faster, they are less generic (such as timer wheels), so require workarounds on the application side. And here a design parameter of libev comes into play again: If your application is fine with a timer wheel and can gain an advantage from it, you can put it on top of libev timers with practically no overhead. The reverse wouldn't be true. It is usually trivial to find a data structure that performs better for a specific problem, but libev needs to perform well for anything reasonable you throw at it (and preferably performs ok even in unreasonable cases). The 4-heap in libev is pretty close to be generically optimal for most use cases. -- The choice of a Deliantra, the free code+content MORPG -----==- _GNU_ http://www.deliantra.net ----==-- _ generation ---==---(_)__ __ ____ __ Marc Lehmann --==---/ / _ \/ // /\ \/ / [email protected] -=====/_/_//_/\_,_/ /_/\_\ _______________________________________________ libev mailing list [email protected] http://lists.schmorp.de/mailman/listinfo/libev
