--+KJYzRxRHjYqLGl5
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Thu, Jan 20, 2005 at 02:09:13AM +0100, Havard Eidnes wrote:
> ...and here follows some revised profiling data.  Unsurprisingly,
> ufs_lookup still dominates completely:

As it will. ufs_lookup is doing two things in the initial case. It is=20
checking to see if the name exists, and it is looking for a slot to add=20
the new file in if it doesn't exist.

Becasue we don't build in-kernel lists of files in the directory, we have=
=20
to do a full search (O(n)) of the directory to see if the name is or isn't=
=20
there already.

To further complicate things, we also use that initial search to look for=
=20
empty entries. If we don't find the name, we will use one empty entry to=20
store the to-be-created inode. So even if we used an in-core tree (or hash=
=20
table) to tell if the file doesn't exist, we still need to know where to=20
create it in the dir.

The answer is if we do create an in-core index (via a balanced tree or a
hash or whatever), we also create a linked list indicating which entries
in the directory are empty. Then creating becomes O(log n) or O(c) for the
lookup and O(c) for the entry-finding.

The question of course is writing code to handle this and then deciding=20
when we use it - if the directory only has a few entries or is only so=20
big, it may be easier to just do the current linear searches.

Take care,

Bill

--+KJYzRxRHjYqLGl5
Content-Type: application/pgp-signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.3 (NetBSD)

iD8DBQFB7w2zWz+3JHUci9cRAkxwAJ0Um0kgKh95ExA9Uy1dmAHgw2MKwwCglKh6
GzhsbUecSD/oDSkC+NdITSY=
=tzFo
-----END PGP SIGNATURE-----

--+KJYzRxRHjYqLGl5--