2
$\begingroup$

While creating an algorithm, the following question came up:

In uniform cost, what is the time cost of a process that creates a thread?

Is there a difference between creating a thread in a thread pool vs creating a thread in runtime?

I know these questions should be self-explanatory, but I cannot seem to find an answer.

$\endgroup$
  • $\begingroup$ In most theoretic models, there are no threads at all. Is there any reason to think that such creation is not $O(1)$ in both cases? Are you really asking, "which is faster"? $\endgroup$ – Raphael May 19 '14 at 18:38
2
$\begingroup$

The cost of thread creation is constant but large on most real systems. (Think approximately the same cost as doing 1000 function calls of a function that does nothing but return a small constant. On most systems it requires a call into the kernel, which is pretty expensive.)

The point of a thread pool is to try to amortize this large constant cost over multiple thread creation/destruction requests. A thread pool is an abstraction that caches threads that are currently not in use, thus can be allocated relatively quickly instead of going through the enormous cost of creating a new thread. A typical thread pool might work as follows:

  • starts out empty
  • if a request is made for a thread from the pool and the pool is currently empty, then create a new thread and return it to the requester.
  • if a request is made to "exit" a thread, then instead of really shutting the thread down you insert a pointer to the thread into the thread pool and put the thread to sleep.
  • if a request is made for a thread from the pool and the pool contains a sleeping thread, then wake the thread up, give it the requested work, and return the pointer to the thread to the requester.
$\endgroup$
2
$\begingroup$

Every model of computation has a supported list of instructions, each associated with its time complexity. Thread handling is not a basic instruction in any model I'm aware of, but probably for practitioners of parallel computation, it is. The time complexity really depends on your viewpoint. If you're interested in optimizing the inner working of the operating system, then thread creation is not a basic operation at all, and its cost is associated with the algorithms implementing it. If you're interested in parallel computation, then probably thread creation is a primitive operation of unit cost. It all depends on the context.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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