From owner-freebsd-questions@FreeBSD.ORG Thu Nov 29 14:42:36 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 2A70116A46C for ; Thu, 29 Nov 2007 14:42:36 +0000 (UTC) (envelope-from cpghost@cordula.ws) Received: from fw.farid-hajji.net (fw.farid-hajji.net [213.146.115.42]) by mx1.freebsd.org (Postfix) with ESMTP id B0EE713C457 for ; Thu, 29 Nov 2007 14:42:35 +0000 (UTC) (envelope-from cpghost@cordula.ws) Received: from epia-2.farid-hajji.net (epia-2 [192.168.254.11]) by fw.farid-hajji.net (Postfix) with ESMTP id 254F3E0312; Thu, 29 Nov 2007 15:42:33 +0100 (CET) Date: Thu, 29 Nov 2007 15:42:30 +0100 From: cpghost To: Bill Moran Message-ID: <20071129154230.5ba29b43@epia-2.farid-hajji.net> In-Reply-To: <20071129084244.eaba6f7a.wmoran@potentialtech.com> 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> Organization: Cordula's Web X-Mailer: Claws Mail 3.0.2 (GTK+ 2.12.1; i386-portbld-freebsd6.2) Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Cc: Wojciech Puchar , questions@freebsd.org, Mark Evans 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: Thu, 29 Nov 2007 14:42:36 -0000 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/