Date: Wed, 24 Sep 1997 02:55:15 -0700 From: John-Mark Gurney <gurney_j@efn.org> To: current@FreeBSD.ORG Subject: timeout management (was: Re: cvs commit: ...) Message-ID: <19970924025515.60364@hydrogen.nike.efn.org> In-Reply-To: <19970922233930.12159@hydrogen.nike.efn.org>; from John-Mark Gurney on Mon, Sep 22, 1997 at 11:39:30PM -0700 References: <199709220505.XAA29116@rocky.mt.sri.com> <199709220548.XAA08824@pluto.plutotech.com> <199709221839.MAA01809@rocky.mt.sri.com> <19970922233930.12159@hydrogen.nike.efn.org>
next in thread | previous in thread | raw e-mail | index | archive | help
well... I proposed that we used a fibonacci heap as a solution to this problem... the fibonacci heap will do: FUNCTION TIMING (amortized) add new timeout O(1) check for timeout O(1) expire x timeouts O(x lg n) for n = number of timeouts remove a timeout O(lg n) for n = number of timeouts now, you have to take into account that this is amortized time... so at points in time, they may take longer.. but all the major work is actually done when you remove a timeout... I have preliminaty code that will implement a generic fibonacci heap, but it would not be ideal for something like this (to many function calls in my option)... it also doesn't support inital static storage or a free list so it doesn't allocate/deallocate elements unneccessarly I ran some tests.. on my amd k5/90 running tests on my k5, these are the number I come up with: Number Elements Max Heap Size User Time (adv over three runs) 1,000,000 1,000 29.2 1,000,000 100 23.9 1,000,000 10 21.6 as you can see, as the heap grows, the time to process isn't very significant.. and you can probably assume that most of this overhead is in the actual allocation and freeing of the elements.. which adding a freelist would actually help this numbers tremendously... as I stated earlier.. the largest part of this code is the data overhead per element which is currently at 28 bytes.. this includes a void * ptr for your "key", which means with small modification, we can get the data per timeout into 32bytes... that means it would take 16k to store 512 timeouts plus heap overhead (right now 24bytes) plus freelist overhead... if you would like a copy of the code, I'm willing to make it available (under BSD copyright of course) but I still would like to clean and comment the code some more... plus some more regression tests of the code is in order too... -- John-Mark Gurney Modem/FAX: +1 541 683 6954 Cu Networking Live in Peace, destroy Micro$oft, support free software, run FreeBSD
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?19970924025515.60364>