From owner-freebsd-questions@FreeBSD.ORG Wed Dec 12 19:32:33 2007 Return-Path: Delivered-To: questions@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id CD73616A41B for ; Wed, 12 Dec 2007 19:32:33 +0000 (UTC) (envelope-from mbe2@bayou.com) Received: from smtp.bayou.com (smtp.bayou.com [209.209.192.40]) by mx1.freebsd.org (Postfix) with ESMTP id ABC4E13C468 for ; Wed, 12 Dec 2007 19:32:33 +0000 (UTC) (envelope-from mbe2@bayou.com) Received: from bayoucshaffer (firewall.bayou.com [209.209.192.219]) by smtp.bayou.com (8.12.8/8.12.6) with SMTP id lBCJWWkZ031595 for ; Wed, 12 Dec 2007 13:32:32 -0600 (CST) (envelope-from mbe2@bayou.com) Message-ID: <002201c83cf5$2948a560$0d00a8c0@bayoucshaffer> From: "Mark Evans" To: References: <005901c8313f$f7048b70$0d00a8c0@bayoucshaffer><474CA49D.50306@FreeBSD.org><002001c831d5$80ad8670$0d00a8c0@bayoucshaffer><003101c831da$a405bc50$0d00a8c0@bayoucshaffer><20071129122043.A9040@wojtek.tensor.gdynia.pl><20071129084244.eaba6f7a.wmoran@potentialtech.com> <20071129154230.5ba29b43@epia-2.farid-hajji.net> Date: Wed, 12 Dec 2007 13:28:23 -0600 MIME-Version: 1.0 Content-Type: text/plain; format=flowed; charset="iso-8859-1"; reply-type=original Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2900.3138 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.3198 X-Scanned-By: MIMEDefang 2.49 on 209.209.192.40 Cc: Subject: Re: ls -l takes a forever to finish. X-BeenThere: freebsd-questions@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: User questions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 12 Dec 2007 19:32:34 -0000 this program seems to have the same issues with it. Thanks Mark ----- Original Message ----- From: "cpghost" To: "Bill Moran" Cc: "Wojciech Puchar" ; ; "Mark Evans" 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 wrote: > >> In response to Wojciech Puchar : >> >> > > 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 ------------ > > Regards, > -cpghost. > > -- > Cordula's Web. http://www.cordula.ws/ > _______________________________________________ > freebsd-questions@freebsd.org mailing list > http://lists.freebsd.org/mailman/listinfo/freebsd-questions > To unsubscribe, send any mail to > "freebsd-questions-unsubscribe@freebsd.org" > > > -- > 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 > >