ls -l takes a forever to finish.

[Mark Evans]

This issue has been resolved.  Thanks for your assistance everyone.
Changing /etc/nsswitch.conf from "passwd: compat" to read "passwd: files" 
resolved the issue.


Thanks
Mark

----- Original Message ----- 
From: "cpghost" <cpghost at cordula.ws>
To: "Mark Evans" <mbe2 at bayou.com>
Cc: <questions at freebsd.org>
Sent: Thursday, December 13, 2007 12:22 PM
Subject: Re: ls -l takes a forever to finish.


> On Wed, 12 Dec 2007 13:28:23 -0600
> "Mark Evans" <mbe2 at bayou.com> wrote:
>
>> this program seems to have the same issues with it.
>
> [Please don't top post.]
>
> Of course, if "ls -lf" has those issues, "sortls.py" will
> have them too, because it just runs it and sorts its output
> externally with another sorting algorithm. sortls.py speeds
> up "ls -l" considerably for huge (10,000+ entries) directories
> by using another sorting algorithm, it doesn't do anything else.
>
> Just to ask again: while you're waiting for "ls -lf", what
> does "top" say? Is that process accumulating CPU time, or
> is it just sitting around waiting, waiting, waiting...?
> Are you using NFS or another file system where stat(2) is
> expensive?
>
>> Thanks
>> Mark
>>
>>
>> ----- Original Message ----- 
>> From: "cpghost" <cpghost at cordula.ws>
>> To: "Bill Moran" <wmoran at potentialtech.com>
>> Cc: "Wojciech Puchar" <wojtek at wojtek.tensor.gdynia.pl>;
>> <questions at freebsd.org>; "Mark Evans" <mbe2 at bayou.com>
>> Sent: Thursday, November 29, 2007 8:42 AM
>> Subject: Re: ls -l takes a forever to finish.
>>
>>
>> > On Thu, 29 Nov 2007 08:42:44 -0500
>> > Bill Moran <wmoran at potentialtech.com> wrote:
>> >
>> >> In response to Wojciech Puchar <wojtek at wojtek.tensor.gdynia.pl>:
>> >>
>> >> > > ls | wc
>> >> >
>> >> > strange. i did
>> >> >
>> >> > [wojtek at wojtek ~/b]$ a=0;while [ $a -lt 10000 ];do mkdir
>> >> > $a;a=$[a+1];done
>> >> >
>> >> > completed <25 seconds on 1Ghz CPU
>> >> >
>> >> > ls takes 0.1 seconds user time, ls -l takes 0.3 second user time.
>> >> >
>> >> > unless you have 486/33 or slower system there is something wrong.
>> >>
>> >> Another possible scenario is that the directory is badly
>> >> fragmented. Unless something has changed since I last researched
>> >> this (which is possible) FreeBSD doesn't manage directory
>> >> fragmentation during use. If you're constantly adding and removing
>> >> files, it's possible that the directory entry is such a mess that
>> >> it takes ls a long time to process it.
>> >
>> > Yes, that's also possible. But sorting is really the culprit here:
>> > it *is* possible to create a directory with filenames in such a way
>> > that it triggers Quicksort's O(N^2) worst case instead of O(N log
>> > N).
>> >
>> > The following Python (2.5) program calls "ls -lf" and sorts its
>> > output with Python's own stable sort() routine (which is NOT
>> > qsort(3)). On a directory with 44,000 entries, it runs orders of
>> > magnitude faster than "ls -l", even though it has to use the
>> > decorate-sort-undecorate idiom to sort the output according
>> > according the filename, and it is interpreted rather than compiled!
>> >
>> > I guess that replacing qsort(3) in
>> > /usr/src/lib/libc/gen/fts.c:fts_sort()
>> > with another sort algorithm which doesn't
>> > expose this anomaly would solve that problem.
>
> --------------------- cut here ------------------ cut here ------------
> #!/usr/bin/env python
> # sortls.py -- sort output of ls -lf with python's stable sort routine.
>
> import os
>
> def sort_ls_lf(path):
>    "Sort the output of ls -lf path"
>    os.chdir(path)
>    lines = os.popen("ls -lf", "r").readlines()
>    dsu = [ (line.split()[-1], line) for line in lines ]
>    dsu.sort()
>    return ''.join(tupl[1] for tupl in dsu)
>
> if __name__ == '__main__':
>    import sys
>    if len(sys.argv) < 2:
>        print >>sys.stderr, "Usage:", sys.argv[0], "path"
>        sys.exit(1)
>    path = sys.argv[1]
>
>    try:
>        print sort_ls_lf(path)
>    except IOError:
>        pass   # silently absorb broken pipe and other errors
> --------------------- cut here ------------------ cut here ------------
>
> -cpghost.
>
> -- 
> Cordula's Web. http://www.cordula.ws/
>
>
> -- 
> Internal Virus Database is out-of-date.
> Checked by AVG Free Edition.
> Version: 7.5.446 / Virus Database: 268.18.25/744 - Release Date: 4/3/2007 
> 5:32 AM
>
>