From owner-freebsd-current Wed Sep 24 02:55:21 1997 Return-Path: Received: (from root@localhost) by hub.freebsd.org (8.8.7/8.8.7) id CAA19622 for current-outgoing; Wed, 24 Sep 1997 02:55:21 -0700 (PDT) Received: from hydrogen.nike.efn.org (resnet.uoregon.edu [128.223.170.28]) by hub.freebsd.org (8.8.7/8.8.7) with ESMTP id CAA19617 for ; Wed, 24 Sep 1997 02:55:18 -0700 (PDT) Received: (from jmg@localhost) by hydrogen.nike.efn.org (8.8.7/8.8.7) id CAA07361; Wed, 24 Sep 1997 02:55:16 -0700 (PDT) Message-ID: <19970924025515.60364@hydrogen.nike.efn.org> Date: Wed, 24 Sep 1997 02:55:15 -0700 From: John-Mark Gurney To: current@FreeBSD.ORG Subject: timeout management (was: Re: cvs commit: ...) References: <199709220505.XAA29116@rocky.mt.sri.com> <199709220548.XAA08824@pluto.plutotech.com> <199709221839.MAA01809@rocky.mt.sri.com> <19970922233930.12159@hydrogen.nike.efn.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Mailer: Mutt 0.69 In-Reply-To: <19970922233930.12159@hydrogen.nike.efn.org>; from John-Mark Gurney on Mon, Sep 22, 1997 at 11:39:30PM -0700 Reply-To: John-Mark Gurney Organization: Cu Networking X-Operating-System: FreeBSD 2.2.1-RELEASE i386 X-PGP-Fingerprint: B7 EC EF F8 AE ED A7 31 96 7A 22 B3 D8 56 36 F4 X-Files: The truth is out there X-URL: http://resnet.uoregon.edu/~gurney_j/ Sender: owner-freebsd-current@FreeBSD.ORG X-Loop: FreeBSD.org Precedence: bulk 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