Date: Fri, 21 Dec 2007 13:40:48 -0600 From: "Mark Evans" <mbe2@bayou.com> To: <questions@freebsd.org> Subject: Re: ls -l takes a forever to finish. Message-ID: <002201c84409$62d52770$0d00a8c0@bayoucshaffer> References: <005901c8313f$f7048b70$0d00a8c0@bayoucshaffer><474CA49D.50306@FreeBSD.org><002001c831d5$80ad8670$0d00a8c0@bayoucshaffer><a969fbd10711280752v7d38070x5f34d9d652ec4f7f@mail.gmail.com><003101c831da$a405bc50$0d00a8c0@bayoucshaffer><20071129122043.A9040@wojtek.tensor.gdynia.pl><20071129084244.eaba6f7a.wmoran@potentialtech.com><20071129154230.5ba29b43@epia-2.farid-hajji.net><002201c83cf5$2948a560$0d00a8c0@bayoucshaffer> <20071213192206.547cbffe@epia-2.farid-hajji.net>
next in thread | previous in thread | raw e-mail | index | archive | help
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@cordula.ws> To: "Mark Evans" <mbe2@bayou.com> Cc: <questions@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@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@cordula.ws> >> To: "Bill Moran" <wmoran@potentialtech.com> >> Cc: "Wojciech Puchar" <wojtek@wojtek.tensor.gdynia.pl>; >> <questions@freebsd.org>; "Mark Evans" <mbe2@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@potentialtech.com> wrote: >> > >> >> In response to Wojciech Puchar <wojtek@wojtek.tensor.gdynia.pl>: >> >> >> >> > > ls | wc >> >> > >> >> > strange. i did >> >> > >> >> > [wojtek@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 > >
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?002201c84409$62d52770$0d00a8c0>