0

I am trying to optimize code to run in under 7 seconds. I had it down to 8, and now I am trying to use pointers to speed up the code. But gcc gives an error when I try to compile:

.c:29: warning: assignment from incompatible pointer type .c:29: warning: comparison of distinct pointer types lacks a cast

Here is what I had before trying to use pointers:

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

#define N_TIMES     600000
#define ARRAY_SIZE   10000

int main (void)
{
    double  *array = calloc(ARRAY_SIZE, sizeof(double));
    double  sum = 0;
    int     i;

    double sum1 = 0;

    for (i = 0; i < N_TIMES; i++) {

        int     j;

        for (j = 0; j < ARRAY_SIZE; j += 20) {
            sum += array[j] + array[j+1] + array[j+2] + array[j+3] + array[j+4] + array[j+5] + array[j+6] + array[j+7] + array[j+8] + array[j+9];
            sum1 += array[j+10] + array[j+11] + array[j+12] + array[j+13] + array[j+14] + array[j+15] + array[j+16] + array[j+17] + array[j+18] + array[j+19];
            }

        }

    sum += sum1;

    return 0;
}

Here is what I have when I use pointers (this code generates the error):

int     *j;

        for (j = array; j < &array[ARRAY_SIZE]; j += 20) {
            sum += *j + *(j+1) + *(j+2) + *(j+3) + *(j+4) + *(j+5) + *(j+6) + *(j+7) + *(j+8) + *(j+9);
            sum1 += *(j+10) + *(j+11) + *(j+12) + *(j+13) + *(j+14) + *(j+15) + *(j+16) + *(j+17) + *(j+18) + *(j+19);
            }

How do I fix this error? Btw I don't want suggestions on alternative ways to try to optimize the code. This is a homework problem that has constraints about what I'm allowed to do. I think once I get this pointer thing fixed it will run under 7 seconds and i'll be good to go.

Improve this question
2

4 Answers 4

Reset to default
2

comparison of distinct pointer types lacks a cast

This means that you tried to compare a pointer of one type to a pointer of another type, and did so without a cast.

double  *array = calloc(ARRAY_SIZE, sizeof(double));
int     *j;

Pointers to double and pointers to int are not directly comparable. You aren't allowed to compare j to array for this reason. Perhaps you meant to declare j as a pointer to double ?

Improve this answer
Sign up to request clarification or add additional context in comments.

13 Comments

But aren't I comparing an int pointer to an address which is also an int?
@chillpenguin: Pointers are usually implemented as addresses. Pointers are not, conceptually, addresses. Consider a pointer to int "x" -- the expression ++x must increment the "address value" x by sizeof(int), not 1 (assuming address are being used to implement pointers).
if i made j a double pointer would that work right? Or do I have to cast things?
@chillpenguin: The most common machines which may not implement pointers as memory addresses are those machines which use segmentation. en.wikipedia.org/wiki/Memory_segmentation
@chillpenguin: If you intend to read doubles from j, then j does indeed need to be a pointer to double. As implemented now, assuming int is 32 bits and double is 64 bits (typical), you're not adding doubles. :)
|
0

C is a statically typed language, and comparisons across pointer types will give you errors. There is some implicit casting in certain cases, like if you compare a double to an int, because comparing numbers is a common operation. Comparing pointers of different types isn't.

Further, when you increment a pointer over an array, it uses the size of it's dereferenced element to know how far in memory to move. Moving with an int over an array of doubles will lead to issues.

A double will move farther then an int, so you will get more interations with an int pointer anyway.

You could explicitly cast things, but really you should be using a double * for an array of doubles.

Improve this answer

2 Comments

There is no such thing as "implicit casting." A cast is a request to the compiler to either ignore something in the type system, or to generate code to perform a conversion. Perhaps you meant to refer to the "usual arithmetic conversions" (C11 6.3.1.8)?
You are correct. My teacher and book called these implicit casts, but that is not how they are described in the C standard. Would you mind if I edited my comment to more accurately reflect this?
0

I'd be greatly surprised if moving from an array representation to a pointer representation would yield much (if any) speedup, as both are memory addresses (and memory offsets) in the final outputted code. Remember, the array representation is actually a pointer representation in different clothing too.

Instead, I'd look towards one of two techniques:

  1. Embedded MMX representations, to do multiple addition operations within the same register, under the same clock cycle. Then, you need one operation near the end to combine the high double with the low double.

  2. Scatter / Gather algorithims to spread the addition operation across multiple cores (nearly every CPU these days has 4 cores available, if not 16 pseudo-cores (a la hyper-threading))

Beyond that, you can do a few attempts at cache analysis, and at storing intermediates in different registers. There seems to be a deep chain of additions in each of your computations. Breaking them up might yield the ability to spread the on-cpu storage across more registers.

Most operations become memory bound. 20 is a really strange boundary for loop unrolling. Doubles probably are 16 bits, so 20 doubles is 320 bits, which is probably not aligned to your memory cache line size. Try making sure that multiples of your unrolled loop align cleanly with your architecture's level 1 cache, and you might avoid a page fault as you read across cache boundaries. Doing so will speed up your program by some (but who knows how much).

Improve this answer

5 Comments

In C, int[] and int* are distinct types. Arrays are not pointers, even if they decay into pointers when passed to functions. Most importantly for this code, an optimizer can make assumptions about an array which it cannot make about pointers.
I agree, the compiler might have a better time with the array, due to the extra hints the array allows in the C type system. The C type system doesn't survive the translation to assembly / machine code (too bad). From my assembly days, it would be quite a shock to discover that array offsets are implemented in any other form than address + offset, which is what the pointer math does, but without the extra guarantees that arrays make.
I fixed the error and it now compiles just fine. It DOES run faster using pointers btw. It is down to 5.8 seconds from 8 seconds.
Well, the proof is in the testing (when it comes to optimization). Thank you for the update, and I'll take my lumps as being completely wrong in my assumptions. Profiling is funny that way. Glad to hear of your success.
I learned about using pointers to step through an array in class but I don't remember why it is faster... I just remember my instructor said you will need to use it on this assignment to break 7 seconds. Like you said though, the proof is in the testing!
0

" When you increment a pointer over an array, it uses the size of it's dereferenced element to know how far in memory to move. Moving with an int over an array of doubles will lead to issues ".

To avoid your warn: do the below one

for (j= (int *)array; j < (int *)&array[ARRAY_SIZE]; j += 20)
Improve this answer

2 Comments

Instead I just made j a double. That works just as well right?
@chillpenguin, correct, because both variables have the same data type, thus no conversion is necessary. Good call!

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.