I needed to be able to remove a sprite from the List as it was looping through. I found you couldn't do this with a foreach as it would lose the index. So I found this method after a search.

 Are there any long term implications of using this method such as efficiency etc?
 

            for (int i = items.Count - 1; i >= 0; --i)
            {
                p = (Sprite)items[i];

                p.Update(gameTime);
                p.velocity += constantForce;            // add any constant force
                p.velocity /= inertia;

                EdgeCheck(p);

                if (!p.active)
                {
                    items.RemoveAt(i);
                }
            }

no thats fine, any particular reason your looping backwards?

I would use a foreach loop but that is a preference question.

I you want to remove something without the index just use items.Remove(p);
 

I'm looping backwards becuase that's how the example did it :)

 erm I just tried this method again

             foreach (Sprite s in items)
            {
                s.Update(gameTime);
                s.velocity += constantForce;            // add any constant force
                s.velocity /= inertia;

                EdgeCheck(s);

                if (!s.active)
                {
                    items.Remove(s);
                }
            }

 

and now it compiles ok.

I'm confused now as before it gave an error along the lines of the index being lost if I removed an object while looping through the collection. Or will it do this when I run it? (can't run it at the moment due to this pc's video card being rubbish).

 

 

"The foreach statement repeats a group of embedded statements for each element in an array or an object collection. The foreach statement is used to iterate through the collection to get the desired information, but should not be used to change the contents of the collection to avoid unpredictable side effects." Quote from MSDN

I wouldn't use a for each for this sort of function it has the potential to go wrong. also there has been comentes on the effect it has on speed although im not sure on this and wouldnt really worry about it atm. If you understand the for loop and can read it nice and esily i would use that its safer.

as for going forward or backwards, theres no difference technicaly however i do find its easier to deal with if all my loops go in teh same direction unless there is a need for doing them in reverse, its' easier to get your head round when they all iterate from 0 up.

if you want to do a for loop going forward it would be like this:

 for (int i = 0; i <  items.Count ; ++i) // i find its a bit tidyer aswell, i starts as 0 it will increase whilst i is less than the count

 {
}

Well it looks like it's looping backwards so that if an element gets removed while looping, you'll still get the indexes right. If you were to loop foward and remove an element, you would also have to decrement your loop counter.

that is very true zeppadoodle thx 4 pointing that one out

--i is a pre decrement meaning i is decremented before the end of the loop and as you are already subtracting 1 form the list size when you set i you might end up making i negative. if you are not sure put a break point in your code by clicking the line number and step through the code.

 hope that helps

I apologize for going off-topic, but Phantom, that XNA Resource Dev Card thing is a huge eye-sore. Could you please take that thing off your sig? I'm much more intent on reading people's posts, than having to scroll down and look at that thing. What seperates it from a regular Gamercard, is that it's on the left-hand side, meaning you don't have to scroll past it, or whatever. But those Dev Cards are extremely obstificating :(

I even disabled Signatures because I'm so sick of seeing those :\

Personally, I think they're just waaaay too big. I mean, they're bigger than the XBL gamercards. It'd be nice if there was a way that Dev Card could be stretched horizontally. Because, right now, those things are just too bloody damn big.

Sorry bout' that :\

JUst one simple general programming tip if you are looking for good performances: just try to avoid as many times as possible to use division. The main reason is that procs actually don't know how to divide: they multyply using a float (i.e. : 1/2 = 1 * 0.5).

By avoiding divisions, especially in repetitive code, you optimize it. Some compilers do translate the division into a multiplication but when you are using a variable like you do, the compiler just can't predict it.

 My 2 cents

Well...  also keep in mind that if you're going to multiply (or divide) by a power of 2, or a number that's made up of fewer than about three powers of 2 (adding or subtracting), it's even faster to just make it a bitshift or the sum of some bitshifts.

 Beyond three powers of 2, it's going to be hard to read and will probably not cause much if any improvement in speed (i.e., one multiply is roughly as fast as three shifts and two adds/subtracts - the difference used to be quite a bit more back in The Old Days of 8086 programming :-D)
 

There is another way to loop through a generic List...

 items.ForEach(delegate(Sprite p)
{
    p.Update(gameTime);
    p.velocity += constantForce;
    p.velocity /= inertia;

    EdgeCheck(p);

    if (!p.Active)
        items.Remove(p);
});

I'm not entirely sure if that's any faster than a standard for loop though... try it out! :)

