The following reply was made to PR kern/75855; it has been noted by GNATS. From: Gordon Tetlow <[email protected]> To: [email protected], [email protected] Cc: Subject: Re: kern/75855: [libc] getpwent(3) functions on 5.3 with large password file extremely slow Date: Sat, 7 May 2011 01:59:52 -0700
The reason for this is how the compat code scans the password table looking for compat entries. The algorithm is O(m * n) where m is the number of entries to lookup (in the case of the ls -l /home) and n is the number of lines in the password database. This is clearly pessimized and should be able to be better optimized. The current logic is something like: scan each entry in the passwd db: if it starts with '+/-' do compat checking if the key matches, return The logic for files is something like: Lookup exact entry in db, return if found. The process could probably do some amount of intelligence to avoid rescanning the password database on every lookup, but I can't think of anything off the top of my head (it's late). I'll think about it some more. _______________________________________________ [email protected] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-bugs To unsubscribe, send any mail to "[email protected]"
