wsmith@m.cs.uiuc.edu (03/09/89)
I did a test of the computational complexity of the ls and rm programs. I created directories with a large number of files in them (large = 1000-2000). Then, I timed ls commands in these directories. It appeared that the program was quadratic in the amount of system time that it took and n*log n in user time. (This is on a encore 4.2 berkeley Unix.) When I tried it under 4.3 Berkeley Unix on a VAX, it appeared to be order n in system time and n log n user time. The 4.3 version is obviously better. How do other versions of unix perform on large directories? To clean up my mess, I removed the files in two steps. First deleting half with `rm *a` rmand then deleting the rest with `rm *` The 4.3 Unix appeared to be quadratic in system time for this operation, while the 4.2 Unix was cubic or worse in the amount of system time required! (I'm only measuring the curve at 2 points, so it is hard to get a good estimate of the complexity.) Surely rm can do better than cubic, can't it? "rm *" seems to be a common enough idiom that rm could be optimized to handle that case better. I would like rm to be linear in system time. Is that possible? Bill Smith wsmith@cs.uiuc.edu uiucdcs!wsmith
arnold@mathcs.emory.edu (Arnold D. Robbins {EUCC}) (03/11/89)
In article <9000012@m.cs.uiuc.edu> wsmith@m.cs.uiuc.edu writes: >The 4.3 Unix >appeared to be quadratic in system time for this operation, while the 4.2 Unix >was cubic or worse in the amount of system time required! > >Surely rm can do better than cubic, can't it? "rm *" seems to be a common >enough idiom that rm could be optimized to handle that case better. I would >like rm to be linear in system time. Is that possible? This is not really an 'rm' issue, it's a file system issue. The shell (pick a shell, any shell, sh, csh, ksh) sorts the expansion of *; the order the filenames are in the directory is irrelevant to rm. Rm then proceeds to unlink each file in turn, probably randomly deleting entries from the middle of the directory. 4.3 made a number of changes to directory handling over 4.2, one of which was to perform compaction of the blocks in a directory when possible, as entries are deleted. I'll bet that if you were to rm `ls -f` and rm `ls -f | tac` you'd see very interesting behavior (i.e. remove files starting with the first and last files in the directory, respectively), since each unlink has to search the directory from scratch to find the entry. (Actually, on 4.3 the last one would be pathologically bad, while the first would be really quick, due to the directory caching in namei.) I guess the point here is to know where to point the finger; since it was all system time, it's not something that can really be fixed in rm. Your 4.2 vendor should upgrade their filesystem code to 4.3. -- Unix is a Registered | Arnold Robbins -- Emory University Computing Center Bell of AT&T Trademark | DOMAIN: arnold@unix.cc.emory.edu Laboratories. | UUCP: gatech!emory!arnold PHONE: +1 404 727-7636 -- Donn Seeley | BITNET: arnold@emoryu1 FAX: +1 404 727-2599
marcoz@MARCOZ.BOLTZ.CS.CMU.EDU (Marco Zagha) (03/11/89)
In article <9000012@m.cs.uiuc.edu>, wsmith@m.cs.uiuc.edu writes: > [...] "rm *" seems to be a common > enough idiom that rm could be optimized to handle that case better. Don't forget that the shell expands the "*", not rm. All rm sees is a huge argv with one name for every file (except .* files). == Marco (marcoz@cs.cmu.edu) --
chris@mimsy.UUCP (Chris Torek) (03/11/89)
In article <3804@emory.mathcs.emory.edu> arnold@mathcs.emory.edu (Arnold D. Robbins {EUCC}) writes: >I'll bet that if you were to > > rm `ls -f` and > rm `ls -f | tac` > >you'd see very interesting behavior (i.e. remove files starting with >the first and last files in the directory, respectively), since each >unlink has to search the directory from scratch to find the entry. >(Actually, on 4.3 the last one would be pathologically bad, while the >first would be really quick, due to the directory caching in namei.) This did not match what I remembered, so I just checked. You cannot cache the result of a delete operation (it is senseless), so the only thing that would affect the time is the offset cache. Around line 370 of ufs_namei.c, one finds the following comment: /* * If this is the same directory that this process * previously searched, pick up where we last left off. * We cache only lookups as these are the most common * and have the greatest payoff. Caching CREATE has little * benefit as it usually must search the entire directory * to determine that the entry does not exist. Caching the * location of the last DELETE has not reduced profiling time * and hence has been removed in the interest of simplicity. */ The effect unlink order would have, then, is that a forward remove would aid each lookup by reducing the number of entries scanned. The effect should certainly be measurable, but probably not extreme. -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
wsmith@m.cs.uiuc.edu (03/12/89)
>To clean up my mess, I removed the files in two steps. First deleting >half with `rm *a` rmand then deleting the rest with `rm *` The 4.3 Unix >appeared to be quadratic in system time for this operation, while the 4.2 Unix >was cubic or worse in the amount of system time required! >(I'm only measuring the curve at 2 points, so it is hard to get a good >estimate of the complexity.) > >Surely rm can do better than cubic, can't it? "rm *" seems to be a common >enough idiom that rm could be optimized to handle that case better. I would >like rm to be linear in system time. Is that possible? Please ignore these two paragraphs. My method of testing rm was invalid. The reason is that on some systems, the way directories work causes the amount of time to remove a several files to depend on the order that they were created in the directory. It is more work to delete the most recently created file than it is to delete the first file that was created. (There is probably some imprecision in the previous sentence because of the possibility of alternating the creation and deletion of files. I meant only to cover the case of a single file creation phase followed by a single file deletion phase.) (It has also been pointed out that I am not really measuring the complexity of rm or ls at all, but am instead measuring the kernel name-to-inode translation behavior.) What brought this up in the first place was an attempt to decide whether it was better to have 10000 or more files in one directory, to have a fraction of the files in several directories, or at the extreme case, to have 100 of the files in each of 100 directories if I wanted to be able open() individual files quickly. Bill Smith wsmith@cs.uiuc.edu uiucdcs!wsmith
frank@zen.co.uk (Frank Wales) (03/13/89)
In article <4461@pt.cs.cmu.edu> marcoz@MARCOZ.BOLTZ.CS.CMU.EDU (Marco Zagha) writes: >In article <9000012@m.cs.uiuc.edu>, wsmith@m.cs.uiuc.edu writes: >> [...] "rm *" seems to be a common >> enough idiom that rm could be optimized to handle that case better. > >Don't forget that the shell expands the "*", not rm. All rm sees >is a huge argv with one name for every file (except .* files). This was my first thought upon reading what Bill posted, and then I thought: "maybe he means the act of deleting all the files in a directory is a common one, and should be handled specially." Certainly, rm never sees the '*', only the results of its (sorted, hidden-file-less) expansion. Maybe adding a '-A' (for All, harder to type than '-a') option to rm would be justified. No doubt doing so would break jillions of scripts. :-) -- Frank Wales, Systems Manager, [frank@zen.co.uk<->mcvax!zen.co.uk!frank] Zengrange Ltd., Greenfield Rd., Leeds, ENGLAND, LS9 8DB. (+44) 532 489048 x217
les@chinet.chi.il.us (Leslie Mikesell) (03/13/89)
In article <9000014@m.cs.uiuc.edu> wsmith@m.cs.uiuc.edu writes: >What brought this up in the first place was an attempt to decide whether >it was better to have 10000 or more files in one directory, to have a >fraction of the files in several directories, or at the extreme case, >to have 100 of the files in each of 100 directories if I wanted to be >able open() individual files quickly. The maximum optimal size probably varies with the OS version. I've been told that directory access becomes much less efficient when the directory inode goes to triple indirect blocks (300 files?). Under SysV directories never shrink by themselves, so access efficiency depends on how many files have ever been in that directory at once instead of how many are currently there. If you have a scheme to determine which of 100 directories a particular file will be stored under, that calculation is almost certain to be faster than a search of many hundreds of extra files in the same directory. Les Mikesell
chris@mimsy.UUCP (Chris Torek) (03/13/89)
In article <7919@chinet.chi.il.us> les@chinet.chi.il.us (Leslie Mikesell) writes: >The maximum optimal size probably varies with the OS version. I've >been told that directory access becomes much less efficient when >the directory inode goes to triple indirect blocks (300 files?). 300?!? (Maybe 300! :-) [read `300 factorial']) Assuming the SysV file system is unchanged from the V7 file system of 1976 or so (which, for the most part, it is), an inode remembers 13 blocks maximum. Of these, the first 10 are direct, the 11th is single indirect, the 12th is double indirect, and the 13th is triple indirect. (All this from memory of 4.1BSD, and correspondingly suspect.) If the block size is 512 bytes (it is either 512 or 1024), and a directory entry is 16 bytes (it is), the directory first switches to *single* indirects at 5120 bytes, or 5120/16=320 entries. Using 1 kbyte blocks this doubles to 640. A single indirect block points to up to 170 (I think---this is 512/3) more blocks (512 bytes each again), so to reach double indirects you need (10*512 + 170*512)/16 = 5760 entries. By then you will have run out of inodes due to the SysV inode eater bug :-) . With 1024 byte blocks a single indirect should handle 341 more blocks, for a total of (10*1024 + 341*1024)/16 = 22464 entries. 4.[23]BSD uses a block size of 4096 or 8192 bytes, and has 12 direct blocks, so while its directory entries can be larger (but probably average about the same---an 8 character file name uses roundup(8,4) + 4 + 4 = 16 bytes; 9 to 12 character names use 20 bytes), it takes either 12*4096=49152 bytes or 12*8192=98304 bytes, or more than 2450 20-byte entries (more than 4950 with 8 kbyte blocks) before it needs to go to indirects. (The same, of course, goes for plain files.) -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
tale@pawl.rpi.edu (David C Lawrence) (03/14/89)
In article <1541@zen.UUCP> frank@zen.co.uk (Frank Wales) writes:
frank> Maybe adding a '-A' (for All, harder to type than '-a') option
frank> to rm would be justified. No doubt doing so would break
frank> jillions of scripts.
I realize that there is a smiley there, but why should adding -A or -a
break any scripts at all? Doesn't seem that anyone should have it as
a flag to rm in a script.
--
tale@rpitsmts.bitnet, tale%mts@rpitsgw.rpi.edu, tale@pawl.rpi.educmf@cisunx.UUCP (Carl M. Fongheiser) (03/14/89)
In article <7919@chinet.chi.il.us> les@chinet.chi.il.us (Leslie Mikesell) writes: >The maximum optimal size probably varies with the OS version. I've >been told that directory access becomes much less efficient when >the directory inode goes to triple indirect blocks (300 files?). Yikes. I'm sure you mean double indirect or even just indirect blocks. A file with triple indirect blocks in it is unthinkably large; a directory containing triple indirect blocks is even more unthinkable! If you do manage a directory with triple indirect blocks, yes, your directory access will be *very* slow. >Under SysV directories never shrink by themselves, so access efficiency >depends on how many files have ever been in that directory at once >instead of how many are currently there. If you have a scheme to >determine which of 100 directories a particular file will be stored >under, that calculation is almost certain to be faster than a search >of many hundreds of extra files in the same directory. Nonsense. System V directories don't shrink, but they don't grow unless they need to, either. System V can and will fill in holes in directories. Carl Fongheiser University of Pittsburgh
karish@forel.stanford.edu (Chuck Karish) (03/14/89)
In article <1541@zen.UUCP> frank@zen.co.uk (Frank Wales) wrote: >In article <4461@pt.cs.cmu.edu> marcoz@MARCOZ.BOLTZ.CS.CMU.EDU (Marco Zagha) writes: >>In article <9000012@m.cs.uiuc.edu>, wsmith@m.cs.uiuc.edu writes: >>> [...] "rm *" seems to be a common >>> enough idiom that rm could be optimized to handle that case better. >Maybe adding a '-A' (for All, harder to type than '-a') option to rm would >be justified. Great, another feature! How about using an alias instead: alias rmall 'ls -f | xargs rm -f' This avoids the overhead of sorting the names in the directory. It also suppresses those annoying queries from rm. Chuck Karish hplabs!hpda!mindcrf!karish (415) 493-7277 karish@forel.stanford.edu
tale@pawl.rpi.edu (David C Lawrence) (03/14/89)
In article <9000012@m.cs.uiuc.edu>, wsmith@m.cs.uiuc.edu writes: wsmith> [...] "rm *" seems to be a common wsmith> enough idiom that rm could be optimized to handle that case better. In article <1541@zen.UUCP> frank@zen.co.uk (Frank Wales) wrote: FW>Maybe adding a '-A' (for All, harder to type than '-a') option to rm would FW>be justified. In article <871@Portia.Stanford.EDU> karish@forel.stanford.edu (Chuck Karish) writes: CK> Great, another feature! How about using an alias instead: CK> CK> alias rmall 'ls -f | xargs rm -f' CK> CK> This avoids the overhead of sorting the names in the directory. CK> It also suppresses those annoying queries from rm. By your own quoting, Chuck, the reason Frank suggested -A was for optimization. Invoking ls to pipe to xargs which calls rm is not the optimum strategy. -- tale@rpitsmts.bitnet, tale%mts@rpitsgw.rpi.edu, tale@pawl.rpi.edu
gwyn@smoke.BRL.MIL (Doug Gwyn ) (03/14/89)
In article <1541@zen.UUCP> frank@zen.co.uk (Frank Wales) writes: >Maybe adding a '-A' (for All, harder to type than '-a') option to rm would >be justified. No doubt doing so would break jillions of scripts. :-) New options aren't likely to break existing scripts. However, I don't understand the problem. "rm -r ." seems sufficient.
terryl@tekcrl.LABS.TEK.COM (Terry Laskodi) (03/14/89)
In article <1541@zen.UUCP+ frank@zen.co.uk (Frank Wales) writes: +In article <4461@pt.cs.cmu.edu> marcoz@MARCOZ.BOLTZ.CS.CMU.EDU (Marco Zagha) writes: +>In article <9000012@m.cs.uiuc.edu>, wsmith@m.cs.uiuc.edu writes: +>> [...] "rm *" seems to be a common +>> enough idiom that rm could be optimized to handle that case better. +> +>Don't forget that the shell expands the "*", not rm. All rm sees +>is a huge argv with one name for every file (except .* files). + +This was my first thought upon reading what Bill posted, and then I thought: +"maybe he means the act of deleting all the files in a directory is a +common one, and should be handled specially." Certainly, rm never sees +the '*', only the results of its (sorted, hidden-file-less) expansion. + +Maybe adding a '-A' (for All, harder to type than '-a') option to rm would +be justified. No doubt doing so would break jillions of scripts. :-) There already is an option like that; try "rm -r <directory-name>" (and, yes I know "*" won't match . files....).
frank@zen.co.uk (Frank Wales) (03/14/89)
In article <TALE.89Mar13132118@imagine.pawl.rpi.edu> tale@pawl.rpi.edu writes: >In article <1541@zen.UUCP> frank@zen.co.uk (Frank Wales) writes: >frank> Maybe adding a '-A' (for All, harder to type than '-a') option >frank> to rm would be justified. No doubt doing so would break >frank> jillions of scripts. > >I realize that there is a smiley there, but why should adding -A or -a >break any scripts at all? Doesn't seem that anyone should have it as >a flag to rm in a script. No reason I can think of, but then I've seen scripts, programs and entire systems break for the most ridiculous reasons imaginable that nothing really surprises me any more. You'd be amazed at the assumptions people make when they write things. Just being my usual cynical self, that's all. ;-) -- Frank Wales, Systems Manager, [frank@zen.co.uk<->mcvax!zen.co.uk!frank] Zengrange Ltd., Greenfield Rd., Leeds, ENGLAND, LS9 8DB. (+44) 532 489048 x217
karish@forel.stanford.edu (Chuck Karish) (03/14/89)
In article <TALE.89Mar13170500@imagine.pawl.rpi.edu> tale@pawl.rpi.edu wrote: >In article <9000012@m.cs.uiuc.edu>, wsmith@m.cs.uiuc.edu writes: >wsmith> [...] "rm *" seems to be a common >wsmith> enough idiom that rm could be optimized to handle that case better. >In article <1541@zen.UUCP> frank@zen.co.uk (Frank Wales) wrote: >FW>Maybe adding a '-A' ... option to rm would be justified. >In article <871@Portia.Stanford.EDU> karish@forel.stanford.edu >(Chuck Karish) writes: >CK> Great, another feature! How about using an alias instead: >CK> >CK> alias rmall 'ls -f | xargs rm -f' >By your own quoting, Chuck, the reason Frank suggested -A was for >optimization. Invoking ls to pipe to xargs which calls rm is not the >optimum strategy. If I understand the problem correctly, my pipeline takes an algorithm that's exponential in time w.r.t. the number of directory entries, and recasts it so it's linear. Is this optimization, or not? When I type 'rm *' the shell sorts the argument list before passing it to rm, which does a pretty fair job of maximizing the amount of directory scanning that rm has to do. 'ls -f' presents the arguments to rm in directory order, so rm always seeks by exactly one directory entry to get from one argument to the next. If a hack is needed, it's to the shell, not to rm. If it were possible (is it already?) to do filename globbing without sorting, the 'ls -f' would be unnecessary. All accesses of large directories are expensive, not just 'rm *'; adding a no-sort option to the shell would provide a single feature that would help many utilities. The '-A' option would eliminate the need for the xargs call (the problem posed only arises in cases where the argument list is likely to exceed ARG_MAX), but would do so only for the one special case. Chuck Karish hplabs!hpda!mindcrf!karish (415) 493-7277 karish@forel.stanford.edu
danny@itm.UUCP (Danny) (03/14/89)
In article <TALE.89Mar13170500@imagine.pawl.rpi.edu> tale@pawl.rpi.edu writes:
~Invoking ls to pipe to xargs which calls rm is not the
~optimum strategy.
The best "stragety" (thanks, Bugs) I've ever heard of is:
use clri to zap the directory,
and fsck to clean up the mess.
The story began with a news-passing scheme which saved articles as
files in a directory to be passed to another machine. When said machine
was down, the directory grew. Gatech had literally thousands of files
to be sent, so, they either copied them to tape, or said, "Forget it!"
Then came the rm. It ran overnight, and was still far from done. One
of the gurus from MSDC (Hi Dan!) suggested the above idea, which took
about 10 minutes. Ok, ok, you do have to unmount the partition, but,
even so, quadratic it ain't.
WARNING! Not for the faint-of-heart! "Experience and informed
courage count for much." - from someplace in the Version 7 man pages,
dealing with addled file systems.
Danny
--
Daniel S. Cox
(seismo!gatech!itm!danny)dhesi@bsu-cs.UUCP (Rahul Dhesi) (03/15/89)
In article <1280@itm.UUCP> danny@itm.UUCP (Danny) writes [about cleaning up runaway directories]: > The best "stragety" (thanks, Bugs) I've ever heard of is: > use clri to zap the directory, > and fsck to clean up the mess. VAX/VMS has a consistent command structure and the switch /nodirectory always, always means "not a directory". Therein lies a tale. There is a command "set file" that does many things to files, and it accepts many options while doing those things. The manual documented "set file/nodirectory" to mean "act on these files only if they aren't directories", but the command interpreter understood it to mean "make sure these aren't directories." So if you did $ set file/nodirectory *.* all subdirectories matching *.* suddenly became regular files. In effect, we had a command that was (a) accessible to ordinary users and (b) documented to be harmless but (c) did a near-clri on specified directories. Unfortunately, the same unprivileged users couldn't do the equivalent of fsck (analyze/disk or something like that). I think they fixed it. I didn't try it again. -- Rahul Dhesi UUCP: <backbones>!{iuvax,pur-ee}!bsu-cs!dhesi ARPA: dhesi@bsu-cs.bsu.edu
les@chinet.chi.il.us (Leslie Mikesell) (03/16/89)
In article <16364@mimsy.UUCP> chris@mimsy.UUCP (Chris Torek) writes: >In article <7919@chinet.chi.il.us> les@chinet.chi.il.us (Leslie Mikesell) >writes: >>The maximum optimal size probably varies with the OS version. I've >>been told that directory access becomes much less efficient when >>the directory inode goes to triple indirect blocks (300 files?). > >300?!? (Maybe 300! :-) [read `300 factorial']) OK, OK.. indirect blocks, not triple indirect blocks. Shows how much you miss when all you have to go by is the man pages. Back to the subject though, a simple-minded test of catting 1000 tiny files in one directory to /dev/null vs. 100 files in each of 10 directories using xargs and explicit filenames so shell expansion would not be a factor showed that the large directory took about twice the sys time. This confirmes my more casual observations that having large directories on a machine hurts performance in general, at least under SysV. The worst case seems to be accessing large directories on a remote machine using RFS. Les Mikesell
guy@auspex.UUCP (Guy Harris) (03/21/89)
>>Under SysV directories never shrink by themselves, so access efficiency >>depends on how many files have ever been in that directory at once >>instead of how many are currently there. If you have a scheme to >>determine which of 100 directories a particular file will be stored >>under, that calculation is almost certain to be faster than a search >>of many hundreds of extra files in the same directory. > >Nonsense. System V directories don't shrink, but they don't grow unless >they need to, either. System V can and will fill in holes in directories. System V will fill in holes, so will most other UNIX systems. Nevertheless, the claim that Les Mikesell makes is not "nonsense"; directory searches go all the way out to the end of the directory, and if the directory once held 10,000 entries, then unless your system shrinks directories, the search will have to scan through all 10,000 of those entries, even if they're empty. A directory name lookup cache can alleviate this problem; I think the DNLC in S5R4 will be used both with the V7 (System V) file system and the Berkeley (UFS) file system (which, in S5R4, should shrink directories as per 4.3BSD).