kern/75855: [libc] getpwent(3) functions on 5.3 with large password file extremely slow

[Gordon Tetlow]

The following reply was made to PR kern/75855; it has been noted by GNATS.

From: Gordon Tetlow <gordon at tetlows.org>
To: bug-followup at FreeBSD.org, bruce at 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.