Date: Tue, 14 Jan 2003 03:42:49 -0800 From: Terry Lambert <tlambert2@mindspring.com> To: Igor Sysoev <is@rambler-co.ru> Cc: arch@FreeBSD.ORG Subject: Re: getsysfd() patch #1 (Re: Virtual memory question) Message-ID: <3E23F7B9.3FA2B37@mindspring.com> References: <Pine.BSF.4.21.0301141429390.26727-100000@is>
next in thread | previous in thread | raw e-mail | index | archive | help
Igor Sysoev wrote: > I do not want to say that kernel-based timers are useless or too expensive. > > I only want to say that if application need to set and delete timers > too often then it's much better to set and delete them in user space > because most of them will never fired and calling kernel to set or cancel > them is expensive. I've personally implemented a lot -- scores -- of call-conversion schedulers in my career, including timer support. The points that Matt makes about the kqueue/select style timeout as a building block are really very valid, if you need closed to fixed intervals as possible, at least within the non-RT scheduling constraints forced on you if you are using FreeBSD (the main reason I never joined John Dyson in his "rewrite the FreeBSD kernel" crusade was that he had no intention of dealing with RT issues, only SMP issues). > > for timers, they work better if they are cancelled before they > > ever fire, because cancellation is by reference, whereas firing > > is by traversal. > > In server that I'm deleloping I use delta value between timeouts > so firing is cheap as cancelation. Firing timers are on the head > of queue. This only works for fixed intervals timers, or variable interval timers with very high insertion costs -- effectively, you must implement in terms of absolute monotonically increasing tick count, and then traverse the outstanding list to perform an order insertion. The best case you can get is hashed vector insertion, where you must hit the hash and then traverse to the end of the list or the next hash bucket... effectively, a skiplist. This works OK for timers that are inserted, and left there, but it sucks for one-shots, it sucks for timers that are going to be deleted (you pay your cost up front), and it sucks for repeating timers (you have to pay the insertion cost each time). So basically, it doesn't answer two of the three types of timers that Matt desribed. Note that just going ahead and implementing this way sucks, too. Better to implement fixed interval event list heads that were inserted into a btree or a TST for the first event, and then tail-inserted for each timer request, so you can traverse from the head and get a 100% hit rate, minus 1, for an arbitrary number of timer events. Matt's suggested facilities have this same overhead problem, FWIW. > I did not argue against previous, current or future implementation > of timers in the kernel. I mean that if user-level application > need to set thousands timers (i.e. web server with thousands > connections) it's better to manage them in user space and set > only one the most early timer in the kernel via kqueue/select/poll. Batch them agross kqueue calls, and amortize the costs. Pushing down 100 timers with 1 call costs only 1/100th of a sytem call per timer. -- Terry To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-arch" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?3E23F7B9.3FA2B37>