Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I'm working on a system file scanner that reveals info about various files (e.g. size, last used, duplicates, etc). Currently I'm traversing the file system once just to get a good measure of the files I'll be processing, I then loop through doing the actual processing (size info, hash info, etc). Obviously that immediately creates an entire layer of "extra" processing, but it allows me to use the previously acquired info to provide the user with some "progress data".

I've been looking for a good mechanism to use in order to speed up the process while still showing progress data for end users. I thought about creating separate threads (one for appending files to a stack, and the other for reading from the stack as they became available), but that might get out of hand programmatically quickly.

In the interest of speeding up the initial scan, I currently perform a "find path" (or the equivalent depending on what OS is being used) and grab all of the output. This, however, prevents me from negating entire subfolders (if the user desires) as it simply recursively lists everything. Certain OSes do have command line options for negating directories, etc, but I need a cross-platform solution.

So, aaaaaaall that said, does anyone have any algorithmic suggestions for being speedy while providing quality progress? I'm not fundamentally tied to any specific language. I'm looking more for a higher level view of what needs to occur.

Best.

share|improve this question
    
Commenters: comments are meant for seeking clarification, not for extended discussion. If you have a solution, leave an answer. If your solution is already posted, please upvote it. If you'd like to discuss this question with others, please use chat. See the FAQ for more information. –  user8 Jun 14 '11 at 1:52
    
@Mark Trapp♦: So chat is the only way to get clarification on a complex and difficult-to-answer question? That seems to make an already complex problem even more complex. I apologize for trying to clarify and simplify. –  S.Lott Jun 15 '11 at 15:10
    
@S.Lott After 20+ comments, @humble_coder found nothing he wanted to add to his question when prompted. If a question isn't very useful even after a couple of comments asking for clarification, feel free to down-vote, edit, or vote to close; but extended discussion should be done in chat. –  user8 Jun 15 '11 at 15:24
    
@@Mark Trapp♦: It seems heavy-handed to edit or close, and ineffective to move to chat. But since the question hasn't been clarified, I'm clearly in the wrong. –  S.Lott Jun 20 '11 at 2:30
add comment

7 Answers

You've got an I/O-bound problem. That means you'll have to fit the computation to match the I/O. You're likely dealing with physical harddisks, which means that seeks are dominant. Therefore, "speedily" translates to "minimum number of seeks".

We can therefore list the following principles: 1. Scan entire directories (breadth first). Don't be tempted to enter subdirectories before you've scanned the parent directory; going back takes another seek. 2. Save all data you can possibly get from a directory. Having to go back takes another seek.

Now, some filesystems (eg NTFS) save small file content inside the directory entries. On such systems, you should hash those file contents immediately after you've scanned the directory. Otherwise, it really doesn't matter when you do. It may be wise to scan subdirectories first so you can report the running count of files found, and delay reading large files.

When you truely want to push high-performance, asynchronous I/O is the proper solution. This won't be needed on regular PCs, even an SSD isn't that fast, but high-end file servers can overload a single thread. In such systems, a solution such as Boost ASIO can scale. You'll just throw read requests to Boost ASIO, and it will return results some time later as they come in. Possibly on other threads, if needed. This gives the underlying O/S more flexibility to handle the read requests.

share|improve this answer
add comment

'If Mohammed won't come to the mountain, the mountain must come to Mohammed.'

You can't always make it fast. Sometimes You need to make it appear to be fast.

Fake progress bar speed. User wants to know something is happening, user wants fast feedback. There are some studies which show how to make progressbar appear more fluid and faster, but I dont remember the papers.

There is a study on how to make progressbar appear to go faster. Some other links to more research how to make make progress bar appear to be faster.

share|improve this answer
add comment

Not tied to a specific language? Erm. Most of what comes to mind is avoiding as much file-comparison work as possible (With a corresponding increase in data you keep in memory) rather than trying to optimize the traversals.

  1. Keep a data-structure/map that uses byte-counts as keys and a list of file identifiers as the payloads. Whenever you add a file to the data-structure, if it goes into a list and it has "neighbors" of the same file-size, you know you may need to compare it more deeply to those neighbors.
  2. Don't hash entire files unless you really need to. Instead, consider hashing sequential "chunks" of the file. Two files that are identical will require you to hash them both in their entirety, but two files that differ very early on will require less work. If you can, store these chunk-hashes in memory to make future checks faster.
  3. Don't go overboard on threads, just keep the file I/O stuff separate from your user-interface or main thread. Consider using a framework (in Java, that could be Executors) so that if you need to tune the number of threads you have doing tasks, you can.
  4. For a GUI program, consider the idea of telling users that duplication-checks on files have a "pending" status. This means you immediately show the user everything except duplication-checks, and just fill those in as time permits.
