• Uncategorized

#### Question Detail

I have a program which calculates the “happy numbers” between an interval (definition). I have to write it in two ways, first one has to be sequential, second has to be parallel. The first program is done, and all I did was add an omp-specific line to the parallel version. The problem is, every time I run it it gives me this error: `*** glibc detected *** ./p: double free or corruption (fasttop):` and then prints the “backtrace” and the “memory map”. I think it has something to do with the malloc and realloc I called, but no idea what. Could you help me with this?

``````#include <stdio.h>
#include <omp.h>
#include <sys/time.h>
#include <math.h>

#define LLI long long int

int length(LLI n) {
int len = 0;
while (n != 0) {
n /= 10;
len++;
}
return len;
}

void breakdown(int *a, LLI n, int len) {
int i;
for (i = len - 1; i >= 0; i--) {
a[i] = n % 10;
n /= 10;
}
}

int calculate(int *a, int* len) {
int i, sum = 0;
for (i = 0; i < *len; i++) {
sum += pow(a[i], 2);
}
if (sum < 10) {
*len = 1;
} else {
*len = length(sum);
breakdown(a, sum, *len);
}
return sum;
}

int calculateHappy(int *a, int len) {
int sum;
do {
sum = calculate(a, &len);
} while (len != 1);
if (sum == 1) {
return 1;
}
return 0;
}

int main(int argc, const char* argv[]) {
if (argc != 4) {
printf("man no good bro i ned 3 parameter\np: interval left border\nq: interval right border\nthreadNr: think bro think what could it be\n");
exit(0);
}

LLI p, q, i, *result;
int *a, len, j, happyNr = 0, threadNr;
p = atoll(argv);
q = atoll(argv);
result = (LLI*) malloc (1 * sizeof(LLI));
if (p >= q) {
printf("man no good bro p < q man\n");
exit(0);
}
struct timeval start, stop;
gettimeofday(&start, NULL);
for (i = p; i < q; i++) {
len = length(i);
a = (int*) malloc (len * sizeof(int));
breakdown(a, i, len);
if (calculateHappy(a, len)) {
happyNr++;
result = (LLI*) realloc (result, happyNr * sizeof(LLI));
result[happyNr - 1] = i;
}
}
gettimeofday(&stop, NULL);

printf("The program took %d seconds/%d microseconds to run\n", stop.tv_sec - start.tv_sec, stop.tv_usec - start.tv_usec);
FILE *f = fopen("output.txt", "w");
if (happyNr != 0) {
fprintf(f, "The happy numbers are: \n");
for (i = 0; i < happyNr; i++) {
fprintf(f, "%lli ", result[i]);
}
fprintf(f,"\n");
} else {
fprintf(f, "In the interval [%lli, %lli] there are no happy numbers.\n", p, q);
}
free(result);
return 0;
}
``````

The command I ran the code with was `gcc main.c -o p -fopenmp` and then `./p 1 100 5`, but the error occurs at any number of threads (except 1 of course).

The problem is that you have data races using shared variables `len`,`a`, `happyNr` and array `result`. Variables `len` and `a` have to be defined as private, increase of `happyNr` and reallocation of `result` have to be protected. Just adding a few lines of OpenMP code your program will be OK (but not very fast, see comments below):

``````    #pragma omp parallel for default(none) private(i, len, a) num_threads(threadNr) shared (happyNr, result, p, q)
for (i = p; i < q; i++) {
len = length(i);
a = (int*) malloc (len * sizeof(int));
breakdown(a, i, len);
if (calculateHappy(a, len)) {
#pragma omp critical
{
happyNr++;
result = (LLI*) realloc (result, happyNr * sizeof(LLI));
result[happyNr - 1] = i;
}
}
free(a);
}
``````

Note that:

1. You have forgot to free `a`. Allocation and deallocation of memory is not a good idea inside a loop. You should rewrite it (e.g. just use `int a[(int) log10(LLONG_MAX)+1];`), if speed is a concern. (It may be your homework, so it is not important at all.)
2. Continuous reallocation of array `result` is very slow and requires the use of `critical` section (i.e. locks). It would be much better to allocate an array large enough to store all data, in this case you do not have to use `critical` section (atomic operation or reduction would be enough) and your program may run even faster.
3. Always define your variables in their minimum required scope. It is especially important in OpenMP code to avoid data race as variables defined inside a parallel region are private by default. On the other hand it also helps the compiler to make better optimizations.
4. Use `a[i]*a[i]` instead of `pow(a[i], 2)` as integer multiplication is much faster than floating point `pow` function.

Putting all together:

``````int calculate(int *a, int* len) {
...
sum += a[i]*a[i];
...
}

int main(int argc, const char* argv[]) {

const int max_a_size=(int) log10(LLONG_MAX)+1;
...
LLI* result = (LLI*) malloc ((q-p) * sizeof(LLI));
//check for memory allocation problems here

struct timeval start, stop;
gettimeofday(&start, NULL);
for (LLI i = p; i < q; i++) {
int len = length(i);
int a[max_a_size];
breakdown(a, i, len);
if (calculateHappy(a, len)) {
int old_happyNr;
#pragma omp atomic capture
old_happyNr=happyNr++;
result[old_happyNr] = i;
}
}
gettimeofday(&stop, NULL);

printf("The program took %f seconds to run on %d threads\n", stop.tv_sec- start.tv_sec+ (stop.tv_usec- start.tv_usec)/1000000.0, threadNr);
printf("There are %d happy numbers between %lld and %lld. \n", happyNr, p,q);

...
}
``````

It scales well with number of threads, on my laptop I got the following result:

``````g++-11 2.cpp -fopenmp -O3 -mavx2 -Wall && time ./a.out
The program took 1.254470 seconds to run on 8 threads
There are 14255378 happy numbers between 1 and 100000000.

real    0m1.260s
user    0m9.088s
sys     0m0.389s

The program took 7.132763 seconds to run on 1 threads
There are 14255378 happy numbers between 1 and 100000000.

real    0m7.138s
user    0m7.124s
sys     0m0.010s
``````

#### You may also like...

This site uses Akismet to reduce spam. Learn how your comment data is processed.