C: splitting a sum across threads without sharing
Give each thread its own range and result slot, then combine the results after joining.
On this page
C structs, pointers, and the pthread lesson.
- Give each thread its own range and result slot, then combine the results after joining.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
The simplest safe way to parallelize is to share nothing that changes. Each thread gets its own range of the input and its own output field in a struct. No thread writes to anything another thread reads, so no lock is needed. The main thread waits for all threads with pthread_join and then combines the partial results.
pthread_create passes one void pointer to the thread function, so the program passes a pointer to a struct that holds the range and the result. The structs live in an array in main, which outlives the threads. This pattern, partition, compute independently, and combine, is the basis of map-reduce and most parallel loops.
Code example
#include <pthread.h>
#include <stdio.h>
typedef struct {
int from;
int to;
long sum;
} Job;
static void *work(void *arg) {
Job *job = arg;
job->sum = 0;
for (int i = job->from; i <= job->to; i++) {
job->sum += i;
}
return NULL;
}
int main(void) {
Job jobs[4] = {{1, 250, 0}, {251, 500, 0}, {501, 750, 0}, {751, 1000, 0}};
pthread_t threads[4];
for (int t = 0; t < 4; t++) {
pthread_create(&threads[t], NULL, work, &jobs[t]);
}
long total = 0;
for (int t = 0; t < 4; t++) {
pthread_join(threads[t], NULL);
printf("part %d: %ld\n", t + 1, jobs[t].sum);
total += jobs[t].sum;
}
printf("total: %ld\n", total);
return 0;
}part 1: 31375 part 2: 93875 part 3: 156375 part 4: 218875 total: 500500
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
#include <pthread.h>#include <stdio.h> typedef struct { int from; int to; long sum;} Job; static void *work(void *arg) { Job *job = arg; job->sum = 0; for (int i = job->from; i <= job->to; i++) { job->sum += i; } return NULL;} int main(void) { Job jobs[4] = {{1, 250, 0}, {251, 500, 0}, {501, 750, 0}, {751, 1000, 0}}; pthread_t threads[4]; for (int t = 0; t < 4; t++) { pthread_create(&threads[t], NULL, work, &jobs[t]); } long total = 0; for (int t = 0; t < 4; t++) { pthread_join(threads[t], NULL); printf("part %d: %ld\n", t + 1, jobs[t].sum); total += jobs[t].sum; } printf("total: %ld\n", total); return 0;}Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Four disjoint ranges, each with its own result field. | — | — | |
| Each thread receives a pointer to its own job. Nothing is shared between threads. | 4 threads running | — | |
| Wait for the thread before reading its result. | 4 threads running | — | |
| The partial sums, for example 1..250 = 31375. | 4 threads running | part 1: 31375 part 2: 93875 part 3: 156375 part 4: 218875 | |
| The parts add up to n(n+1)/2 for n = 1000. | total = 500500 | part 1: 31375 part 2: 93875 part 3: 156375 part 4: 218875 total: 500500 |
Behind the scenes
How C processes this code
The C compiler produces a native program. Variables occupy memory, and execution enters main.
Cost and common mistakes
O(n) work in total; ideal elapsed time O(n / p) on p cores.
- If the jobs array were a local variable in a function that returns before the threads finish, the threads would use freed stack memory.
- Placing results in adjacent array elements can slow threads down through false sharing, since they write to the same cache line. Padding the struct avoids it.
- Starting a thread costs time. Tiny jobs run faster on one thread.
Try it yourself
Where would you add a lock if all threads added to one shared total?
Reveal answer and reasoning
Around the update of the shared total, or better, avoid the shared total as this program does.