How do i speedily traverse a file system while extracting/extrapolating various data and provide user feedback?

Question

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.

Answer 1

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.

Answer 2

'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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.