2

This is my usecase:

Traverse a filesystem, gauge its entire size and then upload it to Dropbox.

Looks quite easy and is quite easy. Now if I do it using celery and spawn a thread for each folder(With sub files), then it becomes an easier process to gather all the data and gauge the size and then upload it to dropbox.

But I feel I'm doing something wrong here. If I implement this on a server, I'm surely overloading it by spawning a thread for each folder that is out there. Hence, what algorithms should I use to make this a faster process? Both as a data retrieval and data uploading. Links/References would help.

6
  • 1
    This really has nothing to do with algorithms... spawning a thread per folder is an approach/implementation, the algorithm you propose is a classical recursive DAG walk (probably a formal name for this I don't know) Commented Mar 2, 2013 at 2:33
  • @JimmyHoffa That's sort of what I thought and was rather cynical of myself whether to take any advice or not. My point being, I don't want to overload my server with a lot of threads. So was thinking what sort of algorithms ensure fast data retrieval from let's say 20 folders without actually spawning 20 threads of each of them.
    – IamH1kc
    Commented Mar 2, 2013 at 2:41
  • 1
    I really feel your question could be asked more clearly given what is actually you're problem. Your actual problem domain is about how to constrain parallelism resources, and two answers that immediately come to mind are Thread Pool and thread rotation ala node.js Commented Mar 2, 2013 at 2:46
  • 2
    I'm surely overloading it by spawning a thread for each folder that is out there. -- That is not at all self-evident, although it might matter how many cores you have on the server machine. I did write a Windows Service once that did something similar to this; I put all of the processing requests in a queue, and then spun up four threads (it was a quad-core machine) to process four requests at a time, until the queue was empty. Commented Mar 2, 2013 at 5:26
  • 5
    Why not simple single threaded code? Chances are that you're IO bound anyways, and HDDs don't like you reading data in several places at once. Commented Mar 2, 2013 at 9:10

1 Answer 1

6

The short version: absent unusual circumstances, you should use a single-threaded traversal. As @CodesInChaos says, your computer is likely to be I/O bound in both phases of your task: size-checking and uploading alike.


Trying to spawn a thread per directory is a recipe for fork-bombing your machine into oblivion. More precisely, there is no point in invoking more threads than are necessary to saturate your performance bottlenecks. Note that there are 2 likely bottlenecks: the performance of your filesystem, and the performance of your network link to Dropbox.

For uploading data to Dropbox, your network is almost certainly the bottleneck. You should easily be able to saturate any broadband link with a single-threaded traversal.

For finding the size of the filesystem, your bottleneck will also be I/O, but the details depend on the actual filesystem. For a solid-state drive, you probably won't benefit from more than a single thread. I suspect that you may gain a modest benefit from a bounded number of threads in a single-disk filesystem, as the OS can potentially schedule head stops a bit more efficiently if it has a queue. The question is, would a small performance margin be worth the cost of implementing and maintaining a more complex implementation? (E.g., handling cases like multiple hard links may be difficult enough with a single-threaded implementation...)

A distributed filesystem might benefit quite a lot from a multithreaded traversal. However, the details of how to extract the best performance are likely to depend on the specific system.

1
  • The operating system may schedule head stops a bit more efficiently, but it may also colossally screw up. Depends on the operating system.
    – Jan Hudec
    Commented Mar 5, 2013 at 13:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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