Can I execute two functions at the same time?

Question

I am new to programming. I know that a computer executes instructions in the order they are given.

I'm learning C and I wrote this:

#include <stdlib.h>
#include <stdio.h>

int comp(const char *a, const char *b) {
  return *a - *b;
}

int main() {
  char str[] = "Hello, world! I'm learning C and it's awesome!";
  qsort(str, sizeof(str) - 1, sizeof(char), comp); // -1 because of NUL-terminator.
  puts(str);
  return 0;
}

However, when I want to sort multiple very large arrays, this can take a while. My computer has multiple processing cores so I want to take advantage of that. Is that possible? Can code run in parallel and how would I do that?

^{_{P.S. I know I have to profile the code before optimizing it, but for now assume this is a very slow operation.}}

I guess that would be what you call threading. There's lots of threading libraries out there, though I don't know about pure C. I think on Unix you have fork() to create a child process which can run parallel to the main process. — LiMuBei, Nov 28 '11 at 17:35
@LiMuBei `fork` creates a child *process*. Does that mean that the processes don't share the same memory? — Dutchman, Nov 28 '11 at 17:37
This is interesting. I know you are learning C, but if you take a look at some assembly language you can, in fact, execute two or more instructions atomically at the same time. The Itanium processor is an example of a processor that can perform this. — Trevor Arjeski, Nov 28 '11 at 17:39
@LiMuBei: In C there's the [pthreads](http://en.wikipedia.org/wiki/POSIX_Threads) library. — Mike Bailey, Nov 28 '11 at 17:39
@user1069825: They don't. To share a memory segment between processes, you need to do that explicitly: http://www.cs.cf.ac.uk/Dave/C/node27.html — Amadan, Nov 28 '11 at 17:40

score 5 · Accepted Answer · answered Nov 28 '11 at 17:37

5

What you're looking for is called threading. There are a great many resources and tutorials out there on the Internet to get you started with parallelizing code.

answered Nov 28 '11 at 17:37

Adam Maras

26,269
6
65
91

Thanks. I looked at an example using pthread and simulated a lengthy operation using sleep(1) (I simulated it a few times). All operations ended after 1 second, so they were executed at the same time. – Dutchman Nov 28 '11 at 17:56

score 0 · Answer 2 · answered Nov 28 '11 at 17:38

0

You can start looking at threads, but it's considered an advanced topic. There is also libraries that help with making some things parallel, like OpenMP.

answered Nov 28 '11 at 17:38

Some programmer dude

400,186
35
402
621

1

Note that OpenMP does not make it any less advanced, it just makes the code shorter. – Dietrich Epp Nov 28 '11 at 17:39
OpenMP makes *some* tasks simpler. Others may be more complicated and may be more well expressed in a different threading library. – Mike Bailey Nov 28 '11 at 17:42

score 0 · Answer 3 · answered Nov 28 '11 at 17:42

Yes, code can run in parallel using multiple threads or multiple processes. Another form of parallelism is SIMD, where the same operation gets performed in parallel on multiple sets of operands.

Now, being able to run code in parallel doesn't automatically lead to being able to sort things in parallel. For this, you'll need a suitable algorithm. There exist a few parallel sorting algorithms, some of which are mentioned in the Wikipedia article on quicksort.

score 0 · Answer 4 · edited May 23 '17 at 10:08

Before resorting to parallelism, you should make sure your algorithm is as fast as possible, and that depends on exactly what you're sorting. For example, if you're sorting numbers that occupy a limited range, you might be able to use an O(N) sort. Otherwise, an O(NlogN) algorithm like MergeSort would work.

Suppose you chose MergeSort. Then, even though it's O(NlogN), it may still have room for a large constant factor of speedup, which you should do. Here's how I do it.

That done, suppose you have 4 cores. Then you could just split the dataset in 4 roughly equal segments and sort those in parallel, one per core. Then you can finish up with two O(N) passes to merge the results.

Can I execute two functions at the same time?

4 Answers4