C++ code optimization

[Arta]

'int' is the data type (integer). The * before the identifier (i) indicates that you are creating a pointer to an int, rather than the int itself. 'new' is an operator which allocates memory - in simpler terms, it creates new variables. The second 'int' tells 'new' that you wish to allocate space for an integer variable. The square brackets denote the number of ints you wish to allocate.

This may seem confusing, but arrays and pointers are basically interchangeable in C/C++. An array is simply a pointer to the first item in the array, and square brackets (more formally, the subscript operator) can be used with array and pointer types.

So, all together, the line:

Code Select Expand


int *i = new int[number_of_ints_needed];


Means:

Create an identifier, i, which is a pointer to an integer. Allocate enough memory to store number_of_ints_needed integers and place the starting address for that block of memory in the pointer variable i.

[MyndFyre]

This may seem confusing, but arrays and pointers are basically interchangeable in C/C++. An array is simply a pointer to the first item in the array, and square brackets (more formally, the subscript operator) can be used with array and pointer types.

To explain why this is:

Let's say you declare an array of ints, 5 items long.  You could do either one of these statements:

Code Select Expand


int i[5] = new int[5];
// or
int *i = new int[5];

When you declare this array -- either way you do it -- you're telling the compiler to set aside some memory for your use.  So really, you're getting some memory.  Each "slot" in memory has a specific address.  The type int on 32-bit computers takes up 32 bits, or 4 bytes.  Arrays are stored contiguously -- which means that all of the items are right next to each other.  So, let's say that you get the address:
0x10048540
as the value of "i".  That is the address of the first item in your array.

How do you get at the second one?

Well, if you know that the first one takes up four bytes of space, and that the items in the array all line up right next to each other --

just add four to the original address!  0x10048544!

How does this apply?

As Arta said, pointers and arrays are generally interchangeable.  When you declare memory plainly using malloc(), these statements can still be equivalent:

Code Select Expand


int *i = new int[5]; // this is the second one from above)
int *i = malloc(5 * sizeof(int));

Note the sizeof operator, which determines the amount of memory a specific type takes up.  malloc() is used primarily in C, where the new operator is not available.  Generally, C++ users use new because it's more clear.

All told, these loops mean pretty much the same thing:

Code Select Expand


// loop A
int *i = new int[5];
for (int c = 0; c < 5; c++)
{
  *(i + c * sizeof(int)) = c;
  cout << "i[" << c << "] = " << *(i + c * sizeof(int)) << std::endl;
}
// loop B
int i[5] = new int[5];
for (int c = 0; c < 5; c++)
{
  i[c] = c;
  cout << "i[" << c << "] = " << i[c] << std::endl;
}
// loop C
int *i = new int[5];
for (int c = 0; c < 5; c++) // watch this loop, it is the coolest.
{
  *i = c; // dereference i, assign the c to the value pointed at
  cout << "i[" << c << "] = " << *i++ << std::endl; // after getting the value pointed to, increment the pointer
}

The first one is tough to grasp, but think about how it runs and how it applies to oddly-sized values such as structures and classes.  Note that the expression inside the parenthesis:
i + c * sizeof(int)
is the pointer that's being dereferenced.  Let's say i contains that value I gave you before, 0x10048540.  Run it through:

Code Select Expand

int *i = new int[5];
i = 0x10048540

Code Select Expand


for (int c = 0; c < 5; c++)
{
  *(i + c * sizeof(int)) = c;
  cout << "i[" << c << "] = " << *(i + c * sizeof(int)) << std::endl;
}

Iteration 1: c = 0.
(i + c * 4) = 0x10048540.  *(0x10048540) = 0, which is the value of c.
Iteration 2: c = 1.
(i + c * 4) = 0x10048544.  *(0x10048544) = 1, which is the value of c.
Iteration 3: c = 2.
(i + c * 4) = 0x10048548.  *(0x10048548) = 2, which is the value of c.
Iteration 4: c = 3.
(i + c * 4) = 0x1004854c.  *(0x1004854c) = 3, which is the value of c.
Iteration 5: c = 4.
(i + c * 4) = 0x10048550.  *(0x10048550) = 4, which is the value of c.