share|improve this answer
    
Nice. I'll touch on each line item: 1) I'm actually storing the data in an "in-memory" SQLite database. That aspect works really well -- especially for nifty comparisons after the fact. I don't want to make any assumptions during the data retrieval as I'll be performing different comparisons later (e.g. by hash, by name, by size, etc) 2) I do this already. I hash a few bytes from the beginning, the middle and the end. –  humble_coder Jun 7 '11 at 6:28
    
3) I totally agree, I just threw that out there as an "I'm not opposed to getting dirty if I have to" 4) Yeah, I'm just not a fan of the spinning cursor or barber pole indicators going on forever without some explicit feedback –  humble_coder Jun 7 '11 at 6:29
add comment

I may not understand what you are trying to do with the data but... Isn't this a map-reduce problem? For each folder, use the map function to pull the data you need from it (since you can distribute the number of directories to any number of threads/processes that can perform the mapping function, they can all run "in parallel" and as they report in, you get a set of progress indications. Then reduce the dataset to provide the specific info you want to give the user.

Also, do you understand where you are timebound for this problem? IF you do this function for an entire filesystem, you might not be able to read all the directory/file info from cache, so you may be limited to hard drive seek times to build your list. If you end up waiting for the drive, it might not make sense to optimize CPU/display usage.

share|improve this answer
add comment

As a general rule

Threads are probably going to slow your application down if they both are doing concurrent IO access to the same physical interface ( network or disk ).

Strategies

Map / Reduce can be applied for statistics and other things that fit into that model and can be updated incrementally as the files are processed.

Having an event driven system will allow for real time feedback to your user, but will not let them know percentage complete of the entire process, only of the current event. inotify is a good place to start if you are on Linux, other OS platforms have equivelent native APIs to do the same thing.

Caching the list of files, to get totals for progress on very large jobs will probably be a good thing, even if it adds to the overall time, the user will know how long to take a break while the job works.

A hybrid solution of caching some things and creating events to process in a map reduce manner will be the best middle ground you can expect, then responding to events that happen in real time using some platform specific notification mechanism will be your best solution.

Remember IO is limited by physics, threading will just increase contention for already stressed physical resources.

share|improve this answer
    
Multithreading on IO actions would be bad, but having one thread to handle IO and having it pass results to other threads for computation will not decrease performance. –  Daenyth Jul 15 '11 at 13:49
add comment

From just scanning your question I can only give some very general advice.

Multithreading will definitely help performance, depending upon how much processing that you are doing. Try to seperate I/O components from processing components in your software design and then you can write the first version synchronously, then go back later and modify the software to do these things in parallel.

Secondly, I know that using recursion to traverse a file system is tempting. You will see a performance improvement if you use loops instead of recursion, although how large of an improvement will depend upon the size of your input.

What you might consider is having one thread handle the I/O and pass off results to another thread for processing. That way your CPU is not waiting for slow I/O with the disk.

Also, if this system is going to have a user interface, you are most assuredly going to want to, at a minimum, place the UI on a seperate thread of execution. This will definitely increase performance, particularly considering the potentially long running and resource intensive operation you are going to have running in the background with all of the I/O and processing of the file metadata.

I would use one thread to continuosly loop through directories on the file system and read the metadata into a data structure that is thread safe. Then I would have another thread processing that data and extracting whatever information from it that you are wanting to provide to the user, and storing that information in another thread safe data structure. Finally, your UI should be on its own thread of execution and update itself anytime the data in the second thread safe data structure is modified.

Just a side note, the .NET Framework has a "FileSystemWatcher" class that will effectively handle everything but the UI for you. If you don't want to use .NET, you might at least consider reading up on the documentation for that class to give you a head start. Take a look at Mono for .NET if you are interested in cross-platform.

share|improve this answer
add comment

I wrote a library to do something similiar, but it's only really suited for filesystems that have many drive heads (like lustre or panfs). We gather information on hundreds of millions of files (about 20PB of data) on a regular basis. Take a look at the paper we wrote as well as the library to distribute the workload and tools to analyze the data.

If you have a smaller filesystem, CEA wrote a program called Robinhood to do something similiar.

share|improve this answer
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.