Date: Tue, 22 Apr 2003 00:53:42 -0400 (EDT) From: Bill Wells <bill@twwells.com> To: Terry Lambert <tlambert2@mindspring.com> Cc: freebsd-hackers@freebsd.org Subject: Re: maxfiles, file table, descriptors, etc... Message-ID: <E197pmo-000CRx-A0@bill.twwells.com> In-Reply-To: <3EA43297.44FC6E44@mindspring.com>
next in thread | previous in thread | raw e-mail | index | archive | help
> 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.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?E197pmo-000CRx-A0>