Loop B is pretty obvious -- but wait.  What about loop C?

Loop C changes the value of the pointer variable, which is fine if you're working with a local variable and you have a copy of the original pointer available.  If you overwrite the only copy of the pointer, though, how do you know where your array began?
Let's look at this code closely:

Code Select Expand


// the loop body.
  *i = c; // dereference i, assign the c to the value pointed at
  cout << "i[" << c << "] = " << *i++ << std::endl; // after getting the value pointed to, increment the pointer

The first time the loop runs, c will be 0, so we don't need to change where we're pointing to.  So, *i = c means, store the value of c in the location in memory where i points.  i points at 0x10048540, and 0 is being stored there.
The second line is an expression that prints to the console.  It works just like all the others, with this exception:

Code Select Expand

*i++
This code says, "Get the value that i is pointing to, and then increment i by the size of its type."

The C++ compiler is smart enough to remember what kind of variable i is -- remember, it's a pointer to an integer.  An integer is 4 bytes large.  When we say to increment a pointer, we want it to point to the next location in memory in which an integer is held, so the compiler does it automatically for us. 

Iteration 1: i = 0x10048540.  Iteration 2: i = 0x10048544.  Iteration 3: i = 0x10048548.  Etcetera.

Hope this wasn't too much for you at once!

[Kp]

To explain why this is:

Let's say you declare an array of ints, 5 items long.  You could do either one of these statements:

Code Select Expand


int i[5] = new int[5];
// or
int *i = new int[5];


Actually, no, you can't.   Observe:

Code Select Expand

