maxfiles, file table, descriptors, etc...

[Bill Wells]

> 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.