Phantom PF:

no thats fine, any particular reason your looping backwards?

It's so the function remains linear instead of quadratic.

By looping backwards, the function is O(n) instead of O(n^2). I know he just copied it from a sample, but that's the reason the sample does it.

The list is implemented internally by an array, so removing an item from an arbitrary location is an O(n) operation because it requires shifting all remaining items forward in the array to fill the space. The worst-case performance occurs when removing the first element, because every remaining element has to be shifted. The best-case performance occurs when removing the last element, because it takes constant time.

For small arrays, you'll never notice the difference. However, for large arrays, this can be quite a bit faster.

--Stephen

CrazedTurnip:

--i is a pre decrement meaning i is decremented before the end of the loop and as you are already subtracting 1 form the list size when you set i you might end up making i negative. if you are not sure put a break point in your code by clicking the line number and step through the code.

 hope that helps

Post-decrement vs pre-decrement of the iterator in a for-loop makes no difference to the comparison because the comparison is done at the top of the loop after the iterator has been adjusted.

fair 'nuff.

This is getting a bit off-topic but...

Technically, prefix notation (++i or --i) is slightly more efficient than postfix notation (i++ or i--). Basically, postfix notation requires at least one more stack operation than prefix (see http://www.thunderguy.com/semicolon/2002/08/13/prefer-prefix-operators-over-postfix/ for more info). For small loops this will hardly make any difference. But for large loops -- perhaps one million or more iterations -- prefix versus postfix can make a noticeable difference.

iq01:

This is getting a bit off-topic but...

Technically, prefix notation (++i or --i) is slightly more efficient than postfix notation (i++ or i--). Basically, postfix notation requires at least one more stack operation than prefix (see http://www.thunderguy.com/semicolon/2002/08/13/prefer-prefix-operators-over-postfix/ for more info). For small loops this will hardly make any difference. But for large loops -- perhaps one million or more iterations -- prefix versus postfix can make a noticeable difference.

Agreed, getting a bit off topic but that's not true for C#. In C# prefix or postfix only makes a difference if there is an assignment.

j  = i++;

is obviously different to

j = ++i;

but if there is no assignment, such as in a for loop, then the compiler will produce identical IL for both prefix and postfix.

Cheers,
Leaf.

JunkMailer:

Agreed, getting a bit off topic but that's not true for C#.

Continuing off-topic...

This isn't even true for C or C++, at least not for any remotely competent optimizing compiler.

This is in fact a great example of why you need to be careful when recommending specific micro-optimizations. This advice may have been true at one time for one compiler, but it should always be qualified with that information. It might be accurate to say "When using the 1997 version of FooBar C++ compiler on x86, preincrement generated code that used three less clock cycles than postincrement". But it is very dangerous to generalize that advice and assume it will always remain true for other compilers, languages, and platforms!

I suppose it all comes down to programming technique.  Some techniques may be more efficient than others.  For some reason I'm not particularly a fan of 'for' loops.  I'm not entirely sure why.  My technique is similar to the following:

                int iAccum = 0;
                while (iAccum < iTotalSpaceObjects)
                {
                    SpaceObjectList[iAccum] = EnemySpaceObject;

                    float fRandScnPosX = ((float)randNum.Next(-500, 500));                  
                    float fRandScnPosY = ((float)randNum.Next(-500, 500));
                    SpaceObjectList[iAccum].vPosition.X = fRandScnPosX;
                    SpaceObjectList[iAccum].vPosition.Y = fRandScnPosY;
                   
                    iAccum++;
                }

I think 'for' loops are supposed to be more efficient as far as processing is concerned but for me this is easier to read.

Lemunde:

I suppose it all comes down to programming technique.
...
but for me this is easier to read.

Programming style is incredibly subjective, and everyone has different ideas about what is most beautiful and readable.

One thing I have really come to appreciate over the years is the importance of idiom. In any language or group of programmers, there will be certain common styles that everybody uses. For instance if I wrote this in C#, this would be an idiomatic way to iterate over an array:

    foreach (int value in array)
    {
       ...
    }

In K&R C, this is an idiomatic way to iterate over a linked list:

    for (item = list->head; item; item = item->next) {
       ...
    }

Both languages offer many different ways to do these same things, but those patterns are so common that any experienced programmer will instantly recognise them and understand what they are doing. Note also that idiom is about more than just the keywords and constructs you choose: this also affects your choice of variable names and code layout. For instance if I was to rewrite the linked list example in Win32 C, as opposed to K&R C, it would look like this:

    for (item = list->pHead; item != NULL; item = item->pNext)
    {
       ...
    }

Basically the same, but my "head" and "next" fields have a different name, and I put my opening curly brace in a different place.

So why does idiom matter?

When I first started programming, I didn't think it did. I knew what I liked, and I didn't particularly care if anyone else disagreed with me: I was happy just to do things in whatever way made most sense to me.

Over the years, though, I learned that the vast majority of programming is done as part of a team. Writing new code is actually a fairly small part of how most professional programmers spend their days. Far more time goes into reading code written by other people, sometimes to learn how it works so you can call it from your own code, other times because you need to make some change in it or fix a bug.

If everybody on a team uses a different set of idioms, this makes it unneccessarily hard to read each other's code. Whenever you have to open up a source file written by someone else, that feels like going into a strange foreign territory where nothing quite makes sense and you don't really feel comfortable until you get back into your own nice familiar safe source code. Not fun, and it is amazing just how much this can slow down the development process!

Once I figured this out, I decided it was important for everyone working on a shared codebase to use the same set of idioms, so their code will all look the same and anyone will easily be able to read and modify it.

This requires some flexibility. For instance the common idioms in my old job at Climax were totally different to the idioms used here on the XNA team. Some of that is due to the move from C++ to C#, but most of it is just a cultural thing. I had to totally alter my personal style and learn to write code in a radically different way when I moved jobs.

These days, whenever I learn a new language or start working in a new environment, I look around to see what style people are commonly using, and try to fit in with that as best I can. This isn't always easy, especially if I personally might not like every aspect of that style, but I figure the most important thing is to be consistent and make sure my code will be easily readable by everyone around me.

Shawn Hargreaves:

JunkMailer:

Agreed, getting a bit off topic but that's not true for C#.

Continuing off-topic...

This isn't even true for C or C++, at least not for any remotely competent optimizing compiler.

Actually, that shouldn't be accurate.  In C++, a postincrement->preincrement optimization, on classes that have operator-overloaded postincrement and preincrement methods, isn't easy for a compiler to do; the postincrement operator results in secondary methods being invoked that can have side-effects.

That's why programmers are advocated to prefer preincrement in their code.

lord pi:

Actually, that shouldn't be accurate.  In C++, a postincrement->preincrement optimization, on classes that have operator-overloaded postincrement and preincrement methods, isn't easy for a compiler to do; the postincrement operator results in secondary methods being invoked that can have side-effects.

That's why programmers are advocated to prefer preincrement in their code.

When dealing with performance, guesswork is no substitute for measurement.

Shall we measure this?

I wrote this test app:

    #include "list"

    using namespace std;

    int SumPreIncrement(const list<int> &data)
    {
        int sum = 0;
    
        for (list<int>::const_iterator it = data.begin(); it != data.end(); ++it)
            sum += *it;
        
        return sum;
    }

    int SumPostIncrement(const list<int> &data)
    {
        int sum = 0;
    
        for (list<int>::const_iterator it = data.begin(); it != data.end(); it++)
            sum += *it;
        
        return sum;
    }

I compiled it using:

    cl /Ox /EHsc /c test.cpp

And disassembled the result using:

    dumpbin /disasm test.obj > test.asm

Here are the results:

?SumPreIncrement@@YAHABV?$list@HV?$allocator@H@std@@@std@@@Z (int __cdecl SumPreIncrement(class std::list<int,class std::allocator<int> > const &)):
  00000000: 53                 push        ebx
  00000001: 56                 push        esi
  00000002: 57                 push        edi
  00000003: 8B 7C 24 10        mov         edi,dword ptr [esp+10h]
  00000007: 8B 47 04           mov         eax,dword ptr [edi+4]
  0000000A: 8B 30              mov         esi,dword ptr [eax]
  0000000C: 33 DB              xor         ebx,ebx
  0000000E: 8B FF              mov         edi,edi
  00000010: 3B 77 04           cmp         esi,dword ptr [edi+4]
  00000013: 74 11              je          00000026
  00000015: 03 5E 08           add         ebx,dword ptr [esi+8]
  00000018: 3B 77 04           cmp         esi,dword ptr [edi+4]
  0000001B: 75 05              jne         00000022
  0000001D: E8 00 00 00 00     call        __invalid_parameter_noinfo
  00000022: 8B 36              mov         esi,dword ptr [esi]
  00000024: EB EA              jmp         00000010
  00000026: 5F                 pop         edi
  00000027: 5E                 pop         esi
  00000028: 8B C3              mov         eax,ebx
  0000002A: 5B                 pop         ebx
  0000002B: C3                 ret
  0000002C: CC                 int         3
  0000002D: CC                 int         3
  0000002E: CC                 int         3
  0000002F: CC                 int         3
?SumPostIncrement@@YAHABV?$list@HV?$allocator@H@std@@@std@@@Z (int __cdecl SumPostIncrement(class std::list<int,class std::allocator<int> > const &)):
  00000030: 53                 push        ebx
  00000031: 56                 push        esi
  00000032: 57                 push        edi
  00000033: 8B 7C 24 10        mov         edi,dword ptr [esp+10h]
  00000037: 8B 47 04           mov         eax,dword ptr [edi+4]
  0000003A: 8B 30              mov         esi,dword ptr [eax]
  0000003C: 33 DB              xor         ebx,ebx
  0000003E: 8B FF              mov         edi,edi
  00000040: 3B 77 04           cmp         esi,dword ptr [edi+4]
  00000043: 74 11              je          00000056
  00000045: 03 5E 08           add         ebx,dword ptr [esi+8]
  00000048: 3B 77 04           cmp         esi,dword ptr [edi+4]
  0000004B: 75 05              jne         00000052
  0000004D: E8 00 00 00 00     call        __invalid_parameter_noinfo
  00000052: 8B 36              mov         esi,dword ptr [esi]
  00000054: EB EA              jmp         00000040
  00000056: 5F                 pop         edi
  00000057: 5E                 pop         esi
  00000058: 8B C3              mov         eax,ebx
  0000005A: 5B                 pop         ebx
  0000005B: C3                 ret

Not only do the two versions take the same number of instructions, but they actually generated the exact same sequence of instructions!

Moral: be very very careful when you assume performance advice from some number of years ago will still be true today. Compilers are smart, and they get smarter all the time. Be suspicious of anything you haven't measured yourself on your particular platform using the latest version of your development tools.

I'd like to phrase the famous quotation, "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil."

I'm sure that the discussion wether you should always try to use ++i instead of i++ can be dropped :-)

I believe that no consideration should be made with regards to optimizing code other than generally known best practices. Then your application could be profiled and refitted in order to solve bottlenecks.

I was once asked if I knew anything about optimization in a job interview, and I answered that if the specified requirements have not even been met in an application then it's unnecessary to start thinking about optimizing it, because the application is not even functionable!

I could sum my views up in the following phrase, that code readability is prio A, and should never be sacrificed for code optimization.

A friend of mine works at a international consulting firm who uses extreme programming as their main choice of project workflow.

They are actually not allowed to make comments in their code(!), meaning that if your code needs comments then it's not readable enough. I back up those views 100% and take great benefit from applying that practice.

Bjorn Goransson

Shawn Hargreaves:

lord pi:

Actually, that shouldn't be accurate.  In C++, a postincrement->preincrement optimization, on classes that have operator-overloaded postincrement and preincrement methods, isn't easy for a compiler to do; the postincrement operator results in secondary methods being invoked that can have side-effects.

That's why programmers are advocated to prefer preincrement in their code.

When dealing with performance, guesswork is no substitute for measurement.

Shall we measure this?

I wrote this test app:

    #include "list"

    using namespace std;

    int SumPreIncrement(const list<int> &data)
    {
        int sum = 0;
    
        for (list<int>::const_iterator it = data.begin(); it != data.end(); ++it)
            sum += *it;
        
        return sum;
    }

    int SumPostIncrement(const list<int> &data)
    {
        int sum = 0;
    
        for (list<int>::const_iterator it = data.begin(); it != data.end(); it++)
            sum += *it;
        
        return sum;
    }

I compiled it using:

    cl /Ox /EHsc /c test.cpp

And disassembled the result using:

    dumpbin /disasm test.obj > test.asm

Here are the results:

?SumPreIncrement@@YAHABV?$list@HV?$allocator@H@std@@@std@@@Z (int __cdecl SumPreIncrement(class std::list<int,class std::allocator<int> > const &)):
  00000000: 53                 push        ebx
  00000001: 56                 push        esi
  00000002: 57                 push        edi
  00000003: 8B 7C 24 10        mov         edi,dword ptr [esp+10h]
  00000007: 8B 47 04           mov         eax,dword ptr [edi+4]
  0000000A: 8B 30              mov         esi,dword ptr [eax]
  0000000C: 33 DB              xor         ebx,ebx
  0000000E: 8B FF              mov         edi,edi
  00000010: 3B 77 04           cmp         esi,dword ptr [edi+4]
  00000013: 74 11              je          00000026
  00000015: 03 5E 08           add         ebx,dword ptr [esi+8]
  00000018: 3B 77 04           cmp         esi,dword ptr [edi+4]
  0000001B: 75 05              jne         00000022
  0000001D: E8 00 00 00 00     call        __invalid_parameter_noinfo
  00000022: 8B 36              mov         esi,dword ptr [esi]
  00000024: EB EA              jmp         00000010
  00000026: 5F                 pop         edi
  00000027: 5E                 pop         esi
  00000028: 8B C3              mov         eax,ebx
  0000002A: 5B                 pop         ebx
  0000002B: C3                 ret
  0000002C: CC                 int         3
  0000002D: CC                 int         3
  0000002E: CC                 int         3
  0000002F: CC                 int         3
?SumPostIncrement@@YAHABV?$list@HV?$allocator@H@std@@@std@@@Z (int __cdecl SumPostIncrement(class std::list<int,class std::allocator<int> > const &)):
  00000030: 53                 push        ebx
  00000031: 56                 push        esi
  00000032: 57                 push        edi
  00000033: 8B 7C 24 10        mov         edi,dword ptr [esp+10h]
  00000037: 8B 47 04           mov         eax,dword ptr [edi+4]
  0000003A: 8B 30              mov         esi,dword ptr [eax]
  0000003C: 33 DB              xor         ebx,ebx
  0000003E: 8B FF              mov         edi,edi
  00000040: 3B 77 04           cmp         esi,dword ptr [edi+4]
  00000043: 74 11              je          00000056
  00000045: 03 5E 08           add         ebx,dword ptr [esi+8]
  00000048: 3B 77 04           cmp         esi,dword ptr [edi+4]
  0000004B: 75 05              jne         00000052
  0000004D: E8 00 00 00 00     call        __invalid_parameter_noinfo
  00000052: 8B 36              mov         esi,dword ptr [esi]
  00000054: EB EA              jmp         00000040
  00000056: 5F                 pop         edi
  00000057: 5E                 pop         esi
  00000058: 8B C3              mov         eax,ebx
  0000005A: 5B                 pop         ebx
  0000005B: C3                 ret

Not only do the two versions take the same number of instructions, but they actually generated the exact same sequence of instructions!

Moral: be very very careful when you assume performance advice from some number of years ago will still be true today. Compilers are smart, and they get smarter all the time. Be suspicious of anything you haven't measured yourself on your particular platform using the latest version of your development tools.

aww ..(const list<int> &data)

const parameters and c++ references. the 2 things I miss the most in c#

Bornemix:

I'd like to phrase the famous quotation, "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil."

Bjorn Goransson

I have to second this. I understand the original poster said he was getting an error, so answers regarding that issue were great, but let's not bog him down with trying to focus to hard on optimization of his code before he really needs it.

Original Poster:

Test the method to make sure it does what you want, but down worry about prefix vs. postfix, or foreach  vs. for vs. while IF the code does what you want. When you get down the road a bit and your tests show a less than optimal performace, then go back and try to find places to clean it up a bit.

If you worry to much about optimization at the start, you will make a lot of sideways progress, optimizing a method over and over, but not much forward progress.