Re: [Libevent-users] announcing libev, towards a faster and more featureful libevent
On Sun, Nov 04, 2007 at 09:56:44PM -0800, Scott Lamb [EMAIL PROTECTED] wrote: returning from event_loop, leaving the app unclear on what has happened and what to do. In any case, you can get the same behaviour as libevent by calling unloop in case of an error, so the interface is strictly more powerful. Another reason this is undesirable: to get the libevent behavior, I'd have to have this logic in *every callback* to get the same behavior. Hmm, one could actually roll this into the libevent compatibility layer. I'll think about this (didn't occur to me before). Note, however, that I think the libevent interface is undesirable, as it leaves me unclear on what happened and no reasonable way to recover (e.g. in the case of EBADF in select). Also, with libevent, you would need similar logic around each call to event_add/del and so on, because those can all fail in libevent, so its just a different place, really. (And I do think I will provide an oom-error handler for this specific case, as it is about the only generic error that isn't specific to some watcher). Thanks for these ideas, -- The choice of a Deliantra, the free code+content MORPG -==- _GNU_ http://www.deliantra.net ==-- _ generation ---==---(_)__ __ __ Marc Lehmann --==---/ / _ \/ // /\ \/ / [EMAIL PROTECTED] -=/_/_//_/\_,_/ /_/\_\ ___ Libevent-users mailing list Libevent-users@monkey.org http://monkey.org/mailman/listinfo/libevent-users
Re: [Libevent-users] announcing libev, towards a faster and more featureful libevent
On Sun, Nov 04, 2007 at 10:04:05PM -0800, Scott Lamb [EMAIL PROTECTED] wrote: Realistically, I think unit tests and bug reports/workarounds are about the only reason to blacklist specific event dispatchers. select() sucks, but well, that's why it's at the bottom of the list, right? There is a hardcoded priority list that only incidentally has the same order as the constants, but yes, select comes last, even if its usually faster than poll :) If you are really concerned about syscall overhead (you mentioned it in another context, though I don't think it should be a major concern), you might want to prefer poll() to epoll() or kqueue() if you're going to Yes, I thought about dynamically using select for a small (~50 or so) fd sets as select is faster than epoll in many common small scenarios, but that is mostly an epoll vs. poll issue. For kqueue, I can't quite see the overhead, as kqueue has the same number of syscalls per iteration as select/poll (namely one). the sysclal is more complicated, but is likely faster than poll in all cases (I have zero benchmark data on that, maybe the bsd people fucked it up, but likely, they didn't :) But that's a situation where you'd want a little more coarseness: low startup overhead methods vs. low per-socket overhead ones. Resorting to naming specific event mechanisms seems undesirable in terms of older programs taking advantage of newer event facilities. It is meant strictly as a benchmark, bug workaround, tuning mechanism. Less being able to programmatically decide which is best but more offering the user a mechanism to influence based on e.g. a config file, so one can configure your mythical big app to use select because it performs better in practise. Choice isn't evil, as long as there is an obvious default choice if you don't care (which is 0/EV_METHOD_AUTO). -- The choice of a Deliantra, the free code+content MORPG -==- _GNU_ http://www.deliantra.net ==-- _ generation ---==---(_)__ __ __ Marc Lehmann --==---/ / _ \/ // /\ \/ / [EMAIL PROTECTED] -=/_/_//_/\_,_/ /_/\_\ ___ Libevent-users mailing list Libevent-users@monkey.org http://monkey.org/mailman/listinfo/libevent-users
Re: [Libevent-users] announcing libev, towards a faster and more featureful libevent
Marc Lehmann wrote:
On Sun, Nov 04, 2007 at 09:56:44PM -0800, Scott Lamb [EMAIL PROTECTED] wrote:
returning from event_loop, leaving the app unclear on what has happened
and what to do.
In any case, you can get the same behaviour as libevent by calling unloop
in case of an error, so the interface is strictly more powerful.
Another reason this is undesirable: to get the libevent behavior, I'd
have to have this logic in *every callback* to get the same behavior.
Hmm, one could actually roll this into the libevent compatibility
layer. I'll think about this (didn't occur to me before).
Note, however, that I think the libevent interface is undesirable, as it
leaves me unclear on what happened and no reasonable way to recover (e.g.
in the case of EBADF in select).
No, as I said before, libevent retains errno. I've attached a
demonstration program. If it doesn't return 0 when run against your
libevent emulation layer, your code is broken.
Also, with libevent, you would need similar logic around each call to
event_add/del and so on, because those can all fail in libevent, so its just
a different place, really.
It's not just a different place - it's where the failure happened.
(And I do think I will provide an oom-error handler for this specific
case, as it is about the only generic error that isn't specific to some
watcher).
Thanks for these ideas,
#include stdlib.h
#include stdio.h
#include unistd.h
#include event.h
#include errno.h
#include string.h
const int BADFD = 64;
static void
cb(int fd, short events, void *cbarg)
{
}
int
main(int argc, char **argv)
{
struct event ev;
int sts;
const char *method;
/* Initialize, hopefully with select method */
putenv(EVENT_NOKQUEUE=yes);
putenv(EVENT_NODEVPOLL=yes);
putenv(EVENT_NOPOLL=yes);
putenv(EVENT_NOEPOLL=yes);
putenv(EVENT_NORTSIG=yes);
putenv(EVENT_NODEVPORT=yes);
event_init();
method = event_get_method();
if (strcmp(method, select) != 0)
return EXIT_FAILURE;
/* add a bad descriptor */
close(BADFD); /* just to be sure */
event_set(ev, BADFD, EV_READ|EV_PERSIST, cb, NULL);
sts = event_add(ev, NULL);
if (sts != 0)
return EXIT_FAILURE;
/* try dispatching */
sts = event_dispatch();
if (sts != 0) {
perror(event_dispatch);
return (errno == EBADF) ? EXIT_SUCCESS : EXIT_FAILURE;
}
return EXIT_FAILURE;
}
___
Libevent-users mailing list
Libevent-users@monkey.org
http://monkey.org/mailman/listinfo/libevent-users
Heap-based timer implementation (was Re: [Libevent-users] announcing libev, towards a faster and more featureful libevent)
On Sun, Nov 04, 2007 at 05:19:36PM -0800, Christopher Layne wrote: On Sun, Nov 04, 2007 at 05:04:25PM -0800, Scott Lamb wrote: * timers are managed by a priority queue (O(1) for important operations as opposed to O(log n) in libevent, also resulting in much simpler code). In terms of concrete data types, you appear to have used a binary heap? So by important operations you mean removal, correct? Insertion is still O(log n)? The asymptotic behavior is no different, then, as insertion happens at least as often as removal. Not to put on my O-face, but binary heap insert is *average* O(1). There should be a performance win for libevent, when it comes to timer checking, as using a heap will also be O(1) for heap_min() - which will benefit pending timer calculation code. However, early delete w/ pending timer will need some rigging or tombstone games. I wouldn't be surprised that, in a case where one is consistently resetting timers (think read/write before x time passes) and re-adding said event, that in the end it will be the same amount of CPU time. In case anybody here isn't watching the commits list [1], Niels applied a patch from Maxim Yegorushkin to make the timeout implementation based on a heap, rather than a RB-tree. Thanks, Maxim! This will probably need some testing; if anybody wants to play around with it, just check out the SVN trunk [2] and send in any bugs you run into, or any improvements that we should make. [1] The list is [EMAIL PROTECTED] ; go to https://lists.sourceforge.net/lists/listinfo/levent-commits if you want to subscribe. [2] The subversion repository is at https://levent.svn.sourceforge.net/svnroot/levent To check out trunk, make sure you have subversion installed, and type svn co https://levent.svn.sourceforge.net/svnroot/levent/trunk libevent-trunk yrs, -- Nick Mathewson pgph6MPLjfKJi.pgp Description: PGP signature ___ Libevent-users mailing list Libevent-users@monkey.org http://monkey.org/mailman/listinfo/libevent-users
Re: [Libevent-users] announcing libev, towards a faster and more featureful libevent
On Sun, Nov 04, 2007 at 09:47:59PM -0800, Christopher Layne [EMAIL PROTECTED] wrote: What is my program supposed to do? It can't distinguish them, and the correct behavior in each of these conditions is totally different. Also, in the program I'm thinking of, libev chose to kill this file descriptor probably means a network link just went down. Ergh. Great point. It should back away and leave things alone - notifying to the caller (or whoever else is listening) this is not acceptable to me - I suggest you fix it - because I won't (aka unix way). The caller in this case is the callback, however, because its the continuation of whatever code requested to watch e.g. a bad fd in the first place. Also, there is no way around an error status for the callback, one simply *must* provide a sensible status to the callback when something goes wrong, because that might be a long time after the watcher was added. So instead of notifying both the caller of the start funktion and the callback later, I don't see why notifying the callback in all cases would be worse, in fact, it lets you have errors easier. And yes, if you don't check for errors in your callback you are doomed. Returning errors to the caller of the event only requires additional checking code, and I have yet to see any code that actively checks for problems while calling event_once or event_add. But most callbacks do the sensible thing when called with EV_ERROR even when they don't care, because in the case of I/O errors they will try to read or write and see it doesn't work. No, on error your library may have muddied the water already by screwing with the file descriptors. libevent also makes errors clearer by simply returning error from the failed function (I'm thinking of event_once() vs ev_once() here.) Yes, closing is not a good idea, reporting an error and removing the event form the fd set is enough. However, I still maintain concentrating error handlign in the one place where its likely to be present already as opposed to reporting errors to places where nobody cares (show me the code that catches errors after making event_(once|del|add) calls) is the right thing to do. Wether one reports more detailed errors is then another question. And might be solved as easily as giving errno a defined value to use. -- The choice of a Deliantra, the free code+content MORPG -==- _GNU_ http://www.deliantra.net ==-- _ generation ---==---(_)__ __ __ Marc Lehmann --==---/ / _ \/ // /\ \/ / [EMAIL PROTECTED] -=/_/_//_/\_,_/ /_/\_\ ___ Libevent-users mailing list Libevent-users@monkey.org http://monkey.org/mailman/listinfo/libevent-users
Re: [Libevent-users] announcing libev, towards a faster and more featureful libevent
On Mon, Nov 05, 2007 at 09:50:54AM -0800, Scott Lamb [EMAIL PROTECTED] wrote: leaves me unclear on what happened and no reasonable way to recover (e.g. in the case of EBADF in select). No, as I said before, libevent retains errno. I've attached a demonstration program. If it doesn't return 0 when run against your libevent emulation layer, your code is broken. Libev actually pinpoints the faulty fd and tells the callback, which belongs to the part of the code that actually created the event watcher in the first place. libevent doesn't allow you to do that. so even when errno tells you ebadf, you can do nothing about it, because you cnanot identify the event watcher responsible for it. -- The choice of a Deliantra, the free code+content MORPG -==- _GNU_ http://www.deliantra.net ==-- _ generation ---==---(_)__ __ __ Marc Lehmann --==---/ / _ \/ // /\ \/ / [EMAIL PROTECTED] -=/_/_//_/\_,_/ /_/\_\ ___ Libevent-users mailing list Libevent-users@monkey.org http://monkey.org/mailman/listinfo/libevent-users
Re: [Libevent-users] announcing libev, towards a faster and more featureful libevent
On Sun, Nov 04, 2007 at 09:37:52PM -0800, Scott Lamb [EMAIL PROTECTED] wrote: There is actually a lot of code that relies on this just working, and the only other event loop I know that has a problem with this is Tk. Ugh, I'd argue that idiom is broken. But if the support's free, I guess it doesn't matter. Well, the idiom is how it works in most languages nowadays, so wether broken or not its important to support. The main problem is that with the current libevent implementation, failures are completely silent. as is required for integration of other event-based libraries, without having to force the use of some construct around event_loop. I don't udnerstand that, there is no construct around event_loop, its handled completely seperately. My question was in response to your I added idle watchers, pid watchers Ah, now I get it :) Well, it requires a construct around event_loop because there is no way to hook into event_loop. Of course, if you have those watcher type you don't need anything around your loop call. Sorry if that was worded confusingly. This is true, but its an optional feature you don't have to use. In case you wonder, EV, the perl interface to libev, uses this feature. It makes most sense when embedding, of course (not all the world is an .so :). Hmm, in your Perl example, I wouldn't rule out you wanting to share the event loop with some C-based library and being unable to do so. If you want to share it, you of course cannot do that unless that c-based library uses the same version of the code. But this is in no way difefrent to libevent: if one program links it statically and other shared, or if one program uses 1.3d and another 1.3e (different sonames), then you can't share it either. There's definitely nothing you can't do with a void*, so this is all a question of efficiency. Its also a question of coding overhead, which is probably more important than efficiency in this case. Especially as efficieny is a red herring. in the libev proposed api, callbacks get the watcher object passed, which a) is often what you want anyways b) is allocated by user code, so you cna just make the struct larger by appending your data. this solves the efficiency issue and also makes for a simpler API. In fact, I pondered long on wether I even add a void *arg to each event watcher, but I thought the overhead of havign to subclass is large in the common case where a single pointer indeed is enough. In any case, let me repeat that this is an optional feature, not a limitation, in the API. I assert that the cost of a sizeof(void*) to point to the relevant part of your structure (which can be nearby...still reasonable cache locality) is not too high. Its higher than necessary, and more complex than neccessary. All callbacks will be called with EV_ERROR when an error occurs. And yes, if you don't do error handlign and endlessly retry the same operation in a loop, you run into problems. But as that is an obvious programming bug, I don't see any problem here. Hmm. Let me introduce a use case: an event-driven program which must not fail. init or similar. I worked on such a program recently. If it were unreliable, you would have to send the system back to the factory for repair (i.e., flashing new software). On ENOMEM, it would basically sleep and retry. This was quite successful (memory could be temporarily consumed by network buffers, etc, which cleared itself up after a while). This could be solved easier with having a generic callback thats called in such special conditions. The alternative to have every event_add etc. call surrounded by checking code is not realistic, especially if some of the code is not easily changable (such as the libevent code itself which doesn't check for such errors!). For this program, it's important to know more than that an error has occurred. EV_ERROR is totally inadequate. You already know more: you know which watcher caused it, or which watcher is responsible. What is my program supposed to do? It can't distinguish them, and the correct behavior in each of these conditions is totally different. Also, in the program I'm thinking of, libev chose to kill this file descriptor probably means a network link just went down. Ergh. killing the file descriptor might indeed be harsh. all that libev does now is stop the event watcher and signal an error. Besides, if you cannot malloc the few bytes ev_once requires you need a *lot* of good error handlign code to continue sensibly. Yes, as I've mentioned above, there are programs for which this level of error handling is necessary. I agree, but libevent already doesn't provide this, so its moot to compare this case to libevent. However, it would be very interetsing to actualyl talk about an API that solves this problem. For example, on ENOMEM, one could have a callback thats called, because I cna imagine that sleeping is a common
Re: [Libevent-users] announcing libev, towards a faster and more featureful libevent
Marc Lehmann wrote: Hi! On tuesday, I sent mail about various problems with libevent and its current API as well as implementation. Unfortunately, the mail has not yet shown up, but fortunately, it has been superseded by this one :) In that mail, I announced that I will work on the problems I encountered in libevent (many of which have been reported and discusssed earlier on this list). After analyzing libevent I decided that it wasn't fixable except by rewriting the core parts of it (the inability to have multiple watchers for the same file descriptor event turned out to be blocking for my applications, otherwise I wouldn't have started the effort in the first place...). The results look promising so far: I additionally implemented a libevent compatibility layer and benchmarked both libraries using the benchmark program provided by libevent: http://libev.schmorp.de/bench.html Here is an incomplete list of what I changed and added (see the full list at http://cvs.schmorp.de/libev/README, or the cvs repository at http://cvs.schmorp.de/libev/): fixed or improved: * multiple watchers can wait for the same event, there is no limitation to one or two watchers for signals and io. Could you give me an example of where that is important? * there is full support for fork, you can continue to use the event loop in the parent and child (or just one of them), even with quirky backends such as epoll. Nice; seems like that's come up on the list several times. * there are two types of timers, based on real time differences and wall clock time (cron-like). timers can also be repeating and be reset at almost no cost (for idle timeouts used by many network servers). time jumps get detected reliably in both directions with or without a monotonic clock. (See my other mail about Linux's new timerfd facility.) Nice; repeating and absolute timers have come up several times before, too. * timers are managed by a priority queue (O(1) for important operations as opposed to O(log n) in libevent, also resulting in much simpler code). In terms of concrete data types, you appear to have used a binary heap? So by important operations you mean removal, correct? Insertion is still O(log n)? The asymptotic behavior is no different, then, as insertion happens at least as often as removal. * event watchers can be added and removed at any time (in libevent, removing events that are pending can lead to crashes). (They don't lead to crashes, as someone mentioned.) * different types of events use different watchers, so you don't have to use an i/o event watcher for timeouts, and you can reset timers seperately from other types of watchers. Also, watchers are much smaller (even the libevent emulation watcher only has about 2/3 of the size of a libevent watcher). Nice; separate types can be nice for documentation purposes if nothing else. * I added idle watchers, pid watchers and hook watchers into the event loop, as is required for integration of other event-based libraries, without having to force the use of some construct around event_loop. Pardon my ignorance, but what are hook watchers? pid watchers I assume to be a fancy SIGCHLD handler? That's a potentially useful feature, but why would it require a construct around event_loop? * the backends use a much simpler design. unlike in libevent, the code to handle events is not duplicated for each backend, backends deal only with file descriptor events and a single timeout value, everything else is handled by the core, which also optimises state changes (the epoll backend is 100 lines in libev, as opposed to 350 lines in libevent, without suffering from its limitations). Nice. As for compatibility, the actual libev api is very different to the libevent API (although the design is similar), but there is a emulation layer with a corresponding event.h file that supports the event library (but no evbuffer, evnds, evhttp etc.). I think the API needs more hashing out. It is...different...but I'm not sure it's necessarily better, and I don't like change for change's sake. A few notes: * what is the purpose of EV_COMMON? From first glance, I'm concerned that it could not be used properly unless libev.so and all callers are compiled with the same flags, which seems impractical if the library ever gains wide use. * on ev_once failure, you're calling the callback with EV_ERROR? Yuck. That's quite surprising behavior, and I could see it leading to stack overflows as each ev_once tries to issue another one. * What's your use case for ev_loop_new() and ev_loop_default()'s bitmask of allowed implementations? * (again, just skimming) you're closing fds automatically on ENOMEM? Ergh. That seems rather undesirable for many applications. Cheers, Scott ___ Libevent-users mailing list Libevent-users@monkey.org
Re: [Libevent-users] announcing libev, towards a faster and more featureful libevent
On Sun, Nov 04, 2007 at 05:04:25PM -0800, Scott Lamb [EMAIL PROTECTED] wrote: * multiple watchers can wait for the same event, there is no limitation to one or two watchers for signals and io. Could you give me an example of where that is important? Mostly in environments using some form garbage collection. For example, this idiom is common in Perl: $event = EV::io $fd, ... If $event happens to contain an old watcher and $fd happens to refer to the same fd as that old watcher, this will lead into probelms as the watchers are both alive for a short time. There is actually a lot of code that relies on this just working, and the only other event loop I know that has a problem with this is Tk. * there are two types of timers, based on real time differences and wall clock time (cron-like). timers can also be repeating and be reset at almost no cost (for idle timeouts used by many network servers). time jumps get detected reliably in both directions with or without a monotonic clock. (See my other mail about Linux's new timerfd facility.) (timerfd unfortunately makes little sense for this, as it adds overhead but I can't see the compelling advantage, as one will still run into the same time jump problems with periodic timers). Nice; repeating and absolute timers have come up several times before, too. This was something I always missed in event loops. That is, some event loops have one timer type, some the other, but never both. * timers are managed by a priority queue (O(1) for important operations as opposed to O(log n) in libevent, also resulting in much simpler code). In terms of concrete data types, you appear to have used a binary heap? So by important operations you mean removal, correct? removal: O(log n) insertion: O(log n) find next: O(1) still O(log n)? The asymptotic behavior is no different, then, as insertion happens at least as often as removal. Yes, but: a) finding the next timwer is a constant time issue b) a red-black tree is more than three times as slow (see the updated benchmark at http://libev.schmorp.de/bench.html, especially the difference between the first (no timers) and the second examples (timers in use)) * I added idle watchers, pid watchers and hook watchers into the event loop, as is required for integration of other event-based libraries, without having to force the use of some construct around event_loop. Pardon my ignorance, but what are hook watchers? if you want to plug-in other event-based libraries into the event loop you need to get to be able to hook into the event loop. this is what those watcher types provide. the alternative would be to write your own event_loop with EV_NONBLOCK, but that isn't modular, that is, if you have two difefernt sofwtare modules having their own event_loop you *must* use, you lose. prepare/check watchers use this problem nicely. A number of event loops have them, and they are useful for other things, such as transpoarently integrating coroutine packages etc. Its not a killer feature, just very very useful in some cases. pid watchers I assume to be a fancy SIGCHLD handler? Yes. That's a potentially useful feature, but why would it require a construct around event_loop? I don't udnerstand that, there is no construct around event_loop, its handled completely seperately. The reason is exists is allowing to share this potentially unsharable resource. For example, poll and select let you do everything (with fds), but you can of course only have one component per (single-thread) process using them, as they are blocking. The same thing is true for signals: you can't share them with sigaction, as sigaction only allows one user. And the same thing is true for sigchld. If your event loop provides support for it, you will less likely run into a situation where two sofwtare packages in the same process need access to it and stomp over each other. * the backends use a much simpler design. unlike in libevent, the code to handle events is not duplicated for each backend, backends deal only with file descriptor events and a single timeout value, everything else is handled by the core, which also optimises state changes (the epoll backend is 100 lines in libev, as opposed to 350 lines in libevent, without suffering from its limitations). Nice. And while investigating the WIN32-Code/win32.c libevent backend, I found out that its just a glorified variant of the select backend, except its O(n) in registering and deregistering. As for compatibility, the actual libev api is very different to the libevent API (although the design is similar), but there is a emulation layer with a corresponding event.h file that supports the event library (but no evbuffer, evnds, evhttp etc.). I think the API needs more hashing out. It is...different...but I'm not sure it's necessarily better, and I don't like change for change's sake. There has been no
Re: [Libevent-users] announcing libev, towards a faster and more featureful libevent
On Mon, Nov 05, 2007 at 02:42:16AM +0100, Marc Lehmann wrote: On Sun, Nov 04, 2007 at 05:19:36PM -0800, Christopher Layne [EMAIL PROTECTED] wrote: Not to put on my O-face, but binary heap insert is *average* O(1). There should be a performance win for libevent, when it comes to timer checking, as using a heap will also be O(1) for heap_min() - which will benefit pending timer calculation code. However, early delete w/ pending timer will need some rigging or tombstone games. I wouldn't be surprised that, in a case where one is consistently resetting timers (think read/write before x time passes) and re-adding said event, that in the end it will be the same amount of CPU time. No, because a red-black tree is much more complex in management, so even if both operations are O(log n), the heap usually wins hands down. Both insertion and removal are of the same complexity, on average, in a heap, of the data is random. However, libev has an interface (ev_timer_again) that incrementally updates the heap. Also, for repeating timers in general, there is no removal/insertion but only an incremental update. Right, which is not due to an inherent advantage of heap vs rbtree - but due to our luck in time always going in one direction. I believe similar code was present in libevent as it was. This in itself should be no different. Regarding pending events, this is solved in the same way for all events (not unlike how libevent does it): There is only one place where a pending event can be, and that is on its associated pending list. When an event gets stopped, and is found pending, it will be removed form the pending queue by nulling out its pointer. My point was that an event_del() on an event which has been called before it's timer has expired *or* an event_add() with a new timer will require reheapifying atleast part of the timer heap. Having an intrinsically sorted collection of elements and then altering a value within the middle of said collection before it has sifted to the top will require a reheap from that point on. Which isn't really that big a deal as similar time is spent in the present RB implementation as it is. I'm all for a binary-heap rather than a RB-tree personally. I think the performance will benefit primarily for heap_min() (which is done before every re-entry into the event backend to reset the max-wait timer for epoll/poll/select, etc). -cl ___ Libevent-users mailing list Libevent-users@monkey.org http://monkey.org/mailman/listinfo/libevent-users
Re: [Libevent-users] announcing libev, towards a faster and more featureful libevent
On Mon, Nov 05, 2007 at 02:42:16AM +0100, Marc Lehmann [EMAIL PROTECTED] wrote: However, libev has an interface (ev_timer_again) that incrementally updates the heap. Also, for repeating timers in general, there is no removal/insertion but only an incremental update. Oh, and sorry for always forgetting stuff... the rationale for supporting this operation is that I think its pretty important to support timers that get reset all the time without usually firing (e.g. idle read timeouts on a normally busy tcp connection). The other rationale is that its trivial to implement with a heap, because you already have all the code to do it: /* incremental timer update in ev_timer_again: */ w-at = mn_now + w-repeat; downheap (timers, timercnt, w-active - 1); /* compare with timer removal: */ timers [w-active - 1] = timers [--timercnt]; downheap (timers, timercnt, w-active - 1); In such a case (updating a timer) the event will simply wander down from current place in the heap to its new place. I am not sure wether this can be done with an rb-tree (likely), but I am sure that I do not want to have to maintain the code that does that :) (In any case, see the timer benchmark for a good comparison of heap vs. red-black-tree). -- The choice of a Deliantra, the free code+content MORPG -==- _GNU_ http://www.deliantra.net ==-- _ generation ---==---(_)__ __ __ Marc Lehmann --==---/ / _ \/ // /\ \/ / [EMAIL PROTECTED] -=/_/_//_/\_,_/ /_/\_\ ___ Libevent-users mailing list Libevent-users@monkey.org http://monkey.org/mailman/listinfo/libevent-users
Re: [Libevent-users] announcing libev, towards a faster and more featureful libevent
On Sun, Nov 04, 2007 at 06:00:56PM -0800, Christopher Layne [EMAIL PROTECTED] wrote: My point was that an event_del() on an event which has been called before it's timer has expired *or* an event_add() with a new timer will require reheapifying atleast part of the timer heap. Hmm, I do not see why this would ever be the case. Removing a timer that hasn't expired yet might actually be much cheaper than removing the one at the top element because it isn't at the root, so the n in the O(log n) is potentially much smaller. Having an intrinsically sorted collection of elements and then altering a value within the middle of said collection before it has sifted to the top will require a reheap from that point on. Not sure what you mean with re-heap, but the opertaion you describe is the same O(log n) operation as for removing elements elsewhere in the heap. And given that you take the latets timer and insert it at that point, removing a timer that hasn't expired is usually faster. Which isn't really that big a deal as similar time is spent in the present RB implementation as it is. No, I still maintain that the RB tree is slower because its rebalancing operations are frequent and very complex. Heap code is trivial. Yes, they have the same asymptotic growth behaviour, but the practical cases are all very far away from infinity, and the hidden C in O(log n) is quite important. (Again, please refer to the benchmark at http://libev.schmorp.de/bench.html which directly contrasts behaviour of libevent and libev with timers and no timers, especially look at the difference in runtime when timers are being used). I'm all for a binary-heap rather than a RB-tree personally. I think the performance will benefit primarily for heap_min() (which is done before every re-entry into the event backend to reset the max-wait timer for epoll/poll/select, etc). I thought so, too, until recently but in fact the event loop is run pretty rarely (except in benchmarks), and if you handle hundreds of clients within each run (very typical of busy servers), then you can have hundreds of timer updates, and these do show up in timing measurements. -- The choice of a Deliantra, the free code+content MORPG -==- _GNU_ http://www.deliantra.net ==-- _ generation ---==---(_)__ __ __ Marc Lehmann --==---/ / _ \/ // /\ \/ / [EMAIL PROTECTED] -=/_/_//_/\_,_/ /_/\_\ ___ Libevent-users mailing list Libevent-users@monkey.org http://monkey.org/mailman/listinfo/libevent-users
Re: [Libevent-users] announcing libev, towards a faster and more featureful libevent
On Mon, Nov 05, 2007 at 02:46:36AM +0100, Marc Lehmann wrote: On Sun, Nov 04, 2007 at 04:09:08PM -0800, Scott Lamb [EMAIL PROTECTED] wrote: Have you seen the new Linux timerfd API? Where available, you can wait for CLOCK_MONOTONIC and CLOCK_REALTIME events independently. Beats heuristics, How? I still need to detect time jumps. If my ev_periodic is to be scheduled every minute, on the minute, and somebody resets the time the timer needs to be rescheduled. With timerfd I would need to detetc that and remove/insert the timer again. (You might have no use for periodics for timeouts, but they are designed to solve this very problem :) timerfd() has good and redundant points... as far as I can tell, it's an inversion of userkernel code that results in the same goal. http://lwn.net/Articles/245688/ -cl ___ Libevent-users mailing list Libevent-users@monkey.org http://monkey.org/mailman/listinfo/libevent-users
Re: [Libevent-users] announcing libev, towards a faster and more featureful libevent
Marc Lehmann wrote: That seems rather undesirable for many applications. Well, its arguably better than libevents behaviour, which is simply returning from event_loop, leaving the app unclear on what has happened and what to do. In any case, you can get the same behaviour as libevent by calling unloop in case of an error, so the interface is strictly more powerful. Another reason this is undesirable: to get the libevent behavior, I'd have to have this logic in *every callback* to get the same behavior. ___ Libevent-users mailing list Libevent-users@monkey.org http://monkey.org/mailman/listinfo/libevent-users
Re: [Libevent-users] announcing libev, towards a faster and more featureful libevent
Scott Lamb wrote: * What's your use case for ev_loop_new() and ev_loop_default()'s bitmask of allowed implementations? libevents unconditional use of getenv raised concerns with me and apperently some users on this list, too, so this is one way to disable this (EVMETHOD_ANY instead of EVMETHOD_ALL). Also, I am sure some apps want control over the allowed event loops, e.g. to rule out select becasue it is known to be not wrokign for them. Ahh, I'd have to agree that getenv() seems sketchy. But with the interface you've supplied, you can't simply blacklist select() without Hmm. I was going to check this out more and forgot before sending the email. Realistically, I think unit tests and bug reports/workarounds are about the only reason to blacklist specific event dispatchers. select() sucks, but well, that's why it's at the bottom of the list, right? If you are really concerned about syscall overhead (you mentioned it in another context, though I don't think it should be a major concern), you might want to prefer poll() to epoll() or kqueue() if you're going to use a loop a couple times on a small number of fds then throw it away. But that's a situation where you'd want a little more coarseness: low startup overhead methods vs. low per-socket overhead ones. Resorting to naming specific event mechanisms seems undesirable in terms of older programs taking advantage of newer event facilities. ___ Libevent-users mailing list Libevent-users@monkey.org http://monkey.org/mailman/listinfo/libevent-users
Re: [Libevent-users] announcing libev, towards a faster and more featureful libevent
On Sat, Nov 03, 2007 at 09:15:07PM +0100, Marc Lehmann wrote: snip In that mail, I announced that I will work on the problems I encountered in libevent (many of which have been reported and discusssed earlier on this list). After analyzing libevent I decided that it wasn't fixable except by rewriting the core parts of it (the inability to have multiple watchers for the same file descriptor event turned out to be blocking for my applications, otherwise I wouldn't have started the effort in the first place...). A good itch, indeed. The results look promising so far: I additionally implemented a libevent compatibility layer and benchmarked both libraries using the benchmark program provided by libevent: http://libev.schmorp.de/bench.html Here is an incomplete list of what I changed and added (see the full list at http://cvs.schmorp.de/libev/README, or the cvs repository at http://cvs.schmorp.de/libev/): Man. More pressure to rename my library from libevnet to something else ;) snip * there is full support for fork, you can continue to use the event loop in the parent and child (or just one of them), even with quirky backends such as epoll. Curious how you managed to do this. Are you checking the process PID on each loop? * there are two types of timers, based on real time differences and wall clock time (cron-like). timers can also be repeating and be reset at almost no cost (for idle timeouts used by many network servers). time jumps get detected reliably in both directions with or without a monotonic clock. But then they're not truly real-time, no? snip * event watchers can be added and removed at any time (in libevent, removing events that are pending can lead to crashes). This is news to me. Can you give more detail, maybe with pointers to code? * different types of events use different watchers, so you don't have to use an i/o event watcher for timeouts, and you can reset timers seperately from other types of watchers. Also, watchers are much smaller (even the libevent emulation watcher only has about 2/3 of the size of a libevent watcher). libevnet does this for I/O; timer is always set separately from read/write events. (Point being, its using libevent.) * I added idle watchers, pid watchers and hook watchers into the event loop, as is required for integration of other event-based libraries, without having to force the use of some construct around event_loop. Needing to do an operation on every loop is arguably very rare, and there's not much burden in rolling your own. PID watchers, likewise... how many spots in the code independently manage processes (as opposed to one unit which can just catch SIGCHLD). Also, curious how/if you've considered Win32 environments. * the backends use a much simpler design. unlike in libevent, the code to handle events is not duplicated for each backend, backends deal only with file descriptor events and a single timeout value, everything else is handled by the core, which also optimises state changes (the epoll backend is 100 lines in libev, as opposed to 350 lines in libevent, without suffering from its limitations). libevnet optimizes state changes. Logically every I/O request is single-shot (which is more forgiving to user code), but it actually sets EV_PERSIST and delays libevent bookkeeping until the [libevnet bufio] callback returns. If the user code submits another I/O op from its callback (highly likely) then the event is left unchanged. It's still re-entrant safe because it can detect further activity up the call chain using some stack message passing bits (instead of reference counting because I also use mem pools, but I digress). Again, point being this can be done using libevent as-is. As for compatibility, the actual libev api is very different to the libevent API (although the design is similar), but there is a emulation layer with a corresponding event.h file that supports the event library (but no evbuffer, evnds, evhttp etc.). Well... if you can persuade me of the utility then this Christmas I might want to investigate writing an evdns-like component. See the lookup component of libevnet. There are lots of nice things I need in a DNS resolver that evdns and others are incapable of handling. And I've also written more HTTP, RTSP, and SOCKS5 parsers than I can remember. snip The obvious plan would be to take the evhttp etc. code from libevent and paste it in to libev, making libev a complete replacement for libevent with an optional new API. The catch is, I'd like to avoid this, because I am not prepared to maintain yet another library, and I am not keen on replicating the configure and portability work that went into libevent so far. If you ask me, it would prove more fortuitous to re-write the DNS and HTTP components then to replace libevent. Reason being because it would be hard to substantively improve on DNS/HTTP without altering the API, whereas
Re: [Libevent-users] announcing libev, towards a faster and more featureful libevent
On Sat, Nov 03, 2007 at 03:45:39PM -0700, William Ahern [EMAIL PROTECTED] wrote: A good itch, indeed. I am currently working on integrating all modules from libevent, so it becomes a full libevent replacement (and it already runs all of the testsuite that doesn't require access to internals). * there is full support for fork, you can continue to use the event loop in the parent and child (or just one of them), even with quirky backends such as epoll. Curious how you managed to do this. Are you checking the process PID on each loop? I considered that, but I think its too slow (one also needs to be careful that watchers don't change e.g. epoll state until the getpid check is done), or at leats I think I don't want that speed hit, no matter what. Instead, I make it the users job to actually call me after a fork. I provide three functions: void ev_fork_prepare (void); void ev_fork_parent (void); void ev_fork_child (void); which you cna simply plug into pthread_atfork and it will work. The reason I don't myself is that I don't want to require pthreads just for that, but the perl interface for example does, so perl programs will be safe. I wrote full support for fork even though its not automatic because it can be done and is fully supported. With libevent, you can't free the event base in general (program crashes with an assertion has has been documented on this list a number of times). * there are two types of timers, based on real time differences and wall clock time (cron-like). timers can also be repeating and be reset at almost no cost (for idle timeouts used by many network servers). time jumps get detected reliably in both directions with or without a monotonic clock. But then they're not truly real-time, no? Within the limits of technology, they are: - timers (based on monotonic time) will time out after n seconds (whatever was configured), even if the date resets in between (libevent can do that only for backward time jumps). - periodicals will simply be rescheduled, if a periodic timer is scheduled to fire at some point then it will not be affected by the time jump, it will still fire at that point (its more complicated with periodic timers scheduled to repeat, if you schedule a periodic timer to execute on every minute than libev will try to schedule it to occur when time() % 60 == 0, regardless of any time jumps. Of course, detecting and correcting this cnanot be done completely reliable with sub-second precision (there is no API in posix to do that), but with a monotonic clock, libev should manage quite fine to detect even very small time jumps caused by ntpd. (With no monotonic clock its a heuristic, obviously). * event watchers can be added and removed at any time (in libevent, removing events that are pending can lead to crashes). This is news to me. Can you give more detail, maybe with pointers to code? That is how I read the code in event.c on first glance. But in fact, it seems to be safe. I initially thought only removing the current watcher is safe. (I was in fact fooled by some bugs in the testsuite). Sorry for the confusion, I was too busy implementing all the other goodies, and right now I am busy implementing the remaining parts to get 100% event API support. * different types of events use different watchers, so you don't have to use an i/o event watcher for timeouts, and you can reset timers seperately from other types of watchers. Also, watchers are much smaller (even the libevent emulation watcher only has about 2/3 of the size of a libevent watcher). libevnet does this for I/O; timer is always set separately from read/write events. (Point being, its using libevent.) Even libevent is somewhat fast if you don't combine timeouts and io watchers in the same struct event. But it is of course quite the waste. * I added idle watchers, pid watchers and hook watchers into the event loop, as is required for integration of other event-based libraries, without having to force the use of some construct around event_loop. Needing to do an operation on every loop is arguably very rare, and there's not much burden in rolling your own. Its a quality issue. If you have a program that uses libevent and a library that needs to hook into it, it simply cannot be done. I happen to have many such cases. It basiclaly happens as soon as you use libevent as some part of some big program (such as in form of a perl module :), where many components might want to hook into the event loop. With that functionality in place, you can do it. Without it, you simply fail. It doesn't matter much, as libev is still faster than libevent even with all those watcher types. PID watchers, likewise... how many spots in the code independently manage processes (as opposed to one unit which can just catch SIGCHLD). You could say the same about signals and be right just as well, they are not as
