Optimization / using pointers to access arrays

Question

I have an exercise about optimization. I need to optimize a program which rotates and image by 45 degrees. I know accessing arrays using pointers is more efficient, so I tried the changes below- the original code:

RGB* nrgb = (RGB *)malloc(imgSizeXY*3);//3=sizeof(RGB)
//...
for (i=imgSizeY-1; i>=0; --i)
    {
        for (j=imgSizeX-1; j>=0; --j)
        {
                //...
                int y=(i*imgSizeX+j);
                nrgb[y].r = *imgInd; //*imgInd computed earlier

The changes:

    RGB* nrgb = (RGB *)malloc(imgSizeXY*3);//3=sizeof(RGB)
    RGB* rgbInd = nrgb+imgSizeXY-1;
    for (i=imgSizeY-1; i>=0; --i)
    {
        for (j=imgSizeX-1; j>=0; --j)
        {
              rgbInd->r=*imgInd;
              --rgbInd;

but when using pointers, the program produces an erroneous output. I have been staring at it for hours, and still have no idea why. Any ideas? Thank you very much!

Where is your reference for "Pointer syntax is faster than array syntax" — Karthik T
– Karthik T, Commented Jan 12, 2013 at 8:01
45 degrees arround which point? The center or some corner of the image? — Ivaylo Strandjev
– Ivaylo Strandjev, Commented Jan 12, 2013 at 8:02
@izomorphius The center. So the program originally shifted the coordinates, multiplied by rotation matrix and then shifted back. I have improved it to consist of a maximal computation outside of the loop and minimal computation within it, but still that is the general idea. If you have any tips on faster ways to do it, I will be glad to hear them. — Idan
– Idan, Commented Jan 12, 2013 at 8:08
@Idan so are you sure you are talking about 45, not 90 degrees? — Ivaylo Strandjev
– Ivaylo Strandjev, Commented Jan 12, 2013 at 8:09

Kotu · Accepted Answer · 2013-01-12 08:09:47Z

2

There is no difference between access array elements by pointer and access by index. You can see that if produce assembler code. Index notatiin more simple.

answered Jan 12, 2013 at 8:09

Kotu

1,1107 silver badges12 bronze badges

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

3 Comments

Idan Over a year ago

Sorry, but I've been taught differently... Notice we may be tested on old systems (if your argument relies on smart modern compilers). Also, notice that for the index notation, the computation y=(i*imgSizeX+j) should be held each time(!) while the pointer notation avoids that computation and surely saves time

Kotu Over a year ago

I mean you cannot increase speed by using pointer notation instead of indexes. But you have changed algorithm. You need debug your code.

Voo Over a year ago

@Idan Being "taught" something doesn't make it correct (and even if it was correct when taught, things change quickly). For optimization the best test is always to test the actual problem. This means look at the produced assembly, but basically the optimization you're doing manually is a really basic one that compilers can generally easily figure out themselves (strength reduction). Don't waste your time rewriting everything and probably introducing bugs before you're somewhat sure it actually will help.

Paul Hankin · Accepted Answer · 2013-01-12 10:22:19Z

0

An L1 cache hit is an order of magnitude faster than an L2 cache hit, which itself is an order of magnitude faster than a main memory access. See Numbers Every Computer Scientist Should Know. For image operations, you expect that you're going to have to do a lot of memory reads and writes, so you should expect to primarily be concerned with cache efficiency when optimising your code.

So concentrate on finding ways to use the caches more effectively, and don't worry too much that your compiler isn't optimising simple pointer arithmetic optimally.

answered Jan 12, 2013 at 10:22

Paul Hankin

58.8k11 gold badges99 silver badges125 bronze badges

Collectives™ on Stack Overflow

Optimization / using pointers to access arrays

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related