Take the 2-minute tour ×
Unix & Linux Stack Exchange is a question and answer site for users of Linux, FreeBSD and other Un*x-like operating systems.. It's 100% free, no registration required.

Faux pas: The "fast" method I mention below, is not 60 times faster than the slow one. It is 30 times faster. I'll blame the mistake on the hour (3AM is not my best time of day for clear thinking :)..

Update: I've added a summary of test times (below).
There seem to be two issues involved with the speed factor:

  • The choice of command used (Time comparisons shown below)
  • The nature of large numbers of files in a directory... It seems that "big is bad". Things get disoprportionately slower as the numbers increase..

All the tests have been done with 1 million files.
(real, user, and sys times are in the test scripts)
The test scripts can be found at paste.ubuntu.com

#
# 1 million files           
# ===============
#
#  |time   |new dir   |Files added in  ASCENDING order  
#  +----   +-------   +------------------------------------------------- 
#   real    01m 33s    Add files only (ASCENDING order) ...just for ref.
#   real    02m 04s    Add files, and make 'rm' source (ASCENDING order) 
#                      Add files, and make 'rm' source (DESCENDING order) 
#   real    00m 01s    Count of filenames
#   real    00m 01s    List of filenames, one per line
#   ----    -------    ------
#   real    01m 34s    'rm -rf dir'
#   real    01m 33s    'rm filename' via rm1000filesPerCall   (1000 files per 'rm' call)
#   real    01m 40s    'rm filename' via  ASCENDING algorithm (1000 files per 'rm' call)
#   real    01m 46s    'rm filename' via DESCENDING algorithm (1000 files per 'rm' call)
#   real    21m 14s    'rm -r dir'
#   real    21m 27s    'find  dir -name "hello*" -print0 | xargs -0 -n 1000 rm'
#   real    21m 56s    'find  dir -name "hello*" -delete'
#   real    23m 09s    'find  dir -name "hello*" -print0 | xargs -0 -P 0 rm'
#   real    39m 44s    'rm filename' (one file per rm call) ASCENDING
#   real    47m 26s    'rm filename' (one file per rm call) UNSORTED
#                                                       

I recently created and deleted 10 million empty test files. Deleting files on a name by name basis (ie rm filename), I found out the hard way that there is a huge time difference between 2 different methods...

Both methods use the exact same rm filename command.

Update: as it turns out, the commands were not exactly the same... One of them was sending 1000 filenames at a time to 'rm'... It was a shell brace-expansion issue where I thought each filename was being written to the feeder file on a line of its own, but actually it was 1000 per line

The filnames are provide via a 'feeder file' into a while read loop..
The feeder file is the output of ls -1 -f
The methods are identical in all reaspects, except for one thing:

  • the slow method uses the unsorted feeder file direct from ls -1 -f
  • the fast method uses a sorted version of that same unsorted file

I'm not sure whether the sorting is ths issue here, or is it perhaps that the sorted feeder file just happens to match the sequence in which the files were created (I used a simple ascending integer algorithm)

For 1 million files, the fast rm filename method is 60 times faster than the slow method... again, I don't know if this is a "sorting" issue, or a behind-the-scenes hash table issue... I suspect it is not a simple sorting issue, because why would ls -1 -f intentionally give me an unsort listing of a freshly added "sorted" sequence of filenames...

I'm just wondering what is going on here, so it doesn't take me days (yes days) to delete the next 10 million files :) .... I say "days" because I tried so many alternatives, and the times involved increase disproportionatly to the numberof file involved .. so I've only tested 1 million in detail

BTW: Deleting the files via the "sorted list" of names is actually faster than rm -rf by a factor of 2.
and: rm -r was 30 times slower than the "sorted list" method

... but is "sorted" the issue here? or is it more related to a hashing(or whatever) method of storage used by ext4?

The thing which quite puzzles me is that each call to rm filename is unrelated to the previous one .. (well, at least it is that way from the 'bash' perspective)

I'm using Ubuntu / bash / 'ext4' / SATA II drive.

share|improve this question
1  
You're doing it wrong! (tm) Ever heard of find -delete? –  alex Mar 21 '11 at 15:29
    
