Path: utzoo!attcan!uunet!convex!killer!rpp386!jfh
From: jfh@rpp386.Dallas.TX.US (The Beach Bum)
Newsgroups: comp.unix.wizards
Subject: Re: libraries
Summary: quadratic file system behavior
Message-ID: <10211@rpp386.Dallas.TX.US>
Date: 20 Dec 88 21:28:37 GMT
References: <14946@mimsy.UUCP> <1269@nusdhub.UUCP> <15080@mimsy.UUCP>
Reply-To: jfh@rpp386.Dallas.TX.US (The Beach Bum)
Organization: Big "D" Home for Wayward Hackers
Lines: 41

In article <15080@mimsy.UUCP> chris@mimsy.UUCP (Chris Torek) writes:
>This is all quite false.  Even without using a ranlib (symbol table
>file) scheme, the directory need only be searched once, and every file
>within it opened once to build the linker's symbol table; then, or
>after reading the symdef file, those files that contained needed
>routines would have to be opened once to read their contents.

[ Definitions:		N		Number of files in directory
			#ofModules	Number of files required for link
			EntriesPerBlock	Directory entries per FS block
]

This should display quadratic file system behavior [ or worse ;-) ]
even with a linear read of the directory.  Each file lookup will require
N/2 file entries [ more or less ... ] to be scanned in the directory
[ and don't forget those BIG BSD style directories ;-) ] for each of
the N files in the directory.  This give up to N**2/2 entries which must
be checked.  The number of entries searched converts to blocks of
directory I/O at the rate of EntriesPerBlock, which is either bounded,
or [ for System V ] a constant.

With a symbol table file, the file system sees N/2 * #ofModules I/O.
With large links, #ofModules approaches N.

With a library, the file system see at most 2 * LibrarySize blocks
at most.  As an earlier poster noted, the average object file in a 
library is smaller than a 1K block.  Thus, the directory block I/O
dominates when #ofModules is greater than EntriesPerBlock.  [ did I
do that right? ]  For System V, this would occur when more than 32
modules were being loaded.  Your milage may vary.

The big loser is namei(), who doesn't have the slightest clue as to
what you are doing.  With a library file the I/O routines can be
optimized to handle the specific task of locating object files.  namei()
was never intended to be a general purpose index searching tool ;-)
Perhaps we should have ISAM directories ;-)  COBOL here we come ...
-- 
John F. Haugh II                        +-Quote of the Week:-------------------
VoiceNet: (214) 250-3311   Data: -6272  |"Unix doesn't have bugs,
InterNet: jfh@rpp386.Dallas.TX.US       | Unix is a bug"
UucpNet : <backbone>!killer!rpp386!jfh  +--              -- author forgotten --