From owner-freebsd-hackers@FreeBSD.ORG Mon Apr 21 21:53:56 2003 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id EF8CD37B401 for ; Mon, 21 Apr 2003 21:53:56 -0700 (PDT) Received: from mail.junkproof.net (mail.junkproof.net [206.55.70.12]) by mx1.FreeBSD.org (Postfix) with ESMTP id 4C31943FCB for ; Mon, 21 Apr 2003 21:53:56 -0700 (PDT) (envelope-from bill@twwells.com) Received: from mail (helo=mail.junkproof.net) by mail.junkproof.net with local-bsmtp (Exim 3.32 #1) id 197pn0-0005io-00 for freebsd-hackers@freebsd.org; Mon, 21 Apr 2003 23:53:54 -0500 X-Filter-Status: ok mail.junkproof.net 6 Received: from bill.twwells.com ( [68.32.144.147] ) by mail.junkproof.net via tcp with submission id 3ea4cadc-14fc17; Mon, 21 Apr 2003 23:53:48 -0500 Received: from bill by bill.twwells.com with local (Exim 4.14) id 197pmo-000CRx-A0; Tue, 22 Apr 2003 00:53:42 -0400 In-Reply-To: <3EA43297.44FC6E44@mindspring.com> To: Terry Lambert Date: Tue, 22 Apr 2003 00:53:42 -0400 (EDT) X-Mailer: ELM [version 2.4ME+ PL99b (25)] MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset=US-ASCII Message-Id: From: Bill Wells cc: freebsd-hackers@freebsd.org Subject: Re: maxfiles, file table, descriptors, etc... X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 22 Apr 2003 04:53:57 -0000 > An interesting aside here is that the per process open file table, > which holds references to file for the process, is actually > allocated at power-of-2, meaning each time it needs to grow, the > size is doubled, using realloc(), instead of malloc(), to keep the > table allocation contiguous. This means if you use a lot of files, > it takes exponentially increasing time to open new files, since > realloc has to double the size, and then copy everything. For a > few files, this is OK; for 100,000+ files (or network connections) > in a single process, this starts to become a real source of overhead. Let's say you just allocated the 9th element. You started out with a table of one element, doubled it (copying 1), doubled it to 4 elements (copying 2 + 1 or 3), thence to 8 (copying 4 + 3 or 7) and finally to 16 (copying 8 + 7 or 15). To allocate then 2**n + 1'th entry, you will have to do 2**(n+1) copies. Thus you will do (2**(n+1) - 1) / (2**n + 1) copies per allocated entry. This is the worst case, since additional allocations up to 2**(n+1) don't incur any additional copies. The upper bound is two entries copied per entry allocated. This makes exponential allocation a *linear time* algorithm. This just isn't a major time cost unless the chunkiness of the time spent is an issue.