this program seems to have the same issues with it.
Thanks
Mark
----- Original Message -----
From: "cpghost" <[EMAIL PROTECTED]>
To: "Bill Moran" <[EMAIL PROTECTED]>
Cc: "Wojciech Puchar" <[EMAIL PROTECTED]>;
<[EMAIL PROTECTED]>; "Mark Evans" <[EMAIL PROTECTED]>
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 <[EMAIL PROTECTED]> wrote:
In response to Wojciech Puchar <[EMAIL PROTECTED]>:
> > ls | wc
>
> strange. i did
>
> [EMAIL PROTECTED] ~/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
"[EMAIL PROTECTED]"
--
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
_______________________________________________
freebsd-questions@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-questions
To unsubscribe, send any mail to "[EMAIL PROTECTED]"