/tmp> cat tst.cc
int* foo() {
        int i[5] = new int[5];
        return i;
}
/tmp> g++ -c tst.cc
g++ -c tst.cc
tst.cc: In function `int* foo()':
tst.cc:2: error: invalid initializer
Short explanation is that int i[5] = new int[5]; is nonsense and prohibited.  Also, a couple of other notes:

As Arta said, pointers and arrays are generally interchangeable.  When you declare memory plainly using malloc(), these statements can still be equivalent:

Code Select Expand


int *i = new int[5]; // this is the second one from above)
int *i = malloc(5 * sizeof(int));

Note the sizeof operator, which determines the amount of memory a specific type takes up.  malloc() is used primarily in C, where the new operator is not available.  Generally, C++ users use new because it's more clear.

malloc returns a void*, which can be implicitly cast to int* in C, but not in C++.  So, those statements are not equivalent since the second one won't compile without a cast.  Also, operator new implicitly calls an appropriate constructor, whereas malloc does not.  Thus, it's extremely ill-advised (though quite legal) to use malloc to allocate a non-POD type.  Come to think of it, that kind of wizardry is required if you want to allocate an array and use a non-default constructor.

All told, these loops mean pretty much the same thing:

Code Select Expand


// loop A
int *i = new int[5];
for (int c = 0; c < 5; c++)
{
  *(i + c * sizeof(int)) = c;
  cout << "i[" << c << "] = " << *(i + c * sizeof(int)) << std::endl;
}
// loop B
int i[5] = new int[5];
for (int c = 0; c < 5; c++)
{
  i[c] = c;
  cout << "i[" << c << "] = " << i[c] << std::endl;
}
// loop C
int *i = new int[5];
for (int c = 0; c < 5; c++) // watch this loop, it is the coolest.
{
  *i = c; // dereference i, assign the c to the value pointed at
  cout << "i[" << c << "] = " << *i++ << std::endl; // after getting the value pointed to, increment the pointer
}


Actually, only loop C will even work correctly.   Loop A falls prey to the very thing you're trying to show him: implicit pointer arithmetic.  'i' is of type 'int', so the compiler is automatically multiplying c by sizeof(int) (more correctly, by sizeof(*i), which happens to be sizeof(int)), so doing it explicitly means you multiply by 16 instead of 4.  Loop B won't compile due to the aforementioned illegality of assigning a new int[5] to an int[5].

[MyndFyre]

Appreciate the corrections Kp <3  I thought I might be thinking in C.

[Gnathonic]

After much tinkering, I finally got it. I didn't quite realize what one part of my problem was, but as for the other part, Thanks Arta. Although it took me awhile to get what you were talking about with the "i" thing, I hadn't heard anyone call vars / pointers an "identifier" before so I thought you were talking about something else. After that I got confused wondering how I would call upon an unlabeled array. So I went back to your code and just kind of stared at it trying to find any way to call the array. Then it hit me. "i" = "identifier", "identifier" = array name, this experiance = epiphany. Afterwords I kind of smacked my self up side the head while saying duh to myself. Of well, thanks anyways for your posts MyndFyre and Kp. They were both informative and humorous. Here's my code as it stands. If you can think of anything to speed it up it would be helpful, cause all the things I knew of I already added.

Code Select Expand


#include "filter.h"


int runProc(const FilterActivation *fa, const FilterFunctions *ff);

int RunProc(const FilterActivation *fa, const FilterFunctions *ff) {
    PixDim w, h;
    Pixel32 *src, *dst;
LONG DifAA, DifAB, DifBA;
static Pixel32 *Frame = new Pixel32[2*fa->src.h*fa->src.w];

DifAA = 0;
DifAB = 0;
DifBA = 0;

    src = (Pixel32 *)fa->src.data;
   

    h = fa->src.h;
    do {
        w = fa->src.w;

        do {
Frame[w+h*(fa->src.w)+fa->src.h*fa->src.w] = Frame[w+h*fa->src.w];
            Frame[w+h*fa->src.w] = *src++;
        } while(--w);

        src = (Pixel32 *)((char *)src + fa->src.modulo);
    } while(--h);

dst = (Pixel32 *)fa->dst.data;

h = fa->src.h;
    do {
        w = fa->src.w;

        do {
DifAA +=
(abs(((Frame[w+h*fa->src.w] & 0xFF0000)) - (Frame[w+h*fa->src.w+fa->src.w] & 0xFF0000)) >>16)+
(abs(((Frame[w+h*fa->src.w] & 0x00FF00)) - (Frame[w+h*fa->src.w+fa->src.w] & 0x00FF00)) >>8)+
abs(((Frame[w+h*fa->src.w] & 0x0000FF)) - (Frame[w+h*fa->src.w+fa->src.w] & 0x0000FF));
DifAB +=
(abs(((Frame[w+h*fa->src.w] & 0xFF0000)) - (Frame[w+h*fa->src.w+fa->src.h*fa->src.w+1] & 0xFF0000)) >>16) +
(abs(((Frame[w+h*fa->src.w] & 0x00FF00)) - (Frame[w+h*fa->src.w+fa->src.h*fa->src.w+1] & 0x00FF00)) >>8) +
abs(((Frame[w+h*fa->src.w] & 0x0000FF)) - (Frame[w+h*fa->src.w+fa->src.h*fa->src.w+1] & 0x0000FF));
DifBA +=
(abs(((Frame[w+h*fa->src.w+fa->src.h*fa->src.w] & 0xFF0000)) - (Frame[w+h*fa->src.w+fa->src.w] & 0xFF0000)) >>16)+
(abs(((Frame[w+h*fa->src.w+fa->src.h*fa->src.w] & 0x00FF00)) - (Frame[w+h*fa->src.w+fa->src.w] & 0x00FF00)) >>8) +
abs(((Frame[w+h*fa->src.w+fa->src.h*fa->src.w] & 0x0000FF)) - (Frame[w+h*fa->src.w+fa->src.w] & 0x0000FF));
} while(--w);
--h;
} while(--h);

if((DifAA<=DifAB) && (DifAA<=DifBA))
{
h = fa->src.h;
do {
w = fa->src.w;

        do {
        *dst++ = Frame[w+h*fa->src.w];
} while(--w);

        dst = (Pixel32 *)((char *)dst + fa->dst.modulo);
} while(--h);
}

else if((DifAB<DifAA) && (DifAB<DifBA))
{
h = fa->src.h;
do {
w = fa->src.w;

        do {
        *dst++ = Frame[w+h*fa->src.w];
} while(--w);

dst = (Pixel32 *)((char *)dst + fa->dst.modulo);
w = fa->src.w;
--h;

do {
        *dst++ = Frame[w+h*fa->src.w+fa->src.h*fa->src.w];
} while(--w);

        dst = (Pixel32 *)((char *)dst + fa->dst.modulo);


} while(--h);
}

else
{
h = fa->src.h;
do {
w = fa->src.w;

        do {
        *dst++ = Frame[w+h*fa->src.w+fa->src.h*fa->src.w];
} while(--w);

dst = (Pixel32 *)((char *)dst + fa->dst.modulo);
w = fa->src.w;
--h;

do {
        *dst++ = Frame[w+h*fa->src.w];
} while(--w);

        dst = (Pixel32 *)((char *)dst + fa->dst.modulo);


} while(--h);
}

    return 0;
}


[Kp]

Myndfyre:

Although it took me awhile to get what you were talking about with the "i" thing, I hadn't heard anyone call vars / pointers an "identifier" before so I thought you were talking about something else.

Well, strictly speaking an identifier is more general than a variable.  Consider the following:

Code Select Expand

void foo() {
    printf ("Foo!\n");
}foo is an identifier for the function defined, although foo is not a variable.  All pointers are variables (even when they're constant), but not all variables are pointers.

"i" = "identifier", "identifier" = array name

Just so you're clear on this point, "i" was an arbitrarily chosen name, and probably picked more out of convention than because he intended to talk about identifiers.  Historically, C people use i, j, k, l, etc. in order as loop control or otherwise short-lived simple purpose variables.  Of course, if your variable serves some purpose worth giving it another name (for example, your code uses 'w' as a copy of the width), that's quite ok too.

Your prototype is unnecessary, for two reasons.  First, you miscapitalized the name in the prototype.  In C, names are case sensitive, so prototyping runProc tells the compiler nothing about RunProc.  Second, you immediately thereafter define the function, and all modern compilers that I know of will use a definition as an implicit prototype if one has not been provided.

You declare Frame as a static Pixel32 pointer, but then initialize it with values that are retrieved from the function invocation.  That's dangerous, since if you call RunProc again with a larger set of parameters, Frame will not be reallocated to the new size.  If you can stand the performance hit of the memory allocations, I'd recommend making Frame a non-static variable.  If you do, don't forget to free it at the end.

I note that you're still not using my suggestion about caching inside the loops, and it's dependent on your compiler and optimization level whether the compiler will be bright enough to strength reduce your loops for you.  Aside from that and a few cases where you're doing a*b+c*b, which could be rewritten as (a+c)*b to reduce number of operations, the only other change I would suggest is positioning on the opening brace and doing an =% to fix your formatting.

[Adron]

All pointers are variables (even when they're constant), but not all variables are pointers.

*(char*)0x401000 = 0;
int i = 0;
1[(char*)&i] = 'a';

(char*)&i and 0x401000 aren't variables though? Pointers can also just be constant or non-constant expressions.

[Kp]

All pointers are variables (even when they're constant), but not all variables are pointers.

*(char*)0x401000 = 0;
int i = 0;
1[(char*)&i] = 'a';

(char*)&i and 0x401000 aren't variables though? Pointers can also just be constant or non-constant expressions.

Bleh, don't confuse him with complex constructs.  He wasn't even tracking our memory allocation code without deep explanation.

[Adron]

All pointers are variables (even when they're constant), but not all variables are pointers.

*(char*)0x401000 = 0;
int i = 0;
1[(char*)&i] = 'a';

(char*)&i and 0x401000 aren't variables though? Pointers can also just be constant or non-constant expressions.

Bleh, don't confuse him with complex constructs.  He wasn't even tracking our memory allocation code without deep explanation.

Yes, yes, just don't teach him broad generic statements such as "all pointers are variables" when there are actually pointers that aren't  

To him: Having an expression that is a pointer isn't that uncommon actually, my examples are just weird because I wanted to make them without declaring a lot of variables, structures, etc.

[Mephisto]

Well, strictly speaking an identifier is more general than a variable.  Consider the following:

Code Select Expand

void foo() {
    printf ("Foo!\n");
}foo is an identifier for the function defined, although foo is not a variable.  All pointers are variables (even when they're constant), but not all variables are pointers.

Isn't foo actually a variable being a pointer to the function? I'm under the impression that all function names are actually pointers, and from your example a pointer is a variable (in most cases).

[Gnathonic]

(uh conversation and lots of er whatever...)

I'll start from my last post.
Everything that I used in my code came from this example code in a small tutorial on the VDub filter system:

Code Select Expand


#include "filter.h"


int runProc(const FilterActivation *fa, const FilterFunctions *ff);

int RunProc(const FilterActivation *fa, const FilterFunctions *ff) {
    PixDim w, h;
    Pixel32 *src, *dst;

    src = (Pixel32 *)fa->src.data;
    dst = (Pixel32 *)fa->dst.data;

    h = fa->src.h;
do {
        w = fa->src.w;

        do {
            Pixel32 old_pixel, new_pixel;

            old_pixel = *src++;

            new_pixel = (old_pixel & 0xFF0000) + ((old_pixel & 0x00FEFE)>>1) + 0x008000;

            *dst++ = new_pixel;
        } while(--w);

        src = (Pixel32 *)((char *)src + fa->src.modulo);
        dst = (Pixel32 *)((char *)dst + fa->dst.modulo);
    } while(--h);

    return 0;
}
I simply thought the code had to be there, thanks for offering that bit of information, like everything else I will take that into note and take advantage of it later.
As far as the static declaration that won't be a problem. Everytime the resolution (or anything for that matter) is changed, VDub will unload and reload all the filters , and video resoltion can not change in mid-film so that's not a problem either, but thanks anyways, and sorry for not having explaned the VDub filter system in the slightest. Since I'm at it, the program has other code, but it's just VDub stuff, if you want I can post it but you probably won't find anything interesting in it. This code gets compiled as an dll, if that helps with anything.
I tried using your caching code stuff but found myself unable. Is there anything more then what you posted that you think I should know in order to be able to use it. Or this might work instead of explaning several functions to the point where any fool can grasp it just give me some exaple code that covers the following: caching a var to whatever you would call them (can you teach me the terminalogy here?), and then caching a different var to the same what ever you would call them (I need to learn the terms I feel dumb every time I say something like that.). Ok, the math simplafication thing doesn't go over too well on a sleep deprived brain, that's something I should have cought, thanks. When it comes to the formating, if that's the standard sure I'll change it, but I don't get what the "=%" is referencing to.

End of response to Kp's first message.

And as for the posts following that referenced to my level of understanding. You're right, but it's ok to not understand what's bad it to stay confused. We all have our low moments in everything, but we all learn and progress. One day I hope to be a help to those who need guidance, thanks for yours.

[Kp]

Unfortunately, there is no single standard on formatting.  However, I don't think you're following any of them atm.   =% would normalize your formatting if you were using Vim as your editor.

[Gnathonic]

Unfortunately, there is no single standard on formatting.

But there are some more commonly accepted bits of formating that are done, or am I wrong on this part also.

However, I don't think you're following any of them atm.

On the last post I made of code I learned it from, or the one before. On the on before when I copied it across it dropped some of the spacing, tabing, indenting, or whatever you want to call it. But on the code I learned it from it copied right. I would have edited the other one but couldn't see the indenting correctly when I went to edit the post.

  =% would normalize your formatting if you were using Vim as your editor.

Nope, I'm not using Vim, just Microsoft's VC++...
Can that use it and if so, how would one use it?

[Arta]

Isn't foo actually a variable being a pointer to the function? I'm under the impression that all function names are actually pointers, and from your example a pointer is a variable (in most cases).

It's certainly not a variable - it's a function identifier - but I suppose it could be considered a const pointer to the function. It can certainly be used that way.

I'm not sure of the internal construction of this though: can someone clarify? Anyone got the grammar handy?

[gameschild]

just reading through and not sure but:
FARPROC funcPtr = (FARPROC)functionName;
should give you a pointer to that function so i think in a way the function name is a pointer