Date: Sat, 7 May 2011 09:40:08 GMT From: Gordon Tetlow <gordon@tetlows.org> To: freebsd-bugs@FreeBSD.org Subject: Re: kern/75855: [libc] getpwent(3) functions on 5.3 with large password file extremely slow Message-ID: <201105070940.p479e8Wv015745@freefall.freebsd.org>
next in thread | raw e-mail | index | archive | help
The following reply was made to PR kern/75855; it has been noted by GNATS. From: Gordon Tetlow <gordon@tetlows.org> To: bug-followup@FreeBSD.org, bruce@engmail.uwaterloo.ca 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.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201105070940.p479e8Wv015745>