Your 2 tests start in unequal conditions (I don't pretend this is important indeed): one reads the filenames from a file, and the other reads the filenames from a file that has been created (sorted) immediately before the test. It might be that the file being cached in the 2nd case plays some (or maybe not, who knows). For the tests to be in more equal conditions, perhaps you should do a simple cat to a fresh file before the 1st test--in place of sort before the 2nd test. –  imz -- Ivan Zakharyaschev Mar 22 '11 at 19:16
    
And I recommend you to present your observations and your question in a more clear fashion. Please, one thing at a time: compare just 2 cases in one question, bring the two important cases to the forground, all other is just background information; please make this clear. Don't mix several observations in one posting, please. –  imz -- Ivan Zakharyaschev Mar 22 '11 at 19:22
    
Presenting system and user-space time from your might also be important for solving the puzzle, so please include them in your question. Which of them makes the big difference in your tests? –  imz -- Ivan Zakharyaschev Mar 22 '11 at 19:23
    
@imz System and user-space time are shown in the test scripts (as I have mentioned above) at paste.ubuntu.com/583908... Regarding limiting the number of test results, some people may find the full range of tests useful. –  Peter.O Mar 23 '11 at 2:06
show 6 more comments

2 Answers

up vote 1 down vote accepted

rm -r is expected to be slow as its recursive. A depth first traversal has to be made on the directory structure.

Now how did you create 10 million files ? did u use some script which loops on some order ? 1.txt,2.txt,3.txt... if yes then those files may too be allocated on same order in contigous blocks in hdd.so deleting on same order will be faster.

"ls -f" will enable -aU which lists in directory order which is again recursive.

share|improve this answer
1  
McAlot: I can't see how 'recursive' would matter in this case, as there are no sub-directories involved... Yes I did use "1.txt,2.txt,3.txt'. Perhaps there are several things interacting: eg, Why does it take only 1min 30s to create 1 million files, but it takes 7m 10s to create 2 million. and after deleting them, recreating the 1 million much takes longer (9m 30s) its weird; everything is running slowly all of a sudden. This has happend before too. I think(?) deleting the directory fixed it. Is there a file daemon involved (nautilus; locate) maybe? To be continued... –  Peter.O Mar 21 '11 at 19:22
    
In general, filesystems aren't optimized for dealing with large numbers of files in the same directory. I'm not familiar with ext4 specifically, but for other formats the directory entries were just marked as unused when files were deleted. That means they still must be skipped over when doing operations in the directory. That would explain the behavior that you are seeing. –  KeithB Mar 21 '11 at 20:22
1  
I deleted the 'now slower' directory, and used a different name for a new directory. The time to create 1 million files is now back down to 1m 33s (vs 9m 30s when the directory "contains" 2 million deleted files, the first million having the same name as the newly added 1 million) ... interesting, and it tallies with your "...just marked as unused" comment ... getting there; it's starting to make sense :) –  Peter.O Mar 22 '11 at 1:52
    
@fred.bear My bad, i really didn't know the actual hierarchy and my answer was guess. also your test actually stresses the metadata but not actual files as they are empty files. The best way to benchmark this kind of issue is to take files from /var or cache of web server. anyway your test too sounds intresting, can you try deleting with two listed methods in different directories..say like /sample1/1.txt,2.txt... and /sample2/1.txt,2.txt.. –  rajaganesh87 Mar 22 '11 at 17:07
    
@Mr.Confused.A.Lot... Thanks for you help. Your explanation helped me understand more about the filesystem and some of its mannerisms... I have now got a reasonable sense of what was causing the different speed issues... some were just choice of bash commands, and others were simply filesystem issues (I'm left with a new motto: "big is bad" for directories... (for some actions, at least)... –  Peter.O Mar 22 '11 at 18:20
add comment

You should optimize the filestructure. So instead of

for i in $(seq 1 1000); do touch file.$i; done

do something smarter like (bash assumed):

function bucklocate() 
{ 
    hash=$(echo -n "$1"|md5sum|cut -f1); 
    echo -n "${hash:1:1}/${hash:7:1}/${hash:9:2}/$1"; 
}

hexdig="{0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f}"
eval mkdir -p $hexdig/$hexdig/$hexdig$hexdig


for i in $(seq 1 1000); do touch $(bucklocate file.$i); done

Now this example is rather slow because of the use of md5sum[1], use something like the following for much faster response, as long as you don't need any particular filenames, duplicates are of no concern and there is no need for a repeatable hash of a certain name :)

mkdir -pv {0,1,2,3,4,5,6}/{0,1,2,3,4,5,6,7,8,9,10,12}
for  a in $(seq 1 100); do i=$RANDOM; echo touch "$(($i%7))/$(($i%13))/file.$i"; done

Of course this is all sloppily borrowing concepts from hashtables

share|improve this answer
    
I think that you are saying "use smaller directories" ... That's an intersting idea; a home grown DBMS which makes a tree from a 'tree-less' group of files". Some might call it forward planning :) ... If it works (and it probably does), then it is a good idea! :) ... I'm starting to get the idea that 'big is bad' wnen it comes to the number of files in a directory (for ext4 at least)... You have presented a preemptive workaround (+1) and I'm slowly getting an idea of why some deleting methods are faster than others in any given directory; small or large... Thanks –  Peter.O Mar 22 '11 at 1:45
    
Yup sorry for not being more explicit on the idea of keeping dirs small –  sehe Mar 23 '11 at 0:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.